4 Presentations

• 
  04:10 PM - 04:35 PM

  Load Balancing Congestion Games

  • Altman Eitan, presenter, INRIA
  • Corinne Touati, Inria
  • Hisao Kameda, Univ of Tsukuba

  A central question in routing games has been to
  establish conditions for the uniqueness of the equilibrium, either
  in terms of network topology or in terms of costs. This question
  is well understood in two classes of routing games. The first is
  the non-atomic routing introduced by Wardrop on 1952 in the
  context of road traffic in which each player (car) is infinitesimally
  small; a single car has a negligible impact on the congestion.
  Each car wishes to minimize its expected delay. Under arbitrary
  topology, such games are known to have a convex potential and
  thus a unique equilibrium. The second framework is splittable
  atomic games: there are finitely many players, each controlling
  the route of a population of individuals (let them be cars in road
  traffic or packets in the communication networks). In this paper,
  we study two other frameworks of routing games in which each of
  several players has an integer number of connections (which are
  population of packets) to route and where there is a constraint
  that a connection cannot be split. We extend results obtained previouosly for
  linear cost to general nonlinear convex link costs.
  Through a particular game
  with a simple three link topology, we identify various novel and
  surprising properties of games within these frameworks. We show
  in particular that equilibria flows are not unique even in the potential
  game setting of Rosenthal with strictly convex link costs. We
  compute the ptice of anarchy and the price of stability and
  analyse its dependence on the cost structure. We
  show that non-symmetric equilibria arise in symmetric
  networks.

• 
  04:35 PM - 05:00 PM

  Myopic and Farsighted Players in the Local Public Goods Game

  • Péter Bayer, presenter, Maastricht University
  • Jean-Jacques Herings, Maastricht University
  • Ronald Peeters, Maastricht University
  • Frank Thuijsman, Department of Knowledge Engineering, Maastricht University

  We study farsighted behavior against myopic opponents in the local public goods game. We show the existence and payoff-uniqueness of optimal strategies in every network structure. We characterize the outcomes of the game and show that the game reaches an absorbing state almost surely for every network. We identify networks that allow or do not allow the farsighted player to exploit his myopic opponents.

• 
  05:00 PM - 05:25 PM

  Discrete Rent Seeking Game applied to Social Medium Selection and to Block Chain

  • Fabrice Lebeau, ENS Lyon
  • Altman Eitan, presenter, INRIA
  • Corinne Touati, Inria
  • Nof Abuzainab, INRIA

  We consider in this paper a discrete version of the rent seeking game. We show its equivalence to a
  congestion game and compute the pure potential of the game. In contrast to the continuous case, we show that there may be various equilibria. We show that the potential is M-concave which allows us to characterize the equilibria and to propose an algorithm for computing it. We then present a learning mechanism which allows us to give an efficient algorithm to determine an equilibrium. We determine the asymptotic form of the equilibrium and discuss the implications on the social medium selection problem. We present two plications of these games. The first consists of
  competition of content creators in routing their content through various media. The routing decisions may correspond to the selection of a social network (e.g. twitter versus facebook or linkedin) or of a group within a given social network. The utility for a player to send its content to some medium is given as the difference between the dissemination utility at this medium and some transmission cost. We then discuss on aplication of the discrete Rent Seeking Game to competition in block chain.
  

• 
  05:25 PM - 05:50 PM

  Hedonic Games and Maximum Likelihood Method for Network Partitioning

  • Vladimir Mazalov, presenter, Institute of Applied Mathematical Research Karelian Research Center of RAS

  The objective of paper is to show the relationship between the game-theoretic approach and the maximum likelihood method in the problem of community detection in networks. We formulate a cooperative game related with network structure where the nodes are players in a hedonic game and then we find the stable partition of the network into coalitions. This approach corresponds to the problem of maximizing a potential function and allows to detect clusters with various resolution. We propose here the maximum likelihood method for the tuning of the resolution parameter in the hedonic game.
  Based on the hedonic game play the algorithm for network partitioning is constructed. Stable partition is the partition for which the potential function reaches a maximum. Finally, we provide illustrative examples which explain the essence of our method. Application on real-world networks and a wellknown benchmark demonstate the efficience of this method.
  The research was supported by the Russian Fund for Basic Research (projects no. 16-01-00183-a and 16-51-55006).