18th International Symposium on Dynamic Games and Applications

Grenoble, France, 9 — 12 July 2018

18th International Symposium on Dynamic Games and Applications

Grenoble, France, 9 — 12 July 2018

Schedule Authors My Schedule

Networks

Jul 12, 2018 04:10 PM – 05:50 PM

Location: room H.103

Chaired by Vladimir Mazalov

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

Back