On the Strategy-proof Social Choice of Fixed-sized Subsets

This thesis gives a contribution to strategy-proof social choice theory, in which one investigates to what extent there exist voting procedures that never can be manipulated in the sense that some voter by misrepresentation of his preferences can change the outcome of the voting and obtain an alternative he prefers to that honest voting would give. When exactly one element should be elected from a set of at least three alternatives, then the fundamental result in strategy-proof social choice theory, the Gibbard-Satterthwaite theorem, shows that there in general exists no satisfactory non-manipulable voting procedure. However, in many practical voting situations, e.g., when the available alternatives can be ordered on a political left–right scale, individual preferences have a structure which is known as single-peakedness, and in this case it is possible to find reasonable strategy-proof voting procedures. In this thesis, we analyze the more general voting situation when the number of alternatives that should be elected is greater than one but fixed, which for instance is the case in elections to national parliaments, and we are able to prove results analogous to the single-valued case: in general, there exist no reasonable non-manipulable voting procedures, but when preferences are single-peaked, voting can be made strategy-proof. In connection with our analysis of the strategy-proof social choice of fixed-sized subsets, we obtain also two additional interesting results: firstly, we show that the Gibbard-Satterthwaite theorem not only holds for complete preferences, but also for a large class of domains of partial preferences, and secondly, we are able to make the statement of the original Gibbard-Satterthwaite theorem more precise by proving that every reasonable voting procedure not only can be manipulated, but some voter can manipulate it in such a way that he obtains at least his second best alternative