Mathematical Modeling (Notes)

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

The materials below were developed for both graduate and undergraduate courses taught under the title "Mathematical Modeling." The philosphy of these courses is to cover as broad a range of topics with a modeling flavor as possible. It it generally easier to get a deeper knowledge of a subject X where one has seen the key ideas and some of the major results than it is to start off reading in a book devoted only to the content of topic X. Both issues involving modeling and situations where mathematics can be used to get insight will be considered. Some of these materials have been developed with the assistance of Stuart Weinberg, Teachers College.

Some of these items were also developed in conjunction with the P-credit courses offered by Math for America in conjunction with its Professional Development and Outreach program in the New York City area.

----------------------------------------------------------------------------

Material added in Spring and Summer, 2021

--------------------------------------------------------------------------------

Jordan Ellenberg at the University of Wisconsin in Madison has written an expository article about gerrymandering. The issue is that after each state is assigned its "fair" number of seats based on the 2020 census, the highly politicized state legislatures get to draw the district lines for new Congressional districts. Without safeguards these lines can be drawn to advantage one political party of another. Mathematics can be used to try to imporove the fairness of what is done.

Essay about gerrymandering

----------------------------------------------------------------------------

Material added in Fall, 2020

--------------------------------------------------------------------------------

Generally speaking a college education is a good investment despite the costs because college graduates tend to do better financially than those who don't get a college (community college) degree. However, in America many teachers don't get as much benefit from going to college as do other college graduates. A report discussing and quantifying the issue can be found below.

Teachers don't do as well as other college graduates

Here are 95 categories which one can use to classify mathematical work. This list is that used by the London Mathematical Society. Similar lists are used by the American Mathematical Society.

Classifying the parts of mathematics

--------------------------------------------------------------------------------

Material added in Summer and Fall, 2019

--------------------------------------------------------------------------------

When different voting systems are useed (Borda, Condorcet, etc.) one might be interested in how "representative" of the voter's preferences the "winner" of the election turns out to be. This recent paper addresses this issue. The paper sets the stage for the question but the discussion is quite technical.

Representativeness of a collection of preferences

--------------------------------------------------------------------------------

Lots or research in mathematics education, medicine, and science requires sampling from a population with the goal of understanding something about the population based on the sample. Much of the "theory" here is based on random sampling, the meaning of which is easily subject to "confusion." This account may prove of interest:

Idea behind a random sample

--------------------------------------------------------------------------------

Donald Saari is one of the most important contributors to the mathematical theory of elections. You can easily track down his many articles (many easily available in pdf form online) as well as his many books. For a very short (pg. 891-895) comment by him about the theory elections you can look at the Princeton Companion to Applied Mathematics. The table of contents of this impressive book is below. Very little of the book is devoted to discrete applied mathematics, in contrast to "classical" applied mathematics which is traditionally rooted in Calculus ideas. Below you will also find a small pdf item about a particular aspect of modeling.

Table of Contents for Princeton Companion to Applied Mathematics

Brief extract from Princeon Companion to Applied Mathematics about modeling

--------------------------------------------------------------------------------

Steven Brams, who co-invented approval voting along with Peter Fishburn (Bell Labs) has written a letter to the NY Times arguing that given the reality tat there are more than 20 active candidates trying to get the Democratic Party nomination for President, the Democratic Party would almost certainly get a more viable candidate if approval voting were used rather than the plurality voting currently in use.

Steven Brams, letter to the NY Times, July 4th, 2019

--------------------------------------------------------------------------------

This essay gives brief discussions of the many voting methods that have been proposed over the years to improve on the plurality method appraoch to voting. What mathematics makes clear is that find a way to translate individual views into an "agenda" for society by using elections is a complex involved process.

Voting Methods

Here are some notes, activities, questions and examples related modeling elections.

Voting activity

Challenging Elections

2019 Democratic primary issues

Modeling elections and voting behavior

Mathematical modeling can be carried out systematically in any field - physics, chemistry, economics, biology, geology, psychology, etc. While the public is not that familiar with the academic discipline called operations research (OR) (management science), OR modeling is especially appealing as an area to deal with in K-12 mathematics classes because many aspects of what OR addresses are things one sees in everyday life: mail delivery, snow removal, vans to deliver packages to one's house or appartment building, creation of electircal networks or sewer systems, assigning workers to jobs (tasks), scheduling, etc. This collection of activities calls attention to some of the relatively easy models that can be tied to OR problems for locations in a small urban grid.

Operations Research models

Operations Research models - more details

Hop-on-off bus model

Algorithms related to urban OR problems

Graph Theory is a very useful tool for modeling. Is a very basic indtroduction.

Graph Theory Primer

This modeling activity 'celbrates" the fact that the July 4th holiday is almost upon us. It is in the spirit of what are called Fermi problems, to do "back of the envelope calculations for some question, typically using plausible estimates for "data."

Hot dog consumption

This essay discusses various "themes" and how modeling ideas can be used to get insight into these areas of applicability.

Thematic approaches to modeling

Essay the nature of mathematical modeling, compared with "problem solving."

This activity is related to assigning students grades.

Activity related to assigning students grades

This activity relates to how to modeling the notion of friendship between individuals.

Modeling the notion of friendship

This model is related to delivering items from a "source" to those who sell/distribute the item (e.g. bakeries shipping breads to supermarket chains) so supplies meet demands at minimal cost. This model is a special case of a linear programming problem but it can be examined by trial and error or graph theory ideas. This type of problem is known as the transportation problem.

Delivering breads from bakeries to stores

Allocation problems, school choice questions, and matching markets all involve interesting ideas that are surprisingly elementary and deserve a place in K-12 education. The top trading cycle of David Gale is one approach to this kind of problem as well as the deffered acceptance algorithm of Gale and Shapley.

Allocation using the Top Trading Cycle approach

Stable marriage ideas

School choice activity

Many interesting experiments can be done to see if people use the ideas that game theory offers into how one might "best" act in a particular situation. This activity probes the game, often called the ultimatum game, which explores how "altruistic" one might be in a certain situation.

Activity involving people's willingness to share

--------------------------------------------------------------------------------

Material added in Summer and Fall, 2018

--------------------------------------------------------------------------------

After the census is carried out 2020 the Commerce Department will carry out its Congressional mandate to assign each of the 50 states the number of seats it will have in the House Of Representatives. The paper by H.P. Young on district shape is useful for those looking for topics to show "applications" for geometrical ideas that come up in teaching K-12 geometry. Ideas explored include area, perimeter, incircle and circumcircle. The other "notes" deal with ideas replated to apportionment - fair ways of all allocating an indivisible number of positive integer things.

Article by Peyton Young about how to measure the compactness of "legistlative" regions/districts.

Exploring Apportionment

Exploring the Apportionment Model

Districting Activity

Here are three essays about some of the technical details (with arithmetic worked out) of the methods of apportionment which are easiest to do in K-12 classrooms.The mathematics involved is little more than arithmetic and for those who like the comfort of the details of examples, I find these rather appealing concerning the link between doing examples and obtaining conceptual understanding. For many, conceptual understanding only comes after algorithmic "comfort."

Apportionment I

Apportionment II

Adams, Webster's and Jefferson's Apportionment Methods - Example

------------------------------------------------------------------------------

If people have prferences for items allocated to them (perhaps at random) an improved allocation may be possible by "trading" among the "players." David Gale's Top Trading Cycle Algorithm has many appealing properties and can be used to obtain an improved allocation. Ideas related to this are useful for school choice and room allocation by a college.

Reallocation of items among a group of people (top trading cycles)

--------------------------------------------------------------------------------

Many American cities have allowed students to apply for a K-12 school to attend using a centralized market approach. This system, known as school choice, uses mathematical ideas to try to "match" schools and students in a way that works well for both the students and the schools. The mathematics involved in these systems typically involves the Top Trading Cycle algorithm of David Gale, and deferred acceptance algorithm of David Gale and Lloyd Shapley. Alvin Roth and his students and colleagues have been involved with the design of many of these systems.

School Choice Activity

--------------------------------------------------------------------------------

