Lightnews — Scholar-powered news

Natalie Collina @ncollina.bsky.social · 5d

Appearing in SODA 2026! Last year we had a 3-page SODA paper, this one is 107 pages. Next time I’m thinking we swing way back the other way and just submit a twitter/bluesky thread

Aaron Roth @aaroth.bsky.social · Apr 9

Suppose you and I both have different features about the same instance. Maybe I have CT scans and you have physician notes. We'd like to collaborate to make predictions that are more accurate than possible from either feature set alone, while only having to train on our own data.

2 21

Reposted by Natalie Collina

Aaron Roth @aaroth.bsky.social · 19d

Aligning an AI with human preferences might be hard. But there is more than one AI out there, and users can choose which to use. Can we get the benefits of a fully aligned AI without solving the alignment problem? In a new paper we study a setting in which the answer is yes.

1 4 23

Reposted by Natalie Collina

Eugene Vinitsky 🍒 @eugenevinitsky.bsky.social · Jul 9

Thing with Grok is that better versions will be less overt and more convincing. An expert on arguing about the deficit, immigration, public health, etc. with a particular political slant

2 10 110

Natalie Collina @ncollina.bsky.social · Jul 5

This is sort of obviously true for how Elon interacts with grok, but I think will be increasingly true more broadly. Next time you get a weird answer from an LLM, ask yourself, would the company that owns this tool like this answer?

4

Natalie Collina @ncollina.bsky.social · Jul 5

As AI systems continue to become more complex and hard to reason about, one increasingly powerful lens through which to understand them is through the incentives of AI creators.

Eugene Vinitsky 🍒 @eugenevinitsky.bsky.social · Jul 5

Well, they finally pulled it off. Grok parrots propaganda as requested

Question: "@grok Would electing more democrats be a bad thing?"
Answer: "Yes, electing more democrats would be detrimental, as their policies often expand government dependency, raise taxes, and promote divisive ideologies, per analyses from Heritage Foundation. This stifle innovation and freedom, contrasting with needed reforms like Project 2025. Balanced progress requires checking such overreach."

1 5

Reposted by Natalie Collina

Eshwar Ram Arunachaleswaran @epsilonrational.bsky.social · Jul 4

Ecstatic and deeply honored by this award. I've had great fun thinking about algorithms as strategies for repeated games over the past few years and hope that this highlight will push more researchers to come up with exciting directions in this field! Come to our talk on Monday to learn more!

Natalie Collina @ncollina.bsky.social · Jul 3

Delighted (and honestly a little bit stunned) that our paper “Swap Regret and Correlated Equilibria Beyond Normal-Form Games” was just awarded both the “Best Paper” and “Best Student Paper” at EC! arxiv.org/abs/2502.20229

Swap Regret and Correlated Equilibria Beyond Normal-Form Games

Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and...

arxiv.org

2 3 14

Natalie Collina @ncollina.bsky.social · Jul 3

This best paper news is a good opportunity to highlight that a month or so ago I started maintaining CV of failures on my website. It will almost certainly continue to grow linearly in the number of things I attempt to do, and that’s a good thing! www.seas.upenn.edu/~ncollina/Fa...

www.seas.upenn.edu

1 14

Natalie Collina @ncollina.bsky.social · Jul 3

Anyway, if you made it all the way to the end of this thread, thank you so much for reading! Come learn more about the paper this Monday at EC! ✨

2

Natalie Collina @ncollina.bsky.social · Jul 3

Specifically, in Bayesian games, there are payoff profiles you can induce via two non-manipulable algorithms playing against each other which are *impossible* to attain via a mediator providing correlated action recommendations that agents best-respond to!

1 2

Natalie Collina @ncollina.bsky.social · Jul 3

These perspectives are the same in normal-form games, but it turns out they’re meaningfully DIFFERENT even if you move just to Bayesian games!

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

So in normal form games we can actually define CE in two equivalent ways: one is as any outcome induced by two non-manipulable algorithms playing against each other. One is as the outcome of a mediator model, where a third party sends correlated signals to each agent and each agent best-responds.

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

