The majority game with an arbitrary majority

DOI10.1016/J.DAM.2015.12.016zbMATH Open1336.05001arXiv1402.5913OpenAlexW1501675551MaRDI QIDQ284827FDOQ284827

Authors: John R. Britnell, Mark Wildon 

Publication date: 18 May 2016

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

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.

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

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

zbMATH Keywords

majority game

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On computing majority by comparisons
• Variants of the majority problem.
• Beyond knights and knaves
• Title not available (Why is that?)
• The plurality problem with three colors and more.
• Search for a majority element
• Determining the majority
• Computing majority with triple queries

Cited In (5)

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

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)