All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 5 of 5

Showing per page

A distributed voting scheme to maximize preferences

Peter Auer, Nicolò Cesa-Bianchi (2006)

RAIRO - Theoretical Informatics and Applications

We study the problem of designing a distributed voting scheme for electing a candidate that maximizes the preferences of a set of agents. We assume the preference of agent i for candidate j is a real number xi,j, and we do not make any assumptions on the mechanism generating these preferences. We show simple randomized voting schemes guaranteeing the election of a candidate whose expected total preference is nearly the highest among all candidates. The algorithms we consider are designed so that...

A note on the voting problem.

Miguel Angel Fiol Mora (1992)

Stochastica

Let v(n) be the minimum number of voters with transitive preferences which are needed to generate any strong preference pattern (ties not allowed) on n candidates. Let k = [log2n]. Then it is shown that v(n) ≤ n-k if n and k have different parity, and v(n) ≤ n-k+1 otherwise.

A tight quantitative version of Arrow’s impossibility theorem

Nathan Keller (2012)

Journal of the European Mathematical Society

The well-known Impossibility Theorem of Arrow asserts that any generalized social welfare function (GSWF) with at least three alternatives, which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a dictatorship, is necessarily non-transitive. In 2002, Kalai asked whether one can obtain the following quantitative version of the theorem: For any ϵ > 0 , there exists δ = δ ( ϵ ) such that if a GSWF on three alternatives satisfies the IIA condition and its probability of non-transitive...

Currently displaying 1 – 5 of 5

Page 1