Paper being referred to: http://www.cs.cmu.edu/~arielpro/15896/docs/paper9.pdf (The Computational Difficulty of Manipulating an Election).

I have a query in Theorem 1 of this paper; specifically, in the last argument of its proof.

enter image description here enter image description here

enter image description here

In the proof, the last argument is that $S(P,c)\geq S(P,u)$ (by the previous implications) and $S(P,c)<S(P,u)$ (because placing $u$ while completing $P$ would make $c$ lose). I understand that placing $u$ in $P$ would make $c$ lose; however, I don't understand why that means that $S(P,c)<S(P,u)$. Can someone clarify this?

My understanding is that the author intends to say that $u$ would become the winner, and hence (by the responsiveness property of the score function), $S(P,x)<S(P,u)\mbox{ }\forall x\in C\implies S(P,c)<S(P,u)$. However, why does $c$ not being the winner by putting $u$ mean that $u$ is the winner? Can't it be possible that there is some other candidate (alternative) $u'\in U$ who becomes the winner by placing $u$?

For this, what I've thought is that till before placing $u$, $S(P,c)\geq S(P,x)\mbox{ }\forall x\in C\backslash U$; and we don't know what the final $S(P,x)$ will be for any $x\in U$. My conjecture then is that placing $u$ could only give us information about $S(P,u)$ and not about any $x\in U\backslash \{u\}$; however, is this conjecture correct? If so, why? Can it not be possible that placing $u$ there could give us information about $S(P,x)$ for some $x\in U\backslash\{u\}$? What property of the score function $S(P):C\rightarrow \mathbb{R}$ precludes this (or at least precludes $S(P,x)$ from getting definitely larger than $S(P,c)$, for any $x\in U\backslash\{u\}$)?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.