"Games, algorithms and optimization"

June, 7 2013, 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-10h35: Krzysztof R. Apt (CWI, University of Amsterdam) , Social Network Games

10h35-11h10: Carmine Ventre (Teeside University) , Using Lotteries to Approximate the Optimal Revenue

11h10-11h20: Short break

11h20-11h55: Jerome Lang (CNRS, Université Paris Dauphine), Group Activity Selection Problem

11h55-12h30: Thomas Pradeau (Ecole des ponts Paristech), Congestion games with affine cost functions: computation of an equilibrium in the multiclass case

12h30-14h15: lunch

14h15-14h50: Henk W. Norde (Tilburg University), Monotonic stable solutions for minimum coloring games

14h50-15h25: Angelo Fanelli (CNRS, University of Caen), Computing approximate pure Nash equilibria in congestion games

15h25-15h45: coffee break

15h45-16h20: Rob van Stee (Max Planck Institut Informatik), A unified approach to truthful scheduling on related machines

16h20-16h55: Diodato Ferraioli (Université Paris Dauphine), Designing Frugal Best-Response Mechanisms for Social Network Coordination Games

17H00: Closing

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.

How to come

Abstracts

Social Network Games (Krzysztof R. Apt, Sunil Simon): To better understand the spread of various products through a social network Apt and Markakis introduced in 2011 a threshold model, in which the nodes influenced by their neighbours can adopt one out of several products. To analyze the consequences of such product adoption we associate with each such social network a natural strategic game between the agents. In these games the payoff of each player weakly increases when more players choose his strategy, which is exactly opposite to the congestion games. We show that such games may have no Nash equilibrium and that determining an existence of a Nash equilibrium is NP-complete. We also clarify the status and the complexity of the finite best response property (FBRP), the finite improvement property (FIP), and of a new property that we call the uniform FIP.

Using Lotteries to Approximate the Optimal Revenue (Carmine Ventre and Paul W Goldberg): There has been much recent work on the revenue-raising properties of truthful mechanisms for selling goods to selfish bidders. Typically the revenue of a mechanism is compared against a benchmark (such as, the maximum revenue obtainable by an omniscient seller selling at a fixed price to at least two customers), with a view to understanding how much lower the mechanism’s revenue is than the benchmark, in the worst case. We study this issue in the context of lotteries, where the seller may sell a probability of winning an item. We are interested in two general issues. Firstly, we aim at using the true optimum revenue as benchmark for our auctions. Secondly, we study the extent to which the ex- pressive power resulting from lotteries, helps to improve the worst-case ratio. We study this in the well-known context of digital goods. We show that in this scenario, collusion- resistant lotteries (these are lotteries for which no coalition of bidders exchanging side payments has an advantage in lying) are as powerful as truthful ones.

Group Activity Selection Problem (Jerome Lang): We consider a setting where one has to organize one or several group activities for a set of agents. Each agent will participate in at most one activity, and her preferences over activities depend on the number of participants in the activity. The goal is to assign agents to activities based on their preferences. We put forward a general model for this setting, which is a natural generalization of anonymous hedonic games. We then focus on a special case of our model, where agents' preferences are binary, i.e., each agent classifies all pairs of the form "(activity, group size)" into ones that are acceptable and ones that are not. We formulate several solution concepts for this scenario, and study them from the computational point of view, providing hardness results for the general case as well as efficient algorithms for settings where agents' preferences satisfy certain natural constraints.

Congestion games with affine cost functions: computation of an equilibrium in the multiclass case (Frédéric Meunier, Thomas Pradeau): We consider a nonatomic congestion game on a connected graph, with several classes of users. Each user wants to go from its origin vertex to its destination vertex at the minimum cost and all users of a given class share the same characteristics: cost functions on each arc, and origin-destination pair. Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine and propose an extension of Lemke's algorithm able to solve this problem.

