TY - GEN
T1 - Dominant Strategy Allocation of Divisible Network Resources with Limited Information Exchange
AU - Ge, Hao
AU - Berry, Randall A.
N1 - Funding Information:
This work was supported in part by the National Science Foundation grant TWC-1314620.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/10/8
Y1 - 2018/10/8
N2 - A fundamental problem in many network systems is how to allocate limited resources among competing agents, who may have their own incentives. The well-known Vickrey-Clarke-Groves (VCG) mechanism provides an elegant solution to this incentive issue. In particular, VCG implements the socially optimal outcome in dominant strategies. However, it is also well-known that this mechanism can require an excessive amount of communication. Approaches have been studied that relax the communication requirements while also relaxing the incentive guarantees to use Nash equilibria instead of dominant strategies. Here, we take a different approach and study mechanisms with limited information that still have dominant strategy outcomes, but suffer an efficiency loss. We characterize this loss for the case of a single divisible resource. We first consider a mechanism in which information is limited by quantizing the resource into a finite number of units and allocating each of these to one agent via a VCG mechanism. This limits each agent to submitting a finite number of real values. We subsequently consider the case where each value is also quantized before being reported by each agent. Finally, we present numerical examples of the performance of these mechanisms.
AB - A fundamental problem in many network systems is how to allocate limited resources among competing agents, who may have their own incentives. The well-known Vickrey-Clarke-Groves (VCG) mechanism provides an elegant solution to this incentive issue. In particular, VCG implements the socially optimal outcome in dominant strategies. However, it is also well-known that this mechanism can require an excessive amount of communication. Approaches have been studied that relax the communication requirements while also relaxing the incentive guarantees to use Nash equilibria instead of dominant strategies. Here, we take a different approach and study mechanisms with limited information that still have dominant strategy outcomes, but suffer an efficiency loss. We characterize this loss for the case of a single divisible resource. We first consider a mechanism in which information is limited by quantizing the resource into a finite number of units and allocating each of these to one agent via a VCG mechanism. This limits each agent to submitting a finite number of real values. We subsequently consider the case where each value is also quantized before being reported by each agent. Finally, we present numerical examples of the performance of these mechanisms.
UR - http://www.scopus.com/inward/record.url?scp=85056158430&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056158430&partnerID=8YFLogxK
U2 - 10.1109/INFOCOM.2018.8486341
DO - 10.1109/INFOCOM.2018.8486341
M3 - Conference contribution
AN - SCOPUS:85056158430
T3 - Proceedings - IEEE INFOCOM
SP - 2753
EP - 2761
BT - INFOCOM 2018 - IEEE Conference on Computer Communications
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE Conference on Computer Communications, INFOCOM 2018
Y2 - 15 April 2018 through 19 April 2018
ER -