Towards truthful mechanisms for binary demand games: A general framework

Ming-Yang Kao*, Xiang Yang Li, Weizhao Wang

*Corresponding author for this work

Research output: Contribution to conferencePaper

22 Scopus citations

Abstract

The family of Vickrey-Clarke-Groves (VCG) mechanisms is arguably the most celebrated achievement in truthful mechanism design. However, VCG mechanisms have their limitations. They only apply to optimization problems with a utilitarian (or affine) objective function, and their output should optimize the objective function. For many optimization problems, finding the optimal output is computationally intractable. If we apply VCG mechanisms to polynomial-time algorithms that approximate the optimal solution, the resulting mechanisms may no longer be truthful. In light of these limitations, it is useful to study whether we can design a truthful non-VCG payment scheme that is computationally tractable for a given allocation rule O. In this paper, we focus our attention on binary demand games in which the agents' only available actions are to take part in the a game or not to. For these problems, we prove that a truthful mechanism M = (O, P) exists with a proper payment method P iff the allocation rule O satisfies a certain monotonicity property. We provide a general framework to design such P. We further propose several general composition-based techniques to compute P efficiently for various types of output. In particular, we show how P can be computed through "or/and" combinations, round-based combinations, and some more complex combinations of the outputs from subgames.

Original languageEnglish (US)
Pages213-222
Number of pages10
DOIs
StatePublished - Dec 1 2005
EventEC'05: 6th ACM Conference on Electronic Commerce - Vancouver, Canada
Duration: Jun 5 2005Jun 8 2005

Other

OtherEC'05: 6th ACM Conference on Electronic Commerce
CountryCanada
CityVancouver
Period6/5/056/8/05

Keywords

  • Demand games
  • Mechanism design
  • Pricing
  • Selfish agent

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Towards truthful mechanisms for binary demand games: A general framework'. Together they form a unique fingerprint.

  • Cite this

    Kao, M-Y., Li, X. Y., & Wang, W. (2005). Towards truthful mechanisms for binary demand games: A general framework. 213-222. Paper presented at EC'05: 6th ACM Conference on Electronic Commerce, Vancouver, Canada. https://doi.org/10.1145/1064009.1064032