Efficient black-box reductions for separable cost sharing
From MaRDI portal
(Redirected from Efficient black-box reductions for separable cost sharing)
Abstract: In cost sharing games with delays, a set of agents jointly allocates a finite subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A prominent example is uncapacitated facility location (UFL), where facilities need to be opened (at a shareable cost) and clients want to connect to opened facilities. Each client pays a cost share and his non-shareable physical connection cost. Given any profile of subsets allocated by the agents, a separable cost sharing protocol determines cost shares that satisfy budget balance on every resource and separability over the resources. Moreover, a separable protocol guarantees existence of pure Nash equilibria in the induced strategic game for the agents. In this paper, we study separable cost sharing protocols in several general combinatorial domains. We provide black-box reductions to reduce the design of a separable cost-sharing protocol to the design of an approximation algorithm for the underlying cost minimization problem. In this way, we obtain new separable cost-sharing protocols in games based on arbitrary player-specific matroids, single-source connection games without delays, and connection games on -series-parallel graphs with delays. All these reductions are efficiently computable - given an initial allocation profile, we obtain a cheaper profile and separable cost shares turning the profile into a pure Nash equilibrium. Hence, in these domains any approximation algorithm can be used to obtain a separable cost sharing protocol with a price of stability bounded by the approximation factor.
Recommendations
Cites work
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- A Characterization of Undirected Graphs Admitting Optimal Cost Shares
- A class of games possessing pure-strategy Nash equilibria
- A course in game theory.
- A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- A threshold of ln n for approximating set cover
- Algorithmic Aspects of the Core of Combinatorial Optimization Games
- An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
- An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
- Applications of approximation algorithms to cooperative games
- Approximation Algorithms for Directed Steiner Problems
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Black-box reductions for cost-sharing mechanism design
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Competitive cost sharing with economies of scale
- Conflicting congestion effects in resource allocation games
- Cooperative facility location games
- Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling
- Cost allocation for steiner trees
- Cost-sharing scheduling games on restricted unrelated machines
- Designing cost-sharing methods for Bayesian games
- Designing network protocols for good equilibria
- Designing networks with good equilibria under uncertainty
- Efficient black-box reductions for separable cost sharing
- Exact and approximate equilibria for optimal group network formation
- Greedy Strikes Back: Improved Facility Location Algorithms
- Heuristics for the fixed cost median problem
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- Improved Bounds for Facility Location Games with Fair Cost Allocation
- Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games
- Minimum cost spanning tree games
- Near-optimal network design with selfish agents
- Network characterizations for excluding Braess's paradox
- Non-cooperative facility location and covering games
- Non-cooperative tree creation
- On cost allocation for a spanning tree: A game theoretic approach
- On the core of network synthesis games
- On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
- Optimal cost sharing for capacitated facility location games
- Optimal cost sharing for resource selection games
- Price of stability in survivable network design
- Resource buying games
- Spanning network games.
- Steiner tree approximation via iterative randomized rounding
- Strategic cooperation in cost sharing games
- Strategyproof sharing of submodular costs: budget balance versus efficiency
- Strong price of anarchy
- The Price of Stability for Network Design with Fair Cost Allocation
- Tighter Bounds for Graph Steiner Tree Approximation
- When ignorance helps: graphical multicast cost sharing games
Cited in
(4)
This page was built for publication: Efficient black-box reductions for separable cost sharing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4991670)
