Monte-Carlo Algorithms for Comparison of Voting Methods

Date: 
Friday, April 14, 2006 - 2:57pm

Omer Egecioglu
Date: Wenesday, April 19, 2006
Time: 3:00pm-4:00pm
Location: Engineering I, Room 2114

Abstract:
We will consider a number of voting methods such as Condorcet, Borda,
and Plurality with Run-off in the Impartial Anonymous and Neutral
Culture model (IANC). In this model voter preferences are treated
through a class of preference profiles (called roots) in which both the
names of the voters and of the alternatives (candidates) are immaterial.
We describe a Monte-Carlo method and a testbed to answer various
questions about the properties and behaviors of anonymous and neutral
social choice rules for large parameters. For example, we can
experimentally answer questions such as:

* The likelihood of the existence of Condorcet winners,
* The probability of Condorcet and Plurality rules to choose the
same winner,
* The probability that the Borda winner picks the Condorcet winner,
etc..

Even for 20 voters and 10 alternatives, the number of IANC classes
(roots, or structurally different preference profiles) is

17758069318650119858962669239674956879327271587948512064321599292646589480794890970501606240176140489486440.

Furthermore, the equivalence classes do not have the same size. Thus the
problem of generating preference profiles from the uniform distribution that
is required for the Monte-Carlo method itself is nontrivial.

Biography:
currently unavailable

Hosts: Oscar Ibarra, Tobias Höller