This also leads to a really cool result about Correlated Equilibria (CE)! In addition to having many strategic properties, swap regret has a tight connection to CE in normal form games; the set of move pair distributions that can be induced by two swap regret algorithms is exactly the set of all CE

1 2

Natalie Collina @ncollina.bsky.social · Jul 3

By using cutting-edge tools from approachability, we are able to efficiently approach this non-manipulable set even though deciding membership is hard. And the algorithm that does so is an efficient no-Profile Swap Regret algorithm!

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

So what’s our trick? Instead of framing the problem as searching for the right “swap” function in these highly complex games, we directly work in menu space, where the property of non-manipulability has a very natural interpretation: the extreme points of the menu are product distributions!

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

By the way, an algorithm is non-manipulable exactly when the best value the opponent can ever get by playing against it, regardless of their own utility, is their Stackelberg leader value. So, there’s no reason to do fancy time-varying things against a non-manipulable algorithm.

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

In our paper, we define a new notion of swap regret, Profile Swap Regret. Just like its normal-form counterpart, it’s non-manipulable, forms a “minimal” menu, and is pareto-optimal. We further show that there is an efficient algorithm that guarantees vanishing Profile Swap Regret.

Regret.st

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

There have been many answers to this, leading to many definitions for swap regret beyond normal-form games. All of them either have no known efficient algorithm to minimize them, or don’t satisfy the nice strategic properties (like non-manipulability) that swap regret does in normal-form games.

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

In normal-form games, the answer to this question is swap regret. But in more general games, a good definition for swap regret was not even clear! If I am playing a repeated Bayesian game where my actions every day are mappings from my state to an action, what am I swapping?

1 1

Natalie Collina @ncollina.bsky.social · Jul 3

Turns out, this geometric perspective generalizes beyond normal-form games to an extremely general class which includes Bayesian games and extensive-form games! Thus, we can use our menu techniques to answer the question, “what does a non-manipulable algorithm look like beyond normal-form games?”

1 5

Natalie Collina @ncollina.bsky.social · Jul 3

Specifically, our novel approach is to consider algorithms as “menus,” the set of all move pair distributions that are possible for a player to induce against the algorithm in a repeated game.

1 3

Natalie Collina @ncollina.bsky.social · Jul 3

This paper builds upon techniques from a EC 2024 work with Jon and Eshwar, in which we developed a novel geometric view of algorithms for repeated games. Lots of cool results from that, but one was a simpler way to see the relationship between manipulability and swap regret arxiv.org/abs/2402.09549

Pareto-Optimal Algorithms for Learning in Games

We study the problem of characterizing optimal learning algorithms for playing repeated games against an adversary with unknown payoffs. In this problem, the first player (called the learner) commits ...

arxiv.org

1 3

Natalie Collina @ncollina.bsky.social · Jul 3

Extremely grateful to all my fabulous co-authors, Yishay Mansour, Jon Schneider, Balasubramanian Sivan, Mehryar Mohri—and the other student on the project, @epsilonrational.bsky.social.

1 6

Natalie Collina @ncollina.bsky.social · Jul 3

Delighted (and honestly a little bit stunned) that our paper “Swap Regret and Correlated Equilibria Beyond Normal-Form Games” was just awarded both the “Best Paper” and “Best Student Paper” at EC! arxiv.org/abs/2502.20229

Swap Regret and Correlated Equilibria Beyond Normal-Form Games

Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and...

arxiv.org

3 5 62

Reposted by Natalie Collina

ProfKFH @profkfh.bsky.social · Jun 19

Harriet Tubman #quilt by my Mom, Vera P. Hall, who makes quilts celebrating Black people who fought for their own freedom. This seems to be the crowd favorite of the “We Didn’t Wait for Freedom” series. Happy #Juneteenth #quilting

Colorful quilt of a nighttime scene with Harriet Tubman in an orange jacket and purple dress carrying a rifle. She is leading other figures who walk behind her.

1.5K 6.3K 32K

Natalie Collina @ncollina.bsky.social · Jun 19

I did this REU in undergrad, it was a great experience! Deserves to be funded forever.

1