Student Comments for November 3, 2008
Michael Aubourg
Clearly, the strategy-proofness corresponds to the absence of strategic votes.
In open, anonymous environments such as the Internet, mechanism design is complicated by the fact that a single agent like me, can participate in the mechanism under multiple identifiers, which is not very difficult to do, since we just need to create a new email account. One way to address this is to design false-name-proof mechanisms, which choose the outcome in such a way that agents have no incentive to use more than one identifier. Unfortunately, there are inherent limitations on what can be achieved with false-name-proof mechanisms, and at least in some cases, these limitations are crippling. One of the most natural alternative approach is to verify the identities of all agents. Bu this imposes significant overhead and removes any benefits from anonymity which is required for the vote.
Nowadays, we can vote for many online polls. I tried one today, to see what they do in order to prevent us to vote more than once. I tried to vote twice but it did not work.
Thus, there is a kind of security. Obviously, the Internet browser identify my PC. Even if I refreshed the page, it did not work.
As a matter of fact, the website identify me thanks to Internet cookies.
The solution for multiple vote is easy : Reset your cookie, temp files and clear your cache. Here you can vote again !
Now let's have a look on physical votes in the past. In
response to these long standing concerns, in
So this is the question : will photoID legislation actually solve the stated problem, is the social cost greater than the problem stated, and are there cheaper alternatives which could meet both goals of reduced voter fraud and increased citizen access to the polls?
I would argue that compared to simply inking the fingers of voters - a remarkably cheap and effective solution to preventing multiple votes - requiring a voter to present a photoID is unreasonably arduous for too many legitimate voters who would be denied access to the polls, potentially damaging to voters' anonymity , and likely wouldn't prevent non citizen voting anyway.
Peter Blair
Optimal False-Name-Proof Voting Rules with Costly Voting
In this paper the authors consider social choice situations where new manipulation, such as a single agent casting multiple votes, may occur. This is likely to occur in online voting contest that require an email address to vote, where an sufficiently interested agent may sign-up for many internet accounts and vote multiple times in order to ensure that his/her favorite candidate wins. The authors show that there is a voting rule that resuts in the correct choice for the winner in settings where there are two choices and the number of agents tends to infinity, or get very large. A similar result does not hold in the case of three or more alternatives and this is the basis for future work. One criticism of this model is that it assumes that there is some minimal base cost with additional votes. While this is rooted in reality with the example of the catpha phrases that one needs to enter for the email address, it seems also reasonable to consider cases where there are economies of scale for casting multiple votes -- i.e. the manipulating agent gets successively better at creating new accounts, or underwriting the cost for an additional vote, with each additional vote cast. Take for example, if one were to create the email account fakename@gmail,com and then use the back key and create a subsequent account fakeemail1@gmail.com etc, we have a situation in which there are diminishing returns. An even more compelling case is that of a manipulator who writes a script that both creates fake accounts and votes! One way of getting around the problem of extending the results here to situations with >2 alternatives could be to create a tournament style game in which each voter votes between the (n,2) pairs of alternatives using the scoring rule that is false-name-proof for the two alternative case, the winner can be chosen using a run-off method with the existing preferences, or based on the "winning" record in the head-to-head competitions between the pairs or by a tournament style game.
Anonymity-Proof Voting Rules
In this paper the author consider defines a classification of voting rules that are anonymity-proof, that is "it is false-name-proof and it satisfies participation." A voting rule satisfies participation if a voter can not maximize his/her utility by not voting. The results of this classification for anonymity-proof and neutral voting scoring rules are summarized in Theorem #1. I would like to comment on the goals of these types of voting rules in light of the context in which they arise. Typically the goal of online voting is to increase traffic to a given website. I have hear from some people that they types of competitions are most interesting if they are manipulable, i.e. given that an agent can increase his/her utility by manipulating the outcome of the vote, then he/she is more likely to participate period. Moreover, the manipulator is more apt to engage similarly-minded agents to engage in manipulation, leading to a greater rate of participation among potential anonymous/online voters. If the goal of the website hosting the election is to drive up traffic to its site, then it seems like the participation requirement of anonymity-proof voting rules is more important than it's fake-name-proofness. Nevertheless, if one were to insist on having an election that was as fair as possible, it appears that the best way is to impose some kind of stringent identity requirement through a reliable third party where the cost of creating an additional account is so high that the voting process is not subject to manipulation. It should also be noted that in this scenario, the incentives will have to be higher to ensure participation, since voters will no longer have as an incentive to participate their ability to manipulation the outcome of voting.
A voting rule is anonymity-proof if it is false-name-proof and it satisfies participation.
Theorem 1
The class of voting rules f that are anonymity-proof and neutral consists exactly of the following rules.
–
With some probability kf in [0, 1], the rule chooses an alternative uniformly at random.
–
With probability 1 − kf it draws a pair of alternatives uniformly at random;
•
If every vote prefers the same alternative between the two (and there is at least one vote), then it chooses that alternative.
•
Otherwise, it flips a fair coin to decide between the two alternatives.
(All these rules are also false-name-proof in a stronger sense where the voter need not cast any vote with her true preferences, and this also implies that they are all strategyproof.)
Angela Ying
Paper 1: Optimal False-Name-Proof Voting Rules with Costly Voting
This paper was interesting in that it described a new kind of manipulation for voting, namely false-name-proof voting. The main contribution of the paper was creating, in the case of 2 alternatives, voting rules that satisfy false-name-proof in addition to strategy-proof. This kind of voting procedure would therefore be ideal for something like an online vote, where a user theoretically could vote as many times as possible. However, in order for this to happen the author had to assume some kind of cost for the voter to cast additional votes, specified in the paper as c. Without this cost, this system could not be possible. I thought this paper was really interesting because in addition to showing that the voting procedure was false-name-proof and strategy-proof, it also demonstrated that as the number of voters approached infinity, the probability of choosing the most preferred candidate (by plurality) approaches 1, which is ideal. Otherwise, people may not have an incentive to vote at all.
The ideas and the thoroughness of the proofs in this paper were definitely a strong point. However, the paper did not really have a strong optimal rule for k >= 4 alternatives, and had to make more assumptions for k = 3. It would obviously make sense that the more candidates, the more difficult the voting rules would be. I think the statement that "sometimes a vote for one alternative increases the winning probability of another alternative (but not enough to violate strategy-proofness)" was particularly interesting, because it seems that this would be more difficult in group situations, where a coalition of voters may decide to vote against their preferred choice in order to influence the election.
Paper 2: Anonymity-Proof Voting Rules
This paper introduced another concept in voting procedures known as anonymity proof, which means that it is both false-name-proof and satisfies participation (the voter has incentive to participate). The paper proved 6 lemmas about anonymity-proof voting procedures, including a reduction of the general multi-set of votes V to a problem of a pair of votes, which is important in make the problem easier to solve. Finally, the main contribution of the paper is an outline of the actual class of voting rules that is anonymity-proof and strategy-proof. This voting procedure is fairly randomized, which helpd it be strategy-proof. Next, the paper says that the probability of an alternative winning is at most 2/m. Finally, the paper proves that for the rules for 2 alternatives are also group-strategy-proof but for 3 or more alternatives, only a purely random voting procedure would work.
What surprised me about this paper and the results was how random the outcome was. This voting procedure, unlike the one from the other paper for Monday, does not converge to a particular alternative, even if one is heavily or completely favored. Instead, only if all votes rank a first does the probability of a becoming chosen become the max, 2/m. It is even more true for group strategy-proofness. Thus, if we were operating in real life this voting rule would never work, because people would never choose to participate (assuming that there were alternative forms of voting available to them). Thus, even though this is mostly meant for the internet, no one on the internet would actually participate because there are so many other kinds of votes that htey can participate in. THis is the major weakness of the paper.
Brett Harrison
Optimal False-Name-Proof Voting Rules with Costly Voting
By Wagman and Conitzer
This paper explores the susceptibility of voting rules to "false-names", i.e. voters voting more than once. A voting rule that is "false-name-proof" is one where it is never advantageous for a voter to vote multiple times. Several negative results exist showing that certain rules cannot be false-name-proof. This paper offers a positive result which provides an optimal false-name-proof voting rule for two alternatives when the mechanism incurs cost to each voter for each additional vote beyond their first. Interestingly, as the number of voters in this mechanism goes to infinity, this voting rule converges to the majority rule, which is what one would hope for.
It is disappointing that this is, as of row, a theoretical
result at best. For example, state elections will (probably) always be a
majority rule mechanism. So even if a cost were incurred on voters for voting
more than once, the cost may not make a difference since the mechanism is not
the one proposed by the paper. I personally feel that this problem cannot be
solved by mechanism design, but rather by security protocols which prevent
users from registering to vote more than once. I think that such security
measures are highly feasible and would show promise for having, for example, an
online political election. Nevertheless, I enjoyed the result of this paper, although
I think the
Nikhil Srivastava
Wagman et al propose and evaluate a set of optimal false-name-proof voting rules for various alternative numbers under the restriction that extra votes have some cost that voters have to weigh against their utility of voting multiple times. They reach some positive results for n=2 in the many-voter limit, but not for n=3 or higher. The case they consider is interesting, and certainly applicable for the increasing number of systems with anonymity or lack of authentication. I wonder if the "cost of voting" parameter can also be used to model real-world voter turnout - for the internet example, including the important cost of supplying a private email address to a website - for online and real elections.
Conitzer's next paper extends the results to anonymity-proof rules, namely false-name-proof rules that also guarantees it is never disadvantageous for an agent to cast their own true vote. Interestingly, all voting rules of this type are of a very specific form. I was surprised what a restriction this added, intuitively-simple assumption makes to the form of voting rules.
Alice Gao
Both papers try to characterize voting rules that are false-name-proof. When casting additional votes is costless, the results seem to be very negative. In this case, Conitzer reported that false-name-proof voting rules are unresponsive to agents' preferences. To me, this class of voting rules seem really unsatisfactory because they use a great deal of randomization. On the other hand, Wagmana nd Conitzer stated that some reasonable false-name-proof voting rules can be found when there is a cost associated with making additional votes. A major unsatisfactory part of their results is that the number of candidates is rather small (2 to 3).
In my opinion, false-name-proofness only becomes an issue for an anonymous environment such as the Internet. Therefore, theoretical results should pay sufficient attention to formulating reasonable assumptions which are specifically relevant to this environment. I think, incurring a small cost for additional votes sounds like a reasonble idea. However, the amount of cost needs to be justified using real world scenarios. The paper by Conitzer presented good motivation for this problem, but it offered a rather negative and disappointing result. Conitzer also presented several other perspectives that we can take on to attack this problem. For example, some possible ways are to try to verify agents' identities, or try to make it difficult for agents to create multiple identities. There are all interesting directions, and perhaps, a combination of several approaches might give us a better result rather than using any single one at a time. A possible project idea would be to explore the possible voting scenarios for a small number of candidates and voters, and try to find characteristics generalizable to more general settings.
Xiaolu Yu
Optimal False-Name-Proof Voting Rules with Costly Voting
The main contribution of this paper is that it characterizes the most responsive false-name-proof-with-costs voting rule. Motivated by previous works on unresponsive FNP-without-costs voting, the article proves that costs on additional votes could help the rule select the majority winner converge to 1 as the voting population grows large. One complication of mechanism design is that false-name- proofness is even much more restrictive than strategy-proofness; not even the majority rule is false-name-proof. Bearing in mind that a FNL-with-costs rule guarantees the cost of casting additional votes always outweighs the benefit to an agent, the author reaches a very positive result, though this convergence property does not apply to multi-agents case.
One interesting point raised by the article considering a single agent casting multiple votes is that the higher cost c of additional votes, the less often that FNP2 fails to choose the majority winner. I would like to have a more advanced idea how the cost varies with the number of voters n in order to guarantee the majority winner is always chosen. Is there an upper bound for c when n -> ∞? Another question in the group false-name-proof case is if the whole set of the proof holds for the implicit condition, i.e., each agent in the coalition casts some of the additional votes.
The bottom-line is that the cost for each additional vote is at least c, while a single agent can have different costs for her nth and (n+1)th votes. Does there exist a profile of c for each additional vote, as a function of the number or voters, which gives the fastest convergence to 1 given n? If so, I suspect that some voters may be able to find arbitrage opportunities or manipulate other's votes.
Anonymity-Proof Voting Rules
The importance of this paper is characterizing the anonymity-proof neutral voting rules, as either choosing an alternative at random, or drawing two alternatives at random and running the unanimity rule on this pair, or flipping a coin to decide between the two. Anonymity-proof voting rule is also false-name-proof and satisfies participation. It contrasts with strategy-proof (SP) in that SP chooses vote at random rather than alternative; SP chooses the one with more voters within the chosen pair, not necessarily the one ranked first in all voters, or in another word, no SP rule is clearly optimal. Interestingly, neither of the two groups of rules implies the other.
If no good anonymity-proof mechanisms turn out to exist for a given setting, how can we avoid multiple votings? I am not completely clear about the difference between a simple FNP introduced in the above paper and the anonymity-proof studied here. Verifying agents' identity seems not very practical to me, although I am not very well convinced why adding costs to additional votes cannot help stop the problem.
Subhash Arja
Both papers by V. Conitzer, et al. seek to explore ways to prevent voting rules to be manipulated by those voting multiple times. One paper explores just the possibility of preventing multiple votes by associated a cost to additional votes, which is referred to as False-name-proof voting rules. The other paper goes one step further and proves conditions that include anonymity, which satisfies voluntary participation. The applications for these theoretical areas are just starting to becoming popular. Therefore, the two papers start exploring areas that have not been applied to a wide range yet. For example, one example that was given in the paper was the choice of the 7 Wonders of the World. In addition, more recently, such surveys have been used to judge who had the most effect on voters after Presidential debates along with internet polling about who voters are likely to vote for.
In the paper where only false-name-proof voting rules are considered, the major limitation of the results is that as the number of voters goes up, the probability that the majority winner is chosen is low for the costless case. Also, the authors only consider 2 alternatives for a particular voter. While this assumption works in most cases since there are no more than 3 candidates, it is not helpful in cases of many possible choices. In reality, the cost to vote multiple times is relatively small since it is quite easy to use multiple email addresses or variations on a person's name. The other paper additionaly considers voluntary participation and the result is shown to not be group strategy-proof. However, this paper also looks at two alternatives for a particular voter and is very limited in this manner.
Some future areas of research to extend beyond these papers is to implement a scenario where it is impractical for a participant to vote more than once. Another way to minimize multiple votes is to make the first vote free but charge a fee for subsequent votes. This would provide a significant barrier to voting multiple times. However, this does not guarantee that no one will vote more than once to skew the election.
Victor Chan
Papers: Optimal False-Name-Proof Voting rules with Costly Voting and Anonymity-Proof Voting Rules
The two papers examined were Optimal False-Name-Proof Voting rules with Costly Voting and Anonymity-Proof Voting rules, by Wagman and Conitzer and Conizter respectively. Both paper are trying to find a way to avoid people casting multiple votes in an anonymous election. The first paper tries to create voting rules that are false-name-proof, and the approach it takes involves adding cost and the voting rule seems to be a variation of plurality voting with a randomized aspect. The second paper appears to deal with a voting scheme, where voters rank all their candidates of choice, and a randomized voting rule is then applied to that. The following is a closer examination of the two papers.
The main contribution of the first paper was showing optimal false-name-proof voting rules for the 2 alternative and 3 alternative cases. The paper introduces the notion of cost for additional votes in an anonymous election. The FNP2 voting rule is then introduced, and the purpose is to have the elected alternative be the same as the majority preference, while at the same time minimizing the effect multiple votes cast by the same voter. In the case of FNP2, it was shown that varying the cost c, in the rule could lead to a convergence, where the rule would produce the majority preference with high probability. Furthermore, the paper then extends this to a 3 candidate case, with similar results. The author's were unable to produce a result for the 4+ category, however they do provide a linear optimization problem that can be used to find the optimal false-name-proof voting rule.
An interesting insight of the paper was that increasing the number of voters did not seem to converge the probability of FNP2 and majority agreeing to 1. The figure that presented the probability of FNP2 agreeing with majority, as a function of cost, produced a convergence at 1. It would be interesting if the authors ran the simulation with probability of agreeing with majority, as a function of c, at different levels of n. It might be possible that with a higher n, the convergence is reached at a lower cost c.
What was unclear to me was what the meaning of c was. In the paper, the cost is shown as a decimal value, which acts to affect the value of the second choice in the min{1,x} functions of the rule. I'm not clear where this number can be generated, ie are all the c's referring to a single person's opportunity cost in FNP2, and the group's cost in GFNP2?
The second paper talks about anonymity proof voting rules, which is essentially a voting rule that is false-name-proof and satisfies participation. This paper deals with a voting system where the votes are orders of preferences for the alternatives and the associated utility gained by the voter. As a result, the majority of the proofs in this paper involve demonstrating that casting extra votes can increase the utility of the voter. The main contribution is the result of the combining the 6 lemma's presented and generating a anonymity-proof voting rule, where there is a kf probability of choosing a random candidate as the winner (with uniform distribution), or 1-Kf probability of selecting a winner based on a random pair and taking the winner of that pair.
I am not too clear on the responsiveness of this approach in finding the social choice of the voter. It seems like there is always a possibility that a random person can be selected, even if that candidate was not popular at all.
Both these papers address a problem that is more prevalent as online polling/voting begins to occur. The solution the authors have provided is to create new voting rules. However I believe that this approach might not always work, since having such a complex voting rule would be impossible to explain to the voters. This would be a problem, since most online voting is done and the usual bar graph/statistics is shown as verification of the winner. To the voter, if they know the winner is decide randomly, perhaps the voting rule will have less credibility than a voting rule that is susceptible to false names.
Sagar Mehta
The papers present results for the necessary conditions for false-name-proofness, where an agent can never benefit from using multiple identities, and anonymity-proofness, which is both false-name-proof and it never hurts an agent to cast a vote. For false-name-proofness, it is assumed that there is no cost in casting your first vote, but each additional vote comes at a cost to the user (in an online voting contest, for instance). For instance, we could require each vote to come from a separate email account and the cost of setting up such an account will prevent people from voting multiple times. However, I question the applicability of this result and wonder if there are more ways to incur a cost other than requiring a user to fill out a CAPTCHA for a new email account. While some email clients require you to do this, a person who really wants to vote multiple times without cost can create a program to generate email addresses at some domain name they themselves own and thus circumvent any "cost". Furthermore, if I already have 100 email addresses from a previous vote, the cost for me to vote multiple times is now lower – especially compared to someone who has only one email account. Are there other mechanisms that guarantee a cost on multiple votes (but not on the first vote) in an anonymous setting?
Ziyad Aljarboua
optimal false name proof voting rules with costly voting:
This paper discusses false-name-profanes in voting rules where voters cannot
benefit from casting multiple votes. This paper discusses the case where
additional votes cost voters. Cost could be financial as when manipulators pay
agents to cast their votes multiple times or otherwise. An example of cost is
the effort needed to register multiple email accounts to vote on the Internet.
This paper also introduces an optimal false-name-proof voting rule.
Intuitively, someone can see that a voting rule is false-name-proof if the cost
to cast additional votes out weights the benefit for an agent. The optimal
false-name-proof rule also satisfies the strategy proofness and the neutrality
requirements. In the costly setting, the probability that the optimal
false-name-proof voting rule chooses the alternative that the majority rules
would have chosen converges to one as the number of voters grows. Such optimal
false-name proof rule cannot be generalized for votes where there are more
than 4 alternatives.
In case of vote manipulation on collation level, the rule above is not a group
false-name-proof. Since the group size is unrestricted, there is no lower limit
for the cost of voting that will make such a rule group false-name-proof.
It is assumed that agents have strong preference between the alternatives. How
would the findings of this paper change if agents are indifferent about some of
the alternatives? Also, this paper assumes that agents have binary preference
for alternatives. In other words, agents either prefere an alternative and thus
assign it a utility one or do not prefere the alternative and thus assign it a
utility of zero. What if agents have varying level of preference for
alternatives. Moreover, this paper does not address a realistic scenario when
cost of additional votes out weights the benefit for a voter AFTER casting
several additional votes.
------------------------------------------------
Anonymity-proof voting rules:
This paper shows anonymity-proof neutral voting rule is one that chooses an
alternative informally at random with probability between zero and one and
chooses a pair of alternative uniformly at random with the complement of that
probability. In the latter case, if all voters prefer the same alternative, the
rule chooses that alternative. Otherwise, the rule chooses randomly between the
alternatives with equal probability. This definition of anonymity-proof voting
rule distinguishes it from strategy-proof rules.
Nick Wells
Anonymity-proof voting rules
Anonymity-proof (AP) voting is a set of voting rules that are both
False-Name-Proof (FNP) and also satisfies voluntary participation. The way I
understand it, the framework for AP voting is that if there is not a unanimous
decision then we move to one of two methods for choosing between all candidates
who received some vote. With probably k we choose randomly uniformly between all
the candidates. With probability 1-k, we choose two randomly uniformly, and take
the one of the two with the higher vote (if they’re equal flip a coin). The
paper proves that under this specification there is no incentive to vote
falsely or to vote multiple times. Additionally, the paper shows that these are
the only such rules to meet our AP requirements.
One thing that I seem to misunderstand about this paper: why don’t voters vote
multiple times for their favorite candidate under the provided framework?
Perhaps they are allowed to do that under this framework as long as they are
truthful. Or, perhaps there is no incentive on the margin to vote more than
once…but they why vote at all? I think further explanation of this would be
helpful.
Optimal False-Name-Proof Voting Rules with Costly Voting
As I understand it, False-Name-Proof (FNP) voting is a set of voting rules where
there is no incentive to vote extra where you do not show your true preferences.
Wagman and Conitzer show that if there is some marginal cost to vote that is
more than the benefit to an agent of voting, then there can be a FNP rule. They
also show that as the number of agents increases, the probability that the rule
follows what the majority rule would have been becomes 1. They distinguish this
by proving ti for the case where cost>0. The second part of their paper
outlines Group False-Name-Proofness (GFNP)which deals with potential collusion
in multiagent settings.
I am not sure I completely understand the GFNP very well. I would also be
interested in thinking about how this could play out from a learning in games
framework. Is there anything to be learned here (i.e. collusive behavior)? What
are ways that agents could learn to play their strategies as opposed to being
given them?
Rory Kulz
Optimal False-Name-Proof Voting Rules with Costly Voting
It is strange that this paper talks to a thought I had a couple of
weeks ago. I was thinking about polls on the Internet, when people can
vote over and over for a particular outcome (if, of course, they want
to put in all the effort). Assuming that supporters of a particular
outcome were no more likely to manipulate or to be able to manipulate,
would the expected outcome be much different than if the number of
votes were somehow perfectly restricted to one per voter? So I was
quite amazed to read this paper.
As for the paper itself, I would have liked to have seen a proof for
Theorem 4 or at least a little intuition; it's a neat result but sort
of seems to have been plucked from the Platonic realm, unlike Theorem
2, where their brief justification seems highly plausible.
The future work outlined by this paper is quite clear: finding
strongly optimal FNP and GFNP voting mechanisms for arbitrary numbers
of alternatives, extending convergence/divergence results to the
mechanisms, etc. It definitely feels like there should be some natural
expression for optimal FNP rules, at least, so I found it particularly
surprising that they couldn't find an FNP4.
It's also interesting to me the different ideas of "electioneering"
one can encounter. In the paper last Wednesday, we saw these ideas of
general constructive and destructive manipulation by changing votes.
Both Conitzer papers look at the problem of casting multiple votes.
Another type of rigging to consider is the following: suppose votes
are organized into disjoint subsets, each under the charge of some
election official. When can an election official (or coalition of
officials) manipulate an election by throwing out up to a certain
fraction of the votes they manage? In general, can we make the idea of
manipulation as broad as possible and still go through a meaningful
game-theoretic analysis and get results? Or is that too hard a
problem? What other specific notions of manipulability have been
looked at in the literature?
On a total side note, this paper had a couple of typos which might be
important to note: on page 2, between definitions 3 and 4, the
expected utility formula only applies when at least one of t^i_A,
t^i_B is
strictly >
x_B), not u_i(x_A, x_B, 0, 0) = P_j(x_A, x_B) + c, which is important
for understanding the voluntary participation condition. And on page
5, regarding the matrix representing P_A for GFNP2, it should not be
symmetric: the second column reads (.8125, .775, .725, .65, .5, 1)
when in reality it should read (.1875, .225, .275, .35, .5, 1) --
obviously as the number of votes for B increases, the probability of A
winning should not increase.
Anonymity-Proof Voting Rules
I read this paper after the other Conitzer paper, so it didn't have
quite as much "whiz bang" to me.
One thing I found suggestive is that the successes of the paper from
last Wednesday and the other Conitzer paper hinge on some
manifestation of cost to the agents for manipulation, whether
represented as utility or else computational complexity. This is I
think a very important idea and perhaps motivational for considering
all sorts of manipulation. Knowing things especially like Arrow's
Impossibility Theorem and Gibbard-Satterthwaite, it isn't much of a
surprise that with unbounded potential to lie and collude, the only
"secure" voting rules you can get (for some sense of "secure") involve
some very high degree of randomization and very low degree of
responsiveness to preference profiles. But again, this isn't really my
area of expertise, and maybe I'm just biased now having read the other
papers. As I mentioned in my other email, though, I'd like to see
similar results and ideas for other notions of manipulation,
especially those that translate into the real world. Certainly
false-name-proofness is a much more desirable property in a real-world
voting scheme than, say, being robust to constructive manipulation
under very unreasonable assumptions of complete information.
Avner May
Optimal False-Name-Proof Voting Rules with Costly Voting, by
Liad Wagman and Vincent Conitzer
Anonymity-Proof Voting Rules, Vincent Conitzer
I felt that these articles attacked an interesting question -- how do you deal with elections in which it is possible for a person to vote multiple times? This question seemed particularly reasonable and relevent given how widespread votes/polls over the internet are. Intuitively, this question seems ridiculous; how can any election not be effected by someone voting multiple times? Wouldn't this effectively have to mean that nobody's vote mattered at all? These papers I thought took this question to the next logical point; under what conditions would people only vote once (aka when would it not be in the person's best interest to vote multiple times). I thought that the way the problem was set up, assigning a utility cost of 0 for the first vote, and a cost of c for every subsequent vote, was very reasonable. I was not very satisfied by the results in the "Anonymity-Proof Voting Rules" paper. I thought that the voting mechanisms they determined would be anonymity-proof would in reality be ridiculous, and would make no sense to implement. In practice, I think that this question is one best answered by coming up with ways of preventing most people from voting multiple times (captchas, requiring e-mail addresses, and hopefully more sophisticated mechanisms), and not by coming up with crazy voting mechanisms, which only work if somewhat specific assumptions are made about the effects of voting on the voters' utility functions.
Hao-Yuh Su
1. Optimal False-Name-Proof Voting Rules with Costly Voting
2. Anonymity-Proof Voting Rules
These two papers both investigate voting rules for different
voting settings. The main difference is that it's assumed that there is a cost
of additional votes in the first paper while there is no cost in the second one.
The first paper characterizes an optimal false-name-proof
voting rules of two alternatives (FNP2), and further proves that, when voting
population grows, the probability that FNP2 chooses the majority winner
converges to 1. It also discusses about the case of more alternatives, like FNP3
and the case of group strategy-proofness, like GFNP2.
The second paper derives a theorem saying that any anonymity-proof
neutral rule alternatives either chooses an alternative at random or draws a
pair of alternatives at random. The anonymity-proof here means it satisfies
voluntary participation and is false-name-proof. Moreover, it discusses about
the change of the property when group strategy-proofness
is added as a requirement.
My first question is that, in the 1st paper, when it derives
FNP3, it assumes that each agent has a utility of 1 for their most preferred
alternative, and 0 for others. Under such scheme, how does strategic voting
work, if voters are indifferent with all those remaining less-preferred
alternatives?
My second question is that if it is practical to investigate
the case of a single manipulator that casting multiple votes? What is the case
if there are multiple single manipulators in a vote? And what is the case if
there are multiple group manipulators?
My last question is that is it practical to investigate the case of infinite voting population without the restriction of voluntary participation?
Travis May
These two papers provide interesting insights on an
additional problem faced by
voting mechanisms: the problem of
anonymity. Beyond the issues that have
been
discussed to date, anonymity
provides one other conceivable problem: multiple
votes per user. These papers propose methods of creating
false-name-proof
voting.
Unfortunately, I did not find the result very satisfying in "Anonymity-Proof
Voting Rules." Essentially,
the result requires unanimity in preference between
two alternatives, or else the voting
result is random. Since unanimity is
rare
in general, and it is particularly
rare when there are many agents involved,
this is a fairly grim result in
practice that essentially says that elections
are unfeasible.
The other paper, "Optimal False-Name-Proof Voting Rules
with Costly Voting," is
more satisfactory with its results. Its model consists of making the first
vote free for users, and then
adding a cost for subsequent votes. The
cost can
be created through requiring a
unique email address or any other mechanism
typically involved in voting - so
this is a reasonable condition to meet. The
paper goes on to argue that as the
number of agents becomes large, the benefit
of voting multiple times is
outweighed by the cost.
It seems that this would apply effectively to a wide range
of cases of online
voting, especially on fairly
trivial topics. Unfortunately, it may
also prove
unsatisfactory for votes that are
more consequential. In particular, I
would
give more weight to comparing the
costs and the benefits between voters. The
agents who intend to vote multiple
times most likely care more about the
election, and they receive higher
benefit for their choice winning. For
example, in restaurant ratings, a
restaurant owner cares more about his rating
than any other individual. He cares so much more, in fact, that a
minimal cost
(such as establishing a new email
account) would be vastly overshadowed by the
benefit of shifting his ratings. While, in theory, he could not do this if
there are enough voters, the fact
that the benefit outweighs the cost by such a
substantial margin makes it
unlikely that there will be enough voters to
outweigh this factor.