Randomized strategies for the plurality problem |
| |
Authors: | Daniel Král’ Tomáš Tichý |
| |
Institution: | a Department of Applied Mathematics and Institute for Theoretical Computer Science,11Institute for Theoretical Computer Science is supported by the Ministry of Education of the Czech Republic as project 1M0545. Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Prague, Czech Republic b Mathematical Institute of the Academy of Sciences of the Czech Republic, ?itná 25, CZ-11567 Prague, Czech Republic |
| |
Abstract: | 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 Ω(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 questions; this almost matches the lower bound . |
| |
Keywords: | Concrete complexity Randomized algorithms Plurality game Majority game |
本文献已被 ScienceDirect 等数据库收录! |
|