Quantized VCG mechanisms for polymatroid environments

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

Abstract

Many network resource allocation problems can be viewed as allocating a divisible resource, where the allocations are constrained to lie in a polymatroid. We consider market-based mechanisms for such problems. Though the Vickrey-Clarke-Groves (VCG) mechanism can provide the efficient allocation with strong incentive properties (namely dominant strategy incentive compatibility), its well-known high communication requirements can prevent it from being used. There have been a number of approaches for reducing the communication costs of VCG by weakening its incentive properties. Here, instead we take a different approach of reducing communication costs via quantization while maintaining VCG’s dominant strategy incentive properties. The cost for this approach is a loss in efficiency which we characterize. We first consider quantizing the resource allocations so that agents need only submit a finite number of bids instead of full utility function. We subsequently consider quantizing the agent’s bids.

Original languageEnglish (US)
Title of host publicationMobihoc 2019 - Proceedings of the 2019 20th ACM International Symposium on Mobile Ad Hoc Networking and Computing
PublisherAssociation for Computing Machinery
Pages261-270
Number of pages10
ISBN (Electronic)9781450367646
DOIs
StatePublished - Jul 2 2019
Event20th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2019 - Catania, Italy
Duration: Jul 2 2019Jul 5 2019

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Conference

Conference20th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2019
CountryItaly
CityCatania
Period7/2/197/5/19

Keywords

  • Mechanism design
  • Quantization
  • Worst-case efficiency

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'Quantized VCG mechanisms for polymatroid environments <sup>∗</sup>'. Together they form a unique fingerprint.

Cite this