Mathematical Game Theory (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 "Game Theory." The philosphy of these courses is to cover as broad a range of topics with a game theory 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.

Game Theory, here, refers primarily to the analysis using mathematical tools of conflict situations as they arise in business, economics, and political science. The subject was "put on the map" by the work of the mathematician John Von Neumann and the economist Oskar Morgenstern. However, there will also be a brief treatment of what have come to be called combinatorial games. Nim is perhaps the best known of such games. These ideas are related to a mathematical understanding of games such as chess and Go.

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

Generic Syllabus

Syllabus

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

Some new materials added for Spring, 2016.

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

Syllabus for 2016

Syllabus

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

Here is an account how ideas from game theory have proved useful in the analysis of energy consumption issues.

Game Theory and energy consumputon

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

The items below relate to some materials and practice involving two-sided markets, stable matchings, and the Gale/Shapley deffered acceptance algorithm. One theoretical aspect of these ideas is that sometimes markets do not need prices to function.

A matching problem with 10 stable matchings!

A practice problem involving Gale/Shapley

A practice problem involving Gale/Shapley

Some notes on Gale/Shapley

An American Mathematical Society Feature Column article about school choice and Gale/Shapley. There are some other Feature Column items on the same topic.

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

A tribute to John Nash has appeared in the Notices of the American Mathematical Society.

A tribute to John Nash which appeared in the Notices of the American Mathematical Society

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

Here are some problems for you to practice your skill in applying some of the more important bankruptcy model solution methods.

Bankruptcy practice problems

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

April is Mathematics Awareness Month, and York celebrated with a Math Day. I prepared a talk about mathematics and electing the US President. This set of slides might provide a bit of a summary for ideas related to voting and mathematics.

Slides for Mathematics Awareness Month talk about Mathematics and Electing the President

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

You can find quite a bit of detail about bankruptcy problems in Ein-Ya Gura's Game Theory book. Gura's doctoral thesis advisor (Michael Maschler) was one of the persons who helped put this problem on the "mathematical map." You can also find a "telegraphic" account of many of the important ideas in this column that I wrote for the American Mathematical Society.

American Mathematical Society Feature Column article about bankruptcy questions

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

Bankrupcty problems, where claims are made but the assets available to pay them off are less than the total of what is being claimed, are especially appealing. Many different algorithms, which yield different answer, but have a natural basis in some fairness idea are easy to invent, and the problems relate to a wide variety of skills that come up in traditional K-12 curriculum.

Bankruptcy Problems and Methods

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

Practice Problems for the Final.

Practice Problems for the Final

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

Honoring Lloyd Shapley's memory, Alvin Roth has written a brief appreciation of Shapley's work. Roth shared the Nobel Prize in economics with Shapley.

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

After one uses some method to decide how many "districts" there should be in a legislative environment one has to draw fair districts, which also make "sense." There is a long tradition, known as gerrymandering where dstricts are designed for political reasons rather than to achieve fairness. There is a large mathematical literature related to this issue, including geometrical work on what it means to have "compact" districts, something that many courts, seeking fairness, have asked for.

This item in the Washington Post is more "informal" but makes some dramatic points.

Example of gerrymandering

Here is another expository account of some of the issues involving gerrymandering.

Different ways to gerrymander

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

Homework Assignment 5: Spring 2016

Homework Assignment 5

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

Here are some notes about voting games, weighted voting games, power indices for such games, and some thought about the issue of the dynamics of coalition formation in contrast to the power of the players.

Coalitonal Games

You can find templates for Banzhaf Power calculations and Shapley-Shubik Power below:

Template for a Banzhaf Power Index Calculation with 4 players

Template for a Shapley-Shubik Power Index Calculation with 4 players

Some practice problems involving weighted voting:

Weighted voting and power indices

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

The pdf file linked below provides an assessment of what game theory has accomplished since its birth and some of the issues that would represent important progress if resolved. Some parts of the article are technical but the major issues are raised in way that does not require knowing lots of technical matters.

"Whither Game Theory?

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

While the carrying out of apportionments based on rounding rules is based only on arithmetic it has a nitty gritty quality. Here is an account of an example in some detail for Webster, Jefferson, and Adam's methods.

Rounding rule apportionment: Jefferson, Webster, and Adams

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

Llyod Shapely, whose background was in mathematics, and perhaps more than other person has been responsible for showing the breadth and depth of game theory, died on March 12, 2016. The concept of the Shapley Value which comes up in so many corners of game theory deservedly honors his seminal idea in assigning a value to a wide class of games.

Obituary for Lloyd Shapley

Some additional comments about Shapley's death collected on the blog of Alvin Roth with whom Shapley shared the Nobel Memorial Prize in Economics:

Comments on the death of Lloyd Shapley

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

The apportionment problem calls for assigning integer numbers which sum to a positive integer h (the number of seats in a legislature) based on a "vector" of votes for parties or percentage populations of states. There are many other applications of this fascinating model, which in the end is concerned with the fact that one can't assign fractions of a legislative seat out, only whole integer numbers. Hamilton's method is based on assigning an integer "lower quota" of seats and if not enough seats have been assigned to assign the remaining seats in the the order of the size of the fractional parts left. Divisor methods (Webster, Jefferson, Huntington-Hill, Dean and Adams) are based on rounding rules. Webster uses the usual rounding rule, while Jefferson always rounds down and Adams rounds up. These two methods (nearly) always require using an adjusted quota to assign the right number of seats but Webster also often requires adjusting the quota rather than merely using the number of persons per representative as a "divisor." By a lovely theorem of Huntingon, one can also use a table to implement the assignment of seats using a particular divisor method. This topic has lots of work with decimals and percentages, as well as relating to ideas about relative versus absolute differences. The US versus European democracy versions of the problem is more complex because each state must by Constitutional mandate be assigned at least one seat.

More notes on Apportionment Problems

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

Here are some practice questions asking you to count ordinal ballots using different election methods. A question of mathematical interest is if one takes the same election and increases the number of votes by a constant for each ballot type appearing, how does this affect the winner of the election using a particular method? For most elections in the real world one might not expect different methods to give different winners, however, one can construct examples of there there happens. The 2016 Republican Primary elections has lots of food for thought about what is a good/fair way to have the candidate who runs for President be a choice that large members of the Republican party want to be on the ballot in the November, 2016 election.

Election Methods Practice

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

Fourth homework assignment, this one to give you practice with counting ballets for the same election using different methods.

Homework 4: Elections

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

Many symmetric non-zero sum 2 person games exist where a Nash equilibrium is unattractive because there is a better outcome for both players. This very recent article has a discussion of some interesting versions of such games as well as a large list of references to the biological and game theory literature which relate to have cooperation between the players might evolve in multiple plays of such games. (Note some games seem reasonable as described for a single play but perhaps not as games that are played over and over again.)

Evolution of Cooperation

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

In elections for European legistlatures voters typically vote for parties rather than individuals to hold the seats. Thus, in a 120 legistlature, parties A, B, and C may get 44%, 32%, and 24% of the votes. The question is how many seats each party should get in the legislature. In the end it all comes down to fractions! In the US, how many seats each state gets in the House of Representative based on the state's population is a similar problem. A complication is that the US Constitution requires every state get at least one seat. Such problems arise in many areas and have a surprisngly complex mathematical structure when trying to do the assignments fairly.

Apportionment Problems

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

Voters express their opinions about alternatives in an election using a ballot. While people rarely have experiences with ballots other than those where one is asked to vote for a single candidate (alternative), mathematical modeling shows the there are many interesting kinds of ballots. These ballots in turn lead to different ways to count the ballots, which give rise to mathematical results, such as Arrow's Theorem, that deal with desirable axioms that different vote counting methods might obey. Approval ballots are being more widely used, and election reformers often suggest using ordinal ballots rather than the "standard" ballot.

Different Kinds of Election Ballots

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

To produce a ballot an individual voter must decide about his/her feelings and preferences among the choices that have to be voted on or decided among. This activity is designed to show some of the complexities of doing this when there are many choices. Many people as individuals show intransitvies in their preferences in practice even when in theory they find it hard to believe this will happen to them. Often this is because there are different "inconsistent" scales on which items are being evaluated. One gets accustomed to the fact that in multiple candidate elections, just as in tournaments, there can be intransitivies of two-way races (matches). It seems more surprising that this can happen for individuals but often does.

Paired Comparison Activity

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

Here is an American Mathematical Society "Feature Column" article that I wrote that deals with the mathematical aspects of voting and elections. It includes very brief information about some of the many people who contributed to the mathematical theory of elections. Other feature column articles I have written deal with games, and other topics treated in this game theory course.

American Mathematical Society Feature Column about voting and elections

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

Here is a very brief account of some of the different methods that can be used to decide an election where the voters produce ordinal preferential (some times called ranked) ballots.

Brief descriptions of some important voting methods

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

Here is an election to practice on using some of the "popular" methods of deciding an election where ordinal preference ballots are available. These methods include plurality, run-off, sequential run-off, Borda, and Condorcet. Other interesting methods are Bucklin and Coombs, but there are surprisingly many appealing methods that one use. Often these methods yield different winners.

Practice different methods for finding the winner of an election

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

The mathematical theory of elections and voting is an especially appealing topic at all levels of the education system, and there there still is a large amount of research being done on the underlying mathematics. Here is an activity to show that different people typically have different feelings about who "deserves" to be elected based on a set of ballots produced by voters. Here the ballots are ordinal preference ballots.

Election Activity

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

Homework 3: 2016

Homework 3

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

Some more game theory problems for practicing basic ideas.

Game Theory Practice

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

Here is a biographical essay about John Nash. One remarkable thing about him was that he suffered from mental illness for a large part of his life.

John Nash

Wikipedia biographies of Nash and other prominent game theorists are listed on this Wikipedia page. As you can see, distinguished game theorists are from a large variety of countries.

List of Wikipedia biographies of game theorists.

Another Wikipedia list of game theorists, this one longer than that above:

List of game theorists who have Wikipedia articles.

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

Prisoner's Dilemma is a very rich world for mathematics (game theory ideas), mathematical modeling (using mathematics in political science and economics) and psychology (under what circumstances do people cooperate?). Many experiments have been done with very varied payoffs in the cells of the Prisoner's Dilemma game. Whole books are devoted to the subject. For those of you who get the "bug" about learning about these ideas, before looking into research papers and books you might find this encyclopedia article about Prisoner's Dilemma a good entry point into the more technical accounts.

Prisoner's Dilemma

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

Cooperation between people and countries affects the lives of all of us. Game theory ideas, in particular, the Prisoner's Dilemma game offers a theoretical and experimental window into understanding how cooperation and trust might "evolve." A pioneer in this study was Robert Axelrod, and he wrote several books about his ideas and experiments. Although Axelrod majored in mathematics as an undergraduate his training is as a political scientist. Furthermore, he does not specialize in game theory. An extraordinary "summary" of what has been learned from Axelrod's work is available in this old book review of one of Axelrod's books by the game theorist Ken Binmore.

Comments on Robert Axelrod's work on Prisoner's Dilemma by Ken Binmore

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

Nash equilibria are a fascinating topic and offer teachers lots of ideas for ways to support topics in the traditional K-12 curriculum in their classrooms. The basic idea is playing a game in way that neither player has a temptation for deviating from what they are currently doing, because if the other play also does not deviate neither player does better.

Nash Equilibria

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

Homework Assignment 2: Spring 2016

Homework Assignment 2

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

Here is a pdf version of an expository paper that appeared in the Proceedings of the National Academy of Sciences about the Nash Equilibrium and its significance.

Expository Account of the Nash Equilibrium written by Charles Holt and Alvin Roth.

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

More practice problems to help you think through issues involving zero-sum matrix games.

Practice problems involving zero-sum matrix games

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

To get the flavor of what people are currently doing as research in the area of game theory you might be interested in the announcement about the 12th European Meeting on Game Theory. Many of the topics that are listed as ones for talks at this conference we will be exploring in our course.

12th European Meeting on Game Theory

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

A major early contributor to the theory of non-zero sum games was John Nash, who sadly was killed in an automobile accident on his way back from accepting the Nobel Prize in Economics in Stockholm. Nash provided a proof for the existence of what are now known as Nash Equilibria for a broad class of games. However, some games have many Nash Equilibria and in some cases none of the equilibra are attractive as ways to play the game. So non-zero-sum games offer a lot of modeling and theoretical opportunties to get insight to strategic thinking and approaches to what constitutes rational play, even for matrix games. The details of the theory are complex but once one masters the theory of zero-sum games there are many instructive examples to try to understand.

Non-zero Sum Games

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

The theory of zero-sum games is very rich, with lots of connections with topics in K-12 mathematics, including probability theory. One can also look at making decisions in a game theory framework. One can take actions and depending on the the state of "nature" various payoffs occur. For example one can drill for oil in a certain location and one find nothing, only natural gas, or a large reserve of oil. There are lots of interesting issues here related to risk aversion and how one measures "utility." One can also look at non-zero sum games. Here the situation is much more complex than for zero-sum games because various ways of playing "rationally" lead to outcomes that are not attractive. In particular, the "paradoxical games" know as Prisoner's Dilemma and Chicken are hard to play because their non-intuitive aspects. These games provide reasonable models for union/management negotiations and conflicts between countries.

Games Against Nature and Non-Zero Sum Games

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

Homework Assignment 1: Spring, 2016

Homework Assignment 1: 2016

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

Game Theory Project: Spring 2016

Game Theory Project 2016

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

The ArXiv is preprint server for recent research and expository articles in the fields of mathematics and computer science (and other fields). Within the computer science section of the ArXiv there is a section specifically for papers related to game theory. Mathematics has no equivalent section. Even the titles of these papers will give you some flavor of what directions game theory is going in, and many of them will get easier to read as you learn more about game theory.

ArXiv Preprint Server

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

You can practice with some of the basic ideas about matrix zero-sum gaems (mostly 2x2 case) by thinking about the questions here.

Practice: Zero-Sum Matrix Games

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

This activity is designed to introduce the idea of matrix games and to help you become familiar with some of the issues in playing zero-sum matrix games.

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

Mathematics has provided dramatic insight into the nature of running elections in a "fair way." This activity shows the value of using ballots where voters provide information about their feeling about all of the candidates. However, it turns out that with the same set of ballots, different methods will elect different winners. This is a surprise for those who somehow think that the will of the people follows automatically from the act of voting. The way the votes are counted, the election method uses, also matters. In the 2016 Republican primaries (and Iowa Caucus) there are a very large number of candidates. This strains the ability of plurality voting in getting a nominee that "lots of people" really want.

Mathematics of Elections Activity

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

Various topics and terms in game theory (and names of well known game theorists) that can be used as search strings on Wikipedia or the web.

Game Theory search strings for Wikipedia or the web

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

A very brief introduction to graphs and digraphs (directed graph) using a few diagrams and treating the terms, vertex, edge, path, circuit, valence, degree, indegree, and outdegree.

Brief introduction to graphs and digraphs

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

Some questions to get you thinking about the nature of games, your past expereience with games, and the way one might model games using mathematics.

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

Here is a small sampler of the kinds of problems and issues that are the domain of the part of mathematics that is known as game theory. This sampler does not include examples related to combinatorial games, which is not a part of what is often described as "game theory."

Game Theory Sampler

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

Some course information

Course Information

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

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

Some new materials added for Spring, 2015.

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

Here is an exmaple that suggests that people knowledgeable about game theory use these ideas in situations that involve political confrontations. This article is about the issue of Greek debt but there have been similar speculations with regard to the flareup of tensions in the Ukraine.

Game Theory Related to the Greek Debt Crisis

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

Some new materials added for Fall, 2014.

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

This new game theory web page has some interesting resources and charts some milestones in the history of game theory, including being able to download a copy of Nash's doctoral thesis.

Game Theory web site (Italy)

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

The winner of the Nobel Memorial Prize in Economics is Jean Tirole. Tirole was born in 1953. Among his many contributions to economics, Tirole has done work in game theory. Here is the link to the wiki article about him and his work:

Jean Tirole

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

Some new materials added for Summer, 2014.

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

One of the giants of game theory and optimization theory, Harold Kuhn died at 88 recently. Here is a brief account of his life:

Obituary for Harold Kuhn

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

An active center for Game Theory in the United States is SUNY at Stony Brook. This year celebrates the 25th anniversary of the game theory center there. This year's conference has many stellar speakers and interesting presentations:

Stony Brook Center for Game Theory

25th Anniversity: Stony Brook Game Theory Center

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

Here is a nice feature article about the work of two mathematical economists, originally from Turkey, Tayfun Sonmez and Utku Unver that talks about applications of game theory. These two scholoars have made important contributions to mechanism design and two-sided markets, in particular to the theory of school choice problems.

The work of Tayfun Sonmez and Utku Unver

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

Some new materials added for Fall, 2013.

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

Here is a short collection of problems (pdf file) that is designed to encourgage students to think about problems related to the Gale-Shapley "marriage problem." What is involved is taking the preferences of n men for n women and these n women for the n men and pairing the men and women in a "stable" way. There are many applications to this circle of ideas, including the pairing of hospitals and medical residents. Alvin Roth and Lloyd Shapley recently won the Nobel Memorial Prize in Economics for work related to these ideas. Other materials related to the Gale-Shapley model appear further below on this web page.

An on-line version of the above problems, rather than a pdf file is also available.

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

Some new materials added for Summer, 2013.

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

Here is another game theory journal, this one being open access, which supplements the list of other journals given below:

Games - open access game theory journal

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

The University of Zurich has a group of people who work on mechanism design questions which has close ties to game theory. It is known as the ESEI Center for Market Design (Engineering Social and Economic Institutions). A description of their work can be found here and they have interesting working papers and publications, some of which have educational implications.

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

Here is a handout "sampler" which illustrates some questions in the spirit of mathematical modeling that deal with game theory and fairness situations. The handout is similar but not identical to others found below.

Modeling Situations in Game Theory and Fairness

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

Some new materials added for Spring, 2013.

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

Syllabus, Spring 2013

Syllabus

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

Here is a sampler of problems and situations which are "informed" by ideas from the theory of games. Many game theory problems and models arise from the broader arena of fairness models. Some of the examples I give have strong ties to game theory and/or were pioneered by game theorists but belong to the domain of fairness models. Many fairness problems have lots of "emotional" content (e.g. should women in the military be able to serve in front line combat operations; LSBG issues, access to abortion, etc.) but here I try to restrict myself to game theory and fairness problems which are amenable to mathematical insights, though "political" and "emotional" fairness issues are no less important (and sometimes profit from mathematical analysis).

Game Theory Sampler

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

Here is some course information, as well as links to blogs that deal with game theory, economics, fairness and equity, computational issues, market design, and mechanism design. There is also a link to the American Mathematical Society Feature Column which has a variety of articles dealing with game theory and fairness related issues.

Course Information and Game Theory blogs

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

This note suggests some questions for you related to game theory and equity situations. The questions raise ways to get students in K-12 thinking about the role games play in society and ways that mathematics might be used to get insight into games.

Some questions related to the game theory environment

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

Wikipedia has many articles related to game theory. These articles are available associated with each of a variety of game theory terms provided below.

Game Theory Terminology - Wikipedia

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

Here are some practice problems involving the use of dominant strategy analysis for zero-sum games. Other issues are finding optimal pure strategies versus optimal mixed strategies in zero-sum games. Solving these problems involves the use of elementary probability theory as well as factoring and/or the algebra of linear equations.

Practice Problems: Zero-Sum Games

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

Here are some notes about matrix games which contrast the behavior of games where a dominant strategy analysis can be carried out compared with what a game that does not allow dominant strategy analysis.

Matrix games - the zero-sum case

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

Here is a list with live links of many of the reserach journals that publish game theory and related equity and fairness articles.

Game Theory Journals

After I created the web page above I found a site that did something similar, including issues related to statistics and behavioral economics added to the game theory theme.

Mathematics and Statistics, Game Theory

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

More practice problems involving the basic ideas about zero-sum games.

Practice Problems-2: Zero-Sum Games

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

Graph theory, the study of geometrical diagrams consisting of dots and lines, has proved to be very valuable in all branches of mathematics. A very abbreviated primer of this subject (one page!) is provided.

Graph Theory Primer

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

Here are some practice problems involving the basic ideas about non-zero-sum games. Non-zero-sum games are much more subtle than the zero-sum ones. One needs to understand the difference between pure strategies and mixed strategies, the notion of an equilibrium or stable outcome. These questions try to give insights into these ideas.

Practice Problems-3: Non-Zero-Sum Games

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

Non-zero-sum games lack many of the more transparent nice properties of zero-sum games. One thing that does get retained is the notion of Nash equilibrium. Unfortunately, though, there is no guarantee that playing a Nash equilibrium strategy is an appealing choice, since in many non-zero-sum games there will be outomces that are "Pareto improvements" over a Nash equilibrium. This means that there are outcomes that at least one player prefers and which are not worse for the other player.

Notes on Nash equilibria and Non-Zero-Sum Games

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

Here are some practice problems involving the basic ideas about voting. To construct a mathematical modeling of voting requires one have candidates (choices), voters, ballots (to allow the voters to express their preferences about the choices), and election decision methods (how to use the ballots to decide on a winner, or a ranking for choices). Elections come up in deciding on a governor, a president or a major, but also in choosing what to serve at the company picnic, best picture of the year, or who to hire from a list of candidates for a job. Pioneering work was done by Borda, Condorcet, Charles Dodgson (Lewis Carroll) and Kenneth Arrow. This is a very appealing topic for teaching arithmetic, logic, basic graph theory, etc.

Practice Problems-4: Elections and Election Methods

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

Mathematical modeling is one of the practice standards for the CCSS-M (Common Core State Standards in Mathematics). However, in many people's minds the reason for teaching modeling is further practice with mathematical techniques - solving linear equations, solving quadratic equations, etc. I belive in a broader concept of what modeling is about. In part, it is a way to encourage people to see mathematics as a subject that emphasizes various themes - fairness, optimization, information, etc. While this essay is not directly related to the content of this course I hope that it offers a perspective on how the theory of games and fairness situations might fit into curriculum at all levels.

Thematic Approaches to Mathematical Modeling

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

When one has geographic districts or countries which have very different populations but one needs to have a legistlature to represent the different "locales" it seems reasonable to use a system where each representative casts a different number of votes. It is tempting to have the weights proportional to population but it is easy to see that this can create representatives who are never members of minimal winning coalitions. Such players are traditionally called dummies. So it makes more sense to have weights so that population is proportional to some measure of power. One way of doing this is the use the Banhaf Power, as is done in NY State. The European Union has made extensive use of weighted voting schemes.

Weighted voting and power indices

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

Here are a few "practice" problems for a "final" summatory examination. The emphasis is on being able to do "typical" algorithmic problems that come up in zero-sum games, non-zero sum games, methods of deciding elections, power of players in weighted voting games, assigning an integer number of seats based on "population" (apportionment), the Gale/Shapley deffered acceptance algorithm, bankruptcy, etc.

Summatory Review of Game Theory and Equity Problems

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

The apportionment problem is a mathematical question which deals with assigning non-negative integer numbers of things (legislative representatives, computers, secretaries, etc.) to claimants based on some numerical parameter of the claimants (population of states, percent vote for a party in an election, number of students in the schools of a school district).The classical versions of this problem are apportioning the 435 seats of the US House of Representatives and the problem of assigning seats to a parliament based on the percentage of vote that each party got in an election. Here are some notes about this topic.

Apportionment I

Apportionment II

Apportionment III

The AMS has two Feature Column Articles about Apportionment (happily the more recent columns don't have this rather cumbersome interface) that survey the issues.

AMS Feature Column on Apportionment

Second AMS Feature Column on Apportionment

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

Here are some notes about apportionment, giving claimants a non-negative number of seats in a parliament of fixed size h. The problem arose naturally in two versions. In the US each "state" has to be given at least one seat, while in Europe, each party must be assigned a block of seats in a way that represents its strengh in the election but there is no guarantee that a party that got a small vote will get a seat.

Notes about some apportionment problem methods

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

Here are some additional notes about apportionment. A review of the Adams, Jefferson and Webster Methods considered as divisor methods is given and then it is described how to do the calculations for these methods usings the rank index approach to the computations. I call this the "table" method. This approach is computationally more straightforward.

Notes about some apportionment problem methods

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

Here are some practice problems involving the Webster, Adams, Jefferson, and Hamilton methods of apportionment. See if you can get a feel for why Adams rewards smaller states while Jefferson rewards larger states.

Practice Problems Involving Apportionment

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

Here are some notes about the many different approaches to solving bankruptcy problems. The basic idea is that one has claimants who are owed money from an estate of size E but the claims add to more than E. What amounts should be given to each claimant so that the amounts returned to the claimants sums to E and the amounts given are fair? Many different approaches to fairness come into play and can lead to very different allocations to the claimants. Axioms can be created which try to characterize which properties the different methods to resolve bankruptcy problems obey.

Bankruptcy Problem Modeling

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

Some new materials added for Fall, 2012.

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

Here is a very brief account of the Nobel Memorial Prize in Economics for 2012 which was awarded to the two mathematicians Alvin Roth and Llyod Shapley for their work in game theory.

Nobel Memorial Prize in Economics, 2012

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

There is a society devoted to dynamical games, which publishes a journal and sponsors conferences. The web page for this society is:

International Society on Dynamic Games

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

Some new materials added for Summer, 2012.

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

Teachers often hear the terms, exercises, problem solving, and mathematical modeling. While there is some similarity between these terms they connote rather different things. This essay tries to distinguish between the terms in an informal way, and some of the examples used come from the realm of fairness problems.

Exercises, Problem Solving, and Modeling

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

While carrying out this particular poll is probably of interest only to me and the students who took my game theory course in the summer of 2012, I think it is valuable for teachers to design polls of this kind to help them get insight into the relative appeal of different topics they treat in courses that they teach.

Poll on Course Topics in a Game Theory Course

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

The apportionment problem is a mathematical question which deals with assigning non-negative integer numbers of things (legislative representatives, computers, secretaries, etc.) to claimants based on some numerical parameter of the claimants (population of states, percent vote for a party in an election, number of students in the schools of a school district).The classical versions of this problem are apportioning the 435 seats of the US House of Representatives and the problem of assigning seats to a parliament based on the percentage of vote that each party got in an election. Here are some notes about this topic.

Apportionment I

Apportionment II

Apportionment III

The AMS has two Feature Column Articles about Apportionment (happily the more recent columns don't have this rather cumbersome interface) that survey the issues.

AMS Feature Column on Apportionment

Second AMS Feature Column on Apportionment

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

A voting game is a way specifying how action gets taken in a legislative body by indicating "winning coalitions" - coalitions that can get some action accomplished. One way of doing this is to have each player cast a number of votes called the weight of that player. There is a quota Q, and any collection of players whoses weights sum to Q or more are winning. However, one can have positive weight in such a voting game without haviing positive "power." This happens when a player is not a member of any "minimum winning coalition." A coalition that wins, but when any player is dropped from the coaliton no longer wins. Such a player is called a dummy. There are many power indices which try to measure the "power" of the players in a voting game either in terms of the coalitions the players are members of or the weights they cast. The best known of these are the Coleman Index, the Shapley-Shubik Index, and the Banzhaf Index.

Template for a Banzhaf Power Index Calculation with 4 players

Template for a Shapley-Shubik Power Index Calculation with 4 players

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

Here is a cost allocation problem, typical of many, where towns or people come together to fund a project that will bring them all benefit but would be two expensive for one person (town) to do on its own. So the issue is developing a way to share the costs that is fair.

Cost Allocation: Fairness of Improving a Road

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

Here are a few "practice" problems about bankruptcy problems. The idea is that one has claims against an asset which is too small to pay off all of the claims. What is a fair way to distribute the asset? Just as with elections there are many reasonable systems which often differ in their distributions.

Bankruptcy Problem Methods - Practice

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

Here are a few "practice" problems about election methods. Methods that have either been used in the "real world" or are appealing because a reason that they might produce a "good" winner can be put forward are: pluarality, run-off, sequential run-off, Borda Count, Coombs, Bucklin, and Condorcet. Different methods can produce the same or different winners. There are a lot of topics in the traditional k-12 curriculum that can be taught and/or motivated with elections issues.

Election Methods Practice

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

Here are a few "practice" problems involving the Gale-Shapley, deferred acceptance algorithm, that finds a stable matching between the two sides of a two-sided market. There are suprisingly many appicatiions of this elegant algorithm. With cleverness one can significantly extend the domain of applicability of this algorithm. The "vanilla" version requires no indifference and that not getting "married" is not an option. Depending on whether the men propose or the women propose one gets two potentially different stable marraiges. However, in many cases there are many other stable marriages.

Gale-Shapley Algorithm - Practice

Gale-Shapley Algorithm - Practice 2

Gale-Shapley Algorithm - Practice 3

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

Here are some notes about two-sided markets. These problems are often couched in terms of pairing off equal numbers and boys and girls in "marriage" in some "stable" way. Applications include matching doctors to hospitals when the finish medical school, school choice, college admissions, etc. The major algorithm here is called the Gale-Shapley, deferred acceptance algorithm.

Two-Side Markets

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

There are lots of wonderful resources about game theory on the web. Two very appealing blogs are:

Alvin Roth's Market Design Blog

Roth also has wonderful materials on his web page. Lots of expository articles, especially about the Gale/Shapely deferred acceptance algorithm and two-sided markets.

Blog devoted to economics, computer science and game theory

Some of the materials treated on this blog are at the research frontier but this in part is why monitoring what is said is especially interesting. Since game theory is quick starting compared with many other parts of mathematics even if the technical stuff is not accessible you can get an idea of the kind of issues that drives research in game theory.

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

Here are more "practice" problems about games that deal with very basic ideas but they also hint at ways that one can use these ideas, say, in an algebra class, or when teaching about mathematical modeling. Being able to simplify games usings using dominant row/column and looking for saddle points is worth practicing so that you can understand the implications of these ideas.

More matrix game problems - two players

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

Here are a few "practice" problems about zero-sum games that deal with very basic ideas but they also hint at ways that one can use these ideas, say, in an algebra class, or when teaching about mathematical modeling.

Zero-sum matrix game problems - two players

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

Here are some brief notes about the nature of zero-sum two person games as well as some activities designed to get one started on matrix games.

Two person zero-sum matrix games

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

The modern history of Game Theory begins with John Von Neumann and Oskar Morgenstern but since then and before there are matters of historical interest. Here is a chronology.

Chronology of Game Theory

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