Stability and Learning in Strategic Games

Speaker: Eva Tardos , Cornell

Date: Tuesday, October 24, 2023

Time: 4:00 PM to 5:30 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G-449

Event Type: Seminar

Room Description: G-449

Host: Sam Hopkins, CSAIL MIT

Contact:

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Eva Tardos: Stability and Learning in Strategic Games

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated games assuming players use a form of no-regret learning to adapt to the environment. We will review how this area evolved since its early days, and also discuss some of the new frontiers, including when repeated interactions have carry-over effects between rounds: when outcomes in one round effect the game in the future, as is the case in many applications. In this talk, we study this phenomenon in the context of a game modeling repeated auction with budgets and queuing systems: routers compete for servers, where packets that do not get served need to be resent, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. In joint work with Giannis Fikioris and Jason Gaitonde respectively, we analyze the resulting highly dependent random processes, and show bounds on the resulting budgeted welfare for auctions and the excess server capacity needed to guarantee that all packets get served in the queuing system despite the selfish (myopic) behavior of the participants.

Milk & Cookies served at 4pm, Seminar to start at 4:15pm.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2023.

Created by Nathan Higgins at Monday, October 23, 2023 at 10:44 AM.