Natalie Collina

Email: ncollina at seas dot upenn dot edu

Google Scholar

DBLP

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 am excited about algorithmic game theory, online learning and contract design. Specifically, I am interested in understanding what algorithms to play in various formulations of repeated games. It turns out that algorithms with regret guarantees are often a great choice, 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!

Papers

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

The Isotonic Mechanism for Best Paper Awards
Garret Wen, Natalie Collina, Weijie Su

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

Talks

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.


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

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

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


Service

Subreviewer, ITCS 2023

Student Volunteer, CCC 2022

PC Reviewer, FAccT 2022

Subreviewer, EC 2021


Contact

Email: ncollina at seas dot upenn dot edu

Google Scholar

DBLP