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 offtered by Mathematics for America in conjunction with its Professional Development and Outreach in the New York City area.

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

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