Titlebook: Algorithmic Game Theory; Third International Spyros Kontogiannis,Elias Koutsoupias,Paul G. Spir Conference proceedings 2010 Springer-Verla

柱廊

Camouflage

Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games,tions to these games. For some settings, we show that the solutions are necessarily Pareto optimal. When this is not the case, we provide a measure to . the distance of the solution from Pareto efficiency. Using this measure, we provide upper and lower bounds on the “Pareto inefficiency” of the diff

RENAL

On Nash-Equilibria of Approximation-Stable Games,quilibria that are far apart, or .-equilibria that are far in variation distance from the true Nash equilibrium strategies, then this prediction may not be possible even in principle. Motivated by this consideration, in this paper we define the notion of games that are ., meaning that all .-approxim

inflate

Improved Lower Bounds on the Price of Stability of Undirected Network Design Games,ory research agenda. Even though the generalization of such games in directed networks is well understood in terms of the price of stability (it is exactly .., the .-th harmonic number, for games with . players), far less is known for network design games in undirected networks. The upper bound carr

Amnesty

On the Rate of Convergence of Fictitious Play, strategy that is given by the empirical frequencies of actions played in previous rounds. There is a close relationship between fictitious play and the Nash equilibria of a game: if the empirical frequencies of fictitious play converge to a strategy profile, this strategy profile is a Nash equilibr

Afflict

On Learning Algorithms for Nash Equilibria,in many naturally arising games, and thus results on the convergence or non-convergence properties of such dynamics may inform our understanding of the applicability of Nash equilibria as a plausible solution concept in some settings. A second reason for asking this question is in the hope of being

不在灌木丛中

On the Structure of Weakly Acyclic Games, game is one where natural distributed dynamics, such as better-response dynamics, cannot enter .. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a . pure Nash equilibrium in every . implies the weak acy

mortgage

Alienated

fallible

On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users, the selfish users by introducing taxes on the network edges. A tax vector is . if all (at least one of) the equilibria in the resulting game minimize(s) the total latency. The issue of designing optimal tax vectors for selfish routing games has been studied extensively in the literature. We study f