Near-optimal network design with selfish agents

DOI10.1145/780542.780617zbMath1192.68019OpenAlexW2121907157MaRDI QIDQ3581253

Éva Tardos, Tom Wexler, Elliot Anshelevich, Anirban Dasgupta

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780617

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Games involving graphs (91A43)

Related Items (38)

Strong equilibrium in cost sharing connection games ⋮ Atomic routing games on maximum congestion ⋮ The Price of Matching with Metric Preferences ⋮ When ignorance helps: graphical multicast cost sharing games ⋮ Dynamics in tree formation games ⋮ Stability in the self-organized evolution of networks ⋮ On the Performances of Nash Equilibria in Isolation Games ⋮ Anarchy Is Free in Network Creation ⋮ Capacitated network design games ⋮ Mechanism and Network Design with Private Negative Externalities ⋮ A network pricing game for selfish traffic ⋮ Price of stability in survivable network design ⋮ Some results of Christos Papadimitriou on internet structure, network routing, and web information ⋮ On the performances of Nash equilibria in isolation games ⋮ Selfish Bin Packing ⋮ The Price of Nash Equilibria in Multicast Transmissions Games ⋮ The price of anarchy of serial, average and incremental cost sharing ⋮ Good neighbors are hard to find: Computational complexity of network formation ⋮ Approximate Strong Equilibrium in Job Scheduling Games ⋮ Introduction to computer science and economic theory ⋮ Extending the notion of rationality of selfish agents: second order Nash equilibria ⋮ Selfish bin packing ⋮ Two-group knapsack game ⋮ On the severity of Braess's paradox: designing networks for selfish users is hard ⋮ $\mathcal{NP}$ -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games ⋮ When Ignorance Helps: Graphical Multicast Cost Sharing Games ⋮ An efficient and almost budget balanced cost sharing method ⋮ A contract-based model for directed network formation ⋮ Almost budget-balanced VCG mechanisms to assign multiple objects ⋮ Network design with weighted players ⋮ Competitive Cost Sharing with Economies of Scale ⋮ The Price of Anarchy of a Network Creation Game with Exponential Payoff ⋮ Non-cooperative tree creation ⋮ Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links ⋮ Network investment games with Wardrop followers ⋮ Geometric spanner games ⋮ Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games ⋮ On the sequential price of anarchy of isolation games

This page was built for publication: Near-optimal network design with selfish agents