DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2019.20

Consensus in Equilibrium: Can One Against All Decide Fairly?

Authors: Itay Harel, Amit Jacob-Fanani, Moshe Sulamy, and Yehuda Afek

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract

Is there an equilibrium for distributed consensus when all agents except one collude to steer the decision value towards their preference? If an equilibrium exists, then an n-1 size coalition cannot do better by deviating from the algorithm, even if it prefers a different decision value. We show that an equilibrium exists under this condition only if the number of agents in the network is odd and the decision is binary (among two possible input values). That is, in this framework we provide a separation between binary and multi-valued consensus. Moreover, the input and output distribution must be uniform, regardless of the communication model (synchronous or asynchronous). Furthermore, we define a new problem - Resilient Input Sharing (RIS), and use it to find an iff condition for the (n-1)-resilient equilibrium for deterministic binary consensus, essentially showing that an equilibrium for deterministic consensus is equivalent to each agent learning all the other inputs in some strong sense. Finally, we note that (n-2)-resilient equilibrium for binary consensus is possible for any n. The case of (n-2)-resilient equilibrium for multi-valued consensus is left open.

Cite as

Itay Harel, Amit Jacob-Fanani, Moshe Sulamy, and Yehuda Afek. Consensus in Equilibrium: Can One Against All Decide Fairly?. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harel_et_al:LIPIcs.OPODIS.2019.20,
  author =	{Harel, Itay and Jacob-Fanani, Amit and Sulamy, Moshe and Afek, Yehuda},
  title =	{{Consensus in Equilibrium: Can One Against All Decide Fairly?}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.20},
  URN =		{urn:nbn:de:0030-drops-118065},
  doi =		{10.4230/LIPIcs.OPODIS.2019.20},
  annote =	{Keywords: distributed computing, game theory, rational agents, consensus}
}

Document

DOI: 10.4230/LIPIcs.DISC.2018.5

The Role of A-priori Information in Networks of Rational Agents

Authors: Yehuda Afek, Shaked Rafaeli, and Moshe Sulamy

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract

Until now, distributed algorithms for rational agents have assumed a-priori knowledge of n, the size of the network. This assumption is challenged here by proving how much a-priori knowledge is necessary for equilibrium in different distributed computing problems. Duplication - pretending to be more than one agent - is the main tool used by agents to deviate and increase their utility when not enough knowledge about n is given. We begin by proving that when no information on n is given, equilibrium is impossible for both Coloring and Knowledge Sharing. We then provide new algorithms for both problems when n is a-priori known to all agents. However, what if agents have partial knowledge about n? We provide tight upper and lower bounds that must be a-priori known on n for equilibrium to be possible in Leader Election, Knowledge Sharing, Coloring, Partition and Orientation.

Cite as

Yehuda Afek, Shaked Rafaeli, and Moshe Sulamy. The Role of A-priori Information in Networks of Rational Agents. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{afek_et_al:LIPIcs.DISC.2018.5,
  author =	{Afek, Yehuda and Rafaeli, Shaked and Sulamy, Moshe},
  title =	{{The Role of A-priori Information in Networks of Rational Agents}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.5},
  URN =		{urn:nbn:de:0030-drops-97945},
  doi =		{10.4230/LIPIcs.DISC.2018.5},
  annote =	{Keywords: rational agents, distributed game theory, coloring, knowledge sharing}
}

Search Results

Documents authored by Sulamy, Moshe

Consensus in Equilibrium: Can One Against All Decide Fairly?

Abstract

Cite as

The Role of A-priori Information in Networks of Rational Agents

Abstract

Cite as

Thanks for your feedback!

Could not send message