Designing Network Protocols for Good Equilibria
From MaRDI portal
Publication:3053150
DOI10.1137/08072721XzbMath1207.68164OpenAlexW2162057799MaRDI QIDQ3053150
Ho-Lin Chen, Gregory Valiant, Tim Roughgarden
Publication date: 4 November 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/08072721x
game theoryNash equilibriumdirected graphsnetwork designprice of anarchyundirected graphsnetwork cost-sharing gamescost-sharing protocolsShapley protocol
Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Deterministic network models in operations research (90B10) Network protocols (68M12)
Related Items
Optimal cost sharing for capacitated facility location games ⋮ Tight Bounds for Cost-Sharing in Weighted Congestion Games ⋮ Efficient coordination mechanisms for unrelated machine scheduling ⋮ How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium ⋮ Truth-telling and Nash equilibria in minimum cost spanning tree models ⋮ Nash equilibria with minimum potential in undirected broadcast games ⋮ \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games ⋮ Sharing Non-anonymous Costs of Multiple Resources Optimally ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ Minimum cost connection networks: truth-telling and implementation ⋮ Optimal Cost-Sharing in General Resource Selection Games ⋮ Strategic cooperation in cost sharing games ⋮ Unnamed Item ⋮ The price of anarchy as a classifier for mechanism design in a Pareto-Bayesian-Nash context ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Designing cost-sharing methods for Bayesian games ⋮ Minimizing Rosenthal potential in multicast games ⋮ On the efficiency of the proportional allocation mechanism for divisible resources ⋮ Trouble comes in threes: core stability in minimum cost connection networks ⋮ Restoring Pure Equilibria to Weighted Congestion Games ⋮ Unnamed Item ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ A Characterization of Undirected Graphs Admitting Optimal Cost Shares ⋮ Designing Cost-Sharing Methods for Bayesian Games ⋮ Dynamics of Profit-Sharing Games ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ On the Price of Anarchy of cost-sharing in real-time scheduling systems ⋮ Topological price of anarchy bounds for clustering games on networks ⋮ Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games ⋮ Enforcing efficient equilibria in network design games via subsidies