Dominant Strategy Allocation of Divisible Network Resources with Limited Information Exchange

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

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationINFOCOM 2018 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2753-2761
Number of pages9
ISBN (Electronic)9781538641286
DOIs
StatePublished - Oct 8 2018
Event2018 IEEE Conference on Computer Communications, INFOCOM 2018 - Honolulu, United States
Duration: Apr 15 2018Apr 19 2018

Publication series

NameProceedings - IEEE INFOCOM
Volume2018-April
ISSN (Print)0743-166X

Other

Other2018 IEEE Conference on Computer Communications, INFOCOM 2018
Country/TerritoryUnited States
CityHonolulu
Period4/15/184/19/18

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Dominant Strategy Allocation of Divisible Network Resources with Limited Information Exchange'. Together they form a unique fingerprint.

Cite this