"Games, algorithms and optimization"
June, 24 2011, Paris, France
Inscription
Free of charge. Just send an email with your name and affiliation at workshopgamesparis6 (at) gmail (dot) com
Preliminary program
9h30: welcome to participants
10h-10h40: Tobias Harks (Technische Universitat Berlin), Designing Cost Sharing Protocols for Resource Allocation Games
10h40-11h20: George Christodoulou (University of Liverpool), Coordination Mechanisms for Selfish routing
11h20-12h: Christoph Dürr (Université Paris 6), Nash Equilibria for different Policies in Scheduling Games
12h-13h30: meal
13h30-14h10: Marieke Quant (Tilburg University), Congestion network problems and related games
14h10-14h50: Xavier Zeitoun (Université Paris 2), On the complexity of approximate Nash equilibrium in Congestion Games with negative delays
14h50-15h10: coffee break
15h10-15h50: Martin Hoefer (RWTH Aachen), Contribution and Matching Games in Networks
15h50-16h30: Bruno Escoffier (Université Paris Dauphine), The price of optimum in a matching game
Abstracts
Designing Cost Sharing Protocols for Resource Allocation Games (T. Harks): Resource allocation problems play a key role in many applications, including traffic networks, telecommunication networks and economics. In most applications, the allocation of resources is determined by a finite number of players, each optimizing an individual objective function. An important question in all these applications is the degree of suboptimality caused by selfish resource allocation. Because the set of Nash equilibria of a resource allocation game depends on the cost sharing methods used, I will first introduce the fundamental problem of designing cost sharing methods so as to minimize the resulting worst-case efficiency loss of Nash equilibria. For two concrete classes of resource allocation games I will present recent advances in designing optimal or near-optimal cost sharing protocols.
Nash Equlibria for different Policies in Scheduling Games (C. Dürr): In this survey we consider the load balancing problem, were we have some parallel machines and each player has to select one where to submit his job. User want to complete their jobs earliest as possible. As social cost we consider some norm on the machine loads, for example the L_infinity norm. We are restricted to specify publicly a scheduling policy, which determines how jobs assigned on a machine are to be scheduled. There are different options and some will always admit a pure Nash equilibrium, some not. In the positive case, what is the price of anarchy then. So we try to find out what is the best policy in this scenario. This talk will cover an ongoing work with Johanne Cohen and Nguyen Kim Thang.
Congestion network problems and related games (M. Quant): Generally speaking, in economic congestion situations agents use facilities from a common pool. Typically the costs of a facility will depend on the number of users. This will lead to a congestion effect. Within the game theoretic literature emphasis within the analysis of congestion effects is on a non-cooperative approach. In the cooperative game theoretic literature congestion effects have been considered far less explicitly. We will focus on a particular extension of a standard operations research problem: minimum cost spanning network problems where the total costs of a specific network depend on the actual number of users of the various parts of the network. Here, congestion may cause positive or negative effects, which can be modeled with concave and convex cost functions, respectively. In short, we consider congestion network problems. E.g. the congestion of road networks fits within this framework. We analyze congestion network problems from a cooperative point of view by focusing not only on finding an optimal network for a specific set of users but also on the problem of how to allocate the associated jointly generated minimal costs in a fair way among the users. It is derived that for convex cost congestions costs there always exist a stable allocation vector. For concave congestions costs this need not to be the case, however in this case there always exist optimal tree networks.
On the complexity of approximate Nash equilibrium in Congestion Games with negative delays (X. Zeitoun): Congestion games can describe several interesting routing and resource allocation scenarios in networks. More importantly from a game theoretic perspective, the Improvement Dynamic converges to a Pure Nash Equilibrium. The problem of finding an exact Nash in congestion game is PLS-complete. Nevertheless, on Congestion Games with positive delays Chien and Sinclair have found specific conditions that ensure the \eps-approximate Nash equilibrium is reached under a polynomial number of steps of the \eps-Improvement Dynamic. Without those specific conditions, Skopalik and Vöcking have shown finding an approximate Nash Equilibrium the problem is PLS complete. We extend the two last results to Congestion Games that allow negative delays. This is a joint work with Frederic Magniez, Michel de Rougemont and Miklos Santha.
Contribution and Matching Games in Networks (M. Hoefer): We study game-theoretic models that capture allocation and contribution scenarios in (social) networks. Our interest is to characterize when natural iterative improvement dynamics allow players to reach stable situations (quickly). In network contribution games, each agent in a network has a budget of effort that he can contribute to different relationships. To measure success for a relationship we use a reward function which depends on the contribution of the involved agents. Every agent is trying to maximize the reward from all relationships that it is involved in. For convex reward functions, pairwise and strong equilibria correspond to stable matchings and have nice convergence properties. We then consider an extension of this model to locally stable matching, where players explore the graph iteratively by changing their matching decisions. In this case, convergence is still guaranteed, but fast convergence times are slightly more tricky to obtain.
Location
The workshop will take place at University Paris 6, tower 25-26 - room 105 (first floor, entrance through tower 26), 4 place Jussieu 75005 Paris.
Organizing committee
B. Escoffier, L. Gourves, K.T. NGuyen, J. Monnot, S. Moretti, F. Pascual, O. Spanjaard.
Sponsors
The workshop is funded by ANR project COCA and GDR-RO project CONGAS.