July 4th related activity dealing with the consumption of hot dogs and hamburgers on July 4th

Hot dog and hamburger consumption activity (in honor of July 4th)

--------------------------------------------------------------------------------

An election where different reasonable election methods choose different winners.

Different election methods yield different winners

--------------------------------------------------------------------------------

A game situation where typically people behave quite differently from what the "theory" suggests would be rational behavior for them. I think of this as a situation in which "free lunch" is involved.

Free lunch game

--------------------------------------------------------------------------------

An essay urging that K-12 mathematics curriculum and mathematical modeling in K-16 be taught from a thematic point of view (fairness, optimization, etc.) rather than a "techniques" (fractions, solving linear equations, etc.) point of view.

Thematic approach to curriculum, teaching, and modeling

--------------------------------------------------------------------------------

A transporttion problem involving optimal shipment from bakeries to stores.

Delivering breads to bakeries-transporation problem

--------------------------------------------------------------------------------

Brief discussion of a variety of urban operations models such as edge-traversal in a weighted graph and vertex traversal problems in graphs. Algorithms for these problems are discussed as well as "heuristics," procedures that often give reasonably good answers quickly.

Urban operations researuch problems and algorithms to solve them

--------------------------------------------------------------------------------

A major source of modeling problems grows out of trying to provide efficiently run urban services for city dwellers. This collectoin of "situations" explores some major graph theory approaches to urban problems but the "models" are of interest for their theory as well as broad applications.

Urban modeling problems - Graph Theory

--------------------------------------------------------------------------------

This essay discusses terminology such as contexts, problem solving, exercises, and modeling and offers examples to distinguish between their use, including some sample fairness issues.

Contexts, Problem Solving, Exercises, and Modeling

--------------------------------------------------------------------------------

When one does mathematical modeling the more mathematical tools one knows to be able to get insight into the situation the better. One such powerful tool is graph theory, dot and line diagrams to help visualize relationships. Here is a very brief introduction to this subject.

Introduction to graph theory

--------------------------------------------------------------------------------

In many settings when one does work in game theory and mathematical modeling it is helpful to be able to generate random permutations of the number from 1 to n or to produce digits from 1 to n independently and randomly (repeats can occur). This site enables one to generate such sequences relatively easily. For example one might want to generate a random list of the preferences of voter j for the candidates named 1 to 11.

Random permutations and sequences, 1 to n

----------------------------------------------------------------------------

Material added in Summer and Fall, 2017

--------------------------------------------------------------------------------

This fascinating article discusses examples of how mathematics, more specifically geometrical ideas, have found use in courtroom procedures.

Courtroom geometry

--------------------------------------------------------------------------------

Gerrymandering (drawing legislative district lines to achieve some set of goals) is becoming increasingly widespread, Mathematical tools are being used both to design districts that unfairly have some "political" or "racial" goal as well as trying to measure if a particular set of district lines is fair and reasonable. Here is a recent article that discusses some of the issues.

Gerrymandering

----------------------------------------------------------------------------

This discussion of an example due to Donald Saari looks at how different the winners and rankings of the plurarity, Borda count and Condorcet method can be for a particular example involving three candidates.

Comparing winners using plurality, Borda count and Condorcet for a 3-person election

--------------------------------------------------------------------------------

While problems about fair division involving horses, camels and unit fractions may display more whimsey than genuine insight into modeling and applications, there is no doubt about the charm of these problems. Here is a preprint of a "survey" about this type of problem that appeared in the Journal of Mathematics and the Arts. Lots of nice material in this journal about connections between mathematics and the art (painting, sculpture, music, etc.).

Fair division involving horses and camels

--------------------------------------------------------------------------------

The mathematical approaches to school choice build heavily on the deferred acceptence algorithm approach to two-sided markets of David Gale and Lloyd Shapley, adapted to the school choice situation. A very readable survey is linked below, which also has a nice account of how the David Gale Top Trading Cycles idea is adapted to school choice.

Survey paper about school choice

--------------------------------------------------------------------------------

Here are a variety of modeling situations/activities of different kinds to think about:

Hot dog activity

Election/Voting Activity

Bread delivery activity

School Districts (Taxicab Voronoi)

School choice activity

Here is a group of modeling activities involving urban operations research and where ideas related to taxicab distance and graph theory come into play.

Urban Operations Reserach - tools, graph theory and taxicab geometry

For the activities in the item above, algorithms have been developed for the models reprresented by the contexts discussed. Here are some more details about the models involved and some ideas about how algorithms for these "types" of OR problems work.

Algorithms for some important OR types of problems

An essay contrasting problem solving, exercises, using contexts, and mathematical modeling.

Modeling, Problem Solving, Exercises, and Contexts explored

This essay contrasts teaching mathematics from a themes rather than techniques point of view.

Themes vs. techniques

This essay provides examples of teaching mathematical modeling from a thematic rather than from a techniques point of view.

Modeling via themes

This activity looks for "real world situations" where people vote and/or elections take place.

When are votes and elections used to make decisions

A brief introduction to graph theory, which is a very valuable tool for mathematical model construction.

Graph Theory Primeer

-------------------------------------------------------------------------------

Material added in Fall, 2016

-------------------------------------------------------------------------------

Fairness is compromised when state legislatures draw district lines for the benefit of the party in power. This gerrymandering phenomenon has grown in the US in recent years. Here is an article about a "lower" court decision about this matter, which probably will eventually come to the Supreme Court. The issue affects the way district lines will be drawn after the 2020 Census.

Recent court decision on gerrymandering (NYTimes)

-------------------------------------------------------------------------------

Two different approaches over using a standard ballot (vote for one candidate) and using the plurality system is to either use a system where a "ranking" ballot is used or a "grading" ballot. The Borda Count and various "Condorcet" completion methods are based on ranked ballots and range/score voting or median voting (Bilinski/Laraki) are based on grading. Here is a recent (joint) paper of Steven Brams which calls attention to "paradoxes" for grade voting systmes.

The Paradox of Grading Systems (Brams/Potthoff)

-------------------------------------------------------------------------------

This web page gives a comparison of the properties of various methods of elections as well as links to pdf files that analyze the extent to which systems other than plurality voting would be an improvement over plurality voting. There are links at the top of the page for other election comparison web pages.

Chart comparing properties of various voting systems

-------------------------------------------------------------------------------

Here are some more activities and links that relate to electing a President. The issues involve apportionment, having students be able to find real world situations that involve models related to the apportionment problem, and district line drawing (gerrymandering) by legislatures. The paper by H.P. Young on district shape is useful for those looking for topics to show "applications" for geometrical ideas that come up in teaching K-12 geometry. Ideas explored include area, perimeter, incircle and circumcircle.

Article by Peyton Young about how to measure the compactness of "legistlative" regions/districts.

Exploring Apportionment

Exploring the Apportionment Model

Districting Activity

Here are three essays about some of the technical details (with arithmetic worked out) of the methods of apportionment which are easiest to do in K-12 classrooms.The mathematics involved is little more than arithmetic and for those who like the comfort of the details of examples, I find these rather appealing concerning the link between doing examples and obtaining conceptual understanding. For many, conceptual understanding only comes after algorithmic "comfort."

Apportionment I

Apportionment II

Adams, Webster's and Jefferson's Apportionment Methods - Example



--------------------------------------------------------------------------------

The details of the way that the Electoral College works are rather complex. Here are a look at some of the details.

Electoral College "Primer"

Rules about members of the Electoral College

--------------------------------------------------------------------------------

