• 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

    Technical Contributions:

• 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 punishment strategy.

Lunch break

• 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 computing. 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

    Invited Speakers:

• 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