Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations

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

1 Citation (Scopus)

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 - Feb 5 2019
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
CountryUnited States
CityMonticello
Period10/2/1810/5/18

Fingerprint

Valuation
Communication
Incentive Compatibility
Mechanism Design
Resources
Divisible
Incentives
Quantization
Strictly
Strategy
Alternatives
Arbitrary

ASJC Scopus subject areas

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

Cite this

Ge, H., & Berry, R. A. (2019). Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018 (pp. 590-595). [8635997] (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2018.8635997
Ge, Hao ; Berry, Randall A. / Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations. 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 590-595 (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018).
@inproceedings{aebf5f0229a64723982a2d02ea1f0dab,
title = "Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations",
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.",
author = "Hao Ge and Berry, {Randall A}",
year = "2019",
month = "2",
day = "5",
doi = "10.1109/ALLERTON.2018.8635997",
language = "English (US)",
series = "2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "590--595",
booktitle = "2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018",
address = "United States",

}

Ge, H & Berry, RA 2019, Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations. in 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018., 8635997, 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, Institute of Electrical and Electronics Engineers Inc., pp. 590-595, 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, Monticello, United States, 10/2/18. https://doi.org/10.1109/ALLERTON.2018.8635997

Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations. / Ge, Hao; Berry, Randall A.

2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc., 2019. p. 590-595 8635997 (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018).

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

TY - GEN

T1 - Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations

AU - Ge, Hao

AU - Berry, Randall A

PY - 2019/2/5

Y1 - 2019/2/5

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

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.

ER -

Ge H, Berry RA. Quantized Dominant Strategy Mechanisms with Constrained Marginal Valuations. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc. 2019. p. 590-595. 8635997. (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018). https://doi.org/10.1109/ALLERTON.2018.8635997