The majority game with an arbitrary majority

DOI10.1016/J.DAM.2015.12.016MaRDI QIDQ284827zbMATH OpenOpenAlexFDO

Authors John R. Britnell, Mark Wildon

Publication date 18 May 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

majority game

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Search theory (90B40)

Abstract: The $k$-majority game is played with $n$ numbered balls, each coloured with one of two colours. It is given that there are at least $k$ balls of the majority colour, where $k$ is a fixed integer greater than $n/2$. On each turn the player selects two balls to compare, and it is revealed whether they are of the same colour; the player's aim is to determine a ball of the majority colour. It has been correctly stated by Aigner that the minimum number of comparisons necessary to guarantee success is $2(n-k)-B(n-k)$, where $B(m)$ is the weight of the binary expansion of $m$. However his proof contains an error. We give an alternative proof of this result, which generalizes an argument of Saks and Werman.

Recommendations

• Variants of the majority problem.
• On more variants of the majority problem
• Determining the majority
• On randomized algorithms for the majority problem
• Majority and plurality problems

Cites work

• Beyond knights and knaves
• Computing majority with triple queries
• Determining the majority
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 922674 (Why is no real title available?)
• On computing majority by comparisons
• Search for a majority element
• The plurality problem with three colors and more.
• Variants of the majority problem.

Cited in

(5)

• Local and global majorities revisited
• The mask game with multiple populations
• Searching for knights and spies: a majority/minority game
• How to Play the Majority Game with Liars
• How to play the majority game with a liar

This page was built for publication: The majority game with an arbitrary majority

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