Natalie Collina

Welcome! I'm a PhD candidate (2021-present) in Computer Science at the University of Pennsylvania, where I am fortunate to be advised by Michael Kearns and Aaron Roth. I work on problems at the intersection of Machine Learning and Game Theory. I'm especially interested in understanding repeated strategic interactions between human and AI agents. My work is supported by an IBM PhD Fellowship in Trustworthy AI, and has previously been supported by AWS AI.
I graduated from undergrad at Princeton University in 2019, where I was fortunate to be advised by Matt Weinberg. From 2019-2021, I was a software engineer at Google. In Summer 2025, I'm an intern at Microsoft Research New England, hosted by Alex Slivkins.

Papers

Note: In my field, authorship for papers is typically alphabetical. Author orderings below are alphabetical by default; when they are author-contribution order, the first author(s) are denoted with an asterisk.

Working Papers

Breaking Algorithmic Collusion Via Simple Defections
Natalie Collina^*, Eshwar Ram Arunachaleswaran, Meena Jagadeeson

Collaborative Prediction: Tractable Information Aggregation via Agreement
Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, Mirah Shi

The Value of Ambiguous Commitments in Multi-Follower Games
Natalie Collina, Rabanus Derr, Aaron Roth
Revise and Resubmit at Games and Economic Behavior (GEB)

Conference Publications

Learning to Play Against Unknown Opponents
Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider
ACM Conference on Economics and Computation (EC) 2025

Swap Regret and Correlated Equilibria Beyond Normal-Form Games
Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan
ACM Conference on Economics and Computation (EC) 2025

Tractable Agreement Protocols
Natalie Collina, Surbhi Goel, Varun Gupta, Aaron Roth
Symposium on Theory of Computing (STOC) 2025;
Pluralistic Alignment Workshop @ NeurIPS 2024

Algorithmic Collusion Without Threats
Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, Juba Ziani
Innovations in Theoretical Computer Science (ITCS) 2025;
CSLaw 2025 (non-archival)

An Elementary Predictor Obtaining 2√T Distance to Calibration
Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, Mirah Shi
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025;
ML-OPT Workshop @ NeurIPS 2024

Pareto-Optimal Algorithms for Learning in Games
Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider
ACM Conference on Economics and Computation (EC) 2024;
ESIF Economics & AI+ML Meeting 2024

Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability
Natalie Collina, Varun Gupta, Aaron Roth
ACM Conference on Economics and Computation (EC) 2024;
ESIF Economics & AI+ML Meeting 2024

Efficient Prior-Free Mechanisms for No-Regret Agents
Natalie Collina, Aaron Roth, Han Shao
ACM Conference on Economics and Computation (EC) 2024

Efficient Stackelberg Strategies for Finitely Repeated Games
Natalie Collina^*, Eshwar Ram Arunachaleswaran, Michael Kearns
International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) 2023

Dynamic Weighted Matching with Heterogenous Arrival and Departure Rates
Natalie Collina, Nicole Immorlica, Kevin Leyton-Brown, Brendan Lucier, Neil Newman
Conference on Web and Internet Economics (WINE) 2020

On the (in)-approximability of Bayesian Mechanism Design for a Combinatorial Buyer
Natalie Collina, Matt Weinberg
ACM Conference on Economics and Computation (EC) 2020;

Journal Publications

The ICML 2023 Ranking Experiment: Examining Author Self-Assessment in ML/AI Peer Review
Buxin Su^*, Jiayao Zhang, Natalie Collina, Yuling Yan, Didong Li, Kyunghyun Cho, Jianqing Fan, Aaron Roth, Weijie J. Su
Journal of the American Statistical Association (JASA)

Other Research

The Isotonic Mechanism for Best Paper Awards
Garrett Wen^*, Natalie Collina, Weijie Su
EC 2024 Workshop on Incentives in Academia.

The Complexity of Mechanism Design Approximation
Senior thesis, 2019. Advised by Professor Matt Weinberg
Outstanding Computer Science Thesis Prize, Sigma Xi Book Award.

Fastermind: Using a SAT-Solver to play Mastermind more efficiently
2018. Advised by Zachary Kincaid, as a Junior Independent Work project.

Maximizing Winnings on Final Jeopardy!
2017. During REU-CAAR at University of Maryland. Jessica Abramson, Natalie Collina, Bill Gasarch

Invited Talks

