Six Candidates Suffice to Win a Voter Majority
Adrian Vetta ( McGill University )
- 12:00 17th October 2025 ( week 1, Michaelmas Term 2025 )Seminar Room 051
Time and place: Seminar Room 051 (Wolfson Building), Fri 17 Oct, 12pm - 12.45pm
Abstract: Given an election of n voters with preference lists over m candidates, Elkind, Lang, and Saffidine (2011) defined a Condorcet winning set to be a collection of candidates that the majority of voters prefer over any individual candidate. Condorcet winning sets of cardinality one (a Condorcet winner) or cardinality two need not exist. We prove however that a Condorcet winning set of cardinality at most six exists in any election.
(Joint work with M. Charikar, P. Ramakrishnan, A. Lassota and K. Wang)