Rationality in the full-information model

Ronen Gradwohl*

*Corresponding author for this work

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

5 Scopus citations

Abstract

We study rationality in protocol design for the full-information model, a model characterized by computationally unbounded adversaries, no private communication, and no simultaneity within rounds. Assuming that players derive some utility from the outcomes of an interaction, we wish to design protocols that are faithful: following the protocol should be an optimal strategy for every player, for various definitions of "optimal" and under various assumptions about the behavior of others and the presence, size, and incentives of coalitions. We first focus on leader election for players who only care about whether or not they are elected. We seek protocols that are both faithful and resilient, and for some notions of faithfulness we provide protocols, whereas for others we prove impossibility results. We then proceed to random sampling, in which the aim is for the players to jointly sample from a set of m items with a distribution that is a function of players' preferences over them. We construct protocols for m ≥ 3 that are faithful and resilient when players are single-minded. We also show that there are no such protocols for 2 items or for complex preferences.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 7th Theory of Cryptography Conference, TCC 2010, Proceedings
Pages401-418
Number of pages18
DOIs
StatePublished - 2010
Event7th Theory of Cryptography Conference, TCC 2010 - Zurich, Switzerland
Duration: Feb 9 2010Feb 11 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5978 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th Theory of Cryptography Conference, TCC 2010
CountrySwitzerland
CityZurich
Period2/9/102/11/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Rationality in the full-information model'. Together they form a unique fingerprint.

Cite this