Randomized strategies for the plurality problem

KRÁĽ, Daniel; J SGALL a T TICHY. Randomized strategies for the plurality problem. Discrete Applied Mathematics. AMSTERDAM: Elsevier B.V., 2008, roč. 156, č. 17, s. 3305-3311. ISSN 0166-218X. Dostupné z: https://doi.org/10.1016/j.dam.2008.05.014.

Základní údaje

Originální název

Randomized strategies for the plurality problem

Autoři

KRÁĽ, Daniel; J SGALL a T TICHY

Vydání

Discrete Applied Mathematics, AMSTERDAM, Elsevier B.V. 2008, 0166-218X

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.783

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.dam.2008.05.014

UT WoS

000261566600016

Klíčová slova anglicky

Concrete complexity; Randomized algorithms; Plurality game; Majority game

---

Anotace

V originále

We consider a game played by two players, Paul and Carol. At the beginning of the game, Carol fixes a coloring of n balls. At each turn, Paul chooses a pair of the balls and asks Carol whether the balls have the same color, Carol truthfully answers his question. Paul's goal is to determine the most frequent (plurality) color in the coloring by asking as few questions as possible. The game is studied in the probabilistic setting when Paul is allowed to choose his next question randomly. We give asymptotically tight bounds both for the case of two colors and many colors. For the balls colored by k colors, we prove a lower bound Omega(kn) on the expected number Of questions; this is asymptotically optimal. For the balls colored by two colors, we provide a strategy for Paul to determine the plurality color with the expected number of 2n/3 + O(root n log n) questions; this almost matches the lower bound 2n/3 - O(root n). (C) 2008 Elsevier B.V. All rights reserved.