Monotonic stable solutions for minimum coloring games (Herbert Hamers, Silvia Miquel, Henk Norde): For the class of minimum coloring games (introduced by Deng et al. (Math Oper Res, 24:751-766, 1999)) we investigate the existence of population monotonic allocation schemes (introduced by Sprumont (Games Econ Behav 2:378-394, 1990)). We show that a minimum coloring game on a graph G has a population monotonic allocation scheme if and only if G is (P4,2K2)-free (or, equivalently, if its complement graph is quasi-threshold). Moreover, we provide a procedure that for these graphs always selects an integer population monotonic allocation scheme.

A unified approach to truthful scheduling on related machines (Leah Epstein, Asaf Levin, Rob van Stee): We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTAS's) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the p-norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it.
The key idea of our novel method is to show that for goal functions that are sufficiently well-behaved functions of the machine loads, it is possible to compute in polynomial time a highly structured nearly optimal schedule. An interesting aspect of our approach is that, in contrast to all known approximation schemes, we avoid rounding any job sizes or speeds throughout. We can therefore find the exact best structured schedule using dynamic programming. The state space encodes a sufficient amount of information such that no postprocessing is needed, allowing an elegant and relatively simple analysis without any special cases. The monotonicity is a consequence of the fact that we find the best schedule in a specific collection of schedules.
Monotone approximation schemes have an important role in the emerging area of algorithmic mechanism design. In the game-theoretical setting of these scheduling problems there is a social goal, which is one of the objective functions that we study. Each machine is controlled by a selfish single-parameter agent, where its private information is its cost of processing a unit sized job, which is also the inverse of the speed of its machine. Each agent wishes to maximize its own profit, defined as the payment it receives from the mechanism minus its cost for processing all jobs assigned to it, and places a bid which corresponds to its private information. For each one of the problems, we show that we can calculate payments that guarantee truthfulness in an efficient manner. Thus, there exists a dominant strategy where agents report their true speeds, and we show the existence of a truthful mechanism which can be implemented in polynomial time, where the social goal is approximated within a factor of 1+eps for every eps>0.

Computing approximate pure Nash equilibria in congestion games (Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik): Among other solution concepts, the notion of the pure Nash equilibrium plays a central role in Game Theory. Pure Nash equilibria in a game characterize situations with non-cooperative deterministic players in which no player has any incentive to unilaterally deviate from the current situation in order to achieve a higher payoff. Unfortunately, it is well known that there are games that do not have pure Nash equilibria. Furhermore, even in games where the existence of equilibria is guaranteed, their computation can be a computationally hard task. Such negative results significantly question the importance of pure Nash equilibria as solution concepts that characterize the behavior of rational players. Approximate pure Nash equilibria, which characterize situations where no player can significantly improve her payoff by unilaterally deviating from her current strategy, could serve as alternative solution concepts provided that they exist and can be computed efficiently. In this letter, we discuss recent positive algorithmic results for approximate pure Nash equilibria in congestion games.

Designing Frugal Best-Response Mechanisms for Social Network Coordination Games (Bruno Escoffier, Diodato Ferraioli, Laurent Gourvès, Stefano Moretti): Social Coordination Games (SCGs) have recently received a lot of attention to model several kinds of interaction problems in social networks. However, the performances of these games at equilibrium may be very bad. This motivates the adoption of mechanisms for inducing a socially optimal state. In this work we consider the design of incentive-compatible best-response mechanisms (Nisan, Schapira, Valiant, Zohar, 2011) for SCGs. Specifically, we would like to compute special fees that may be assigned to players in order to induce the optimum profile of an SCG. Moreover, we would like the mechanism to be frugal, that is no cost is charged to the mechanism designer. We show that a frugal incentive-compatible best-response mechanism for inducing the optimal profile of a two-strategy SCG always exists. Moreover, for such a mechanism, we investigate other properties inspired by envy-freeness, collusion-resistance and fairness. Finally, we show that extensions of the above results to other classes of games or to non-optimal profiles may be hard.

Organizing committee

B. Escoffier, D. Ferraioli, L. Gourves, K.T. NGuyen, J. Monnot, S. Moretti, F. Pascual, O. Spanjaard.

Sponsors

The workshop is funded by ANR project COCA.