ﻻ يوجد ملخص باللغة العربية
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 defined to be the cost of the bought edges plus the sum of distances to all the players in the resulting graph. We identify and characterize various structural properties of strong equilibria, which lead to a characterization of the set of strong equilibria for all $alpha$ in the range $(0,2)$. For $alpha > 2$, Andelman et al. (2009) prove that a star graph in which every leaf buys one edge to the center node is a strong equilibrium, and conjecture that in fact any star is a strong equilibrium. We resolve this conjecture in the affirmative. Additionally, we show that when $alpha$ is large enough ($geq 2n$) there exist non-star trees that are strong equilibria. For the strong price of anarchy, we provide precise expressions when $alpha$ is in the range $(0,2)$, and we prove a lower bound of $3/2$ when $alpha geq 2$. Lastly, we aim to characterize under which conditions (coalitional) improvement dynamics may converge to a strong equilibrium. To this end, we study the (coalitional) finite improvement property and (coalitional) weak acyclicity property. We prove various conditions under which these properties do and do not hold. Some of these results also hold for the class of pure Nash equilibria.
Network Creation Games(NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past r
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 p
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