Natalie Collina

Welcome! I'm a second-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'm broadly interested in examining strategic interactions in algorithmic settings. Some topics I have enjoyed thinking about include online algorithms, mechanism design, and learning in repeated games. My research is supported by a gift from AWS AI .
I 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!

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 . During Summer 2019 I was also fortunate to work with Nicole Immorlica and Brendan Lucier at Microsoft Research. Before starting my PhD, I spent two years working as a software engineer at Google. Check out more about my background and research below!



Increasing Revenue by Adding Noise
Natalie Collina, Michael Kearns, Aaron Roth
In Submission.

Efficient Stackelberg Strategies for Finitely Repeated Games
Eshwar Ram Arunachaleswaran, Natalie Collina, Michael Kearns
AAMAS 2023 (Full Paper). Presented poster at the Simons Workshop for Data-Driven Decision Processes. [Paper]

Dynamic Weighted Matching with Heterogenous Arrival and Departure Rates
Natalie Collina, Nicole Immorlica, Kevin Leyton-Brown, Brendan Lucier, Neil Newman
WINE 2020. [Paper] [Talk]

On the (in)-approximability of Bayesian Mechanism Design for a Combinatorial Buyer
Natalie Collina, S. Matthew Weinberg
EC 2020. [Paper] [Talk]

Other Research

The Complexity of Mechanism Design Approximation (2019)
Senior thesis, advised by Professor Matt Weinberg
Outstanding Computer Science Thesis Prize, Sigma Xi Book Award. [Paper]

Expansion and Consensus for Social Networks (2019)
With Albert Zuo, as a research project for COS 521: Advanced Algorithms. [Paper]

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

Maximizing Winnings on Final Jeopardy! (2017)
With Jessica Abramson, advised by Professor Bill Gasarch
Presented at the 2017 American Mathematical Society Regional Conference.[Paper]

Teaching and Mentorship

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

Awards and Honors

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 Important Honor

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


Subreviewer, ITCS 2023

Student Volunteer, CCC 2022

PC Reviewer, FAccT 2022

Subreviewer, EC 2021


Email: ncollina at seas dot upenn dot edu


Google Scholar