Mechanism design for set cover games with selfish element agents

Xiang Yang Li*, Zheng Sun, Wei Zhao Wang, Xiaowen CHU, Shao Jie Tang, Ping Xu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

In this article, we study the set cover games when the elements are selfish agents, each of which has a privately known valuation of receiving the service from the sets, i.e., being covered by some set. Each set is assumed to have a fixed cost. We develop several approximately efficient strategyproof mechanisms that decide, after soliciting the declared bids by all elements, which elements will be covered, which sets will provide the coverage to these selected elements, and how much each element will be charged. For single-cover set cover games, we present a mechanism that is at least frac(1, dmax)-efficient, i.e., the total valuation of all selected elements is at least frac(1, dmax) fraction of the total valuation produced by any mechanism. Here, dmax is the maximum size of the sets. For multi-cover set cover games, we present a budget-balanced strategyproof mechanism that is frac(1, dmax Hdmax)-efficient under reasonable assumptions. Here, Hn is the harmonic function. For the set cover games when both sets and elements are selfish agents, we show that a cross-monotonic payment-sharing scheme does not necessarily induce a strategyproof mechanism.

Original languageEnglish
Pages (from-to)174-187
Number of pages14
JournalTheoretical Computer Science
Volume411
Issue number1
DOIs
Publication statusPublished - 1 Jan 2010

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Mechanism design
  • Set cover
  • Strategyproof

Fingerprint

Dive into the research topics of 'Mechanism design for set cover games with selfish element agents'. Together they form a unique fingerprint.

Cite this