×

The plurality problem with three colors and more. (English) Zbl 1107.90025

Summary: The plurality problem is a game between two participants: Paul and Carole. We are given \(n\) balls, each of them is colored with one out of \(c\) colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carole answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions \(L_c(n)\) does Paul have to ask in the worst case?
For \(c=2\), the problem is equivalent to the well-known majority problem which has already been solved [M. E. Saks, M. Werman, Combinatorica 11, No. 4, 383–387 (1991; Zbl 0739.05006)]. In this paper we show that \(3\lfloor n/2\rfloor-2\leq L_3(n)\leq \lfloor 5n/3\rfloor-2\). Moreover, for any \(c\leq n\), we show that surprisingly the naive algorithm for the plurality problem is asymptotically optimal.

MSC:

90B40 Search theory
91A46 Combinatorial games
91B24 Microeconomic theory (price theory and economic markets)
05A05 Permutations, words, matrices
68W40 Analysis of algorithms

Citations:

Zbl 0739.05006
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M., Combinatorial Search (1988), Wiley: Wiley New York · Zbl 0663.68076
[2] Aigner, M., Variants of the majority problem, Discrete Appl. Math., 137, 1, 3-26 (2004) · Zbl 1034.68046
[3] M. Aigner, Two colors and more, preprint.; M. Aigner, Two colors and more, preprint.
[4] M. Aigner, G. De Marco, M. Montangero, The plurality problem with three colors, Proc. 21st Ann. Symp. on Theoretical Aspects of Computer Science, STACS 2004, Lecture Notes in Computer Science, Vol. 2996, Montpellier, France, pp. 513-521.; M. Aigner, G. De Marco, M. Montangero, The plurality problem with three colors, Proc. 21st Ann. Symp. on Theoretical Aspects of Computer Science, STACS 2004, Lecture Notes in Computer Science, Vol. 2996, Montpellier, France, pp. 513-521. · Zbl 1122.91301
[5] L. Alonso, P. Chassaing, E.M. Reingold, R. Schott, The chip problem, preprint, available at \(\sim;\); L. Alonso, P. Chassaing, E.M. Reingold, R. Schott, The chip problem, preprint, available at \(\sim;\) · Zbl 1178.68696
[6] Alonso, L.; Reingold, E. M.; Schott, R., Determining the majority, Inform. Process. Lett., 47, 253-255 (1993) · Zbl 0780.68051
[7] Alonso, L.; Reingold, E. M.; Schott, R., The average-case complexity of determining the majority, SIAM J. Comput., 26, 1-14 (1997) · Zbl 0868.68066
[8] G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Proc. 28th Internat. Symp. on Mathematical Foundations of Computer Science, MFCS 2003, Lecture Notes in Computer Science, Vol. 2747, Bratislava, Slovak Republic, pp. 368-377.; G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Proc. 28th Internat. Symp. on Mathematical Foundations of Computer Science, MFCS 2003, Lecture Notes in Computer Science, Vol. 2747, Bratislava, Slovak Republic, pp. 368-377. · Zbl 1124.68401
[9] Fisher, M.; Salzberg, S., Finding a majority among \(n\) votes, J. Algorithms, 3, 375-379 (1982)
[10] Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput., 16, 848-854 (1967) · Zbl 0189.16904
[11] Saks, M. E.; Werman, M., On computing majority by comparisons, Combinatorica, 11, 383-387 (1991) · Zbl 0739.05006
[12] Wiener, G., Search for a majority element, J. Statist. Plann. Inference, 100, 313-318 (2002) · Zbl 0994.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.