ﻻ يوجد ملخص باللغة العربية
In this paper we extend a popular non-cooperative network creation game (NCG) to allow for disconnected equilibrium networks. There are n players, each is a vertex in a graph, and a strategy is a subset of players to build edges to. For each edge a player must pay a cost alpha, and the individual cost for a player represents a trade-off between edge costs and shortest path lengths to all other players. We extend the model to a penalized game (PCG), for which we reduce the penalty counted towards the individual cost for a pair of disconnected players to a finite value beta. Our analysis concentrates on existence, structure, and cost of disconnected Nash and strong equilibria. Although the PCG is not a potential game, pure Nash equilibria always and pure strong equilibria very often exist. We provide tight conditions under which disconnected Nash (strong) equilibria can evolve. Components of these equilibria must be Nash (strong) equilibria of a smaller NCG. However, in contrast to the NCG, for almost all parameter values no tree is a stable component. Finally, we present a detailed characterization of the price of anarchy that reveals cases in which the price of anarchy is Theta(n) and thus several orders of magnitude larger than in the NCG. Perhaps surprisingly, the strong price of anarchy increases to at most 4. This indicates that global communication and coordination can be extremely valuable to overcome socially inferior topologies in distributed selfish network design.
We study strong equilibria in network creation games. These form a classical and well-studied class of games where a set of players form a network by buying edges to their neighbors at a cost of a fixed parameter $alpha$. The cost of a player is defi
We consider polymatrix coordination games with individual preferences where every player corresponds to a node in a graph who plays with each neighbor a separate bimatrix game with non-negative symmetric payoffs. In this paper, we study $alpha$-appro
We propose a simple uncertainty modification for the agent model in normal-form games; at any given strategy profile, the agent can access only a set of possible profiles that are within a certain distance from the actual action profile. We investiga
We study the problem of checking for the existence of constrained pure Nash equilibria in a subclass of polymatrix games defined on weighted directed graphs. The payoff of a player is defined as the sum of nonnegative rational weights on incoming edg
In this paper, we consider the problem of wireless power control in an interference channel where transmitters aim to maximize their own benefit. When the individual payoff or utility function is derived from the transmission efficiency and the spent