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 in the intersection of algorithmic game theory and online learning. I am particularly interested in understanding what algorithms to play in strategic settings with repeated interactions. Some examples of such settings include repeated Stackelberg games, repeated contracting and sequential online prediction. It turns out that algorithms with regret
guarantees are often a great choice in these settings, and therefore much of my research also eludicates the strategic properties of no-regret and no-swap-regret algorithms.
My research has been supported by AWS AI . I also co-lead the University of Pennsylvania's weekly
Theory Seminar.
If you are a researcher (at Penn or otherwise) who is interested in speaking about your research in theoretical computer science, feel free to reach out to me!
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 .
12/2024: I will be interning at Microsoft Research New England this Summer!
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: Excited to be invited to 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!
In Submission
Tractable Agreement Protocols
Natalie Collina, Surbhi Goel, Varun Gupta, Aaron Roth
Accepted to the Pluralistic Alignment Workshop @ NeurIPS 2024
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
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
Workshop Papers
The Isotonic Mechanism for Best Paper Awards
Garrett Wen, Natalie Collina, Weijie Su
EC 2024 Workshop on Incentives in Academia.
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
EC 2024 Workshop on Incentives in Academia.
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
Tractable Agreement Protocols, Junior Theorists Workshop
Tractable Agreement Protocols, Johns Hopkins University Theory Seminar
Tractable Agreement Protocols, Amazon Research Meeting
Tractable Agreement Protocols, EnCORE Student Seminar.
Tractable Agreement Protocols, FOCS 2024 Workshop on Calibration.
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.
Pareto-Optimal Algorithms for Learning in Repeated Games, EnCORE Student Seminar.
Pareto-Optimal Algorithms for Learning in Repeated Games, University of Pennsylvania Theory Seminar.
A General Reduction from No-Regret to No-Swap-Regret, for CIS 6200, University of Pennsylvania.
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.
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 Assistant, New Horizons in TCS Summer School
Head Teaching Assistant, Algorithmic Game Theory (NETS 412, Upenn)
Head Teaching Assistant, Introduction to Algorithms (CIS 320, 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
Leader, University of Pennsylvania Theory Seminar (Fall 2022 -- Present)
Subreviewer, FAccT 2024
Subreviewer, SODA 2024
Subreviewer, ITCS 2023
Student Volunteer, CCC 2022
PC Reviewer, FAccT 2022
Subreviewer, EC 2021
Rising Star in EECS (2024)
AWS AI ASSET Fellow (2023)
University of Pennsylvania Graduate Research Fellowship (2020)
NSF-GRFP Honorable Mention (2020)
Sigma Xi Book Award for Scientific Research (2019)
Outstanding Computer Science Senior Thesis Award, Princeton University (2019)
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)
Email: ncollina at seas dot upenn dot edu