License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05011.12
URN: urn:nbn:de:0030-drops-2061
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/206/
Go to the corresponding Portal

Smordinsky, Rann ; Tennenholtz, Moshe

Overcoming Free Riding in Multi-Party Computations

pdf-format:
05011.SmordinskyRann.Paper.206.pdf (0.2 MB)

Abstract

This paper addresses the question of multi party computation in a model with asymmetric information. Each agent has a private value (secret), but in contrast to standard models, the agent incurs a cost when retrieving the secret. There is a social choice function
the agents would like to compute and implement. All agents would like to perform a joint computation, which input is their vector
of secrets. However, agents would like to free-ride on others contribution.

A mechanism which elicits players secrets and performs the desired computation defines a game. A mechanism is `appropriate if it (weakly) implements the social choice function for all
secret vectors. namely, if there exists an equilibrium in which it is able to elicit (sufficiently many) agents secrets and perform
the computation, for all possible secret vectors. We show that `appropriate mechanisms approach agents sequentially and that
they have low communication complexity.

BibTeX - Entry

@InProceedings{smordinsky_et_al:DagSemProc.05011.12,
  author =	{Smordinsky, Rann and Tennenholtz, Moshe},
  title =	{{Overcoming Free Riding in Multi-Party Computations}},
  booktitle =	{Computing and Markets},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/206},
  URN =		{urn:nbn:de:0030-drops-2061},
  doi =		{10.4230/DagSemProc.05011.12},
  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
Collection: 05011 - Computing and Markets
Issue Date: 2005
Date of publication: 19.07.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI