Recognizing Linked Domain in Polynomial Time
Yongjie Yang · arXiv (Cornell University) · 2017
The celebrated Gibbard-Satterthwaite Theorem states that any surjective social choice function which is defined over the universal domain of preferences and is strategy-proof must be dictatorial. Aswal, Chatterji and Sen generalize the Gibbard-Satterthwaite theorem by showing that the Gibbard-Satterthwaite theorem still holds if the universal domain is replaced with the linked domain. In this note, we show that determining whether an election is linked can be done in polynomial time.