Musical Chairs

DOI10.1137/12088478XzbMATH Open1315.68265arXiv1208.0813OpenAlexW4236326290MaRDI QIDQ2935289FDOQ2935289

Yehuda Afek, Benny Sudakov, Nathan Linial, Eli Gafni, Uriel Feige, Yakov Babichenko

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: In the {em Musical Chairs} game $MC(n,m)$ a team of $n$ players plays against an adversarial {em scheduler}. The scheduler wins if the game proceeds indefinitely, while termination after a finite number of rounds is declared a win of the team. At each round of the game each player {em occupies} one of the $m$ available {em chairs}. Termination (and a win of the team) is declared as soon as each player occupies a unique chair. Two players that simultaneously occupy the same chair are said to be {em in conflict}. In other words, termination (and a win for the team) is reached as soon as there are no conflicts. The only means of communication throughout the game is this: At every round of the game, the scheduler selects an arbitrary nonempty set of players who are currently in conflict, and notifies each of them separately that it must move. A player who is thus notified changes its chair according to its deterministic program. As we show, for $mge2n-1$ chairs the team has a winning strategy. Moreover, using topological arguments we show that this bound is tight. For $mleq2n-2$ the scheduler has a strategy that is guaranteed to make the game continue indefinitely and thus win. We also have some results on additional interesting questions. For example, if $mge2n-1$ (so that the team can win), how quickly can they achieve victory?

Full work available at URL: https://arxiv.org/abs/1208.0813

Recommendations

• Distributed Computing
• On the table and the chair
• scientific article; zbMATH DE number 2060068
• Chess tableaux

zbMATH Keywords

distributed computingasynchronous computationprobabilistic analysisrenamingoblivious computing

Mathematics Subject Classification ID

Noncooperative games (91A10) Distributed algorithms (68W15)

Cited In (4)

• Distributed Computing
• Asynchronous Coordination Under Preferences and Constraints
• The assignment problem
• (The Bride's Chair)²

This page was built for publication: Musical Chairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2935289)