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: Chapter in book/report/conference proceedingConference proceedingpeer-review

5 Citations (Scopus)

Abstract

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
Title of host publicationInternational Conference on Algorithmic Applications in Management
Subtitle of host publicationAAIM 2005: Algorithmic Applications in Management
EditorsNimrod Megiddo, Yinfeng Xu, Binhai Zhu
Place of PublicationBerlin
PublisherSpringer
Pages360-369
Number of pages10
Volume3521
Edition1st
ISBN (Electronic)9783540324409
ISBN (Print)9783540262244
DOIs
Publication statusPublished - 2005
EventFirst International Conference on Algorithmic Applications in Management, AAIM 2005 - Xi'an, China
Duration: 22 Jun 200525 Jun 2005

Publication series

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

Conference

ConferenceFirst International Conference on Algorithmic Applications in Management, AAIM 2005
Country/TerritoryChina
CityXi'an
Period22/06/0525/06/05

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this