Quantifying inefficiency in cost-sharing mechanisms

No abstract is available for this paper.

• Publication year

  2009

• Venue

  JACM

• Publication date

  2009-06-01

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  DOI 10.1145/1538902.1538907
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Unifying computers and dynamical systems using the theory of synchronous concurrent algorithms

  2009cited by this paper
• Approximating power indices

  2008cited by this paper
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game

  2008influential reference
• Is Shapley Cost Sharing Optimal?

  2008cited by this paper
• Introduction to the Inefficiency of Equilibria

  2007cited by this paper
• Optimal Efficiency Guarantees for Network Design Mechanisms

  2007cited by this paper
• Beyond moulin mechanisms

  2007cited by this paper
• Cost Sharing Methods for Makespan and Completion Time Scheduling

  2007influential reference
• Cost-Sharing Mechanisms for Network Design

  2007cited by this paper
• Strong price of anarchy

  2007cited by this paper
• Algorithmic Game Theory: Introduction to the Inefficiency of Equilibria

  2007cited by this paper
• Deducing ink-transmittance spectra from reflectance and transmittance measurements of prints

  2007cited by this paper
• An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem

  2007influential reference
• Optimal Cost-Sharing Mechanisms for Steiner Forest Problems

  2006cited by this paper
• Potential functions and the inefficiency of equilibria

  2006cited by this paper
• New trade-offs in cost-sharing mechanisms

  2006cited by this paper
• Fair cost-sharing methods for scheduling jobs on parallel machines

  2006cited by this paper
• Introduction

  2006cited by this paper
• Limitations of cross-monotonic cost sharing schemes

  2005cited by this paper
• Data streams: algorithms and applications

  2005cited by this paper
• From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem

  2005cited by this paper
• A group-strategyproof mechanism for Steiner forests

  2005influential reference
• Fair Production and Allocation of an Excludable Nonrival Good

  2004cited by this paper
• The price of stability for network design with fair cost allocation

  2004cited by this paper
• Cross-monotonic cost-sharing methods for connected facility location games

  2004cited by this paper
• Strategyproof cost-sharing mechanisms for set cover and facility location games

  2003cited by this paper
• Optimization in the private value model: competitive analysis applied to auction design

  2003cited by this paper
• Group strategy proof mechanisms via primal-dual algorithms

  2003influential reference
• Hardness Results for Multi ast Cost Sharing

  2002cited by this paper
• Equitable cost allocations via primal-dual-type algorithms

  2002influential reference
• Hardness Results for Multicast Cost Sharing

  2002influential reference
• Distributed algorithmic mechanism design: recent results and future directions

  2002cited by this paper
• Strategyproof cost-sharing Mechanisms for Set Cover and Facility Location Problems

  2002cited by this paper
• Applications of approximation algorithms to cooperative games

  2001influential reference
• Sharing the Cost of Multicast Transmissions

  2001cited by this paper
• Strategyproof sharing of submodular costs:budget balance versus efficiency

  2001cited by this paper
• Approximation and collusion in multicast cost sharing (extended abstract)

  2001cited by this paper
• Incremental cost sharing: Characterization by coalition strategy-proofness

  1999cited by this paper
• Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields

  1999cited by this paper
• AUCTION-LIKE MECHANISMS FOR PRICING EXCLUDABLE PUBLIC GOODS

  1999cited by this paper
• Online computation and competitive analysis

  1998cited by this paper
• Solutions manual for Microeconomic theory : Mas-Colell, Whinston and Green

  1997cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• Hardness Of Approximations

  1996influential reference
• REGULAR ARTICLEPotential Games

  1996cited by this paper
• A Course in Game Theory

  1995cited by this paper
• Potential Games

  1994cited by this paper
• A note on the prize collecting traveling salesman problem

  1993cited by this paper
• Partial Equilibrium Approach to the Free-Rider Problem

  1976cited by this paper
• The complexity of theorem-proving procedures

  1971influential reference
• Counterspeculation, Auctions, And Competitive Sealed Tenders

  1961cited by this paper
• 16. Acceptable Points in General Cooperative n-Person Games

  1959cited by this paper

• Dynamic Allocation of Public Goods with Approximate Core Equilibria

  2025cites this paper
• Multidimensional Budget-Feasible Mechanism Design

  2025cites this paper
