# Final Workshop

# "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.

## 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.