King's College London

Research portal

Iterative voting and acyclic games

Research output: Contribution to journalArticle

Standard

Iterative voting and acyclic games. / Meir, Reshef; Polukarov, Maria; Rosenschein, Jeffrey S.; Jennings, Nicholas R.

In: ARTIFICIAL INTELLIGENCE, Vol. 252, 11.2017, p. 100-122.

Research output: Contribution to journalArticle

Harvard

Meir, R, Polukarov, M, Rosenschein, JS & Jennings, NR 2017, 'Iterative voting and acyclic games', ARTIFICIAL INTELLIGENCE, vol. 252, pp. 100-122. https://doi.org/10.1016/j.artint.2017.08.002

APA

Meir, R., Polukarov, M., Rosenschein, J. S., & Jennings, N. R. (2017). Iterative voting and acyclic games. ARTIFICIAL INTELLIGENCE, 252, 100-122. https://doi.org/10.1016/j.artint.2017.08.002

Vancouver

Meir R, Polukarov M, Rosenschein JS, Jennings NR. Iterative voting and acyclic games. ARTIFICIAL INTELLIGENCE. 2017 Nov;252:100-122. https://doi.org/10.1016/j.artint.2017.08.002

Author

Meir, Reshef ; Polukarov, Maria ; Rosenschein, Jeffrey S. ; Jennings, Nicholas R. / Iterative voting and acyclic games. In: ARTIFICIAL INTELLIGENCE. 2017 ; Vol. 252. pp. 100-122.

Bibtex Download

@article{55b48259f12046fc83f526616872ff09,
title = "Iterative voting and acyclic games",
abstract = "Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to artificial intelligence. In such situations, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome, as is often the case both in offline committees and in online voting. Specifically, we are interested in identifying conditions under which such iterative voting processes are guaranteed to converge to a Nash equilibrium state—that is, under which this process is acyclic. We classify convergence results based on the underlying assumptions about the agent scheduler (the order in which the agents take their actions) and the action scheduler (the actions available to the agents at each step). By so doing, we position iterative voting models within the general framework of acyclic games and game forms. In more detail, our main technical results provide a complete picture of conditions for acyclicity in several variations of Plurality voting. In particular, we show that (a) under the traditional lexicographic tie-breaking, the game converges from any state and for any order of agents, under a weak restriction on voters' actions; and that (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but there is always some path of better replies from any initial state of the game to a Nash equilibrium. We thus show a first separation between order-free acyclicity and weak acyclicity of game forms, thereby settling an open question from [Kukushkin 2011]. In addition, we refute another conjecture of Kukushkin regarding strongly acyclic voting rules, by proving the existence of strongly acyclic separable game forms.",
keywords = "Iterative voting, Acyclicity, Convergence, Nash equilibrium",
author = "Reshef Meir and Maria Polukarov and Rosenschein, {Jeffrey S.} and Jennings, {Nicholas R.}",
year = "2017",
month = nov,
doi = "10.1016/j.artint.2017.08.002",
language = "English",
volume = "252",
pages = "100--122",
journal = "ARTIFICIAL INTELLIGENCE",
issn = "0004-3702",
publisher = "Elsevier",

}

RIS (suitable for import to EndNote) Download

TY - JOUR

T1 - Iterative voting and acyclic games

AU - Meir, Reshef

AU - Polukarov, Maria

AU - Rosenschein, Jeffrey S.

AU - Jennings, Nicholas R.

PY - 2017/11

Y1 - 2017/11

N2 - Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to artificial intelligence. In such situations, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome, as is often the case both in offline committees and in online voting. Specifically, we are interested in identifying conditions under which such iterative voting processes are guaranteed to converge to a Nash equilibrium state—that is, under which this process is acyclic. We classify convergence results based on the underlying assumptions about the agent scheduler (the order in which the agents take their actions) and the action scheduler (the actions available to the agents at each step). By so doing, we position iterative voting models within the general framework of acyclic games and game forms. In more detail, our main technical results provide a complete picture of conditions for acyclicity in several variations of Plurality voting. In particular, we show that (a) under the traditional lexicographic tie-breaking, the game converges from any state and for any order of agents, under a weak restriction on voters' actions; and that (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but there is always some path of better replies from any initial state of the game to a Nash equilibrium. We thus show a first separation between order-free acyclicity and weak acyclicity of game forms, thereby settling an open question from [Kukushkin 2011]. In addition, we refute another conjecture of Kukushkin regarding strongly acyclic voting rules, by proving the existence of strongly acyclic separable game forms.

AB - Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to artificial intelligence. In such situations, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome, as is often the case both in offline committees and in online voting. Specifically, we are interested in identifying conditions under which such iterative voting processes are guaranteed to converge to a Nash equilibrium state—that is, under which this process is acyclic. We classify convergence results based on the underlying assumptions about the agent scheduler (the order in which the agents take their actions) and the action scheduler (the actions available to the agents at each step). By so doing, we position iterative voting models within the general framework of acyclic games and game forms. In more detail, our main technical results provide a complete picture of conditions for acyclicity in several variations of Plurality voting. In particular, we show that (a) under the traditional lexicographic tie-breaking, the game converges from any state and for any order of agents, under a weak restriction on voters' actions; and that (b) Plurality with randomized tie-breaking is not guaranteed to converge under arbitrary agent schedulers, but there is always some path of better replies from any initial state of the game to a Nash equilibrium. We thus show a first separation between order-free acyclicity and weak acyclicity of game forms, thereby settling an open question from [Kukushkin 2011]. In addition, we refute another conjecture of Kukushkin regarding strongly acyclic voting rules, by proving the existence of strongly acyclic separable game forms.

KW - Iterative voting

KW - Acyclicity

KW - Convergence

KW - Nash equilibrium

U2 - 10.1016/j.artint.2017.08.002

DO - 10.1016/j.artint.2017.08.002

M3 - Article

VL - 252

SP - 100

EP - 122

JO - ARTIFICIAL INTELLIGENCE

JF - ARTIFICIAL INTELLIGENCE

SN - 0004-3702

ER -

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454