License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-2056
URL: http://drops.dagstuhl.de/opus/volltexte/2005/205/
Müller, Rudolf ; Perea, Andres ; Wolf, Sascha

A Network Approach to Bayes-Nash Incentive Compatible Mechanisms

pdf-format:
Dokument 1.pdf (223 KB)

Abstract

This paper provides a characterization of Bayes-Nash incentive compatible mechanisms in settings where agents have one-dimensional or multi-dimensional types, quasi-linear utility functions and interdependent valuations. The characterization is derived in terms of conditions for the underlying allocation function. We do this by making a link to network theory and building complete directed graphs for agents type spaces. We show that an allocation rule is Bayes-Nash incentive compatible if and only if these graphs have no negative, finite cycles. In the case of one-dimensional types and given certain properties for agents valuation functions, we show that this condition reduces to the absence of negative 2-cycles. In the case of multi-dimensional types and given a linearity requirement on the valuation functions, we show that this condition reduces to the absence of negative 2-cycles and an integratebility condition on the valuation functions.

BibTeX - Entry

@InProceedings{mller_et_al:DSP:2005:205,
  author =	{Rudolf M{\"u}ller and Andres Perea and Sascha Wolf},
  title =	{A Network Approach to Bayes-Nash Incentive Compatible Mechanisms},
  booktitle =	{Computing and Markets},
  year =	{2005},
  editor =	{Daniel Lehmann and Rudolf M{\"u}ller and Tuomas Sandholm},
  number =	{05011},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/205},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}

Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio
Seminar: 05011 - Computing and Markets
Issue date: 2005
Date of publication: 19.07.2005

DROPS-Home | Fulltext Search | Imprint Published by LZI