Survol

[ English ]

Éva Tardos

Jacob Gould Schurman Professor,Department of Computer Science, Cornell University

Série de conférences de la Chaire Aisenstadt

Première conférence

17 janvier 2020, 14 h

Pavillon André-Aisenstadt, salle 6214/6254

"Learning in Games " Vidéo de la conférence

Selfish behavior can often lead to suboptimal outcome for all participants, a phenomenon illustrated by many classical examples in game theory. Over the last decade we developed good understanding on how to quantify the impact of strategic user behavior on the overall performance in many games (including traffic routing as well as online auctions). In this talk we will focus on games where players use a form of learning that helps them adapt to the environment, and consider two closely related questions: What are broad classes of learning behaviors that guarantee high social welfare in games, and are these results robust to situations when game or the population of players is dynamically changing.

Deuxième conférence

19 janvier 2022, 15h

Sur Zoom :
https://umontreal.zoom.us/j/83385843066?pwd=NHZubjlvRW1uNnRIMU92alBXNE9zQT09
ID de réunion : 833 8584 3066
Code secret : 178403

Stability and Learning in Strategic Queueing Systems

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. Unfortunately, these results do not apply 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 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 Jason Gaitonde, we analyze the resulting highly dependent random process. We find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, then despite selfish behavior of the queues, the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. Further, if queues are more patient in evaluating their outcomes , maximizing their long-run success rate, stability can be ensured with just 1.58 times extra capacity, strictly better than what is possible assuming the no-regret property.