Mechanism design for set cover games when elements are agents

Zheng Sun*, Xiang Yang Li, Wei Zhao Wang, Xiaowen CHU

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

5 Citations (Scopus)


In this paper we study the set cover games when the elements are selfish agents. In this case, each element 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 truthful mechanisms, each of which decides, 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 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 truthful mechanism.

Original languageEnglish
Pages (from-to)360-369
Number of pages10
JournalLecture Notes in Computer Science
Publication statusPublished - 2005
EventFirst International Conference on Algorithmic Applications in Management, AAIM 2005 - Xian, China
Duration: 22 Jun 200525 Jun 2005

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Mechanism design for set cover games when elements are agents'. Together they form a unique fingerprint.

Cite this