|[Note: draft version, minor changes could be made. ]
9.00 - 10.00 Keynote talk:
Prof. Berthold Vocking (University of Aachen) - Uncoordinated Two-Sided Matching Markets
Various economic interactions can be modeled as two-sided matching markets. A central solution concept to these markets are stable matchings, introduced by Gale and Shapley. It is well known that stable matchings can be computed in polynomial time, but many real-life markets lack a central authority to match agents. In those markets, matchings are formed by actions of selfinterested agents, whose behavior is often modeled by Nash dynamics such as best and better response dynamics. In this talk, we summarize recent results on random Nash dynamics in two-sided markets.|
Break: 30 min
10.30 - 11.00
Worst-case analysis of non-cooperative load balancing
Olivier Brun, Balakrishna J. Prabhu, LAAS-CNRS
We investigate the impact of heterogeneity in the amount of incoming traffic routed
by dispatchers in a non-cooperative load balancing game. For a fixed amount of
total incoming traffic, we give sufficient conditions on the cost function under
which the worst-case social cost occurs when each dispatcher routes the same amount
of traffic, that is, the game is symmetric. Using this result, we give lower bounds
on the Price of Anarchy for(i) cost functions that are polynomial on server loads;
and (ii) cost functions representing the mean delay of the Shortest Remaining
Processing Time (SRPT) service discipline.
11.00 - 11.30
Equilibrium Pricing with Positive Externalities
Nima Ahmadi Pour Anari, Shayan Ehsani, Mohammad Ghodsi, Hamid Mahini (Sharif University of Technology, Iran)
Nima Haghpanah, Nicol Immorlica (Northwestern University, USA)
Vahab S. Mirrokni (Google Research NYC, USA)
We study the problem of selling an item to strategic buyers in the
presence of positive historical externalities, where the
value of a product increases as more people buy and use it. This
increase in the value of the product in these settings is the
result of resolving bugs or security holes after more usage. We
consider a continuum of buyers that are partitioned into a
finite set of types where each type has a valuation
function based on the actions of other players. Given a fixed
sequence of prices, buyers have to choose a day at which to buy
the product, i.e., they have to decide to adopt the product early
in the game or later after more players already adopt it. We model
this strategic setting as a game among buyers and the seller,
study existence and uniqueness of equilibria of these games, and
identify revenue-maximizing pricing sequence for the seller.
More specifically, we first prove that continuity of valuation
functions is a necessary and sufficient condition for existence of
equilibria in these games. Next, we show that the equilibrium is
essentially unique only if the valuation function of each type
only depends on the aggregate amount of players who bought the
product, and is insensitive to the identities of those players. We
then study revenue-maximizing price sequences by the seller for
settings with well-behaved equilibria and present an FPTAS for the
a special case: the linear
settings that are characterized by an initial bias and a linear
influenceability coefficient. |
- 11.30 - 12.00
Internal-Regret with Partial Monitoring: Calibration-Based Optimal Algorithms
Vianney Perchet, University Paris 6, France
We consider a repeated game with partial monitoring,
i.e. where players do not observe their opponents actions
nor their payoffs but receive random signals. In this framework, we
provide an algorithm that has no internal regret. It is based on the
computation of a strategy that satisfies a property that extends the
notion of calibration; it is indeed calibrated with respect to a
Laguerre diagram, instead of a usual Voronoi diagram.
The rates of convergence of our algorithms are optimal, both if the laws of the signals received by a player depend on his action or not, and even for the external regret.
12.00 - 12.30
Instablity of a punishment strategy in correlated equilibria
Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto (Kyoto University, NTT Labs, Japan)
In game theory, to achieve correlated equilibria without a trusted mediator, the idea of replacing the
mediator with protocol execution by players is suggested. Before players take actions in a game, players
communicate with each other by following a protocol. In that model, the concept of a punishment strategy
is defined for cases in which a player (or some players) aborts the protocol. In this paper, we present an
example of game in which a punishment strategy does not work and suggest an improved definition of a
14.00 - 15.00 Keynote talk:
Prof. Bruno Gaujal (INRIA, France) -
Optimization in large Markovian systems: reducing the information gap
This talk investigates the optimal behavior of Markov decision
processes made of distributed objects evolving in a common
environment, when the number of objects (N) goes to infinity.
In the finite time horizon case, we show that when the number of objects
becomes large, the optimal cost of the system converges to the
optimal cost of a mean field limit system that is deterministic. Convergence also holds
for optimal policies.
This shows that the value of information disappears when N goes to infinity.
Our framework is applied to a brokering problem in grid
We provide bounds on the price of anarchy (resulting from a lack of central information)
and show how this can be reduced when the size of the system grows.
Several simulations with growing numbers of processors
are reported. They compare the performance of the optimal policy
of the limit system used in the finite case with classical
policies by measuring its asymptotic gain.
15.00 - 15.30 Distributed learning in a Congestion Poisson Game
Julio Rojas, Habib Sidi, El-Azouzi Rachid, Yezekael Hayel (University of Avignon, France)
This paper deals with a game theoretic model based on a Congestion Poisson Games. The novelty of our study is that
we focus on a totally distributed mechanism that can be employed such that the system will converge to the Nash equilibrium for every fixed number of player. We are interested in observing the impact of arrivals and departures of players on the convergence metrics of the algorithm. To do this, we propose some adaptations of a basic reinforcement learning algorithm for which we carried out extensive simulations. Our main problems are first, how a player is aware of changes in the system state and second, what it should do in that case. We propose several approaches to detect system state changes and we show that there is no need to restart the algorithm at each event to attain convergence to a Nash equilibrium in 80\% of the time.
15.30 - 16.00
Selection of global maximizer in potential games under general class of revision opportunity.
Pierre Coucheney (INRIA - LIG, France)
The logit response dynamics is a particular model of learning in games. In this dynamics, players adopt an action according to a full-support distribution of the logit form, which allocates larger probability to those actions which would deliver (myopically) larger payoffs. As the noise vanishes, the distribution concentrate on best response. Recently, Alos-Ferrer and Netzer characterized the long-run behaviour of this dynamics. While it is known that, in an exact potential game, and for an asynchronous scheme, the dynamics select the global optimum, they showed that this result does not extend to more general class of game and revision opportunity (who learns when?). In this talk, we present a continuous model of learning that reaches the global optimum of the potential function for a larger class of revision opportunity. We apply this result to a general atomic routing game optimisation problem.
Break: 30 min
16.30 - 17.00
Strong Equilibria in Bottleneck Congestion Games
Max Klimm (Technical University of Berlin, Germany)
We provide an axiomatic framework for the the well studied
lexicographical improvement property and derive new results on the
existence of strong Nash equilibria for a very general class of
congestion games with bottleneck objectives. This includes extensions of
classical load-based models, routing games with splittable demands,
scheduling games with malleable jobs, and more.
Furthermore, we discuss the computational complexity of computing pure
Nash and strong equilibria in these games.
17.00 - 17.30
Scheduling policies for scheduling games
Christoph Durr (CNRS - LIX, France)
In a scheduling game, each player owns a job and chooses a specific machine to execute it, out of a pool of available machines. His concern is to get his job completed as early as possible. The social cost however is the maximal work load over all machines. In a pure Nash equilibrium the social cost might not be optimum, and two important measures of the game are the price of anarchy, which is the ratio between the social cost of the worst Nash equilibrium and the social optimum, and the price of stability, which is the ratio between the social cost of the best Nash equilibrium and the social optimum. How can we influence the player's choice to keep these values small? As a game designer, we can define publicly scheduling policies, that specify how jobs assigned to a machine will be executed, and the choice of a policy will influence the choice of the players and affect the price of anarchy and price of stability. In this talk we give a survey over different policies that have been proposed in the literature and observe how well they behave in different parallel machine environments.
This talk builds on the paper "Non-clairvoyant Scheduling Games" presented with Nguyen Kim Thang at the the 2nd International Symposium on Algorithmic Game Theory in 2009.
17.30 - 18.00