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
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
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 -