Natalie Collina

Email: ncollina at seas dot upenn dot edu

Welcome! I'm a fourth-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 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 . My research spans two primary paradigms:

In one, I give guarantees for Human-AI collaborative tasks that remain robust under worst-case assumptions. Consider a doctor who would like to diagnose a series of patients as they arrive, and has access to AI predictions for each. The doctor and the AI may have complementary information about patients, but this information may be high-dimensional and/or illegible to the other party. I construct protocols which efficiently incorporate the expertise of the human and AI system, allowing them to arrive at a consensus [1], and in many cases do as well as if they had directly pooled their data [2]. These results do not require any assumption on the true label outcomes or that the Human and AI have a shared prior; despite this, the guarantees are similarly strong to those previously shown in the Bayesian setting.

In the other, I study scenarios in which an AI system or algorithm is deployed, and other agents strategically interact with or attempt to manipulate it. Consider an algorithm designed to match rideshare drivers to riders, which a driver might interact with repeatedly. Over time, a driver may learn that accepting the first rider that appears--the "myopic" strategy--is not optimal, as the system might provide closer riders after a rejected ride. Thus, the driver may learn to best-respond to the AI model in "algorithm space," adapting their behavior over time to maximize their own objectives. Learning algorithms are increasingly deployed for these sorts of long-run tasks. Inspired by this, I ask: what is a good learning algorithm to deploy against an agent optimizing over the long run? I model these repeated strategic interactions as repeated games, and use tools from game theory in order to reason about outcomes. I study optimal algorithmic commitments given no information about the downstream user [3] and given a prior on their preferences [4]. I show that the "no-swap regret" property, a refinement of no-regret, fundamentally characterizes robustness to manipulation in these settings [5].

I also have work that bridges these paradigms, including studying strategically optimal algorithmic commitments in prior-free environments [6] and the ability of no-swap regret algorithms to empower collusive-looking outcomes in pricing games [7]. Ultimately, my goal is to address foundational challenges in building trustworthy and aligned machine learning systems.

I co-lead the University of Pennsylvania's weekly Theory Seminar and the EC Gender Inclusion Workshop. Before starting my PhD, I spent two years working as a software engineer at Google. Before that, I graduated summa cum laude from Princeton University in Fall 2019 with a major in Computer Science and a minor in History and Diplomacy. While at Princeton I was fortunate to be advised by Matt Weinberg .

Recent News

1/2025: Our paper Tractable Agreement Protocols accepted to STOC'25!

12/2024: Honored to recieve an IBM PhD Fellowship!

12/2024: In Chicago to give a talk at the Junior Theorists Workshop

11/2024: Our paper Algorithmic Collusion without Threats accepted to ITCS'25!

10/2024: Gave a talk at the FOCS Calibration Workshop on our new work on tractable agreement protocols

10/2024: I will be attending Cornell ORIE's Young Researchers Workshop

10/2024: Our (3-page) paper on distance to calibration accepted to SODA'25!

09/2024: Honored to be recognized as one of MIT's Rising Stars in EECS

05/2024: Three papers accepted to EC'24!

03/2024: I co-organized the EC Gender Inclusion Workshop co-located with EC

Papers

In Submission

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

Swap Regret and Correlated Equilibria Beyond Normal-Form Games
Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan

The Value of Ambiguous Commitments in Multi-Follower Games
Natalie Collina, Rabanus Derr, Aaron Roth

Learning to Play Against Unknown Opponents
Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider

Conference Publications

Tractable Agreement Protocols
Natalie Collina, Surbhi Goel, Varun Gupta, Aaron Roth
Symposium on Theory of Computing (STOC) 2025. Also accepted to the 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. Also accepted to CSLaw 2025, non-archival track.

An Elementary Predictor Obtaining 2\sqrt(T) Distance to Calibration
Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, Mirah Shi
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025. Also accepted to the 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. Also accepted to the 2024 ESIF Economics and AI+ML Meeting.

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. Also accepted to the 2024 ESIF Economics and AI+ML Meeting

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 (Full Paper)

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, S. Matthew Weinberg
ACM Conference on Economics and Computation (EC) 2020

Journal Publications

Analysis of the ICML 2023 Ranking Data: Can Authors' Opinions on Their Own Papers Assist 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

Algorithmic Collusion Without Threats, CSLAW 2025

Algorithmic Collusion Without Threats, ITCS 2025

Tractable Agreement Protocols, TOC4Fairness Seminar

Tractable Agreement Protocols, Junior Theorists Workshop

Tractable Agreement Protocols, Johns Hopkins University Theory Seminar

Tractable Agreement Protocols, AWS Responsible AI Science Meeting

Tractable Agreement Protocols, FOCS 2024 Workshop on Calibration.

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 with Multiple Non-Myopic Agents: Policy Regret and Limited Liability, ESIF 2024.

Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability, EC 2024.

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 Heterogenous 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! 2017 American Mathematical Society Regional Conference.

Work Experience

Software Engineer, Google Cloud (2019-2021)

Research Intern, Microsoft Research (2019)

Software Engineering Intern, Amazon Web Services (2018)

Research Intern, REU in Combinatorics, Algorithms and AI for Real Problems at University of Maryland (2017)

Teaching and Mentorship

Head Teaching Assistant, Advanced Topics in Machine Learning (CIS 6200, UPenn)

Teaching Assistant, New Horizons in TCS Summer School

Head Teaching Assistant, Algorithmic Game Theory (NETS 4120, UPenn)

Head Teaching Assistant, Introduction to Algorithms (CIS 3200, UPenn)

Teaching Assistant, Reasoning about Computation (COS 340, Princeton)

Teaching Assistant, Introductory Sequence (COS 126, 226, 217, Princeton)

Fellow, Princeton Writing Center

Peer Academic Advisor, Rockefellor College, Princeton University

Head Tutor, Petey Greene Program

Service

Leader, University of Pennsylvania Theory Seminar (Fall 2022 -- Present)

PC Reviewer, EC 2025

Subreviewer, FAccT 2024

Subreviewer, SODA 2024

Subreviewer, ITCS 2023

Student Volunteer, CCC 2022

PC Reviewer, FAccT 2022

Subreviewer, EC 2021

Awards and Honors

IBM PhD Fellowship (2024-2025)

Rising Star in EECS (2024)

AWS AI ASSET Fellow (2023)

NSF-GRFP Honorable Mention (2020)

Sigma Xi Book Award for Scientific Research (2019)

Outstanding Computer Science Senior Thesis Award, Princeton University (2019)

Most Important Honors

Most Accurate Costume, University of Pennsylania CS Department Halloween Costume Contest (2024)

Most Orange Costume, University of Pennsylania CS Department Halloween Costume Contest (2023)

Selected as Judge, University of Pennsylvania CS Department Halloween Costume Contest (2022)

First Place, University of Pennslvania CS Department Halloween Costume Contest (2021)

Contact

Email: ncollina at seas dot upenn dot edu

Google Scholar

DBLP