Welcome! I'm a 5th-year PhD student 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 AI and Game Theory. I'm especially interested in understanding repeated strategic interactions between human and AI agents. My work has been awarded with an IBM PhD Fellowship in Trustworthy AI and a joint Best Paper Award/Best Student Paper Award from the ACM Conference for Economics and Computation. I have been recognized as a Rising Star in EECS and my work has been featured in Quanta magazine.
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 was an intern at Microsoft Research New England, where I was lucky to be hosted by Alex Slivkins.
On the Faculty Job Market (2025–2026)
I am seeking faculty positions in Computer Science!
View my CV
Recent News
- 03/2026: Two papers accepted to ICML 2026!
- 03/2026: Our work on Pluralistic Alignment was awarded the Best Paper Award at the AIMS Workshop at ICLR!
- 02/2026: Our work on author self-rankings for ML conferences was featured in an article on Nature Index.
- 11/2025: Our work on algorithmic collusion was featured in a recent Quanta article!
- 11/2025: Our paper Collaborative Predictions was accepted to SODA'26
- 07/2025: Our paper "Swap Regret and Correlated Equilibria Beyond Normal-Form Games" was awarded both Best Paper and Best Student Paper at EC'25!
- 05/2025: Moved to Boston for the summer to start my internship at Microsoft Research New England, hosted by Alex Slivkins!
- 05/2025: Two papers accepted to EC’25!
- 02/2025: Co-organising the EC Gender Inclusion Workshop.
- 01/2025: Tractable Agreement Protocols accepted to STOC’25!
- 12/2024: Honored to receive an IBM PhD Fellowship!
- 12/2024: Gave a talk at the Junior Theorists Workshop in Chicago.
- 11/2024: Algorithmic Collusion Without Threats accepted to ITCS’25!
- 10/2024: Spoke at the FOCS Calibration Workshop on agreement protocols.
- 10/2024: Attended Cornell ORIE’s Young Researchers Workshop.
- 10/2024: An Elementary Predictor Obtaining 2√T Distance to Calibration accepted to SODA’25!
- 09/2024: Named one of MIT EECS Rising Stars!.
- 05/2024: Three papers accepted to EC’24!
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
Narrowing the Collaboration Gap, ProbablyMirah Shi*, Marcel Hussing, Ira Globus-Harris, Natalie Collina, Aaron Roth, and Surbhi Goel Failure Modes in AI Retraining Dynamics Kiarash Banihashem, Natalie Collina, Nicole Immorlica, Brendan Lucier, Aleksandrs Slivkins Personalization Aids Pluralistic Alignment via Competition Natalie Collina, Surbhi Goel, Aaron Roth, and Mirah Shi Best Paper Award at ICLR AIMS Workshop The Sample Complexity of Multicalibration Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth Optimal Lower Bounds for Online Multicalibration Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth Recommending Best Paper Awards for ML/AI Conferences via the Isotonic Mechanism Garrett Wen*, Buxin Su, Natalie Collina, Zhun Deng, Weijie Su Breaking Algorithmic Collusion in Human-AI Ecosystems
Natalie Collina*, Eshwar Ram Arunachaleswaran, Meena Jagadeesan
The Value of Ambiguous Commitments in Multi-Follower Games
Natalie Collina, Rabanus Derr, Aaron Roth
Revise and Resubmit at Games and Economic Behavior (GEB)
Buxin Su*, Natalie Collina, Garrett Wen, Didong Li, Kyunghyun Cho, Jianqing Fan, Bingxin Zhao, Weijie Su
Conference Publications
Emergent Alignment via Competition Natalie Collina, Surbhi Goel, Aaron Roth, Emily Ryu, and Mirah Shi ICML 2026 Bandit Social Learning with Exploration Episodes Kiarash Banihashem, Natalie Collina, Aleksandrs Slivkins ICML 2026Collaborative Prediction: Tractable Information Aggregation via Agreement
Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, Mirah Shi
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2026;
Spotlight presentation at the EC 2025 Workshop on Human-AI Collaboration
Spotlight presentation at the 2025 TTIC Workshop on Incentives for Collaborative Learning and Data Sharing
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
Best Paper Award & Best Student Paper Award
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)
Media:
The Game Theory of How Algorithms Can Drive Up Prices (Quanta Magazine)
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) Discussion Paper
Essays
Menus: A Framework for Learning Against Strategic Opponents
Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan
SIGecom Exchanges, Winter 2026
Other Research
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
Selected Invited Talks (excluding conference talks)
- Emergent Alignment Via Competition
- 2025 UK AISI Alignment Conference
- 2025 Cornell Young Researcher's Workshop
- 2026 Simons Collaboration on the Theory of Algorithmic Fairness
- Learning and Incentives in Human-AI Collaboration
- 2025 MIT Algorithms and Complexity Seminar
- 2025 Northeastern Theory Seminar
- 2025 CMU Theory Lunch
- 2025 NYU Theory Seminar
- 2025 Rational Intelligence Seminar Series
-
Swap Regret and Correlated Equilibria Beyond Normal-Form Games
- EC 2025 (Best Paper Talk)
- 2025 Cornell Theory Seminar
- 2025 JHU Theory Seminar
- 2025 TCS+ Seminar
-
Repeated AI Interaction: How Agents Learn and Strategize over Time
- 2025 CHAI Workshop, session on Cooperation and Coordination
-
Collaborative Prediction: Tractable Information Aggregation via Agreement
- 2025 EC Workshop on Human-AI Collaboration, spotlight talk
- 2025 Caltech RSRG/FALCOM Seminar
- 2025 AWS Responsible AI Science Meeting
-
Tractable Agreement Protocols
- 2025 NYC Student Theory Day
- 2025 TOC4Fairness Seminar
- 2024 Junior Theorists Workshop
- 2024 Johns Hopkins Theory Seminar
- 2024 AWS Responsible AI Science Meeting
- FOCS 2024 Calibration Workshop
-
Algorithmic Collusion Without Threats
- CSLAW 2025
-
Learning to Play Against Unknown Opponents
- 2024 Princeton Mechanism Design Lunch
- 2024 INRIA Paris Optimization Seminar
-
Efficient Prior-Free Mechanisms for No-Regret Agents
- INFORMS 2024
-
Repeated Contracting for Multiple Non-Myopic Agents: No-Regret and Limited Liability
- ESIF 2024
- 2024 EnCORE Seminar (best presentation award)
-
Pareto-Optimal Algorithms for Learning in Repeated Games
- ESIF 2024
- WALE 2024
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 – 2025)
- PC Reviewer, EC 2026; WINE 2025; EC 2025; FAccT 2022
- Sub-reviewer, SODA 2025; FAccT 2024; SODA 2024; ITCS 2023; EC 2021
- Student Volunteer, CCC 2022
Awards & Honors
- Best Paper, EC 2025
- Best Paper with a Student Lead Author, EC 2025
- 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 ⯆
- Best Costume, UPenn CS Halloween 2025
- 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
Every PhD has good and bad moments—so here’s some of both 🙂 Look out for a substantial update to the failure CV post job market!
Contact
Email: ncollina at seas dot upenn dot edu