Cost Sharing and Strategyproof Mechanisms for Set Cover Games

Xiang Yang Li, Zheng Sun, Weizhao Wang

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

15 Citations (Scopus)

Abstract

We develop for set cover games several general cost-sharing methods that are approximately budget-balanced, core, and/or group-strategyproof. We first study the cost sharing for a single set cover game, which does not have a budget-balanced core. We show that there is no cost allocation method that can always recover more than 1/In n of the total cost if we require the cost sharing being a core. Here n is the number of all players to be served. We give an efficient cost allocation method that always recovers 1/In n dmax- of the total cost, where dmax 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 1/n of the total cost for every subset of players. We give an efficient cost sharing scheme that always recovers at least 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, such that each element maximizes its profit when it reports its valuation truthfully; further, the total cost of the set cover is no more than In dmax times that of an optimal solution. When the sets are selfish agents with privately known costs, we present a strategyproof payment mechanism in which each set maximizes its profit when it reports its cost truthfully. We also show how to fairly share the payments to all sets among the elements.

Original languageEnglish
Title of host publicationSTACS 2005
Subtitle of host publication22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2004, Proceedings
EditorsVolker Diekert, Bruno Durand
PublisherSpringer-Verlag Berlin Heidelberg
Pages218-230
Number of pages13
Edition1st
ISBN (Electronic)9783540318569
ISBN (Print)9783540249986
DOIs
Publication statusPublished - 2 Feb 2005
Externally publishedYes
Event22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005 - Stuttgart, Germany
Duration: 24 Feb 200526 Feb 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume3404
ISSN (Print)0302-9743

Conference

Conference22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005
Country/TerritoryGermany
CityStuttgart
Period24/02/0526/02/05

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Service Provider
  • Greedy Algorithm
  • Cost Sharing
  • Cost Allocation
  • Partial Cover

Fingerprint

Dive into the research topics of 'Cost Sharing and Strategyproof Mechanisms for Set Cover Games'. Together they form a unique fingerprint.

Cite this