TY - GEN
T1 - Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations
AU - Ge, Hao
AU - Berry, Randall A.
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/7/2
Y1 - 2018/7/2
N2 - We address the problem of designing efficient allocation mechanisms for a divisible resource, which is a fundamental problem in many networked systems. One milestone in mechanism design is the well-known Vickrey-Clarke-Groves (VCG) mechanism, where there exists a strictly dominant strategy for each agent. However, VCG mechanisms can require an excessive amount of communication making it impractical in some large networked systems. Alternative approaches have been studied that relax the incentive properties of VCG to limit communication. Alternatively, in prior work we considered the use of quantization as a way to reduce communication and maintain dominant strategy incentive compatibility, albeit with a loss of efficiency. Our prior work bounded this efficiency loss allowing for arbitrary concave increasing agent utilities. In this paper, we first refine this analysis when bounds on the marginal utility of an agent are known. In addition to quantizing the resource, we also study mechanisms that quantize the bids an agent can submit and again bound the overall efficiency loss given constraints on the agent's marginal valuations.
AB - We address the problem of designing efficient allocation mechanisms for a divisible resource, which is a fundamental problem in many networked systems. One milestone in mechanism design is the well-known Vickrey-Clarke-Groves (VCG) mechanism, where there exists a strictly dominant strategy for each agent. However, VCG mechanisms can require an excessive amount of communication making it impractical in some large networked systems. Alternative approaches have been studied that relax the incentive properties of VCG to limit communication. Alternatively, in prior work we considered the use of quantization as a way to reduce communication and maintain dominant strategy incentive compatibility, albeit with a loss of efficiency. Our prior work bounded this efficiency loss allowing for arbitrary concave increasing agent utilities. In this paper, we first refine this analysis when bounds on the marginal utility of an agent are known. In addition to quantizing the resource, we also study mechanisms that quantize the bids an agent can submit and again bound the overall efficiency loss given constraints on the agent's marginal valuations.
UR - http://www.scopus.com/inward/record.url?scp=85062866888&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062866888&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2018.8635997
DO - 10.1109/ALLERTON.2018.8635997
M3 - Conference contribution
AN - SCOPUS:85062866888
T3 - 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
SP - 590
EP - 595
BT - 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
Y2 - 2 October 2018 through 5 October 2018
ER -