4 von 4 Kunden fanden die folgende Rezension hilfreich
Short and to the point
11. Dezember 2014
Von
Athan
- Veröffentlicht auf Amazon.com
Format: Gebundene Ausgabe
Let's say all the boys in class decide to rank their favorite 20 cars.
So every boy writes down on a piece of paper his own ranking of those 20 cars and then we go about listing how we would like to work it all out.
0. Suppose we want our ranking to be transitive. So if I know that in the final ranking the Mercedes is above the Honda and the Honda is above the Fiat, then the Mercedes must be above the Fiat.
1. Suppose that no matter how many boys there are in class, no matter how many of the (more than 20 factorial, to accommodate draws, missing cars etc.) permutations are submitted, you want to want to come up with a voting scheme that will deliver one, definitive, ranking. (a property of the scheme known us "Unrestricted Domain")
2. Suppose that in this definitive ranking the Ferrari beats the Mercedes. And then suppose we take the Chevrolet out of the list. If then we repeat the vote without the Chevrolet but with all the other 19 cars, the Ferrari had better still beat the Mercedes, or else our voting scheme is unsatisfactory. (a property known as "Independence of Irrelevant Alternatives")
3. Suppose that in every single boy's ranking the Daihatsu gets beaten by the Lamborghini. It had better also get beaten in the final ranking. (a property known as the "Pareto Principle")
4. Suppose you don't want there to be a boy who always prevails over the rest if he likes one car more than another (this is the "Non-Dictatorship Principle")
The Arrow Impossibility Theorem says you're out of luck. You can't get all of the above.
I guess everybody who's been to elementary school already knows this, but Kenneth J Arrow gave mathematical proof. The proof's rather easy to follow and I close this review with my version of it. The book is dedicated to an exposition of the Theorem and its ramifications.
The result is not a big surprise, obviously, but it is the cornerstone of a beautiful theory. Armed with this result, other economists and philosophers have over the years looked at a number of "voting rules" such as the Anglo-Saxon "first past the post," the French runoff system, the plurality voting rule, ranking of candidates etc. and worked out when they will yield satisfactory results.
This monograph of a book is written by some of the most prominent such theoreticians, including Amartya Sen, Eric Maskin and Partha Dasgupta, with short contributions from Joseph Stiglitz and Kenneth Arrow himself, all beautiful in their own way, though I must say I was confused by the introduction by Prasanta Pattanaik.
Also, there is a full paper here that derives some very significant results concerning when "rank-order" voting "works well" (i.e. satisfies conditions such as the ones I describe above), when "plurality rule" voting "works well," when majority rule is decisive (answer: when there's no "Concordet triplet" such that x>y>z for fewer than half the voters, y>z>x for fewer than half the voters and z>x>y for a third set of fewer than half the voters) and finally all this work yields the extremely powerful result that if, given a set of preferences, you can come up with some rule that "works well," then so will majority rule (and that therefore we have not wasted 200 years of democracy using this rule)
That said, mathematical symbols are used when words would have fully sufficed. The complex math symbols are never, ever "pushed" in the proof. A Lebesgue integral is defined for no reason. (No use is ever made of measure theory anywhere past this definition) The author never says anything along the lines of "we recognize that this set is a group and apply Theorem X from group theory." It's 100% math for the sake of math, and I found that annoying, especially since the book is riddled with errata.
For example, on p. 112 there are extra brackets around the main expression that don't belong; on p. 119 (and again on p. 120 and again on p.p. 143, 144) xRy and xRz and yRxRz and zRxRy are written with the second x's and y's and z's as subscripts when the notation for "x dominates y under R" has been defined as xRy; on p. 123 we are assured that for some t<t expression (5) must hold, when clearly one of the two is the Greek tau etc. etc. Equally, important steps are left to the reader. I struggled with understanding why at the top of p. 121 Limited Favoritism necessarily meant there could only be one alternative that is top-ranked. I've a couple math degrees and I did not enjoy these proofs, I liked Amartya Sen's style more. That is the bottom line.
So here's me cribbing Amartya Sen and having a go at proving the main result, always in the context of boys ranking cars:
Lemma 1: The stickler. Suppose there is a stickler, who is allowed to impose his will on all the other boys on just one pair of cars. Suppose little Johnny can get away with making everybody rank the Ford Pinto higher than the Aston Martin. It can be shown that this automatically makes him the dictator.
Suppose everybody (Johnny included) likes the Mustang more than the Pinto. And suppose everybody (Johnny included) likes the Aston Martin more than the Jaguar. Then, because Johnny likes the Pinto more than the Aston and because just for this one pair Johnny can impose his will on the entire class, the Mustang must (like for Johnny, to whom transitivity also applies) rank higher than the Jaguar in everybody's ranking. Not only that, but we said it should make no difference if we take a car or two out. So then we can take both the Pinto and the Aston out of the reckoning and everybody should (like Johnny) still like the Mustang more than the Jaguar by the independence of irrelevant alternatives. And since everybody ranks the Mustang higher than the Jaguar, then by the Pareto principle the Mustang will rank higher than the Jaguar in the final ranking. And it's all because of Johnny the stickler, who for all we know could be the only boy who likes the Mustang above the Pinto and the Pinto above the Aston Martin and the Aston above the Jaguar. In math speak, if there's an individual who is locally decisive (i.e. over one pair), he is globally decisive.
Lemma 2: Contraction of decisive sets.
Suppose the football team runs the dictatorship. (i.e. it is decisive)
Suppose the offense team all like the Ferrari more than the Lamborghini and the offense team also all like the Ferrari more than the Maserati, but the offense team don't have any preference between the Maserati and the Lamborghini.
Suppose the defence team all like the Ferrari more than the Lamborgini and the defense team also like the Maserati more than the Lamborghini, but the defense team don't have a preference between the Ferrari and the Maserati.
Clearly, the whole football team likes the Ferrari more than the Lamborghini, so we all know which way they two rank.
Now suppose that in some (non-football-playing) boys' lists the Maserati appears above the Ferrari or equal to the Ferrari. Because the football team as a whole ranks the Ferrari above the Lamborghini and the football team as a whole are the dictators, it means that in these boys' lists the Maserati will have to appear above the Lamborghini too, because the football team ranks the Ferrari above the Lamborghini, so this means there are boys who had to obey the defense team's orders with respect to ranking the Maserati and the Lamborghini. They could not have been obeying the offense team as the offense team could not care. So if there are boys who list the Maserati above the Ferrari and if the football team are dictators, then it was the defense team were decisive between the Maserati and the Lamborghini, which makes the globally decisive (by Lemma 1) while the offense team had nothing to do with this and don't belong to the dictatorship.
To avoid this possibility, say there isn't a single boy outside the football team who ranks the Maserati above the Ferrari. But we know the offense team rank it below. So the Maserati ranks below the Ferrari, and that could not have been the work of the defense team, since they don't care. And thus the offense team are decisive between the Ferrari and the Maserati, so by Lemma 1 they are globally decisive (they are the dictators) and the defense team is not.
So we have shown that, unless they coincide in every single ranking, dictatorships are divisible and we have established the second lemma, "contraction of decisive sets."
Armed with these proofs, we're home and dry. By the Pareto Principle, if there's a pair of cars where everybody agrees what the ranking should be, that had better be the final ranking.
In other words, the whole class put together gets to be "the stickler" on any car pair where there is unanimity. By lemma 1, this means the whole class is decisive. The whole class is the dictatorship. By lemma 2, a subset of the class must be the dictatorship. Keep repeating until you're left with one dictator. QED
5 von 6 Kunden fanden die folgende Rezension hilfreich
Misses the Boat on Arrow’s Theorem
9. März 2015
Von
Dick_Burkhart
- Veröffentlicht auf Amazon.com
Format: Gebundene Ausgabe
This book consists of expository lectures by Sen and Maskin on Arrow’s work, commentary by Arrow himself, and supplementary materials especially an introduction by Pattanaik and mathematical papers by Sen and Maskin. However the result would have been far more successful if the organizers had invited a talk by someone like Donald Saari who could have given a far deeper view of the famous Arrow theorem.
At one point Sen even talks about the need to broaden “social choice” theory to include richer sources of information (pp. 76 – 80) – more than just the preferential or rank orderings assumed by the Arrow theorem and used in common voting methods like the Borda Count and Instant Runoff Voting. While a laudable goal, my feeling is that this needs a much different approach, one involving nonlinear agents or dynamics. Yet incredibly Sen fails to note that Arrow’s impossibility result is, in fact, a direct consequence of an assumption that drastically restricts the use of information that is already presents in the voters’ rankings of candidates. This is, of course, the axiom of “Independence of Irrelevant Alternatives”, which I think might be better called the assumption of “Forbidden Intensity” (FI), as it forbids the voting algorithm from using the intensity of a voter’s ranking of one candidate over another.
To illustrate this concept, suppose I am a voter in an election with 4 candidates {a,b,x,y} and I feel strongly that candidate x is by far the best and that candidate y is by far the worst, while I am not enthusiastic about either candidate a or b but would pick a over b if forced to. Thus I would rank these 4 candidates x > a > b > y. However FI says that the electoral ranking, or “social ordering”, of these 4 candidates, as produced by the voting algorithm under consideration, should ignore this difference. That is, the electoral ranking of x and y should not be affected by how I rank a or b – that such rankings are “irrelevant” even though the way I rank a and b in between x and y is the way I express the strong intensity of my opinion, or the weakness of this intensity when I rank no candidates between a and b.
In other words, FI forces the voting algorithm to ignore very important information provided by the voters. The intensity of a ranking of x over y is easily quantified, using a variation on Saari’s concept (pp. 189 - 191," Decisions and Elections", 2001), by defining Iv(x,y) = k if x > a1>… ak-1>y when voter v ranks k-1 candidates (a1,…,ak-1) between x and y. In addition set Iv(x,x) = 0 and Iv(x,y)= -Iv(y,x) if x < y. Then Saari shows that the Borda Count satisfies all the Arrow axioms if FI is modified to permit the voting algorithm to use this intensity function (which implies voter transitivity). This modification Saari calls “Intensity of Binary Independence” but I’d prefer to call it the assumption of “Permitted Intensity” (PI).
In fact, Arrow’s theorem more properly applies to pairwise comparisons (showing the severe limitations of that approach to voting, in line with the Condorcet paradox) rather than rank ordering, where Saari’s theorem hints at the fundamental role of the Borda Count. Arrow’s theorem is also a demonstration of the limitations of the axiomatic approach to voting algorithms, in that some properties which may seem natural from one point of view may have hidden consequences which require a much broader perspective. That perspective should focus more on the practical aspects of voting than on theoretically undesirable properties which may rarely come into play or which can be anticipated and guarded against by appropriate procedures.
For example, as an activist mathematician I often recommend that the Borda Count be used in the form “rank your top 3 choices” (or sometimes 4 or 5), to reduce the cognitive workload of the voter, the vote counting work load, and tactical voting. This seems to be by far the best method in most informal or low key voting situations, such as when a group wants to rank action plans in a way that builds consensus. Combining it with Peter Emerson’s “modified Borda Count” is a good way to discourage single choice voting. In more partisan or large scale situations, a danger is that a faction may run “clone” candidates or superfluous alternatives to subvert the ranking of true alternatives. In this case, a primary election may eliminate the clones, or in some cases proportional representation may be used to identify different factions and their top candidates (I’ve developed my own clustering algorithm for this purpose).
Instead of this kind of practical work, Maskin tries to rescue FI by identifying restrictions to the rankings which will satisfy FI. He cites Black’s “single peakedness” criterion, which guarantees a Condorcet winner. Then he defines simple, but impossible to enforce, criteria for Borda and Plurality voting to satisfy FI. However I see FI as the problem, not the solution, because of the way it refuses to admit important information. And how would you restrict how people rank candidates in any kind of legal, let alone moral, way?
There are also some issues with the mathematics. First of all, Sen’s definition of decisiveness on p. 35 is not clear. His wording says that for a particular voting algorithm a set of voters G is decisive for a pair of candidates {x,y} if whenever all voters in G rank x > y, then x > y in the electoral ranking. The problem here is that {x,y} uses set notation (is not ordered) but the notation x > y specifies an ordering. So should the set {x,y} be replaced by the ordered pair (x,y)?
The answer is “No” because then the proof of the Spread of Decisiveness Lemma fails. That is, the way to prove an ordered pair version of the Lemma, following Sen’s sketch, would be to assume that (a,b) is an arbitrary ordered pair such that all voters in G rank a > b. Then show that the electoral ranking must specify a > b, given that G is decisive for some ordered pair (x,y).
However consider the case (a,b) = (y,x). Then the decisiveness of (x,y) tells us nothing about (a,b) since the hypothesis fails; that is, x > y for all voters in G whereas we need y > x. If {a,b,x,y} constitutes 3 voters with a = y, we encounter a similar problem. We’d want to show a > b given x > y by decisiveness, but the method of proof gives us instead b > x > y=a.
Hence the correct definition of decisiveness is that G is decisive for {x,y} as a set if it decisive for both orderings. That is, if x > y for all voters in G, then x > y electorally, or if y > x or all voters in G, then y > x electorally. This concept is easily generalized to any set X of size 2 or more by saying that G is decisive for X as a set if G is decisive for each ordering of X.
Then Sen’s proof works if {a,b} does not intersect {x,y}. For all voters ranking a > b, which includes all voters in G, we can use FI to transform any ranking of {a,b,x,y} into the canonical ranking a > x > y > b first by switching the ranking of x, then the ranking of y, without affecting the ranking a > b. For all remaining voters we can switch x until a > x and y until y > b, getting y > b > a > x. In both cases a > x and y > b for all voters, so a > x > y > b electorally using Pareto for a > x and y > b and decisiveness for x > y. Hence a > b electorally by transitivity. Likewise we get b > a electorally if b > a for all voters in G using the decisiveness of (y,x) for G, transforming all b > a orderings to the canonical ordering b > y > x > a and the remaining orderings to x > a > b > y.
However, in the case of one of a or b = x or y, separate proof is needed. Take a = x for example and first consider the case that a > b, including all voters in G. Then we can switch a voter’s ranking of a=x > b > y or of y > a=x > b into the canonical ranking a=x > y > b by FI. For the remaining voters we could switch a ranking of b > a=x > y or of b > y > a=x into the canonical ranking y > b > a=x. Thus we get y > b for all voters, so that y > electorally by Pareto, which when combined with x > y electorally by decisiveness yields a > b electorally by the electoral transitivity of a=x > y > b. If instead we want to prove b > a electorally, we’d end of up using the decisiveness of y > x by reduction to the canonical ordering b > y > a=x.
This lemma demonstrates the incredible power of the assumption of Forbidden Intensity, in fact how it is way too powerful for its own good. It’s too bad that these economists have not been talking to mathematicians like Saari, who have moved far ahead in their analysis.