Improving the price of anarchy for selfish routing via coordination mechanisms

DOI10.1007/s00453-013-9753-8zbMath1291.91037arXiv1202.2877OpenAlexW2569128852MaRDI QIDQ2249743

Evangelia Pyrga, Kurt Mehlhorn, Giorgos Christodoulou, George Christodoulou

Publication date: 3 July 2014

Published in: Algorithmica, Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.2877

zbMATH Keywords

price of anarchyalgorithmic game theoryselfish routingcoordination mechanisms

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (9)

Optimal Cost-Sharing in General Resource Selection Games ⋮ Unnamed Item ⋮ Designing cost-sharing methods for Bayesian games ⋮ Improving the price of anarchy for selfish routing via coordination mechanisms ⋮ Decentralized beneficiary behavior in humanitarian supply chains: models, performance bounds, and coordination mechanisms ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Designing Cost-Sharing Methods for Bayesian Games ⋮ Dynamics of Profit-Sharing Games ⋮ Enforcing efficient equilibria in network design games via subsidies

Cites Work

• Unnamed Item
• Unnamed Item
• Worst-case equilibria
• Coordination mechanisms
• Truthful algorithms for scheduling selfish tasks on parallel machines
• Coordination mechanisms for selfish scheduling
• On truthfulness and approximation for scheduling selfish tasks
• On the convergence of descent methods for monotone variational inequalities
• Improving the price of anarchy for selfish routing via coordination mechanisms
• How much can taxes help selfish routing?
• A geometric approach to the price of anarchy in nonatomic congestion games
• Linear tolls suffice: new bounds and algorithms for tolls in single source networks
• Efficiency of Restricted Tolls in Non-atomic Network Routing Games
• How bad is selfish routing?
• Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games
• Pricing network edges for heterogeneous selfish users
• Scheduling Selfish Tasks: About the Performance of Truthful Algorithms
• Equilibria for Networks with Lower Semicontinuous Costs: With an Application to Congestion Pricing
• Inner product spaces for MinSum coordination mechanisms
• Algorithmic Game Theory
• Traffic assignment problem for a general network

This page was built for publication: Improving the price of anarchy for selfish routing via coordination mechanisms