Inducing approximately optimal flow using truthful mediators

Ryan Rogers, Aaron Roth, Jonathan Ullman, Steven Wu

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

15 Scopus citations

Abstract

We revisit a classic coordination problem from the perspective of mechanism design: how can we coordinate a social welfare maximizing flow in a network congestion game with selfish players? The classical approach, which computes tolls as a function of known demands, fails when the demands are unknown to the mechanism designer, and naively eliciting them does not necessarily yield a truthful mechanism. Instead, we introduce a weak mediator that can provide suggested routes to players and set tolls as a function of reported demands. However, players can choose to ignore or misreport their type to this mediator. Using techniques from differential privacy, we show how to design a weak mediator such that it is an asymptotic ex-post Nash equilibrium for all players to truthfully report their types to the mediator and faithfully follow its suggestion, and that when they do, they end up playing a nearly optimal flow. Notably, our solution works in settings of incomplete information even in the absence of a prior distribution on player types. Along the way, we develop new techniques for privately solving convex programs which may be of independent interest.

Original languageEnglish (US)
Title of host publicationEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages471-488
Number of pages18
ISBN (Electronic)9781450334105
DOIs
StatePublished - Jun 15 2015
Externally publishedYes
Event16th ACM Conference on Economics and Computation, EC 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015

Publication series

NameEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation

Other

Other16th ACM Conference on Economics and Computation, EC 2015
CountryUnited States
CityPortland
Period6/15/156/19/15

Keywords

  • Differential privacy
  • Large games
  • Routing games

Fingerprint Dive into the research topics of 'Inducing approximately optimal flow using truthful mediators'. Together they form a unique fingerprint.

Cite this