Designing Networks with Good Equilibria under Uncertainty

DOI10.1137/16M1096694zbMath1430.68013OpenAlexW2914095157MaRDI QIDQ5232329

Alkmini Sgouritsa, George Christodoulou

Publication date: 2 September 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1096694

zbMATH Keywords

online algorithmsnetwork designprice of anarchycost-sharing

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Games involving graphs (91A43) Applications of game theory (91A80) Graph theory (including graph drawing) in computer science (68R10) Network protocols (68M12) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonpreemptive coordination mechanisms for identical machines
• On-line Steiner trees in the Euclidean plane
• Network design with weighted players
• Coordination mechanisms
• Algorithms for the universal and a priori TSP
• An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
• Characterizations of outerplanar graphs
• Designing cost-sharing methods for Bayesian games
• On-line generalized Steiner problem
• The price of stability for undirected broadcast network design with fair cost allocation is constant
• Improving the price of anarchy for selfish routing via coordination mechanisms
• Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
• Efficient coordination mechanisms for unrelated machine scheduling
• Improved lower bounds on the price of stability of undirected network design games
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• An improved LP-based approximation for steiner tree
• Preemptive Coordination Mechanisms for Unrelated Machines
• Optimal Coordination Mechanisms for Multi-job Scheduling Games
• Optimal Cost-Sharing in Weighted Congestion Games
• Coordination mechanisms from (almost) all scheduling policies
• Designing Network Protocols for Good Equilibria
• Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
• The Price of Stability for Network Design with Fair Cost Allocation
• A Ramsey-type result for the hypercube
• Spacefilling curves and the planar travelling salesman problem
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• Approximation via cost sharing
• On the Price of Stability for Undirected Network Design
• Universal approximations for TSP, Steiner tree, and set cover
• Improved lower and upper bounds for universal TSP in planar metrics
• Improved Lower Bounds for the Universal and a priori TSP
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• The traveling salesman problem on a graph and some related integer polyhedra
• Dynamic Steiner Tree Problem
• Designing Networks with Good Equilibria under Uncertainty
• An Improved Upper Bound for the Universal TSP on the Grid
• A Characterization of Undirected Graphs Admitting Optimal Cost Shares
• A General Approximation Technique for Constrained Forest Problems
• Improving the H k -Bound on the Price of Stability in Undirected Shapley Network Design Games
• Coordination Mechanisms for Selfish Routing over Time on a Tree
• Optimal Cost Sharing for Resource Selection Games
• Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games
• Distributed Welfare Games
• Online Network Design Algorithms via Hierarchical Decompositions
• Inner product spaces for MinSum coordination mechanisms
• A Priori Optimization

This page was built for publication: Designing Networks with Good Equilibria under Uncertainty