Show list ⯆

Collaborative Prediciton: Tractable Information Aggregation via Agreement, Caltech RSRG/FALCOM Seminar
Collaborative Prediciton: Tractable Information Aggregation via Agreement, AWS Responsible AI Science Meeting
Collaborative Prediciton: Tractable Information Aggregation via Agreement, CHAI workshop, session on Cooperation and Coordination (upcoming)
Collaborative Prediciton: Tractable Information Aggregation via Agreement, INFORMS Session on Recommendations, Fairness and Human-AI Interaciton (upcoming)
Algorithmic Collusion Without Threats, CSLAW 2025
Algorithmic Collusion Without Threats, ITCS 2025
Tractable Agreement Protocols, STOC (upcoming)
Tractable Agreement Protocols, NYC Student Theory Day
Tractable Agreement Protocols, TOC4Fairness Seminar
Tractable Agreement Protocols, Junior Theorists Workshop 2024
Tractable Agreement Protocols, Johns Hopkins Theory Seminar
Tractable Agreement Protocols, AWS Responsible AI Science Meeting
Tractable Agreement Protocols, FOCS 2024 Calibration Workshop
Learning to Play Against Unknown Opponents, Princeton Mechanism Design Lunch
Learning to Play Against Unknown Opponents, INRIA Paris Optimization Seminar
Efficient Prior-Free Mechanisms for No-Regret Agents, INFORMS 2024
Efficient Prior-Free Mechanisms for No-Regret Agents, EC 2024
Repeated Contracting for Multiple Non-Myopic Agents: No-Regret and Limited Liability, ESIF 2024
Repeated Contracting for Multiple Non-Myopic Agents: No-Regret and Limited Liability, EC 2024
Repeated Contracting for Multiple Non-Myopic Agents: No-Regret and Limited Liability, EnCORE Seminar 2024 (best presentation award)
Pareto-Optimal Algorithms for Learning in Repeated Games, ESIF 2024
Pareto-Optimal Algorithms for Learning in Repeated Games, EC 2024
Pareto-Optimal Algorithms for Learning in Repeated Games, WALE 2024
Efficient Stackelberg Strategies for Finitely Repeated Games, AAMAS 2023
Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates, WINE 2020
On the (in)-approximability of Bayesian Mechanism Design for a Combinatorial Buyer, EC 2020
Maximizing Winnings on Final Jeopardy!, AMS Regional Conference 2017

Work Experience

Research Intern, Microsoft Research (2025)
Software Engineer, Google Cloud (2019 – 2021)
Research Intern, Microsoft Research (2019)
Software Engineering Intern, Amazon Web Services (2018)
Research Intern, REU-CAAR, University of Maryland (2017)

Teaching & Mentorship

Head TA, Advanced Topics in ML (CIS 6200, UPenn)
TA, New Horizons in TCS Summer School
Head TA, Algorithmic Game Theory (NETS 4120, UPenn)
Head TA, Introduction to Algorithms (CIS 3200, UPenn)
TA, Reasoning About Computation (COS 340, Princeton)
TA, Intro Sequence (COS 126/226/217, Princeton)
Fellow, Princeton Writing Center
Peer Academic Advisor, Rockefeller College, Princeton
Head Tutor, Petey Greene Program

Service

Co-organizer, EC Gender Inclusion Workshop, 2024 and 2025
Leader, UPenn Theory Seminar (2022 – present)
PC Reviewer, EC 2025; FAccT 2022
Sub-reviewer, FAccT 2024; SODA 2024; ITCS 2023; EC 2021
Student Volunteer, CCC 2022

Awards & Honors

IBM PhD Fellowship (2025)
Rising Star in EECS (2024)
AWS AI ASSET Fellow (2023)
NSF-GRFP Honorable Mention (2020)
Sigma Xi Book Award (2019)
Outstanding CS Senior Thesis, Princeton (2019)

Most Important Honors

Show list ⯆

Most Accurate Costume, UPenn CS Halloween 2024
Most Orange Costume, UPenn CS Halloween 2023
Judge, UPenn CS Halloween 2022
First Place, UPenn CS Halloween 2021

Curriculum Vitae

Full CV (PDF)

CV of Failures (PDF)

Every PhD has good and bad moments—so here’s some of both 🙂

Contact

Email: ncollina at seas dot upenn dot edu

Google Scholar · DBLP

Recent News