March 19 (Thursday) 10:15-11:15, room C.510 (new building, 5th floor)
Tamás Fleiner (Budapest University of Technology and Economics)
Yet another proof of the Gibbard–Satterthwaite theorem
One of the fundamental results of social choice theory is Arrow’s impossibility theorem, which states that certain natural requirements related to democratic decision-making cannot be satisfied simultaneously. Another closely related result (often derived from Arrow’s theorem) is due to Gibbard and Satterthwaite. In this talk, I present an unorthodox proof of the latter theorem, whose key idea is a reformulation of strategy-proofness. Apparently, Arrow’s theorem can be derived from the resulting statement. Moreover, our reformulation of strategy-proofness can be used in other situations, as well. For example, to prove the strategy-proofness for the proposing side in the deferred acceptance algorithm by Gale and Shapley. If time permits, I will also present a generalization of Arrow’s theorem, whose proof is based on the structure of certain edge-colored mixed graphs.