Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages590-595
Number of pages6
ISBN (Electronic)9781538665961
DOIs
StatePublished - Jul 2 2018
Event56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018 - Monticello, United States
Duration: Oct 2 2018Oct 5 2018

Publication series

Name2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

Conference

Conference56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
Country/TerritoryUnited States
CityMonticello
Period10/2/1810/5/18

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing
  • Energy Engineering and Power Technology
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations'. Together they form a unique fingerprint.

Cite this