Re: [EM] Reference for poll where experts endorsed approval?
Jameson wrote: (Actually, I'm looking for all academic departments/institutes focused on voting systems/social choice. So far, I've found just one: In case it's relevant, the Computational Social Choice Seminar is a series of talks at the Institute for Logic, Language and Computation at the University of Amsterdam: http://staff.science.uva.nl/~ulle/seminar/ They have grad students there doing work in that area, and there's a dedicated course taught as well: http://staff.science.uva.nl/~ulle/teaching/comsoc/ -- Rob LeGrand r...@approvalvoting.org Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
Markus wrote: the runtime to calculate the strongest path from every candidate to every other candidate is O(C^3). However, the runtime to sort O(C^2) pairwise defeats is already O(C^4). So you cannot get a faster algorithm by sorting the pairwise defeats. Can't you sort O(C^2) items in O(C^2 log C) time if you use a O(n log n) algorithm such as heapsort? -- Rob LeGrand r...@approvalvoting.org Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Automated Approval methods (was Single Contest)
Kevin wrote: Yes, but if it were strategy-free somehow, I think it would be worth it. Real life isn't monotone. I don't imagine that all the prettier Yee diagrams would really look like that if voters were using information and strategy! I may be missing something, but I don't see how you can have a nonmonotonic method that is strategy-free. For any example of nonmonotonicity, you should be able to find a single voter that triggers it--say, if that focal voter votes ABXC, then X wins, but if they vote AXBC, then X loses. Whoever wins when X loses, manipulability pops up: Case 1: A wins. Then imagine that the focal voter sincerely thinks ABXC. Insincerely voting AXBC moves the winner from X to A, which is a successful manipulation. Case 2: B wins. Then imagine that the focal voter sincerely thinks ABXC. Insincerely voting AXBC moves the winner from X to B, which is a successful manipulation. Case 3: C wins. Then imagine that the focal voter sincerely thinks AXBC. Insincerely voting ABXC moves the winner from C to X, which is a successful manipulation. This proof may be either flawed or needlessly complex, but it's what came to mind. -- Rob LeGrand r...@approvalvoting.org Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Remember Toby
Kathy wrote: Let all the voters vote for one or two candidates. Considering this Approval-like method on its own, without any proxy aspects, I see problems. Capping the number of candidates that each voter is allowed to approve at 2 destroys some of Approval's desirable properties. First, no longer is your best strategic vote necessarily even weakly sincere; in other words, it will often be to your advantage to approve B and not A even when you prefer A to B. Second, even when all voters have strict preferences over all candidates, there may be an equilibrium that doesn't elect a sincere Condorcet winner. As an overly dramatic example, if the sincere preferences are 49:ABCDEF 3:DCFEBA 48:FECDBA One equilibrium, I claim, would be 49:A,B 3:D 48:F,D which elects D even though 97 of the 100 voters prefer C to D. Just going by intermediate results, as from polls, it might be very difficult for C to emerge as a contender. -- Rob LeGrand r...@approvalvoting.org Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Help naming a new method
Andy wrote: I have a new voting method and I think I need some help naming it. Let me say, first of all, that I admit it may be too complicated for use by the general public. It's a score aggregating method, like Score Voting. Each voter scores each candidate on a scale of 0-100. Each candidate's votes are aggregated independently, with their societal score given by finding the largest number, x, such that x percent of the voters gave that candidate a grade of x or higher. So a candidate where 71% of the people gave a grade of 71 or higher (but the same can't be said of 71+epsilon) will get a final score of 71. It shares a strategy-resistance property with the median that any voter whose score was above the societal score, if he were allowed to change his vote, could do nothing to raise the societal score. (Also, a voter whose score was below the societal score could do nothing to lower the societal score.) This means that if you're only grading one candidate (e.g. choosing an approval rating for the sitting president), then there is a strong incentive for everyone to submit an honest vote. It can be generalized to find the largest number, x, such that F(x) percent of the voters gave the candidate a grade of x or higher, for a non-decreasing function F. F(x)=50, for example, is basically equivalent to find the median. But anything more complicated than F(x)=x is probably hopeless for explaining to people. And the diagonal function F(x)=x has some nice properties. For example, one voter can never unilaterally move the output by more than 100/N, where N is the number of voters. I thought of this method about three years ago. I've been sitting on it since then, proving things for my doctoral thesis, which I finished last fall. I did present this method at the Public Choice Society meeting about a year ago. And I told Drs. Balinski and Laraki about it some time ago. They make mention of it in their recently published book Majority Judgment. I'd like to publish some things in a journal, but I'm thinking I may need a better name for the method. So far, I've called it the linear median and the diagonal median. I've considered the consensus median or the consensus score, but that may be misleading, associating it with consensus societies. Hi Andy, Please see chapter 3 of my dissertation: http://www.cse.wustl.edu/~legrand/dissertation.pdf It motivates and describes a rating system I call AAR DSV (Average- Approval-Ratings Declared-Strategy Voting) that is equivalent to the system applied to each candidate in your linear median method. The motivation is based on how rational voters would vote to try to pull the outcome of a Average-based rating system as close to their ideal point as possible. The chapter also outlines a continuous range of rating systems that includes both the standard AAR DSV and Median systems (including the generalized ones you mention), interpolating between them using a two- dimensional parameterization, and uses data from Metacritic.com to find the best rating system in that range. I prove that, if all voters are only interested in moving the outcome as close to their ideal point as possible, all of these systems are nonmanipulable. This nonmanipulability of course disappears when these systems are applied to each candidate in a single-winner election. My recent research has dealt with generalizing these rating systems to higher-dimensional voting/ outcome spaces of various shapes; I haven't considered applying them to electing a single winner from a discrete set of candidates in a while. I presented a paper on AAR DSV called Approval-rating systems that never reward insincerity at the 2nd International Workshop on Computational Social Choice (COMSOC-2008): http://www.csc.liv.ac.uk/~pwg/COMSOC-2008/ I'd like to see a copy of your doctoral thesis as well. -- Rob LeGrand r...@approvalvoting.org Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] IRV ballot pile count (proof of closed form)
Abd wrote: 34 A 33 BC 33 CB. The Condorcet winner is A, because in the two pairwise elections involving A, A wins AB, 34:33 AC, 34:33. Assuming that by the above votes you mean 34:AB=C 33:BCA 33:CBA, A is not the Condorcet winner and is in fact the Condorcet loser, losing both A:B and A:C by 34:66. Perhaps you had in mind an example like 35:A 32:BC 33:C, by which I mean 35:AB=C 32:BCA 33:CA=B. In this example, C is the Condorcet winner even though C does not have a majority over B. I can see how this example could be seen as an embarrassment to the Condorcet criterion, in that a good method might not choose C as the winner. -- Rob LeGrand r...@approvalvoting.org Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] A computationally feasible method
Kristofer Munsterhjelm wrote: On the other hand, approximating may make strategy more difficult. I think Rob LeGrand wrote something about how approximations to minimax Approval obscured the strategy that would otherwise work. Yes, you're thinking of http://www.cse.wustl.edu/~legrand/legrand06fsm.pdf in which our polynomial-time 3-approximation to fixed-size minimax is shown to be nonmanipulable. Exact FSM on the other hand is both manipulable and NP-hard to compute. I'm now at COMSOC '08 in Liverpool: http://www.csc.liv.ac.uk/~pwg/COMSOC-2008/ Many interesting talks. I'm told the papers will be available on the website sometime after the conference is over. -- Rob LeGrand, psephologist [EMAIL PROTECTED] Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Matrix voting and cloneproof MMP questions
Kristofer Munsterhjelm wrote: You use movie site data for your AAR-DSV examples. Does AAR-DSV manipulability mean that a movie site that uses it would face difficulty telling users which movie is the most popular or highest rated? The manipulability proofs wouldn't harm them as strongly (since very few users rate all of the movies), but they would in principle remain, unless I'm missing something... It all depends on what we assume the voters would be trying to do. If each voter is trying to move the overall rating of each movie as close as possible to his/her ideal rating of that movie, without any regard to how the other movies are rated, then AAR DSV is completely nonmanipulable. On the other hand, if a voter is trying to affect which movie ends up with the highest rating, voting insincerely may sometimes give an advantage. -- Rob LeGrand, psephologist [EMAIL PROTECTED] Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Matrix voting and cloneproof MMP questions
Kristofer Munsterhjelm wrote: (On a related note, has anyone tried to use Range with LeGrand's Equilibrium Average instead of plain average?) I don't recommend using Equilibrium Average (which I usually call AAR DSV, for Average-Approval-Rating DSV) to elect winner(s) from a finite number of candidates. AAR DSV is nonmanipulable when selecting a single outcome from a one-dimensional range, just as median (if implemented carefully) is, but it is manipulable when used as a scoring function in a way similar to how Balinski and Laraki proposed using median: http://rangevoting.org/MedianVrange.html For more on AAR DSV, please see chapter 3 of my now-completed dissertation: http://www.cse.wustl.edu/~legrand/dissertation.pdf -- Rob LeGrand, psephologist [EMAIL PROTECTED] Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Landau and Schwartz set
I know that the Landau set is a subset of the Smith set, and I know
that Schwartz set is a subset of the Smith set, but is Landau set the
subset of the Schwartz set, or is the Schwartz set the subset of the
Landau set?
Both are possible, so neither is generally true. Given the votes
4:ABC
1:BCA
3:CAB
the Landau set is {A, B, C} and the Schwartz set is {A}. Given the votes
3:ABCD
3:BCDA
2:CDAB
1:DABC
the Landau set is {A, B, C} and the Schwartz set is {A, B, C, D}.
--
Rob LeGrand, psephologist
[EMAIL PROTECTED]
Citizens for Approval Voting
http://www.approvalvoting.org/
Looking for a deal? Find great prices on flights and hotels with Yahoo!
FareChase.
http://farechase.yahoo.com/
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Landau and Schwartz set
Kevin Venzke wrote: The defeats are AB, BC, A=C. What reasoning do you use to find that B and C are in the Landau set? I gather I don't have a complete understanding of what Landau refers to, but I'm very surprised if the definition is such that a Landau winner can fail to be a Schwartz winner. This makes Landau seem less worthwhile to me, since Schwartz is more intuitive. I'm using what I believe is Markus Schulze's definition of Landau winners: Candidate A is a Landau winner iff for every other candidate B at least one of the following two statements is correct: (1) A = B. (2) There is a candidate C such that A = C = B. where = means beats or ties pairwise. It's the same thing as Smith except that the beatpaths can be of length at most two. You could easily define a Schwartz-Landau set that may give you want you were expecting by changing beats or ties pairwise in the above definition to beats pairwise. Such a set would always be a subset of the Landau set and of the Schwartz set. -- Rob LeGrand, psephologist [EMAIL PROTECTED] Citizens for Approval Voting http://www.approvalvoting.org/ Check out the hottest 2008 models today at Yahoo! Autos. http://autos.yahoo.com/new_cars.html Election-Methods mailing list - see http://electorama.com/em for list info
