What majority decisions are possible

by Shelah. [Sh:E37]

The main result is the following: Let X be a finite set and D be a non empty family of choice functions for {X} choose {2} closed under permutation of X . Then the following conditions are equivalent: (A) for any choice function c on {X} choose {2} we can find a finite set J and c_j in D for j in J such that for any x not= y in X : c {x,y}=y Leftrightarrow |J|/2<| {j in J:c_j {x,y}= y}| (so equality never occurs) (B) for some c in D and x in X we have | {y:c {x,y}= y}| not= (|X|-1)/2 . We then describe what is the closure of a set of choice functions by majority; in fact, there are just two possibilities (in section 3). In section 4 we discuss a generalization.


Back to the list of publications