Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

Student's Social Choice

February 2002

It's our choices, Harry, that show what we truly are, far more than our abilities.

Albus Dumbledore, Headmaster
Hogwarts School of Witchcraft and Wizardry

Harry Potter, Year 2,
J. K. Rowling
Scholastic, 1999


There is nothing perfect where there is no choice: two qualities are required, the power to choose, and the power to choose better. (p. 29)

Inventiveness springs from genius: good choice from intelligence. (p. 165)

The Art of Wordly Wisdom,
Baltazar Gracian
Barnes & Noble, 1993

The usual math sequence taken by a liberal arts major is two courses long: some sort of intermediate algebra and one more course that is expected to fulfill the aims of liberal arts education with regard to mathematics. This last - the final math course - what should it be? Years ago, this course would most certainly be of the pre-calculus variety. It might have also been an attempt to endear mathematics on students who gave up on the subject long, long ago by presenting its more enticing, often recreational facets (see, for example, a review of [Beck], where the latter was referred to as a magnificent fossil of a book. Sherman Stein's eminently readable book might be in the same category. It was republished in 1999 by Dover Publications, Inc., which places it squarely among the venerable classics. The book can be now had at amazon.com at a throwaway price of $13.96, far below the expected textbook price range.)

A new trend seems to grow roots in math departments and among textbook publishers. I am aware of two fine representatives of this trend: Excursions in Modern Mathematics by P. Tannenbaum and R. Arnold and For All Practical Purposes by COMAP. In less than a decade one underwent 4, the other 5 editions. The books are similar in contents, execution and price ($90+).

In the Preface, the authors of Excursions explain that the "excursions" in this book represent a collection of topics chosen to meet a few simple criteria:

Applicability The connection between the mathematics presented here and down-to-earth, concrete real-time problems is direct and immediate.
Accessibility Interesting mathematics need not always be highly technical and built on layers upon layers of concepts.
Age Modern mathematical discoveries do not have to be only within the grasp of experts.
Aesthetics There is an important aesthetic component in mathematics and, just as in art and music (which mathematics very much resembles), it often surfaces in the simplest ideas.

Following is a small sample of the topics common to the two books (I am more familiar with the Excursions than with the COMAP book, whose contents could be ascertained from the online Description.)

Borda Method

The Borda method, named after Jean-Charles de Borda (1733-1799), is used to select the winner of the Heismann trophy, the American and National Baseball Leagues MVP's, Country Music Vocalist of the Year, school principals, university presidents, and in a host of other real world situations.

The Borda and the Plurality with Elimination (described below) methods use preference ballots, wherein a voter lists the alternatives in order of preference. The Borda method is about counting points. The last alternative on a ballot receives 1 point, the next one receives 2 points and so on. The Borda method selects the alternative with the largest point count.

It may surprise a student to learn that the winner picked up by the Borda method may not be the one preferred by the majority of the voters.

(How to use the applet.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


(Numbers in the upper row indicate the number of votes cast for ballots below. Letters A, B, C, D and so on denote the competing alternatives.)

Plurality with Elimination

The Plurality with Elimination is a natural extension of the majority vote to the case of more than 2 alternatives. Alternatives with the fewest number of (1st place) votes are dropped one after another until only two left, of which the winner is selected by the majority rule.

The Plurality with Elimination method violates the so-called Monotonicity Criteria. It's possible for a winner to lose the elections after someone switched votes in its favor. To see how that may happen, swap the first and the second alternatives on the 4th ballot.

(How to use the applet.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


There are many more methods used to combine individual preferences of the voting population into the Social Choice of the population as a whole. Kenneth Arrow's Impossibility theorem (1951), which in its currently common formulation asserts that no absolutely satisfactory democratic method exists, was called by Arrow himself the General Possibility Theorem: it pointed to a method that satisfied all the reasonable requirements Arrow thought to impose on a Social Choice procedure. Unfortunately, the method came out to be a dictatorship: one fellow's social preferences become the choice of the whole population (with or without election's routine.)

Power Indices

The United Nations Security Council consists of five permanent members (the US, Russia, England, France and China) and 10 nonpermanent members elected for two year periods on a rotating basis from several country blocks. For a motion to pass in the Security Council, it must be approved by all five permanent members and at least 4 nonpermanent ones. The situation is best described as a weighted voting system [39: 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], which indicates that

  1. each of the five permanent members has a weight of 7 (votes), while
  2. each of the ten nonpermanent member has a weight of 1, and that
  3. for a resolution to pass in the Security Council, it must muster at least 39 - the quota - votes.

All five permanent members have in effect veto power and thus wield more power than is suggested by the ratio 7:1. The Banzhaf power index has been invented to evaluated power distribution in weighted voting systems.

A coalition of voters is called losing if the total weight of its members does not reach the quota. Otherwise, a coalition is called winning. A member is critical to a winning coalition if its removal renders the coalition losing. Let there be N vote holders (players, as they are usually called). Let Bi, i = 1, 2, ..., N, denote the number of times the ith player is critical. Introduce B = B1 + ... + BN. Then the Banzhaf power index of the ith player is defined as BPIi = Bi/B.

It could be shown that the Banzhaf power index of a permanent member of the Security Council is more than 10 times greater than that of a nonpermanent member. (The ratio goes up to about 100 for another - Shapley-Shubik's - power index.)

Intuitively, power comes with the number of votes. More votes wield more power. So that the following situation may come as a surprise. It is straightforward to verify that, for the weighted system [8: 5, 3, 1, 1, 1], BPI1 = 9/19. The curious fact is that, if the first player cedes 1 vote to the second player, such that the weighted system becomes [8: 4, 4, 1, 1, 1], the voting power of the first player grows. Indeed, the index BPI1 becomes 1/2 > 9/19. On the other hand, when the second player cedes a vote to the third player, the real loser is the first player. The system becomes [8: 5, 2, 2, 1, 1], and BPI1 drops to 10/22 < 9/19.

(How to use the applet.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


Fair Division

The theory of fair division originates with Hugo Steinhaus (1887-1972), who developed the concepts and several algorithms during the WW II while in hiding from the nazis.

Each of the players that participate in the division of goods has a value system that tags any piece or part of the goods. A division is fair if each of the players thinks his portion constitutes at least 1/Nth (where N is the number of players) of the total.

The problem may seem difficult, but there are several working algorithms that apply in different situations. Not only it is possible to satisfy everyone's idea of fairness, in many cases a tangible part of the goods will be left over.

The method of markers applies in situations where the goods to be divided comprise a large number of small indivisible items that could be arranged in a line or the case where the goods naturally form a linear like entity, e. g., a sea front strip of land.

Each of the players, unbeknownst to the others, places (N-1) markers that divide the goods into N parts of equal (in his private estimation) value. The markers are then combined on a single diagram. The algorithm scans the goods left to right till it meets the leftmost of the first markers. The owner of that marker receives the stretch from the beginning to the marker. By construction, this is of course, in his view, a fair part. The algorithm than scans for the leftmost of the second markers. The owner of that marker receives the stretch between his first and second markers, i.e. the second of the parts he designated as fair. And so on. The last fellow receives the stretch from his last marker to the end of the goods. In the applet below, each player is assigned a color, whereas the black pieces belong to no one.

(How to use the applet.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


Kruskal's Algorithm

A number of universities and federal agencies must be connected via the internet. Throughput and reliability of the fiber optic connections are such that there is no need in redundant lines: it's sufficient that for any two of the organizations involved, there exists just one (perhaps indirect, I. e., through other organizations) communication channel. On the other hand, the costs of connections that depend on the distance between organizations and the terrain to dig through, may differ from one connection to another. A very practical question is what would be the least expensive way to build up the connection network?

After the locations of all organizations have been set up on a map, it became obvious that not all possible connections ought to be considered. Some organizations are too distant from each other, others are separated by naturally impassable territory. Still, among the feasible connections there is significant redundancy. Which combination is least expensive?

There is a surprisingly simple algorithm to answer that question. Kruskal's algorithm (Joseph Kruskal, 1956) proceeds in steps:

  1. On every step mark the cheapest unmarked edge.
  2. See that the marked edges do not form circuits (to avoid redundancy.)
  3. Repeat 1 and 2 while possible.

(Click on connections.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


Kruskal's algorithm exemplifies one approach to problem solving. When there are too many conditions to be satisfied, it may make sense to temporarily drop some conditions and first try to satisfy the remaining ones. (See, for example, a classical geometric construction problem.) At the outset, the requirement of having a connected network is dropped, and the algorithm only concerns with using the cheapest connections. But eventually a combination of the latter turns out to be connected.

As we see, the applicability of the selected topics does not imply their direct usability to the student. (Although the online summary of the COMAP book makes an astonishing claim: "Their text, For All Practical Purposes, tackles the question: If there were a course designed to present concepts of math that apply to today's consumers, what should it include?" Far as I can judge, except for the last, 20th, chapter - Models in Economics - and chapters on statistics, there is nothing in the book of interest to the consumer of either today or tomorrow.)

Other topics covered include additional graph algorithms, the problem of apportionment, scheduling, growth, symmetry and statistics. Each of the topics contributes to the notion that mathematics is an integral part of our society and culture. Most could be introduced with no mathematics at all. Very few require familiarity with algebraic concepts. Most of them could be dug deeper and reveal more of interesting mathematics and its methods. (For example, A. Taylor's book, still very popular, concentrates on only five topics, more or less equivalent to just one of the four parts of the Excursions, but covered in much greater depth and by far more rigorously.)

On the whole, both books offer a nice selection of (currently) unconventional topics. And there is a good chance that every student may like at least one of them. (We learn about one of the courses based on the COMAP book from the MAA's JOMA: The goal of the course is to get every student excited about and involved in at least one aspect of the mathematics that we do.)

But assume that the student did love one of the topics. What then? On reading the Excursions, I got curious about the Social Choice theory, which led to purchasing A. Taylor's Mathematics and Politics, and the problem of apportionment, which directly led to Balinsiki and Young's Fair Representation. (Both are gems in their genres. One as a textbook, the other as a comprehensive expository.) A student, however, concerned over fulfillment of the graduation requirements, would not have time to even contemplate deviating from the course material. But what if there were time? What if the student could also get credit for following his heart? Would not then it be nice to make available to the student some material on the level, of, say, Taylor's book. On the other hand, I can imagine a student in one of Taylor's classes who would rather prefer the less sophisticated chapters from the Excursions or the COMAP book. After all, not all students are the same.

In the introduction to chapter 19, Logic and Modeling, one of the two chapters added in the 5th edition, the authors write:

In the preface to the first edition of For All Practical Purposes, we find the following sentence:

[This book] represents our efforts to bring the excitement of contemporary mathematical thinking to the nonspecialist, as well as help him or her develop the capacity to engage in logical thinking and to read critically the technical information with which our contemporary society abounds.

In part, For All Practical Purposes has met this challenge of developing the capacity to think logically by illustrating how mathematical models can be used to analyze real-world problems. But isn't this challenge itself a real-world problem? If we want to understand what "critical thinking" is, perhaps we can do so by constructing a mathematical model that we can analyze.

Let's apply a similar reasoning to that final course of a liberal arts student. We see students are being taught to make choices, fairly divide the load and schedule jobs. Their developing capacity to think logically can be used to analyze real-world problems. But is not selection of topics into a course, their depth and rigor of exposition a real-world problem? Thompson Learning provides instructors with tools for tailoring courses to their tastes by mixing chapters from multiple titles and by adding new material. By extension, could not the students be permitted to create their own course they would have a better chance of enjoying? I mean just this once, in this final semester of their last stand vis-à-vis mathematics. You know, the technology is out there.

The idea may not be as frivolous as it sounds. I see the topics set up on a virtual network where connections represent a varying degree of rigor or depth, historical background or commonality of method, relevance of subjects, alternative approach, theory and applications. Topics are framed into study units with practice problems and online selftests, passing which students gain access to further topic selections. From time to time students are required to write reports that reflect on their progress. In class, students seek the instructor's guidance and share their ideas and recommendations about the topics. An important graduation requirement is the number of topics mastered. Credit is given for the student's demonstrated ability to follow the connections and for the number of topics mastered in depth. It's all very doable. And the opportunity is of the once-in-a-life-time significance.

To sum up, the books, like the Excursions in Modern Mathematics and For All Practical Purposes, offer an excellent selection of topics. But selection of topics and their depth is dictatorial. In that final math course of the liberal arts graduation requirement, I think, students may be entrusted with making a few choices of their own. For some of the students, for example, may have a taste for recreational mathematics.

References

  1. M. L. Balinski and H. P. Young, Fair Representation, Brookings Institution Press, 2nd edition, 2001
  2. A. Beck, M. N. Bleicher, D. W. Crowe, Excursions into Mathematics, A K Peters, 2000
  3. For All Practical Purposes by COMAP, 5th edition, W. H. Freeman & Company, 1999
  4. S. K. Stein, Mathematcis: The Man-Made Universe, Dover, 1999
  5. H. Steinhaus, Mathematical Snapshots, umpteen edition, Dover, 1999
  6. G. Szpiro, Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present, Princeton University Press, 2010.
  7. A. Taylor, Mathematics and Politics, Springer, 1995
  8. P. Tannenbaum & R. Arnold, Excursions In Modern Mathematics, 4th edition, Prentice Hall, 2001

How to use the applets

Bold numbers could be clicked upon. To increase the number, click to the right of its vertical center line. To decrease it click to the left of the line. Dragging the mouse near the center line will accomplish the same task, but faster.

In the applet with the preference ballots, clicking on small triangles in the upper right corner of a cell swaps that cell with the one directly above.

In the applet demonstrating the method of markers, the colorful horizontal bars are "rails" on which the vertical bars - the markers - slide. The points of intersection with the small circle drawn are draggable. The top bar represents the goods to be shared in the required linear arrangement.


Related material
Read more...

  • The Constitution and Paradoxes
  • Adams' Apportionment Method
  • Banzhaf Power Index Calculator
  • Fair Division: Method of Lone Divider
  • Fair Division: Method of Markers
  • Fair Division: Method of Sealed Bids
  • Fair Division: Method of Sealed Bids II
  • Fast Power Indices
  • Five Methods of Apportionment
  • Four Voting Methods
  • Hamilton's Apportionment Method
  • Huntington-Hill Apportionment Method
  • Jefferson's Apportionment Method
  • Method of Markers II
  • Shapley-Shubik Power Index Calculator
  • Voting Methods and Social Choice
  • Webster's Apportionment Method
  • Weighted Voting and Power Indices
  • |Contact| |Front page| |Contents| |Geometry| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62019093

    Search by google: