1,720,975 research outputs found
Some Anomalies of Farsighted Strategic Behavior
No full textWe investigate the loss in optimality due to the presence of selfish players in sequential games, a relevant subclass of extensive form games with perfect information recently introduced in Paes Leme et al. (Proceedings of innovations in theoretical computer science (ITCS), ACM, New York, pp. 60–67, 2012). In such a setting, the notion of subgame perfect equilibrium is preferred to that of Nash equilibrium since it better captures the farsighted rationality of the players who can anticipate future strategic opportunities. We prove that the sequential price of anarchy, that is the worst-case ratio between the social performance at a subgame perfect equilibrium and that of the best possible solution, is exactly 3 in cut and consensus games. Moreover, we improve the known Ω(n) lower bound for unrelated scheduling to (Formula presented.) and refine the corresponding upper bound to 2n, where n is the number of players. Finally, we determine essentially tight bounds for fair cost sharing games by proving that the sequential price of anarchy is between n+1−Hn and n. A surprising lower bound of (n+1)/2 is also determined for the singleton case. Our results are quite interesting and counterintuitive, as they show that a farsighted behavior may lead to a worse performance with respect to a myopic one: in fact, either Nash equilibria and simple Nash rounds, consisting of a single (myopic) move per player starting from the empty state, achieve a price of anarchy which results to be lower or equivalent to the sequential price of anarchy in almost all the considered cases
Designing Fast Converging Cost Sharing Methods for Multicast Transmissions
No full textWe study a multicast game in non-cooperative directed networks in which
a source sends the same message or service to a set of r receiving users and the
cost of the used links is divided among the receivers according to a given cost sharing
method. By following the approach recently proposed by Chen et al. (Proceedings
of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
pp. 854–863, 2008), we analyze the performances of a family of methods satisfying
certain desiderata, namely, weak and strong budget-balance, fairness and separability.
We show that any fair method may require an arbitrary number of selfish moves
in order to converge to a pure Nash equilibrium, hence we focus on the solutions
obtained after one round of selfish moves. We evaluate their quality according to
two global social functions: the overall cost of the solution and the maximum shared
cost of users. The only method satisfying all the properties is the well-known Shapley
value for which we show an approximation ratio of the solutions reached after a
one round walk equal to \Theta(r2). We then prove that relaxing the strong budget balance and separability properties (we call feasible any method satisfying weak budget
balance and fairness) leads to improved performances since we determine a feasible
method achieving an approximation ratio of the solutions reached after a one round
walk equal to O(r). This bound is asymptotically optimal since we also show that
any method satisfying weak budget balance cannot achieve an approximation ratio
of the solutions reached after a one round walk smaller than r. Finally, we prove the
NP-hardness of computing the sequence of moves leading to the best possible global
performance and extend most of the results to undirected networks
On the sequential price of anarchy of isolation games.
No full textWe study the performance of subgame perfect equilibria, a solution concept which better captures the players’ rationality in sequential games with respect to the classical myopic dynamics based on the notions of improving deviations and Nash equilibria, in the context of sequential isolation games. In particular, for two important classes of sequential isolation games, we show upper and lower bounds on the sequential price of anarchy, that is the worst-case ratio between the social performance of an optimal solution and that of a subgame perfect equilibrium, under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players’ utilities
- …
