Computation and Logic in the Real World; Third Conference on Computability in Europe (CiE2007)

p. 297-306

DOI: 10.1007/978-3-540-73001-9_31

Presentation's date: 2007-06

Abstract:

This paper presents some new results about majority games. Isbell (1959) was the first to find a majority game without a minimum normalized integer representation; he needed 12 voters to construct such a game. Since then, it has been an open problem to find the minimum number of voters of a majority game without a minimum normalized integer representation. Our main new results are: 1. All majority games with less than 9 voters have a minimum integer representation. 2. For 9 voters, there are 14 majority games without a minimum integer representation, but all these games admit a minimum normalized integer representation. 3. For 10 voters, there exist majority games with neither a minimum integer representation nor a minimum normalized integer representation.]]>

Date: 2007-02

Abstract:

This paper presents some new results about majority games. Isbell (1959) was the first to find a majority game without a minimum normalized representation; he needed 12 voters to construct such a game. Since then, it has been an open problem to find the minimum number of voters of a majority game without a minimum normalized representation. Our main new results are: 1. All majority games with less than 9 voters have a minimum representation. 2. For 9 voters there are 14 majority games without a minimum integer representation, but these games admit a minimal normalized integer representation. 3. For 10 voters exist majority games with neither a minimum integer representation nor a minimal normalized integer representation.]]>

Lecture notes in computer science

Vol. 4497, p. 297-306

DOI: 10.1007/978-3-540-73001-9_31

Date of publication: 2007-01