• Robust Double Auctions for Resource Allocation

  2024cites this paper
• Collusion-proof mechanisms for multi-unit procurement

  2023cites this paper
• When Bidders Are DAOs

  2023cites this paper
• On the optimality of Shapley mechanism for funding public excludable goods under Sybil strategies

  2023cites this paper
• Truthful Aggregation of Budget Proposals with Proportionality Guarantees

  2022cites this paper
• Cost Sharing over Combinatorial Domains

  2022cites this paper
• Acyclic Mechanism Design for Freight Consolidation

  2021cites this paper
• An online cost allocation model for horizontal supply chains

  2021cites this paper
• Cost-Sharing Mechanism Design for Social Cost Minimization in Ridesharing Systems

  2021cites this paper
• How to split the costs and charge the travellers sharing a ride? aligning system's optimum with users' equilibrium

  2021cites this paper
• Cost-sharing mechanism for excludable goods with generalized non-rivalry

  2021cites this paper
• Decentralized Ride-Sharing and Vehicle-Pooling Based on Fair Cost-Sharing Mechanisms

  2020cites this paper
• Approximately Socially-Optimal Decentralized Coalition Formation with Application to P2P Energy Sharing

  2020cites this paper
• Approximately Socially-Optimal Decentralized Coalition Formation

  2020cites this paper
• Combinatorial cost sharing

  2019influential citation
• An Ascending Auction for Freight Forwarder Collaboration in Capacity Sharing

  2019cites this paper
• Peer-to-Peer Energy Sharing: Effective Cost-Sharing Mechanisms and Social Efficiency

  2019cites this paper
• Cost Sharing over Combinatorial Domains: Complement-Free Cost Functions and Beyond

  2019cites this paper
• Moulin mechanism design for freight consolidation

  2018cites this paper
• Cost Sharing in Two-Sided Markets

  2018cites this paper
• Deferred-Acceptance Auctions for Multiple Levels of Service

  2017cites this paper
• Combinatorial Cost Sharing

  2017influential citation
• Is Shapley Cost Sharing Optimal ? ∗ ( For the special issue in honor of Lloyd Shapley )

  2016influential citation
• Efficiency and Budget Balance

  2016cites this paper
• Cost-Sharing Mechanism Design for Freight Consolidation among Small Suppliers

  2016cites this paper
• Facility Location with Minimax Envy

  2016cites this paper
• Efficiency and Budget Balance in General Quasi-linear Domains

  2016cites this paper
• Approximately Efficient Cost Sharing via Double Auctions

  2016influential citation
• Efficient cost-sharing mechanisms for prize-collecting problems

  2015influential citation
• Stability coalition formation with cost sharing in multi-agent systems based on volume discount

  2015cites this paper
• Strong Price of Anarchy of Coalition Formation Game with Fair Cost Sharing and Bounded Capacity for Sharing Economy

  2015cites this paper
• Quantifying Inefficiency of Fair Cost-Sharing Mechanisms for Sharing Economy

  2015cites this paper
• Computing Stable Coalitions: Approximation Algorithms for Reward Sharing

  2015cites this paper
• The complexity of egalitarian mechanisms for linear programming games

  2014cites this paper
• Network Cost-Sharing without Anonymity

  2014influential citation
• Modularity and greed in double auctions

  2014cites this paper
• The performance of deferred-acceptance auctions

  2014cites this paper
• Algorithmic Game Theory

  2014cites this paper
• Distributed Signaling Games

  2014cites this paper
• Potential games are necessary to ensure pure nash equilibria in cost sharing games

  2013cites this paper
• Cost-recovering bayesian algorithmic mechanism design

  2013cites this paper
• Cost-sharing mechanisms for scheduling under general demand settings

  2012cites this paper
• Minimizing Rosenthal Potential in Multicast Games

  2012cites this paper
• Black-box reductions for cost-sharing mechanism design

  2012influential citation
• Characterizing distribution rules for cost sharing games

  2011cites this paper
• To Be or Not to Be ( Served ) : Cost Sharing Without Indifferences ∗

  2010cites this paper
• Is Shapley Cost Sharing Optimal?

  2008cites this paper
• An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem

  2007influential citation
• Cost Sharing Mechanisms in Transportation

  year unknowncites this paper