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 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


--------------------------------------------------------------------------------
Return to Joseph Malkevitch's Home Page