The apportionment problem refers to assigning a non-negative integer number of seats in a parliament based on population where there is a geographic basis for representation or based on votes for parties where political parties are the basis for representation. The crux of the issue being that if a party, by way of example, is entitled to 12% of h = 23 seats, one can't put 2.76 representatives in the parliament. Often 2.76 is called the party's exact quota or fair share. So how do the fractions get handled? One approach is by rounding "rules" and another is by the size of the fractions for different parties in the exact quota. Here is a cluser of "notes," some in the form of activies and explorations that examine various aspects of apportionment.Since different algorithms come to mind, with different numberical results, this leads to a study of "fairness" conditions to compare which system is better or worse than another. The culmination of this approach was the Balinski-Young Theorem which showed that no apportionment method could similtanously be "population monotone" ("consistent" in how states are treated in two related apportiomments with regard to population growth) and "quota" (assigning a state either the floor or ceiling function value of its exact quota (rounding the exact quota up or down to the nearest integer when it is not an integer already.)

For background on apportionment problems take a look at:

Expository acouunt of apportionment, Part 1

Expository account of apportionment, Part 2

Apportionment activities

Apportionment methods can violate the quota rule

Apportionments results vary one method to another

--------------------------------------------------------------------------------

Here is a techical article about the issue of manipulating voting systems, with a particular interest in voting systems where it may be hard to figure out how to carry out such a manipulation by an individual or a group of individuals.

Manipulation of voting systems

--------------------------------------------------------------------------------

Here is a relatively recent "senior thesis" which deals with different attempts to find appealing election/voting methods that are relatively simple to understand and implement in the real world and which obey conditions that make them appealing. New methods and ideas are still being invented and explored.

Senior Thesis on election and voting methods

--------------------------------------------------------------------------------

Below are a series of "notes" some in the form of activities and some in the form of examples that explore a variety of aspects of voting behavior and which can be taught/used at a wide variety of grade levels.

In order to produce an ordinal ranked ballot where there are large number of choices some system of deciding one's preferences for the choices must be made. One approach to this is based on paired comparisons. Sometimes this approach may lead to inconsistencies because sometimes one may not produce "transitive" preferences (a P b and b P c does not imply a P c, where P means preferred to).

Decision making based on paired comparisons

This note treats issues related to the difference between ranking (saying for the choices which one prefers to others) and grading (where scores are given to different choices). Voting systems can be based on preference (ordinal) ballots or ballots which are produced using "grades." Approval voting ballots and range ballots are examples of ballots where voters "grade" the choices using scales of different kinds.

Grading vs. ranking

Range voting approach compared with paired comparison approach activity

Aside from a few "sloppy" aspects of the details, the electoral college is a voting situation where players (the states and the District of Columbia) cast blocks of votes. Such games are known as weighted voting games and are common for counties in NY State outside of the metropolitan area and in the European Union. Not surprisingly a small country like Belgium casts fewer votes than a big country like Germany. Now that Britain will leave the European Union the weights cast by the players will have to be reworked. The perhaps unintuitve reality here is that the "power" of the players in a weighted voting game is not proportional to the weight block cast. A player may have positive weight but have no power (0 power) because the player is not a member of any minimal winning coalition. Such players are often called "dummies."

Activity on weighted voting games

--------------------------------------------------------------------------------

The following two sites are very active in promoting insight into election methods that often involve mathematical approaches. You can, if you wish, subscribe to a news feed on the first site which discusses different new ideas about election methods. The range voting site also allows one to subscribe to digests of discussions about elections.

Election methods discussion site

Range voting and more

--------------------------------------------------------------------------------

If one obtains information from voters about all the candidates by asking them to produce a preference or ordinal ballot one might expect that one could select a winner for an election that more closely reflects the preferences of the voters. The problem is that example elections show that with different reasonable methods, different winners emerge. Thus, plurality votings, run-off, sequential run off, Borda Count, Condorcet voting, and median and above voting in specially designed examples may produce different winners for an election. These two examples are due to me and to Julian Wiseman. In these examples the voters don't produce any ties in their preference but not surprisingly ties make the issues "muddier."

Election with many winners using different methods

Another election with multiple winners using different methods

--------------------------------------------------------------------------------

An interestng source of mathematical activities can be generated using the fact that on Nov. 8th, 1916 Americans will vote to begin the process of electing a new President. The winner of the popular vote does not necessarily become President. The winner of the Presidency will emerge from the Electoral College. One useful activity is to take a vote involving different types of ballots and have students think through what an individual has to do to complete a ballot of this kind.

Ballot Generation Tasks for 2016 Presidential Election

--------------------------------------------------------------------------------

Material added in Summer, 2016

--------------------------------------------------------------------------------

The refugee influx that the European Union has experience recently engendered this paper dealing with matching refugees with housing in a particular country. One interesting "side condition" is making the matching compatible with the language spoken by the refugee and the landlord.

Matching refugees to housing

-------------------------------------------------------------------------------

What happens when matchings are generated based on expected performance on an exam and a person does better on the exam than expected?

Matchings when performance is better than expected

-------------------------------------------------------------------------------

When preferential ballots (ordinal ballots) are used some have argued that there is a violation of "one person one vote" for some of the methods that have been proposed to count the ballots. I don't understand the logic of these arguements including some that have been voiced in court decisions. Here is a comment on a Minnesota court which declared the Bucklin method was not allowable. To me what matters is that the person involved gets to visit the voting booth only once, not that there are "unfamiliar" methods used to count these votes. I am not a fan of IRV, prefering "Condorcet" methods but I certainly don't think adopting IRV would be "unconstitutional" either in the state of NY or nationally.

Do IRV or Bucklin violate one person, one vote?

--------------------------------------------------------------------------------

One activity below considers issues related to two people sharing a cab. Here is a much more detailed and complicated approach to modeling this problem that appeared on the ArXiv recently.

Costs and benefits of ride sharing

--------------------------------------------------------------------------------

Sadly, this item from the NY Times makes no mention that the founders of game theory were nearly all mathematicians (Von Neumann, Nash, Gale, Kuhn, Tucker, Shapley, etc.) but it does point out the many "every day" contexts where fairness and game theory isues arise. While current game theory/fairness experts often teach in economics departments they typically have extensive training in mathematics.

NY Times item on Game Theory and Fairness

--------------------------------------------------------------------------------

Common wisdom is that a mathematical idea (theorem) can't be patented. However, this issue has become blurred because courts have upheld the notation that software can be patented. Here is the patent that lists Steven Brams and Alan Taylor as inventors and NYU (where Brams teaches) as the patent assignee. The patent makes interesting reading for a variety of reasons, including its explanation of the methods and ideas involved.

Patent US 5983205 Computer-based method for the fair division of ownership of goods

Patent 5983205

--------------------------------------------------------------------------------

This essay/activity addresses the fact that students often add fractions by adding the numerators and adding the denominators by a context that involves Simpson's Paradox. This paradox involves X being true for each of two disjoint groups but when one merges groups the "opposite" behavior is seen.

Fractions and Simpson's Paradox

After a census each state must be asssigned a number of seats in the House of Representatives and currently Huntingon-Hill is used to to this. But then each state must draw district lines for the seats. When this is done with political goals it is called gerrymandering. This note/activity address mathematical education aspects of this practice.

Districting-Gerrymandering Activity

If a group of people have to "fairly divide" a collection of indivisible objects, a variety of methods have been developed. This activity gets at using a method due to Bronislaw Knaster known as sealed bids or Knaster's Method. Each "player" bids on the objects (truthfully) and then the objects are given to the highest bidder. A "resolution" fund is established using positive and negative values to "equalize" fairness, and in the end, each player (if the bids for the goods are all distinct) gets more than his/her fair (proportional) share. Monetary side payments are required.

Fair Division: Sealed bids - Knaster

This activity gets at using range voting to construct a ranking, which provides a contrast to obtaining rankings by paired comparisons.

Constructing a ranking using range voting

Many urban areas in order to improve schools have done away with the idea of neighborhood schools where that children must attend. Rather students can apply to any school, with the hope that competition between schools for students will improve the schools. Methods of doing school choice systems range include ideas due to Gale and Shapley (with improvments by Alvin Roth and others) and the top tradiing cycle approach of Gale/Scarf. This activity trys gives an example designed to show that there can be a trade-off between "stability" and "efficiency." A link to a nice survey article (pdf) also is provided.

School Choice - Market Design

School Choice A Mechanism Design Approach by Atila Abdulkadiroglu and Tayfun Sonmez

The Electoral College and voting bodies of the European Union illustrate the places where weighted voting is used in practice. Belgium is a small courntry while Italy and German are large ones, so not surprisinlgy they cast different weights in voting bodies of the European Union. Breat Britain, when it leaves the EU will require that the EU reset the weights of the remaining countries of the EU. This activity gets at the idea that power is not proportional to weight in a weighted voting game.

Weighted Voting Game Activity

--------------------------------------------------------------------------------

Here are some "materials" that deal with a connection between facility location, statistics and a variety of other basic mathematical skills. There is also some discussion of the distinction between Euclidean distance (crow flies) and taxicab distance. These units were developed quite a few years ago and were thought of being directed at the 6th grade but one can do versions of this in higher grades as well.

Facility Location (including some taxicab geometry)

Facility location and statistics (including the midrange value)

--------------------------------------------------------------------------------

In honor of July 4th here is a modeling activity involving the eating of hot dogs, a July 4th tradition.

Hot dog activity for July 4th.

Here is a selective (there are literally hundreds of books to choose from) dealing with elections, fairness, and game theory. Many of the authors of these papers are mathematicians but these individuals teach in other departments than a mathematics department.

Selective Bibliography of fairness, elections (voting), and game theory

Historically, the teaching of mathematics at all grade levels has been organized from a techniques point of view (doing arithmetic, solving linear equations, solving quadratic equations, etc.). Here I offer a suggestion that using themes to organize the mathematics we teach might give students a clearer picture of what mathematicians do and what mathematics is about. Perhaps this approach would help students know in what "situations" it would make sense to "call a mathematician."

Techniques Versus Themes

--------------------------------------------------------------------------------

Divisor methods, like the Huntington-Hill method which is currently used to arrive at how many seats each U.S. state gets after each census does not obey the "Quota Rule." Here is an example due to Balinski and Young which shows this, and also connects up with the Balinski-Young Theorem. This theorem states that no apportionment can be both population monotone and obey the quota rule, thereby showing that there is no "perfect" method of apportionment.

Divisor methods can violate the Quota Rule

--------------------------------------------------------------------------------

Here are some activities designed to get at various aspects of mathematical modeling in the area of fairness (and the mathematics related to electing a President), and some "essays" about tools that might be useful for this modeling.

Primer of Graph Theory (one page)

Rankings via paired comparison

Sharing Costs of a Cab Ride

Elections and voting activity

--------------------------------------------------------------------------------

Many people who do research in mathematics education believe that running statistical tests "automaticallY" validates the conclusions that they have gotten. Recently there has be lots of debate about p-tests and how to use them properly and what meaning they have. Here is a recent article in Science about this matter:

Science (AAAS) article about using p-tests

--------------------------------------------------------------------------------

SIAM, the Society for Industrial and Applied Mathematics not only is interested in applied mathematics and mathemamtical modeling but mathematics education as well. As a teacher interested in mathematical modeling, applied mathematics and teaching with contexts, a tremendous source of information is SIAM's publication called SIAM News. This "newsletter" has articles that vary form infomration about famous applied mathematicians, to expository articles of great general interest, to book reivews of applied mathematics books, to highly technical new developments in applied mathematics. You can access copies of SIAM news from the web page below:

Relatively recent issues of SIAM News

Archive of older SIAM News issues

--------------------------------------------------------------------------------

COMAP (The Consortium for Mathematics and Its Applications and SIAM (The Society for Indiustrial and Applied Mathematics) recently released a report urging the teaching of mathematical modeling and use of teaching with contexts at all levels of K-12. For those not familiar with mathematical modeling, its goals and its ideas, this is a good place to begin. The report can be downloaded for free in pdf format or looked at on-line at the URL below.

COMAP-SIAM GAIMME Report on Mathematical Modeling

--------------------------------------------------------------------------------

Material added in Fall, 2015


--------------------------------------------------------------------------------

Queues, or waiting lines, offer many opportunities for data collection and mathematical modeling. The mathematical skills involved include probability theory and statistics. Here is an essay, a few years back, which offers some possibilities.

Waiting Lines

--------------------------------------------------------------------------------

Material added in June, 2015


--------------------------------------------------------------------------------

This brief essay looks at the "anti-plurality" and plurality methods of holding holding elections which shows some paradoxical behavior pointed out by Donald Saari (and co-author). For this example, the Borda Count behaves "sensibly."

Ballot Reversal

--------------------------------------------------------------------------------

This essay deals with fundamental properties of "fair division" schemes. The discussion includes the notions of proportionality, being envy free, and being "efficient" - Pareto Optimality.

Basic Ideas in Fairness

--------------------------------------------------------------------------------

What follows is a collection of brief modeling tasks involving such diverse contests as "rewards" coupons, snow removal, paired comparisons, and hot-dog consumpton.

Modeling Store Coupons

Cost of Snow Removal

Paired Comparisons

Hot Dog Activity

--------------------------------------------------------------------------------

The long drought in California has caused interest in finding ways for individuals to use less water. Here is a modeling task that address some aspects of personal water usage.

Modeling Water Use

--------------------------------------------------------------------------------

Material added in Fall, 2014


--------------------------------------------------------------------------------

The winner of the Nobel Memorial Prize in Economics is Jean Tirole. Tirole was born in 1953. Tirone has used a variety of mathematical approaches for his many contributions to economics, In particular, Tirole has done work in game theory. Here is the link to the wiki article about him and his work:

Jean Tirole

-------------------------------------------------------------------------------

Material added in Summer, 2014


--------------------------------------------------------------------------------

The National Academy of Sciences provides biographical essays for distinguished scholars in many areas, including applied mathematics, mathematics and economics. Here is the page of essays available for economists. Many of these individuals have made important contributions to the theory of games and to the value of modeling in enconomics:

Biographical Memoirs of Economists

--------------------------------------------------------------------------------

Auctions of different kinds are increasingly being used as a way of eliciting private information, within the domain of mechanism design. Here is a story about a recent example:

Auction for Pricing Tickets

--------------------------------------------------------------------------------

Material added in Spring, 2014


Here is a brief description and syllabus for a modeling coures I am teaching in the Spring Semester, 2014. The emphasis of the course will be on modeling in the the behavorial sciences.

--------------------------------------------------------------------------------

This modeling problem belongs more to operations research than to the behavorial sciences but was inspired by some recent nasty weather on the East Coast.

Cost of Snow Removal

--------------------------------------------------------------------------------

This essay in an informal way discusses the meaning of terms such as exercise, problem solving, contexts, and modeling. Various examples from different domains are used as illustrations but there is an extended discussion of bankruptcy questions.

Exercises, Problems Solving and Modeling

--------------------------------------------------------------------------------

In order to makes decisions one has to consider the various choices of actions that one can take and be able to understand which of these actions you consider as better. There are many aspects to this choice environment and this activity about probing your personal feelings about particular kinds of fruit my help see the complexities involved. Here choices are forced in the sense that indifference between alternatives is not allowed, nor is one allowed to choose not to make comparisons between some of the pairs.

Making choices-paired comparisons

--------------------------------------------------------------------------------

Here is a sampler of behavorial sciences "modeling" related problems for a general audience or to introduce a class in middle school or high school to some problems that lie within the domain of what mathematicians are studying that are related to applications in the behavioral and social sciences. There is a heavy emphasis on fairness models and those where a game theory point of view is valuable.

Mathematical Modeling Sampler -Behavorial Sciences

--------------------------------------------------------------------------------

The word "model" has various connotations. This note asks you to think about the notion of howthe phrase mathematical modeling builds on the everyday use of the word "model." It also gives a variant of a diagrammatical way of thinking about the modeling process, and urges you to think about the subtle ways that terms like mathematical model, physical model, modeling, the modeling process, etc. differ from one another.

What is Mathematical Modeling?

Modeling Check List

--------------------------------------------------------------------------------

If one has added some weight recently, how might one work off calories by walking? Here are some charts and questions related to finding a model the clarifies what might be invovled.

Burning Off Calories by Walking

--------------------------------------------------------------------------------

Here is a brief introduction to graph theory, including the definition of such terms as degree, valence, walk, trail, and path.

Introduction to Graph Theory

--------------------------------------------------------------------------------

An article about fair division has appeared in the current Notices of the American Mathematical Society. The 12 page article is somewhat technical but light on "heavy use" of symbols. It uses the notion of preferences between items without ties as an "input" to the algorithms it discusses. The preferences involved are "ordinal" ones and don't try to deal with perceived "intensity" of these preferences. Clicking on the link will enable you to download the pdf file of the article by Steven Brams, Marc Kilgour, and Christian Klamler.

Two Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm

--------------------------------------------------------------------------------

When words are used to describe a "real world" situation often one needs to examine carefully what meaning these words really convey. What does it mean to say that a baby elephant is bigger than a baby giraffe, and is it even true? Modeling often requires a very careful look at how to interpret language in mathematical terms.

Capturing the Meaning of Words Using Mathematics

--------------------------------------------------------------------------------

Very often money does not capture the meaning of the "value" that something has to a person. To deal with this, the concept of "utility" was developed. Utiity, among other things, allows one to begin with a preference structure and tell when something is more preferred to something else by assigning numbers to the objects being compared in a way the "captures" the preference relationships.

What is Utility?

--------------------------------------------------------------------------------

This is a modeling project that is optional but I strongly encourage students to consider doing it, as explained in the project itself.

Optional Project

--------------------------------------------------------------------------------

This homework should be submitted for grading.

First Homework Problem Set

--------------------------------------------------------------------------------

Although this modeling course will not concentrate or deal in detail with statistical modeling, statistics is an extremely important tool for getting insight into the data that may be available in attempting to construct a useful model. Andrew Gelman at Columbia University has a wonderful blog about statistics, probability, and the behavorial sciences. Some of the items are quite technical but one can learn a tremendous amount by sampling regularly from this blog.

Andrew Gelman's Blog (Statistical Modeling, Causal Inference and Social Science)

--------------------------------------------------------------------------------

Notes about different appealing methods of conducting elections. For simplicity the methods are described under the assumption that voters rank candidates (choices) without ties, and without truncation of ballots (not listing all the choices). The methods include, plurality, run-off, sequential run-off, Condorcet, Borda Count, Baldwin's Method, Minimax, Nanson's Method, Coombs' Method, and Bucklin's Method.

Attractive Ordinal Ballot Voting Methods

--------------------------------------------------------------------------------

This homework should be submitted for grading.

Second Homework Problem Set

--------------------------------------------------------------------------------

A recent example of modeling in the behavioral sciences concerns the issue of whether one contributor to income inequality is that marriages are taking place which result in a couple having much more income and wealth than was true in the past. Here is a link to a pdf paper that deals with this issue. The paper is quite technical but you may just want to see how the issues get "framed."

Marry Your Like: Assortative Mating and Income Inequality

--------------------------------------------------------------------------------

This homework should be submitted for grading. It deals with the issue of election methods and whether they "obey" sensible fairness rules.

Third Homework Problem Set

--------------------------------------------------------------------------------

A common tool of mathematical modelers is to use significance tests - compute p-values associated with some hypothesis which is being tested. Many reseearches are calling into question the wisdom of this methodology, especially with regard to whether one can get the "same result" if one repeats the experiment. This concern may have broad implications for education, mathematics education, and psychology since using significance tests is in such fields "part of the culture."

Nature article - Scientific Method: Statistical Error (February 12, 2014)

--------------------------------------------------------------------------------

Warren Smith has a doctorate degree from Princeton (1989 - his thesis is about computational geometry) and for many years now has been promoting a voting system called "range" voting. This is a cardinal ballot system where each voter can cast anywhere from 0 to 99 points for each candidate running for office. The vote for a candidate is the sum of the points she/he gets from all the voters. The web page below promotes range voting but more importantly has collected a tremendous amount of scholarly materials about elections and voting. There are detailed descriptions of many voting methods and lots of information about which voting systems obey which axioms.

Range Voting

--------------------------------------------------------------------------------

Wikis are sites which are maintained and edited by people with passions for particular topics. Electorama has a wide variety of materials and descriptions related to election methods and voting. You can get some idea of the flavor of the site by using the "random page" feature a few times.

Wiki style site devoted to elections and voting

--------------------------------------------------------------------------------

This is a discussion of one of the axioms. monotonicity that Kenneth Arrow suggested a fair/democratic election method should obey. The idea is that having more support should not hurt one's chance of being elected.

Monotonicity

--------------------------------------------------------------------------------

Many aspects of modeling in the behavorial sciences require ideas about probability and randomization. This is a brief essay about the use of spinners in trying to get across the ideas of probability, and the advantages they have over coins and dice.

Randomization Devices

--------------------------------------------------------------------------------

This note encourages you to think about how to pair two groups of people who rank each other in a "useful" way and that reflects the interests of the individuals in the groups. Problems of this kind have come to be known as two-sided markets. Usually, markets are governed by an equilibrium price that reflects supply/demand issues. Here there are no prices.

Two-Sided Markets Example

--------------------------------------------------------------------------------

Practice Problem involving the Gale-Shapley deferred acceptance algorithm. Includes the idea of blocking pair and the breakmarriage approach to finding additional stable marriages beyond the one (or two) female/male optimal stable marriages guaranteed by the Gale/Shapley algorithm.

Practice: Gale/Shapley Algorithm

--------------------------------------------------------------------------------

This homework should be submitted for grading.

Fourth Homework Problem Set

--------------------------------------------------------------------------------

Links to where you read about ideas that we talked about in class involving elections and votings, and two-sided markets (Gale-Shapley models; two-sided markets) are described in this brief essay. The articles appeared as web columns as part of the American Mathematical Society Feature Column series, which regularly has articles that I hope will interest you. I contribute 3 or 4 columns a year to this series.

Expository Articles About Voting, Elections, and Two-Side Markets

--------------------------------------------------------------------------------

This article (pdf download) is a survey of British medical "markets" and how the stability of the matchings seemed to be the key to the survival of the market. Fascinating reading (25 pages, some technical mathematics but you can read around the technical parts for the modeling and history).

Alvin Roth paper on unraveling Brishish medical markets

--------------------------------------------------------------------------------

You can practice the deferred acceptance algorithm to find male and female optimal stable marriages but also to think about how to find other stable marriages since in this example there are eight others. One way to do this is to use the "break-marriage" idea.

Example with Ten Stable Marriages (4 men; 4 women)

--------------------------------------------------------------------------------

Materials from a game theory course I taught in the past might make worthwhile reading.

Materials from a Game Theory Course I taught

--------------------------------------------------------------------------------

Some questions to frame the way people perceive games so that one can think about taxonomy and fairness questions involving the theory of games.

Game Theory Questions

--------------------------------------------------------------------------------

Lots of nice examples, and resources for game theory enthusiasts over a broad range of levels can be found here:

Game Theory .net - About anf Frequenetly asked Questions

Game Theory .net

Glossary of game theory terms:

Glossary of Game Theory Terms

--------------------------------------------------------------------------------

Here are two essays about games that contrast what happens when one has "games against nature" rather than zero-sum games and the complexities that non-zero-sum games illustrate beyond what happens in the zero-sum case.

Games Against Nature and Non-Sero-sum Games

Challenges in Understanding Non-Zero-Sum Games

--------------------------------------------------------------------------------

This homework should be submitted for grading.

Fifth Homework Problem Set

--------------------------------------------------------------------------------


Here are two expositiory articles about voting games that I wrote a while back for the American Mathematical Society:

Voting Games: Part I

Voting Games: Part II

Here are some basic definitions about weighted voting games and some problems to think about in terms of weighted voting games.

Weighted Voting Games and Power Indices

--------------------------------------------------------------------------------

One of the most interesting of ways that mathematics has been used in the behavioral sciences is related to bankruptcy questions. The basic idea is that one has a situation where claims are being made against an asset (perhaps a fund for damages after a hurricane) where the size of the claims exceeds the amount to be dispersed. The issue is what is a fair way to disperse the funds. Below are pdf files of essays about bankruptcy that I wrote for COMAP's newsletter Consortium as well as some other materials.

Consortium Article (COMAP) on Bankruptcy (pdf)

Second Consortium Article (COMAP) on Bankruptcy (pdf)

The Talmudic Method

AMS Feature Column article about Bankruptcy

--------------------------------------------------------------------------------

This is a collection of problems that will serve as a review for the final examination. We have covered elections and votings, matching markets, basic graph theory, weighted voting, bankruptcy, games (zero-sum and non-zero-sum), and apportionment. The problems are rather mechanical and the goal is to have you learn these ideas well enough to want to try teaching them in your own classrooms.

Review for Final Examination

--------------------------------------------------------------------------------

Matthew Jackson who teachers at Stanford (Economics) has written a nice introductory survey of Game Theory that you might find a useful summary and extension for some of the ideas we have looked at. You can download the pdf file from this site.

Matthew Jackson's Basics of Game Theory (pdf file)

--------------------------------------------------------------------------------

Bamkruptcy problems arise when claims agains a "resource" exceed the size of this resource. As with the case of elections many mehtods suggest themselves which have appealing aspects, but result in different settlements for the claimants. This leads one to consider which are the important fairness principles one wants a "good" method to obey. As we saw in the past there are too many desirable propoerties for a single method to deliver them all. Hard choices have to be made. The mathematics involved with the methods themselves is nothing more than some arithmetic and simple algebra.

Notes and Examples of Bankruptcy Methods

Practice Problems involving different methods of bankruptcy

--------------------------------------------------------------------------------

We have by now looked at many fairness questions where the basic framework is that we have a "resource" that is to be distributed to claimants fairly. The objects to be distributed (the resource) can be homogenous (like water or money) or inhomogenous (like a cake with frosting and sugar flowers on top, a painting, or a house). Sometimes the object is infinitely divisible and sometimes it is not. In the apportionment problem we have objects that are indivisible and the number of these items is a positive integer. The usual version of the problem is the seats in a legistlature (parliament). The claims are made on the basis of populations of regions (states) or the number of votes that a party receives. Though the mathematics involved on the surface is only arithmetic, the theory of apportionment and how it is applied is very "detailed." Apportionment problems can also be viewed through the lens of fairness-properties, which is what led to the Balinski-Young theorem about population monotone methods that obey quota.

Apportionment I

Apportionment II

Adams, Webster's and Jefferson's Apportionment Methods - Example

The two articles on Apportionment for the AMS Feature Column were combined and posted here by Warren Smith, on his Range Voting site. Note in particular the example involving 3 states that shows that Hamilton's "Largest Remainder" method violated population monotonicity and house monotonicity (which is less serious). This example is in the second column.

Combined AMS Feature Column Articles about Apportionment Problems and Fairness

Unfortunately, the combined article above has some "glitches" and so you may want to look at the originals, though the formatting is more annoying. Happily the current Feature Column formatting is much better.

My First AMS Feature Column Article About Apportionment

My Second Feature Column Article about Apportionment

--------------------------------------------------------------------------------

Material added in Summer, 2012

--------------------------------------------------------------------------------

Here are links to two very nice expository articles (pdf files) about how Gale/Shapley is used in the real world market of pairing medical students to hospitals where they can carry out there residency. The articles appeared original in SIAM News in 2003.

Medical Students Matching Problems

Improving over Gale/Shapley for Medical Matching Problems

--------------------------------------------------------------------------------

Here are two sets of "mechanical" exercises to cement your skill in solving bankruptcy problems and in using a variety of different methods to decide the winner of an election which involve preference ballots.

Practice Bankruptcy Problems

Practice Election Problems

--------------------------------------------------------------------------------

This is a brief list (with apologies to all the other wonderful books in this area) of important books about games, fairness, and elections. It also includes the important desirable features of a fair division scheme.

Important Books on Fairness, Games, and Elections

--------------------------------------------------------------------------------

Mathematical modeling has interesting connections to other topics mathematicians and mathematics educators are interested in, namely, problem solving and estimation. In honor of July 4th here is a note with a poll and activity to probe the issues related to modeling, estimation, and problem solving.

Hot Dog poll/activity

--------------------------------------------------------------------------------

There are many measures of central tendency in statistics (which single number "presents" a data set "best." Examples include the arithmetic mean, geometric mean, harmonic mean, mode, median, and mid-range value. When one wants to locate a facility (medical center, public lavoratory, fire house, etc.) one often desires to choose a "central" location so perhaps it may not be surprising that there are connections between statistics and facility location issues.

Facility Location and Statistics

--------------------------------------------------------------------------------

It may be worth the time to practice your understanding of the plurality, run-off, sequential run-off, Borda count, and Condorcet methods by doing the problems here. There are also questions that get at whether there might be "general theorems" involved in questions related to elections.

Practice using different election methods

--------------------------------------------------------------------------------

Elections and voting are the cornerstones of a democratic society. There are an amazingly large number of settings where American are involved with voting. We vote for local, state and federal officials, in some cases judges, and within our workplaces and educational institutions. There are also votes within legistlatures, clubs, and other "group structures." One can spend a whole lifetime studying mathematical insights into voting and elections. The mathematics involved covers the full gamut of mathematical tools.

Modeling the winner of an election

--------------------------------------------------------------------------------

How would you model the friendships you see among a collection of people? Would it be helpful for some purposes to use a graph or perhaps some other geometric structure?

Modeling the Notion of Friendship

--------------------------------------------------------------------------------

In order to makes decisions one has to consider the various choices of actions that one can take and be able to understand which of these actions you consider as better. There are many aspects to this choice environment and this activity about probing your personal feelings about particular kinds of fruit my help see the complexities involved.

Making choices-paired comparisons

--------------------------------------------------------------------------------

Here is a one one page introduction to the idea of a graph model. These are geometric diagrams which consist of dots (representing objects) and line segments which indicate relationships between the objects.

One Page Introduction to Graph Theory

--------------------------------------------------------------------------------

Material added in Fall, 2011

This brief note is a collection of modeling problems designed for teachers inspired the recent visit of hurricane Irene to the NYC area.

Some Modeling Problems related to Hurricane Irene

--------------------------------------------------------------------------------

Material added in Fall, 2010

These materials are in the general area of fairness and equity problems.

--------------------------------------------------------------------------------

Here are some notes about the Brams-Taylor Adjusted Winner method.

Notes on the Brams-Taylor Adjusted Winner Method

These notes deal with the method of solving bankruptcy problems that is referred to as the Talmudic Method.

Talmudic Method for Solving Bankruptcy Problems

--------------------------------------------------------------------------------

Material added in August (Fall), 2009

These materials are in the general area of urban operations research problems.

-------------------------------------------------------------------------------

You can download a pdf file version of five modeling questions (each one of which can typically be solved in a single high school or college classroom period. The problems are based on the same "data" which consists of a grid graph with 6 sites singled out. The problems give rise (when scaled to realistic size, and to other settings) to heavily studied questions in "urban" operations research. You can find html versions of similar things if you scroll down to the urban operations research section below.

Vehicle Routing Activity

This activity is to suggest one of the many urban operations research problems which involve the routing of vehicles. This example centers around that gas must be delivered from a "depot" to the individual gasoline stations that get their gas supplies from this depot. This activity asks some questions but does not actually discuss the algorithms that have been developed to solve these kinds of problems. This activity is related to issues about bin packing and the traveling salesman problem.

------------------------------------------------------------------------

These notes treat in skeletal form information about the chinese postman problem, traveling salesman problem, minimimum cost spanning tree, and maximum cardinality and minimum cost weighted matching problems in urban settings.

Urban Operations Research Problems

--------------------------------------------------------------------------------

Materials added for Spring, 2009.


-------------------------------------------------------------------------------

Modeling Situation 1: Food Production

Notes: Modeling Session 1

This brief note discusses some ideas related Modeling Situation 1 and the modeling process in general.

Notes: Modeling Session 1; Part II

This brief note discusses some ideas related Modeling Situation 1 and the modeling process in general. Specifically, the issue of finding data and information that is used in model construction is raised.

Modeling Situation 2: Election Decision

Notes: Modeling Session 2; Elections and Voting

This brief note discusses some ideas related Modeling Situation 2. Different election decision methods give rise to different winners and this means that one has to try to think of ways to assess the pros and cons of different methods. Many nice lessons for K-12 education can be based on election methods and voting ideas. When there is no Condorcet winner for an election what should be done to make the election method "decisive." When there is a Condorcet winner is this the best method?

Practice 1: Election Methods

You can practice your understanding of how plurality, run-off, sequential run-off, Borda Count, Condorcet, and Baldwin work as election methods on an example here. (The ballots are ordinal preferential ballots.) The problems lead in the direction of axiomatizing properties of elections that make sense from a fairness point of view.

Pairwise Preference Matrix

This is a brief note about the pairwise preference matrix and how it can be used in conjunction with the computation of the Borda Count winner and the Condorcet winner (if there is one).

Practice 2: Election Methods

You can practice your understanding of how plurality, run-off, sequential run-off, Borda Count, Condorcet, and Baldwin work as election methods on an example here. (The ballots are ordinal preferential ballots.) The problems lead in the direction of axiomatizing properties of elections that make sense from a fairness point of view. There is also the chance to practice the construction of the pairwise preference matrix and the anti-plurality method is mentioned.

What is Utility?

In many social choice and game theory settings there are payoffs for the outcomes to the participants. While these payoffs sometimes can be thought of as money, psychologically the same amount of money can mean different things to different people. The concept of tility is an attempt to deal with these complexities.

Notes: Modeling Session 3; Elections and Voting; Arrow's Theorem

This note talks briefly about Arrow's Theorem, fairness axioms for election decision methods, and strategic voting. Strategic voting refers to voting for a ballot which reflects something other than your sincere feelings because it will give you a more favored outcome. This can be done when you know what the decision method being used is, and when data about how other voters might vote is available.

Reversing Ballots in Elections Decided by Point Counts Based on Position

Perhaps unintuitively some elections methods yield the same choice (with all outcomes not tied) for society when a set of ballots are totally reversed.

Seemingly nice methods can display unintuitive behavior

In conjunction with trying to provide insight into Arrow's Theorem this note gives examples of "attractive" election methods which show unintuitive behavior.

Notes: Modeling Session 4; Elections and Voting; Weighted Voting

This note talks about an additional fairness condition, called Majority, that some would say should be obeyed by a "reasonable" election decision method. Although much more could be said about "election decision methods" we will move on to another phenomenon that occurs in voting situations. Namely, that votes are being taken by "players" (legislators) who represent groups of different population or economic power. To deal with situations of this kind, weighted voting is sometimes used. The idea is to have each player cast a "block" of votes at once, called the weight of the player. This situation arises in the Electoral College and many of the governing bodies of the European Union.

Practice 3: Weighted Voting Games

Here you can get a chance to practice problems involving the concepts of winning and minimal winning coalitons in a weighted voting game, as well as computing the Banzhaf and Shapley voting power for a weighted voting game.

Banzhaf Power Templete

One can use the templete here to compute the Banzhaf Power of players in weighted voting games with 3 or 4 players.

Notes: Modeling Session 5; Weighted Voting and Voting Games

Here are some comments about situations where weighted voting occurs and some of the pitfalls and unintuitve aspects of weighted voting games.

Inequivalent Weighted Voting Games

This note has all the inequivalent wieghted voting games (which make some sense in practice) with 4 or fewer players. The weighted voting, minimal winning coalitons, and Shapely-Shubik power vector for each game is given.

Weighted Voting Investigation

This note proposes an "open question" which may be of interest to you, or if you teach, to your students. The question involves representing weighted voting games in a way that shows the Banzhaf power relations to the players.

Modeling Situation 3: Traffic Control

Modeling Situation 4: Fair Games

Modeling Situation 5: Bankruptcy

Notes: Modeling Situation 6: Swimming the Atlantic

Modeling Situation 7: Apportionment

Modeling Session 6: Weighted Voting and Apportionment

Some ideas about weighted voting are given here, including the definitions and statement of the theorem of Alan Taylor and William Zwicker about when a voting game can be represented by a weighted voting game. The idea involves the trading of players between winning coalitions. Also, basic ideas about the apportionment model are developed. How should an integer number of seats, which must be assigned to claimants in integer amounts, be assigned based on the size of the claims put forward by the claimants?

Apportioning Seats in the House of Representatives

This is a brief essay about some of the historical and mathematical issues which come up in apportioning the American House of Representatives.

Apportioning Seats in Parliament Using Adams, Webster, and Jefferson's Methods

This essay shows some details of Adam's, Webster's and Jefferson's Methods for apportioning a legislature.

Practice Problems Involving Apportionment Methods

Here is a chance to practice some apportionment methods on some "toy" problems.

Modeling Check List

Modeling Session 7: Apportionment

This note has some information about apportionment models in classical (how many seats does a party get in a parliament based on the votes for the parties) as well as other settings. It is important that apportionment methods be viewed as fair which requires a way to judge whether or not one apportionment is better than another.

Modeling Session 8: Apportionment

Some additional comments on Apportionment

Zero-Sum Matrix Games

Three problems are posed involving payoffs in a two player game, where each player can choose two actings, and where the payoffs to the players add to zero. Our goal is to try to determine when a game of this kind is fair.

Modeling Session 9: Apportionment

This note offers extensive references on apportionment problems as well as specific examples showing how different measures of optimality can be used to defend different apportionment methods. The approach developed here is whether or not the transfer of a seat from one state to another makes the measure smaller or bigger. A very different approach is a global optimization approach.

Practice: Voting Weighted Voting and Apportionment

This collection of problems is designed to develop basic skills with regards to apportionment problems, weighted voting, and election methods.

Modeling Session 10: Solving Zero-Sum Games

This brief note shows how to solve zero-sum 2x2 games where there is no saddle point, and design an optimal spinner to play these games in the "best" fashion.

Modeling Session 11: Non-Zero-Sum Games

Matrices for Chicken and Prisoner's Dilemma, two very important "paradoxical" games are shown because they seem to test the limits of "rational" behavior.

Modeling Session 12: Non-Zero-Sum Games and Games in Extensive Form

These are notes about games in extensive form which offer lots of ways to model conflict situations, including games with a dynamical quality (e.g. reactions of what player 2 can do to what player 1 has done). A brief discussion of Rheinhard Selten's work on extending that of John Nash is given.

Final Review

Sample review problems for a summatory examination that has voting and elections, apportionment, weighted voting, games, and bankrupcty problems.

Modeling Session 13: Bankruptcy Problems

Some notes about the problem of distributing a quantity E to claimants whose claims exceed E. Bankruptcy like problems arise in the distribution of water, or emergency funds, as well as problems concerning the funding of an amount E by collecting taxes from different income groups.

Teaching Mathematics Using Themes Vs. Techniques

The brief essay suggests the advantages, especially in a modeling context, of teaching mathematical ideas using "themes" as an organizing principle.

Downloads Available of Articles about Preferential Voting Systems

You can download for free from this site articles from the British journal Voting Matters which deals with voting systems based on preferential ballots.

--------------------------------------------------------------------------------

Older Materials

--------------------------------------------------------------------------------

Syllabus

--------------------------------------------------------------------------------

A short list of excellent books about fairness models is given below.

Bibliogrpahy of books about fairness and equity

--------------------------------------------------------------------------------

A brief account of cake cutting algorithms is given at the Mathworld site, and there is an excellent list of recent references for those who want to pursue this topic in more detail.

Cake Cutting

--------------------------------------------------------------------------------



A very rich set of mathematical ideas emerge from working on the modeling questions/situations raised below.

Modeling Situations

These situations give rise to many important problems in graph theory, operations research, and other parts of mathematics. For notes about what the key ideas are that these problems lead to, look at the following:

Notes on OR Situations

For the situations 5 and 6 which are not mentioned in the document above, the relevant notes are: Situation 5, Voronoi diagrams; Situation 6, Robbin's Theorem concerning when it is possible to orient a connected underdirected graph, so that the resulting digraph becomes strongly connected.


--------------------------------------------------------------------------------


This election example introduces a notation due to Duncan Black (British political scientist) for expressing preferences of a "voter" in a situation where choices must be ranked by an individual voter. Choices listed towards the top are preferred by the voter.

Election Example


--------------------------------------------------------------------------------

This glossary offers a variety of terms that arise in the use of mathematics to study fairness questions. The terms are drawn from social choice theory (voting and elections), apportionment, and other domains.

Glossary of Fairness Terms

Another glossary

Glossary of Voting/Elections Terminology


--------------------------------------------------------------------------------

One of the most remarkable theorems that mathematics has contributed as an insight into political science and economics is a result of Kenneth Arrow, who won the Nobel Prize for his work. The basic result is that for decision methods that produce rankings when there are three or more alternatives, there is no decision method which obeys a short list of reasonable "fairness" conditions.

Elections and Arrow's Theorem

--------------------------------------------------------------------------------

Practice I: Traversability of Edges in Graphs

--------------------------------------------------------------------------------

Practice II: Voting and Elections


--------------------------------------------------------------------------------

Practice III: Heuristics for the TSP



--------------------------------------------------------------------------------

Practice IV: Minimum Cost Spanning Trees


--------------------------------------------------------------------------------

Practice V: Minimum Cost Perfect Matchings


--------------------------------------------------------------------------------

Practice VI: Game Theory


--------------------------------------------------------------------------------

Practice VI: Zero-Sum Games


--------------------------------------------------------------------------------



When people create rankings by making comparisons between various alternative choices, can one depend on the fact that they will do this accurately?

Paired Comparisons

--------------------------------------------------------------------------------

The essay below discusses the notion of utilities and complements the discussion above about preference between candidates, fruit, or other altneratives to be compared.


Utility


--------------------------------------------------------------------------------

An apportionment example using Webster, Jefferson's and Adam's Methods is worked out, Using the "divisor" approach to these methods. For relatively small house sizes one can usually do problems of this kind using "rank index" approaches to divisor methods.

Apportionment Example using Webster, Adams, and Jefferson's Methods

--------------------------------------------------------------------------------


Here are basic ideas about the traveling salesman problem, finding a minimum cost tour visiting a collection sites.

Traveling Salesman Problem



--------------------------------------------------------------------------------

Many verbal problems/situations can be jumping off points for modeling problems. A collection of problems which lead to a variety of "geometrical" (in the broadest sense) problems can be found below.

Problems which can be modeled using geometrical tools


--------------------------------------------------------------------------------

This essay discusses some of the abstract principles that one might expect to hold in problems that involve fair allocation or division problems.

Fairness Principles


--------------------------------------------------------------------------------

Here is a sampler of fairness and equity problems for a general audience or to introduce a class in middle school or high school to some problems that lie within the domain of what mathematicians are studying that are related to fairness. Fairness Sampler

--------------------------------------------------------------------------------

This essay discusses some mathematical models in political science. The public is accustomed to the effectiveness of using mathematics in physics, engineering, chemistry and biology. Howver, the fact that mathematics provides major insights into the social sciences is less appreciated.

Mathematical Insights into Political Science


--------------------------------------------------------------------------------

Here are some introductory comments about modeling elections and voting.

Elections and Voting

--------------------------------------------------------------------------------

Robert Aumann won the Nobel Memorial Prize in Economics for his contributions to game theory and fairness questions.

Robert Aumann: Nobel Prize Winning Mathematician

Many of Robert Aumann's very provocative and insightful papers can be found via his web page:

Robert Aumann's Publications

--------------------------------------------------------------------------------

Mathematical Modeling Resources of Various Kinds


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

Urban Operations Research


--------------------------------------------------------------------------------

A variety of expository articles dealing with mathematical models in the general area of operations research have appeared in the American Mathematical Society's Feature Column:

a. Urban Geometry (This essay deals with edge traversal problems in graphs: Euler circuits and the Chinese postman problem.)

b. Sales and Chips (This essay deals with the Traveling Salesman Problem, which involves vertex traversal in weighted graph.)

c. Trees: A Mathematical Tool for All Seasons (This essay includes a treatment of minimum cost spanning trees.)

Other OR Materials:

d. TSP (This page collects information about the TSP (Traveling Salesman Problem) and related problems.)

e. Materials for Middle School and High School Teachers (This web page has links for materials, some of them related to modeling, for middle school and high school teachers, including some notes prepared for a "pi day" celebration.)

f. Facility Location Unit (1-dimensional) for 6th graders; Location of a mobile vaccination center

g. Connection between facility location and statistics (This essay which supports the previous notes, deals with ideas connecting facility location problems and statistical concepts such as the mean, median, and mode. The audience is student in grades 6 and higher.)

--------------------------------------------------------------------------------

Fairness Models



A variety of expository articles dealing with mathematical models in the general area of fairness and equity have appeared in the American Mathematical Society's Feature Column:

a. Voting and Elections    (This is a primer about the history of mathematical insights into elections and voting systems.)

b. Apportionment I    (This is the first of a two part essay about apportionment problems, such as deciding how many seats to give each US state in the House of Representatives based on the populations of the states.)

c. Apportionment II    (Part II of a survey essay about apportionment problems.)

d. Voting Games I    (An introduction to votings games such as the Electoral College and the weighted voting system used by the European Union.)

e. Voting Games II    (More about voting games and weighted voting.)

f. Resolving Bankruptcy Claims (A survey of how to resolve bankruptcies, situations where there are not enough assets to pay off all of the claims against these assets.)

g. Rationality and Game Theory    (Game situations which show that the predictions about what constitutes "rational behavior" is not always followed by everyone.)

h. The Process of Electing a President    (An outline of the many aspects of using modeling to get insight into the process of votings and elections.)


Other Fairness Materials:

i. William Thomson at the University of Rochester (Economics) has some wonderful papers (especially survey papers) about various aspects of fair division, fair allocation and related topics.

William Thomson's Papers

j. Herve Moulin at the University of Texas (Economics) has some wonderful papers (especially survey papers) about various aspects of fair division, fair allocation, voting, and related topics.

Herve Moulin's Home Page

--------------------------------------------------------------------------------
You can find a broad list of topics dealing with fairness in this "syllabus" for a college level "humanities course" about fairness.

Topics for a Fairness Course

In the United States the President is not elected directly through popular vote but using the Electoral College. The Electoral College has 51 players who cast different numbers of votes, loosely proportional to the population of the regions the "electors" represent. Here is an example to show that a naive way of assigning weights to voters in a weighted voting game can result in "players" who have positive weight but no power!

Weighted Voting Example

--------------------------------------------------------------------------------

Many sites promote voting systems other than plurality. In particular, the Range Voting web site offers lots of information about voting systems.

Rangevoting Web Site

There are alot of materials about voting on the range voting web site. Here is the site map which will help you get some idea of this range of materials.

Range Voting Site Map

Here is a collection of valuable miscellaneous links related to voting, available from the rangevoting web site.

Miscellaneous Links from at Rangevoting

--------------------------------------------------------------------------------


General Modeling



--------------------------------------------------------------------------------
The Consortium for Mathematics and Its Applications has produced a wide array of excellent materials that deal with all aspects of Mathematical Modeling.

COMAP

This includes many modules, and a journal (UMAP Journal) devoted to both research about mathematical modeling and educational issues related to mathematical modeling. Its "membership privilege" journal, published twice a year has lots of articles and materials about modeling.

COMAP's Journals



--------------------------------------------------------------------------------

A wide variety of mathematical modeling problems at various levels of difficulty and with a variety of levels are available on the web. There are also a variety of contests for high school students and college students about mathematical modeling. Some of these contests are run by COMAP and another by SIAM, the Society for Industrial and Applied Mathematics.

Modeling Problems

Modeling Contests

Moody's Mega Math Challenge (Administered by SIAM)

SIAM's List of Math Competitions (including modeling competitions)


--------------------------------------------------------------------------------

Return to Joseph Malkevitch's Home Page