{"id":1202,"date":"2010-09-06T04:53:00","date_gmt":"2010-09-06T08:53:00","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1202"},"modified":"2010-09-06T04:53:00","modified_gmt":"2010-09-06T08:53:00","slug":"reading-numbers-rule-by-szpiro","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/09\/06\/reading-numbers-rule-by-szpiro\/","title":{"rendered":"Reading “Numbers Rule” by Szpiro"},"content":{"rendered":"

\"\"It is Labor Day weekend here in the US, so, in addition to the mandatory grilling and bicycling with Alexander, I have some time to laze about on the porch reading books (and drinking beer, which is also legally required in my jurisdiction).\u00a0 I have been reading Numbers Rule<\/em><\/a> by George Szpiro.\u00a0 This is a fascinating book on the history of thought about voting rules, starting back with Plato and continuing with Pliny the Younger, Llull, Cusanus, Borda, Condorcet, Laplace, Dodgson, and ending with the impossibility results of\u00a0 Arrow, Gibbard, and Satterthwaite.\u00a0 Interleaved are a few chapters on the problem of allocating seats in a parliament.<\/p>\n

I have done work in this area<\/a> (and Bartholdi, Tovey and Trick even make an appearance on page 115) but I don’t consider myself a specialist.\u00a0 Even specialists, however, might learn something on the history of the field from this book.\u00a0 The Llull-Casanus period (roughly 1200 A.D. to 1450 A.D.) in particular was new to me.\u00a0 This pre-Renaissance period was not one that generally generated a lot of deep insights into non-religious issues (in the Western world), but voting was one area that was of great interest to the ecclesiasticals, most notably in the election of the Pope, but also in electing people for lesser positions such as abbot.<\/p>\n

Voting seems to be an easy problem:\u00a0 we do it all the time.\u00a0 “How many people want A?\u00a0 How many people want B?\u00a0 OK, A wins” is certainly used in our three-person household.\u00a0 But voting is much harder when there are more than two possible outcomes.\u00a0 With A, B, and C as possibilities, having each elector vote for one and then taking the one with the most votes (plurality elections) leads to all sorts of bad outcomes.\u00a0 For instance, it is arguable that having Nader in the 2000 election with Bush and Gore (in the U.S. Presidential election) led to Bush winning while without Nader, Gore would have won.\u00a0 This is an example of violation of “Independence of Irrelevant Alternatives”:\u00a0 shouldn’t an election result be consistent whether or not a third (or fourth or fifth) candidate enters?\u00a0 In other words, if A beats B when only the two run, if C also runs then it should be that either C wins or A continues to win.\u00a0 Stands to reason! But plurality voting is terrible with respect to this condition, so “splitting the opposition” is a standard way to strategically manipulate such an election.<\/p>\n

The book makes it clear that issues of fairness in elections with more than two candidates go back to Greek times.\u00a0 There have been two main approaches in getting beyond plurality voting.\u00a0\u00a0 In both cases, electors rank all of the candidates (unlike in plurality where only the most-preferred candidate is listed).\u00a0 In the first method, candidates get points based on their placements.\u00a0 For a 4 candidate election, every “first place” vote is worth 4, every second place vote is 3, and so on.\u00a0 The candidate with the most votes wins.\u00a0 In the second approach, the pairwise matchups are analyzed and the person who would win the most pairwise elections is deemed the overall winner.\u00a0 Ideally, there is a candidate who would win against any other candidate in a pairwise election, and that person is a natural choice for winner (and a choice that plurality is not guaranteed to choose).\u00a0 Such a candidate is known as a Condorcet winner.<\/p>\n

I had always credited the foundation of these two approaches to Borda and Condorcet respectively.\u00a0 Both lived in the 1700s in France, Borda being a mathematician and military officer, Condorcet being a “pure” scientist and government official.\u00a0 But the real credit for these approaches should really go to Casanus and Llull four hundred years earlier.\u00a0 Numbers Rule<\/em> gives a very good description of their work and all that was new to me.<\/p>\n

One aspect of Numbers Rule<\/em> that I really like is the brief biographical summary at the end of every chapter. Every chapter is based on one (or a few) key figures.\u00a0 Rather than try to weave the biography of that person in with the description of their findings in voting, only the key features are in the main text, while the biographical summary provides a deft summary of the rest of their lives.\u00a0 The people came alive through those summaries, but extraneous details did not hinder the main exposition.<\/p>\n

The book is non-mathematical, in the that the very few equations are exiled to chapter appendices, but it is analytical in the sense that concepts are clearly and completely described.\u00a0 There is no hand-waving or “This is neat but really too hard for you”.\u00a0 Even NP-Completeness gets covered in a reasonable manner (in the context of my own work).<\/p>\n

It is only in the coverage of my own work that I really disagree with the author.\u00a0 Briefly, Charles Dodgson (better known as Lewis Carroll of Alice in Wonderland<\/em> fame) proposed that the winner of an election should be the one who becomes the Condorcet winner with the fewest number of changes to the electors’ ballots.\u00a0 Bartholdi, Tovey and I proved that determining the Dodgson winner is NP-Hard.\u00a0 Szpiro writes that this result was the “death knell” of Dodgson’s Rule, which I think vastly overstates the case.\u00a0 We solve NP-Hard problems all the time, through integer programming, constraint programming, dynamic programming, and practically any other -programming you like.\u00a0 There are very, very few practical elections for which we could not determine the winner of the election in a reasonable amount of time (exceptions would be those with a vast number of candidates).\u00a0 In my mind, the main problem with NP-Hard voting rules is that the losers cannot be succinctly convinced that they really lost.\u00a0 Without a co-NP characterization, losers have to be content with “The computer program I wrote says you lost”, which is unlikely to be satisfying.\u00a0 But I don’t think Dodgson’s rule is dead and I certainly don’t think I killed it!<\/p>\n

Operations research comes out very well in the book.\u00a0 In addition to accurately describing Bartholdi, Tovey and me as Professors of Operations Research (kinda accurately:\u00a0 I was a doctoral student when the paper was written but an Assistant Professor at CMU when it was published), OR takes a star turn on page 189 when the work of Michel Balinski<\/a> is described.\u00a0 Here is part of the description:<\/p>\n

One of Balinski’s areas of expertise was integer programming, a branch of operations research.\u00a0 Developed before, during and after World War II, operations research originated in the military where logistics, storage, scheduling and optimization were prime considerations.\u00a0 But it soon acquired enormous importance in many other fields, for example in engineering, economics and business management.\u00a0 While game theory, developed at the same time, was mainly of theoretical interest, operations research was immediately applied to practical problems.\u00a0 Whenever something needed to be maximized or minimized – optimized for short – and resources were constrained, operations research offered the tools to do so.<\/p><\/blockquote>\n

What a lovely paragraph!<\/p>\n

If you have any interest in learning about why voting and apportionment are not straightforward, and want a readable, history-oriented book on approaches to these problems, I highly recommend Numbers Rule<\/em>:\u00a0 reading it has been a great way to spend a lazy weekend.<\/p>\n","protected":false},"excerpt":{"rendered":"

It is Labor Day weekend here in the US, so, in addition to the mandatory grilling and bicycling with Alexander, I have some time to laze about on the porch reading books (and drinking beer, which is also legally required in my jurisdiction).\u00a0 I have been reading Numbers Rule by George Szpiro.\u00a0 This is a … Continue reading “Reading “Numbers Rule” by Szpiro”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,57],"tags":[],"class_list":["post-1202","post","type-post","status-publish","format-standard","hentry","category-books","category-voting"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1202","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1202"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1202\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1202"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1202"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1202"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}