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: > Well, there aren't technically any (serious) strategy-free methods. I'm > referring more to a method not having obvious strategic incentives, or > at least not having a lot of a single type of strategic incentive, so > that everybody knows that "in method X you should use Y strategy all > the time" etc. Yes, I can't claim that nonmonotonicity always leads to easily generalizable manipulability. I guess a while back I got pretty discouraged by the weak nonmanipulability guarantees that conventional voting systems can make, which led me to take my DSV research in slightly different directions. I just decided to throw that little "proof" out there since I couldn't remember seeing anything like it before. I don't claim it to be especially graceful or useful, and I'll bet someone's done it better anyway. -- 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 A>B>X>C, then X wins, but if they vote A>X>B>C, then X loses. Whoever wins when X loses, manipulability pops up: Case 1: A wins. Then imagine that the focal voter sincerely thinks A>B>X>C. Insincerely voting A>X>B>C moves the winner from X to A, which is a successful manipulation. Case 2: B wins. Then imagine that the focal voter sincerely thinks A>B>X>C. Insincerely voting A>X>B>C moves the winner from X to B, which is a successful manipulation. Case 3: C wins. Then imagine that the focal voter sincerely thinks A>X>B>C. Insincerely voting A>B>X>C 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:A>B>C>D>E>F 3:D>C>F>E>B>A 48:F>E>C>D>B>A 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] "good method" ? , was "IRV ballot pile count (proof of closed form)"
Chris wrote: > > 35:A>B=C > > 32:B>C>A > > 33:C>A=B. > > What "good method" do you have in mind that might not elect > C? I didn't have a method in mind, and I agree that C is the best winner in this example for the reasons you gave. My only point is that the Condorcet criterion should perhaps require majorities if we are to insist upon it. Here is a better example of my point: 41:A>B=C>D 29:B>D>C>A 30:C>B>A>D C is the Condorcet winner even without a true majority over B. I don't see that it would embarrass a method to choose B as the winner of this election. Do you? -- 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] IRV ballot pile count (proof of closed form)
Abd wrote: > 34 A > 33 B>C > 33 C>B. > > The Condorcet winner is A, because in the two pairwise > elections involving A, A wins > > A>B, 34:33 > A>C, 34:33. Assuming that by the above votes you mean 34:A>B=C 33:B>C>A 33:C>B>A, 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:B>C 33:C, by which I mean 35:A>B=C 32:B>C>A 33:C>A=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: [EM] Condorcet question
> Is it always the case that when there is a tie, each member > of the tie defeats everyone else except one? Consider the ranked votes A>B>C>D>E B>C>D>E>A C>D>E>A>B D>E>A>B>C E>A>B>C>D Each candidate has two pairwise victories and two pairwise defeats. -- 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] Nanson / Baldwin method winners are in the smith set
Ian wrote: > Does anyone have a reference for the claim that the Nanson and Baldwin > methods of iterative borda count elimination are in the smith set? I > have seen it claimed in a couple places (i.e. wikipedia), but don't > know where the result came from. Here's how I explained it back in 2003: http://groups.yahoo.com/group/election-methods-list/message/12049 but if you're asking for a published source, I don't know of one. -- Rob LeGrand, psephologist [EMAIL PROTECTED] Citizens for Approval Voting http://www.approvalvoting.org/ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Spearman-unbiased apportionment
Steve Eppley wrote: > If my recollection is correct, there is a related argument in Judith > Best's book "In Defense Of The Electoral College." One of her > conclusions was that, even though small states are represented more > than proportionally in the Electoral College, contrary to appearances > large states are not underrepresented in it. A similar argument: http://www.cs.unc.edu/~livingst/Banzhaf/ It argues that a voter in California is more than 3 times as likely as a voter in Montana to change the outcome of a presidential election. -- Rob LeGrand, psephologist [EMAIL PROTECTED] Citizens for Approval Voting http://www.approvalvoting.org/ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [Election-Methods] Landau and Schwartz set
Kevin Venzke wrote: > --- Rob LeGrand <[EMAIL PROTECTED]> a écrit : > > 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 what > > 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. > > Ok. In either case, isn't it conceivable that the set is totally empty? Yeah, I was a bit hasty as I wrote that. The above makes rough intuitive sense, but carefully defining a "Schwartz-Landau" set may be a bit trickier than I assumed because of the precise way Schwartz must be defined so as to avoid the empty set. I'll investigate defining a Schwartz-Landau set when I can make the time, unless Markus or someone else has already thought about it. -- Rob LeGrand, psephologist [EMAIL PROTECTED] Citizens for Approval Voting http://www.approvalvoting.org/ Boardwalk for $500? In 2007? Ha! Play Monopoly Here and Now (it's updated for today's economy) at Yahoo! Games. http://get.games.yahoo.com/proddesc?gamekey=monopolyherenow 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 A>B, B>C, 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
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:A>B>C 1:B>C>A 3:C>A>B the Landau set is {A, B, C} and the Schwartz set is {A}. Given the votes 3:A>B>C>D 3:B>C>D>A 2:C>D>A>B 1:D>A>B>C 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