Efficient Black-Box Reductions for Separable Cost Sharing
From MaRDI portal
Publication:4991670
DOI10.1287/moor.2020.1050zbMath1466.91141arXiv1802.10351OpenAlexW3081084561WikidataQ113265872 ScholiaQ113265872MaRDI QIDQ4991670
Martin Hoefer, Manuel Surek, Tobias Harks, Anja Schedel
Publication date: 3 June 2021
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.10351
Noncooperative games (91A10) Games involving graphs (91A43) Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal cost sharing for capacitated facility location games
- Cost-sharing scheduling games on restricted unrelated machines
- Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games
- Resource buying games
- Network characterizations for excluding Braess's paradox
- Competitive cost sharing with economies of scale
- Price of stability in survivable network design
- Exact and approximate equilibria for optimal group network formation
- On the core of network synthesis games
- When ignorance helps: graphical multicast cost sharing games
- Non-cooperative facility location and covering games
- An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
- Strong price of anarchy
- Non-cooperative tree creation
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Strategic cooperation in cost sharing games
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- Spanning network games.
- A class of games possessing pure-strategy Nash equilibria
- Designing Cost-Sharing Methods for Bayesian Games
- Designing Network Protocols for Good Equilibria
- A threshold of ln n for approximating set cover
- The Price of Stability for Network Design with Fair Cost Allocation
- A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
- On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
- Improved Bounds for Facility Location Games with Fair Cost Allocation
- Minimum cost spanning tree games
- Heuristics for the fixed cost median problem
- On cost allocation for a spanning tree: A game theoretic approach
- Cost allocation for steiner trees
- Greedy Strikes Back: Improved Facility Location Algorithms
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Designing Networks with Good Equilibria under Uncertainty
- Coordination Mechanisms, Cost-Sharing, and Approximation Algorithms for Scheduling
- Conflicting Congestion Effects in Resource Allocation Games
- Cooperative facility location games
- Approximation Algorithms for Directed Steiner Problems
- Algorithmic Aspects of the Core of Combinatorial Optimization Games
- Optimal Cost Sharing for Resource Selection Games
- Applications of approximation algorithms to cooperative games
- A Characterization of Undirected Graphs Admitting Optimal Cost Shares
- Tighter Bounds for Graph Steiner Tree Approximation
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Steiner Tree Approximation via Iterative Randomized Rounding
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
- Strategyproof sharing of submodular costs: budget balance versus efficiency
This page was built for publication: Efficient Black-Box Reductions for Separable Cost Sharing
