Mechanism design for set cover games when elements are agents

Zheng Sun; Xiang Yang Li; Wei Zhao Wang; Xiaowen CHU

doi:10.1007/11496199_39

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

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-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 language	English
Title of host publication	International Conference on Algorithmic Applications in Management
Subtitle of host publication	AAIM 2005: Algorithmic Applications in Management
Editors	Nimrod Megiddo, Yinfeng Xu, Binhai Zhu
Place of Publication	Berlin
Publisher	Springer
Pages	360-369
Number of pages	10
Volume	3521
Edition	1st
ISBN (Electronic)	9783540324409
ISBN (Print)	9783540262244
DOIs	https://doi.org/10.1007/11496199_39
Publication status	Published - 2005
Event	First International Conference on Algorithmic Applications in Management, AAIM 2005 - Xi'an, China Duration: 22 Jun 2005 → 25 Jun 2005

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	3521
ISSN (Print)	0302-9743

Conference

Conference	First International Conference on Algorithmic Applications in Management, AAIM 2005
Country/Territory	China
City	Xi'an
Period	22/06/05 → 25/06/05

Access to Document

10.1007/11496199_39

Cite this

Sun, Z., Li, X. Y., Wang, W. Z., & CHU, X. (2005). Mechanism design for set cover games when elements are agents. In N. Megiddo, Y. Xu, & B. Zhu (Eds.), International Conference on Algorithmic Applications in Management: AAIM 2005: Algorithmic Applications in Management (1st ed., Vol. 3521, pp. 360-369). (Lecture Notes in Computer Science; Vol. 3521). Springer. https://doi.org/10.1007/11496199_39

Sun, Zheng ; Li, Xiang Yang ; Wang, Wei Zhao et al. / Mechanism design for set cover games when elements are agents. International Conference on Algorithmic Applications in Management: AAIM 2005: Algorithmic Applications in Management. editor / Nimrod Megiddo ; Yinfeng Xu ; Binhai Zhu. Vol. 3521 1st. ed. Berlin : Springer, 2005. pp. 360-369 (Lecture Notes in Computer Science).

@inproceedings{42557aaf0c1d44c89db7ef37df988fc0,

title = "Mechanism design for set cover games when elements are agents",

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.",

author = "Zheng Sun and Li, {Xiang Yang} and Wang, {Wei Zhao} and Xiaowen CHU",

note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; First International Conference on Algorithmic Applications in Management, AAIM 2005 ; Conference date: 22-06-2005 Through 25-06-2005",

year = "2005",

doi = "10.1007/11496199_39",

language = "English",

isbn = "9783540262244",

volume = "3521",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "360--369",

editor = "Nimrod Megiddo and Yinfeng Xu and Binhai Zhu",

booktitle = "International Conference on Algorithmic Applications in Management",

address = "Germany",

edition = "1st",

}

Sun, Z, Li, XY, Wang, WZ & CHU, X 2005, Mechanism design for set cover games when elements are agents. in N Megiddo, Y Xu & B Zhu (eds), International Conference on Algorithmic Applications in Management: AAIM 2005: Algorithmic Applications in Management. 1st edn, vol. 3521, Lecture Notes in Computer Science, vol. 3521, Springer, Berlin, pp. 360-369, First International Conference on Algorithmic Applications in Management, AAIM 2005, Xi'an, China, 22/06/05. https://doi.org/10.1007/11496199_39

Mechanism design for set cover games when elements are agents. / Sun, Zheng; Li, Xiang Yang; Wang, Wei Zhao et al.
International Conference on Algorithmic Applications in Management: AAIM 2005: Algorithmic Applications in Management. ed. / Nimrod Megiddo; Yinfeng Xu; Binhai Zhu. Vol. 3521 1st. ed. Berlin: Springer, 2005. p. 360-369 (Lecture Notes in Computer Science; Vol. 3521).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Mechanism design for set cover games when elements are agents

AU - Sun, Zheng

AU - Li, Xiang Yang

AU - Wang, Wei Zhao

AU - CHU, Xiaowen

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=25144510865&partnerID=8YFLogxK

U2 - 10.1007/11496199_39

DO - 10.1007/11496199_39

M3 - Conference proceeding

AN - SCOPUS:25144510865

SN - 9783540262244

VL - 3521

T3 - Lecture Notes in Computer Science

SP - 360

EP - 369

BT - International Conference on Algorithmic Applications in Management

A2 - Megiddo, Nimrod

A2 - Xu, Yinfeng

A2 - Zhu, Binhai

PB - Springer

CY - Berlin

T2 - First International Conference on Algorithmic Applications in Management, AAIM 2005

Y2 - 22 June 2005 through 25 June 2005

ER -

Mechanism design for set cover games when elements are agents

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this