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. 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 the Practice of 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!

Papers

Publications

Efficient Stackelberg Strategies for Finitely Repeated Games
Eshwar Ram Arunachaleswaran, Natalie Collina, Michael Kearns
AAMAS 2023. 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]