Cost sharing and strategyproof mechanisms for set cover games

Xiang-Yang Li (), Zheng Sun (), Weizhao Wang () and Wei Lou ()
Additional contact information
Xiang-Yang Li: Illinois Institute of Technology
Zheng Sun: Google Inc.
Weizhao Wang: Google Inc.
Wei Lou: The Hong Kong Polytechnic University

Journal of Combinatorial Optimization, 2010, vol. 20, issue 3, No 4, 259-284

Abstract: Abstract We develop for set cover games several general cost-sharing methods that are approximately budget-balanced, in the core, and/or group-strategyproof. We first study the cost sharing for a single set cover game, which does not have a budget-balanced mechanism in the core. We show that there is no cost allocation method that can always recover more than $\frac{1}{\ln n}$ of the total cost and in the core. Here n is the number of all players to be served. We give a cost allocation method that always recovers $\frac{1}{\ln d_{\mathit{max}}}$ of the total cost, where d max is the maximum size of all sets. We then study the cost allocation scheme for all induced subgames. It is known that no cost sharing scheme can always recover more than $\frac{1}{n}$ of the total cost for every subset of players. We give an efficient cost sharing scheme that always recovers at least $\frac{1}{2n}$ of the total cost for every subset of players and furthermore, our scheme is cross-monotone. When the elements to be covered are selfish agents with privately known valuations, we present a strategyproof charging mechanism, under the assumption that all sets are simple sets; further, the total cost of the set cover is no more than ln d max times that of an optimal solution. When the sets are selfish agents with privately known costs, we present a strategyproof payment mechanism to them. We also show how to fairly share the payments to all sets among the elements.

Keywords: Set cover; Selfish agent; Mechanism design; Pricing (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9209-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:20:y:2010:i:3:d:10.1007_s10878-009-9209-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9209-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().