+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************

Zeit: Montag, 6. September 2021, 10:00 Uhr Zoom: https://rwth.zoom.us/j/91549249969?pwd=K1VGbDhkaUlpUDdhSFR3dXh1aWFzQT09 Meeting ID: 915 4924 9969 Passcode: 391915

Referent: Vipin Ravindran Vijayalakshmi, M. Sc. Lehrstuhl für Management Science

Thema: Selfishness in Strategic Resource Allocation Problems

Abstract:

Non-cooperative game theory has emerged as an essential tool in analyzing and predicting the outcome of decentralized systems. Various algorithmic aspects arising due to strategic behavior among multiple non-cooperative users in several classes of resource allocation problems can be studied using a game theoretic approach.

In this talk, we consider congestion games which are often used to model various scenarios of resource allocation by non-cooperative users. Congestion games constitute of a class of games in which a pure Nash equilibrium always exists. The hardness of computing a pure Nash equilibrium in congestion games has been of significant interest in the scientific community over the past two decades. As computing an exact pure Nash equilibrium is known to be hard, we study a weaker notion of pure Nash equilibrium called an approximate pure Nash equilibrium and to that extend, analyze an efficient algorithm that computes approximate pure Nash equilibria in congestion games with an improved approximation guarantee.

In spite of being the predominant class of games to model resource allocation problems involving different users, congestion games lack an element of time dependence, especially in certain application scenarios such as the road transportation network. It is quite unnatural to assume that all users of a road section experience the same congestion. We consider a scheduling game on parallel machines, in which jobs try to minimize their completion time by choosing a machine to be processed on. Each machine uses an individual priority list to decide on the order according to which the jobs on the machine are processed. Here, we study the existence of a pure Nash equilibrium and characterize classes of instances in which a pure Nash equilibrium is guaranteed to exist.

Es laden ein: die Dozentinnen und Dozenten der Informatik