[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| Title: | Mathematics at DEC |
|
| Moderator: | RUSURE::EDP |
|
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
1670.0. "AMM Problem 10252" by RUSURE::EDP (Always mount a scratch monkey.) Fri Oct 02 1992 12:08
Proposed by James S. Weber, The University of Illinois, Chicago, IL.
An election is to be held with V voters who will rank A alternatives.
It is said that alternative X is an "M-majority preference" over
alternative Y if there are at least M voters who prefer X to Y. A
"voter's paradox cycle" is an ordering of the alternatives a[0], a[1],
. . . a[A-1], a[A] = a[0] so that a[i] is preferred over a[i+1] for 0
<= i < A. Prove that a voter's paradox cycle can exist for M-majority
preference if and only if AM <= V(A-1).
| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1670.1 | | HERON::BUCHANAN | The was not found. | Thu Oct 22 1992 16:41 | 17 |
| Imagine each voter goes for one of the following A options:
a[i] prefered to a[i+1] prefered to .... a[n] prefered to a[1]
prefered to ... a[i-1].
Suppose the voters are distributed as evenly as possible (Monopoly
house construction rule) across the A options. Then a[i] is prefered to
a[i+1] by all but at most ceiling(V/A) voters. So there is an M-majority
for all M =< V - ceiling(V/A) = floor(V(A-1)/A).
Therefore an M-majority paradox cycle can exist if AM=<V(A-1).
On the other hand, each voter can contribute to at most A-1 of the A
desirable preferences of a[i] over a[i+1]. We need M votes for each such
preference. So AM =< V(A-1) is necessary for an M-majority paradox cycle.
Andrew.
|