STAFF
HONORARY STAFF
POSTDOCS
PHD STUDENTS
VISITORS
RELATED STAFF
|
| Name |
Title |
Date |
Time |
Room |
| Emin Berker (Carnegie Mellon University) | Computing Optimal Equilibria in Repeated Games with RestartsAbstract: Infinitely repeated games can support cooperative outcomes that are not equilibria in the one-shot game. The idea is to make sure that any gains from deviating will be offset by retaliation in future rounds. However, this model of cooperation fails in anonymous settings with many strategic agents that interact in pairs. Here, a player can defect and then avoid penalization by immediately switching partners. In this paper, we focus on a specific set of equilibria that avoids this pitfall. In them, agents follow a designated sequence of actions, and restart if their opponent ever deviates. We show that the socially-optimal sequence of actions consists of an infinitely repeating goal value, preceded by a hazing period. We introduce an equivalence relation on sequences and prove that the computational problem of finding a representative from the optimal equivalence class is (weakly) NP-hard. Nevertheless, we present a pseudo-polynomial time dynamic program for this problem, as well as an integer linear program, and show they are efficient in practice. Lastly, we introduce a fully polynomial-time approximation scheme that outputs a hazing sequence with arbitrarily small approximation ratio. |
Tuesday, 10 June 2025 |
13:00 |
Huxley 145 |
DynamIC Workshops and Mini-Courses (Complete List)
Short-term DynamIC Visitors (Complete List)
| Name | Affiliation | Arrival | Departure | Host | | Néstor Jara | Universidad de Chile | Monday, 17 March 2025 | Saturday, 12 July 2025 | Martin Rasmussen |
Links
|
