Email: ncollina at seas dot upenn dot edu
Welcome! I'm a third-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 is 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 . Check out more about my research below!
Working Papers
Calibration Bounds in a Stochastic Setting
Eshwar Ram Arunachaleswaran, Natalie Collina, Rabanus Derr, Aaron Roth
Commitments with Ambiguity
Natalie Collina, Rabanus Derr, Aaron Roth
The Isotonic Mechanism for Best Paper Awards
Garret Wen, Natalie Collina, Weijie Su
Analysis of the ICML 2023 Ranking Data: Can Authors' Opinions on Their Own Papers Assist Peer Review?
Buxin Su, Jiayao Zhang, Natalie Collina, Aaron Roth, Yuling Yan,Jianqing Fan, Didong Li, Emma Brunskill, Kyunghyun Cho,
Barbara Engelhardt, Weijie J. Su
Publications and Preprints
Pareto-Optimal Algorithms for Learning in Games
Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider
Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability
Natalie Collina, Varun Gupta, Aaron Roth
Efficient Prior-Free Mechanisms for No-Regret Agents
Natalie Collina, Aaron Roth, Han Shao
An Elementary Predictor Obtaining 2\sqrt(T) Distance to Calibration
Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, Mirah Shi
Efficient Stackelberg Strategies for Finitely Repeated Games
Natalie Collina, Eshwar Ram Arunachaleswaran, Michael Kearns
AAMAS 2023 (Full Paper)
Dynamic Weighted Matching with Heterogenous Arrival and Departure Rates
Natalie Collina, Nicole Immorlica, Kevin Leyton-Brown, Brendan Lucier, Neil Newman
WINE 2020
On the (in)-approximability of Bayesian Mechanism Design for a Combinatorial Buyer
Natalie Collina, S. Matthew Weinberg
EC 2020
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
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.
Mechanism Design without Money, for NETS 3200, University of Pennsylvania.
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, ITCS 2023
Student Volunteer, CCC 2022
PC Reviewer, FAccT 2022
Subreviewer, EC 2021
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 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