Benedict Eastaugh (University of Warwick) – Strategic voting theorems and reverse mathematics

One of the foundational results of voting theory is the Gibbard–Satterthwaite theorem: for finite societies, every function selecting a winner from a finite set of candidates that is immune to manipulation by the misrepresentation of preferences is either constant or dictatorial. In infinite societies, the Gibbard–Satterthwaite theorem can fail: Pazner and Wesley (1977) showed that when the set of voters is infinite, there exist social choice functions that are both non-manipulable ('strategyproof') and non-dictatorial. Their proof rests on the existence of non-principal ultrafilters, a consequence of the axiom of choice, and hence clearly has a nonconstructive aspect. In this talk I will examine the Pazner–Wesley possibility theorem in the context of reverse mathematics, and show that for countable societies it is equivalent over RCA₀ to arithmetical comprehension. I will then formulate a seemingly weaker version of the Pazner–Wesley possibility theorem, using individual strategyproofness rather than coalitional strategyproofness, and raise some open questions regarding the relationship between these two statements.