TCS+ talk: Wednesday, December 3, Natalie Collina, U Penn
Clement Canonne
Our next talk (the last of the season!) will take place this coming Wednesday, December 3rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Natalie Collina from U Penn will speak about "Swap regret and correlated equilibria beyond normal-form games " (abstract below).
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Natalie Collina (U Penn)
Title: Swap regret and correlated equilibria beyond normal-form games
Abstract: 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 guaranteeing non-manipulability against a self-interested opponent. However, the situation for more general classes of games – such as Bayesian games and extensive-form games – is less clear-cut, with multiple candidate definitions for swap-regret but no known efficiently minimizable variant of swap regret that implies analogous non-manipulability guarantees. In this paper, we present a new variant of swap regret for polytope games that we call “profile swap regret”, with the property that obtaining sublinear profile swap regret is both necessary and sufficient for any learning algorithm to be non-manipulable by an opponent (resolving an open problem of Mansour et al., 2022). Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most O(√T) profile swap regret. Finally, we explore the correlated equilibrium notion induced by low-profile-swap-regret play, and demonstrate a gap between the set of outcomes that can be implemented by this learning process and the set of outcomes that can be implemented by a third-party mediator (in contrast to the situation in normal-form games).
Clement Canonne
Dear TCS+ followers,
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow (Wednesday), starting at 12:50pm ET: https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09
(you will need to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ <tcsplus_...@googlegroups.com>
Sent: Wednesday, November 26, 2025 6:38 AM
To: TCS+ Announcement Mailing List
Subject: TCS+ talk: Wednesday, December 3, Natalie Collina, U Penn
Dear TCS+ followers,
Our next talk (the last of the season!) will take place this coming Wednesday, December 3rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Natalie Collina from U Penn will speak about "Swap regret and correlated equilibria beyond normal-form games " (abstract below).
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Natalie Collina (U Penn)
Title: Swap regret and correlated equilibria beyond normal-form games
Abstract: 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 guaranteeing non-manipulability against a self-interested opponent. However, the situation for more general classes of games – such as Bayesian games and extensive-form games – is less clear-cut, with multiple candidate definitions for swap-regret but no known efficiently minimizable variant of swap regret that implies analogous non-manipulability guarantees. In this paper, we present a new variant of swap regret for polytope games that we call “profile swap regret”, with the property that obtaining sublinear profile swap regret is both necessary and sufficient for any learning algorithm to be non-manipulable by an opponent (resolving an open problem of Mansour et al., 2022). Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most O(√T) profile swap regret. Finally, we explore the correlated equilibrium notion induced by low-profile-swap-regret play, and demonstrate a gap between the set of outcomes that can be implemented by this learning process and the set of outcomes that can be implemented by a third-party mediator (in contrast to the situation in normal-form games).
You received this message because you are subscribed to the Google Groups "TCS+" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus_announ...@googlegroups.com.
To view this discussion visit https://url.au.m.mimecastprotect.com/s/0ZdKCnx1jni3OOArySJhACJEw_z?domain=groups.google.com.
For more options, visit https://url.au.m.mimecastprotect.com/s/VyZuCoV1kpfPqqj6oiVi2CpkAug?domain=groups.google.com.