### Abstract

Given m ≥ 3 alternatives and n ≥ 2 voters, let σ(m,n) be the least integer k for which there is a set of k strict preference profiles for the voters on the alternatives with the following property: Arrow's impossibility theorem holds for this profile set and for each of its strict preference profile supersets. We show that σ(3, 2) = 6 and that for each m, σ(m,n)/4^{n} approaches 0 monotonically as n gets large. In addition, for each n and ε > 0, σ(m,n)/(log_{2} m)^{2+ε} approaches 0 as m gets large. Hence for many alternatives or many voters, a robust version of Arrow's theorem is induced by a very small fraction of the set of all (m!)^{n} strict preference profiles.

Original language | English (US) |
---|---|

Pages (from-to) | 83-95 |

Number of pages | 13 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 10 |

Issue number | 1 |

State | Published - Feb 1997 |

### Fingerprint

### Keywords

- Arrow's impossibility theorem
- Minimum profile sets
- Voter preference profiles

### ASJC Scopus subject areas

- Applied Mathematics
- Discrete Mathematics and Combinatorics

### Cite this

*SIAM Journal on Discrete Mathematics*,

*10*(1), 83-95.