Mathematical Game Theory (Notes)

Prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

email:

web page:

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

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

New materials Summer, 2019

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

Here is a modest length survey of voting systems and some of the unexpected behaviors that seemingly attractive systems can be subject to.

Voting systems

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

A recent book about computational social choice theory has wonderful survey articles about voting, game theory, allocation, matching markets, as well as a variety of other game theory and fairness models. Many of the authors are among the most active researchers in these area. You can look at the book here:

Computational Social Choice

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

New materials Spring, 2019

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

Syllabus for Spring, 2019

Game Theory syllabus 2019

Here is a sampler of game theory and fairness situations which we will study during the course of the semester.

Game Theory Sampler

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

This interesting 2x2 non-zero-sum game example has a bit of a surprise, if one computes the Nash equilibria for the game.

2x2 non-zero-sum game example

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

This note discusses an example of matching 7 men with 7 women and shows the many stable marriages that can occur. Study of this example helps one see "tradeoffs" in going from the male optimal stable marriage to the female optimal stable marriage.

Many stable marriages

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

For some hint of how bankruptcy questions have led to new ideas about fairness and new mathematics of value for both economics and mathematics take a look at this "technical" but now outdated essay by William Thomson. A book by Thomson about these matters is to appear shortly.

Fair Allocation

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

The applicability of the Gale/Shapely stable marriage circle of ideas is amazingly rich mathematically. You can find out things about this and related topics from these expository articles.

Marriage Theorems

(skip if you wish the part about the Hall Marriage Theorem; some links no longer work and Alvin Roth, now the winner of the Nobel Memorial Prize in Economics for his work on matching markets is the economics department chair at Stanford, having left Harvard to return to the school where he got his doctorate degree in mathematics).

School Choice

David Austin has also written an AMS feature column about school choice, though his column is a bit more "notation" heavy than mine.

More on School Choice

Stable Matching (comprehensive but "telegraphic."

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

This example due to Donald Saari raises some interesting aspects of using ranked ballots to decide elections. What might you "expect" when a collection of ordinal ballots all get "reversed" on the outcome of the election.

Ballot reversal

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

The stable roomates problem is an interesting variant of the matching market ideas of Gale and Shapely. Instead of n boys ranking n girls, we have 2n people who rank all of the other people for possible pairings as roomates. The top trading cycle algorithm (due to David Gale) is a way to "solve" such problems and mathematically interesting in its own right. Some school choice systems use this idea.

Stable roomates problem and top trading cycle algorithm

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

Some practice problems to explore the Gale/Shapley ideas related to matching markets and stable marriage results.

Practice problems involving Gale/Shapely matching market ideas

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

Gale/Shapley example that illustrates various aspects of the deferred acceptance algorithm environment.

Gale/Shapley matching market instance

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

A brief exposition of ideas related to the Gale/Shapley matching market cirecle of ideas.

Gale/Shapley matching market primer

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

Gale and Shapley developed a matching algorithm for pairing college applicants to schools (colleges) they wanted to attend. The ideas have found very varied applications and the "deferred acceptance" algorithm they developed is very appealing mathematically.

Gale/Shapley model for pairing two equal groups of people (hospitals/med school graduates; judges/law clerks; etc.

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

Bankruptcy problems are characterized by claims agains a "pot" set aside to deal with those claims, but where the pot is not big enough to settle the claims. There are a surprisingly varied range of approaches to settle such questions fairly, and a broad range of situations where such problems arise. Here are some practice problems to explore the "landscape" of such questions.

Bankruptcy problems - practice

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

Here are some review problems for this game theory course. Problems are drawn from zero-sum games, non-zero-sum games, weighted voting, elections, apportionment, bankruptcy, and Gale-Shapley (stable matching) examples.

Cummulative Review Problems

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

Bankruptcy problems deal with claims agains a "pot" (money, antibiotics, etc.) set aside to deal with those claims, but where the pot is not big enough to settle the claims. There are a surprisingly varied range of approaches to settle such questions fairly, and a broad range of situations where such problems arise. Here are some expository notes to explore the "landscape" of such questions.

AMS Feature Column article about bankruptcy problems

COMAP Consoritum article about bankruptcy

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

These notes look at various aspects of using divisor method apportionment methods.

Divisor methods for apportionment

These articles survey mathematical ideas related to apportionment.

AMS survey on apportionment I

AMS survey on apportionment II

There are two technical issues that cause apportionment to be "messy." Below sometimes I will refer to either parties (European apportionment) or states (American apportionment) as "states."

a. Ties occur for some of the methods due to "accidents" of the numbers (more likely when one uses small examples with numbers like 400, 200, 100, 50 as "populations" for the states. Ties greatly complicate the "theory." There is no universal agreement on how to break ties. One approach would be to give the extra set to the claimant with the larger claim.

b. Does each state (party) have to get at least one seat independent of how small its "population" is? Some of the methods (Dean, Adams, Huntington-Hill ) in their "table" (priority list; rank index) versions automatically give each state one seat of the h available. When there are more states (parties) than the house size h, then one can't give each state one seat even if one wants to. However, even with 435 seats in the House of Representatives and there are only 50 states, with some "data" for populations, Hamilton, Jefferson, and Webster may not give each state one seat unless one "forces" this to happen. Then there is the issue of what modification of the usual approach to this method one might want to make. I will not address this. If you want the details look at Balinksi and Young's book Fair Representation. When using the table (priority list) method, sometimes one has to "break" a tie by hopefully some fair approach.

We studied six methods: Hamilton (in a category of its own). The other methods are sometimes called divisor methods or rounding rule methods. However, each has two algorithms, one with divisors and rounding rules and the other using a "table" or "priority list." Bias in discussions of apportionment often means that over many examples (method used in many cases), say, small states are favored. (However, there is the technical issue of what it means to be small!) Below dividing by "0" in essence means force a tie between all states (parties) in the "first round."

Brief comparison chart:

Adams, favors small states; always round up; for table divide by "0", 1, 2, 3, ...

Dean, ----, round using ((a)(a+1)/(a + 1/2)) (harmonic mean), for table divide by "0", 2/(3/2), ....

Huntingon-Hill, ...., round using square root (a)(a+1) (geometric mean), for table divide by "0", square root 2, square root 6, ....

Webster (St. Lague) ...... (Balinksi and Young think this is the best choice in terms of bias - not favoring large or small claimants over many uses of the method; Lawrence Ernst is not so sure), round in usual way. for table divide by 1, 3, 5, 7, .... (really by 1/2. 3/2, 5/2, 7/2, .... but only the relative size not the actual numbers in the table matters)

Jefferson (D'Hondt) favors large states, always round down, for table divide by 1, 2, 3, 4, 5, 6, ...

Hamilton is not house monotone or population monotone but can't violate quota.

Other 5 methods are house and population monotone but can violate quota. (If the exact share a state deserves is not an integer it would get the ceiling or floor of its "fair share.")

Theorem (Balinski and Young) No apportionment is population monotone and obeys quota. (Hence, not "perfect" apportionment method.)

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

The distinguished mathematical economist Martin Shubik died some time ago, but a memorial in his memory was recently held with "testimonials" and information about his achievements. Shubik along with Shapley is credited with the development of an important power index for weighted voting games (Shapley-Shubik power). Look here for some details:

Memories of the late Martin Shubik

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

Examples which show that many appealing different methods of apportionment can yield different solutions starting with the same data.

Different appealing apportionment give different results for the same set of claims

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

More basic ideas about apportionment, in particular, relating divisor methods to "table" methods.

Divisor and table methods examined for apportionment

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

Measuring fairness for apportionment can be done by comparing what happens between pairs of states, using different "measures" of fairness. Different methods are "optimal" for different fairness criteria.

Pairwise fairness for claimants in the apportionment model

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

Brainstorming examples that are "equivalent" to the apportionment model is encouraged and often rewarding

Apportionment model

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

This set of problems involves apportionment using Webster, Hamilton, Adamas and Jefferson (D'Hondt) using both divisor and table methods.

HW 5 Involving Apportionment

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

The apportionment problem involves the assigning of non-negative (or positive) integer numbers of items to claimants based on "honest" claims in some fair manner, usually based on a single data value about each claimant (e.g. population of different states claiming representats in the US Hougse of Representatives); votes for different parties claiming representatives in a legislative parliament). The apportionment problem offers an appealing window for judging the fairness of different competing concepts for what fairness means. Here are some brief notes about the issues.

Notes about Apportionment

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

The apportionment problem involves the assigning of non-negative (or positive) integer numbers of items to claimants based on "honest" claims in some fair manner, usually based on a single data value about each claimant (e.g. population of different states claiming representats in the US Hougse of Representatives); votes for different parties claiming representatives in a legislative parliament). Here is an activity to get you started on the issues involved.

An activity related to the apportionment problem

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

Weight voting is widely used, especially in the European Union where countries differ greatly in economic power and population. In NY State most counties use weighted voting for county governance decision making. Here are some practice problems about weighted voting.

Practice Problems - Weighted voting

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

Shapley power template.

Template for Shapley weighted voting power

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

Template for computing the Banzhaf power in a weighted voting game.

Banzhaf power template

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

Example that some believe casts into doubt the "necessity" of electing a Condorcet winner when there is one. I don't find this example convincing.

Should the Condorcet winner when there is one, be chosen?

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

Essay I wrote that appeared in the Annals of the New York Academy of Sciences about the mathematical theory of elections.

The mathematical theory of elections

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

The terms "contexts," "problem solving," "exercises," and "modeling" are widely used in mathematics education. This essay is designed to contrast and compare the meaning of these terms. A specific example related to "bankruptcy" problem appears which illustrates from my perspective the use of these terms.

Essay contrasting exercises, contexts, problem solving and modeling

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

Homework Problem Set: IV, involving voting and elections.

HW Problem Set IV (Voting and Elections)

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

Here are some practice problems in using different reasonable methods of conducting elections.

Elections practice problems

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

When voters produce ranked ballots there are many reaonsable methods other than plurality (person who gets largest number of first place votes) candidate wins. These include Condorcet, Borda, Sequential run-off (IRV), run-off, Coombs, Bucklin and Baldwin (a run-off based on the Borda count which will select the Condorcet winner when there is one).

Voting methods using ranked ballots

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

Even for matrix 2x2 non-zero-sum games giving good advice about how to play such games is not so clear. This essay works out an example, using ideas of Philip Straffin about Nash equilibria, prudential and counter-prudential strategies. There is much to be learned by looking at all of the "details" of how one might play and why one might play in these ways.

Details of how to play a 2x2 non-zero-sum game with no pure strategy equilibrium

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

Elections and voting are topics one can start to cover in classrooms as early as in kindergarten. This example was designed to show, something that surprises many people, that a set of preference ballots can yield different winners when different appealing methods of counting the ballots is used.

Appealing elections methods can yield diffenent winners for the same set of ballots

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

Deciding which of two candidates one prefers seems to be an easy task. But things get much tougher in practice when one has to produce a "consistent" ranking of many items based on one's preferences about pairs. This active is designed to probe the issues here.

Paired comparison activity

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

The notion of a Nash Equilibrium is very fundamental for game theory. Some games can have very large numbers of such equilibria and until recently the computatonal complexity of computing the Nash Equilbria of a game was not clear. Here is a rather technical paper but the parts at the beginning serve as a survey of ideas related to equilbira in games. Equilibria can be in pure strategies, mixed strategies, or both. For non-zero-sum games Nash Equilibra often don't seem to be the best choice for actual play, which is in sharp contrast to the zero-sum case.

Complexity of Nash Equilibria

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

These notes show how to compute Nash Equilibria for some 2x2 non-zero-sum games. The basic idea is to disregard one's own payoffs and concentrate on "limiting" what your opponent can accomplish - equalizing approach. The notions of prudential and counter-prudential strategies for both players is also explored. These different approaches typically yield different "payoffs" for the players but it is not clear in many cases which course of action is best for a player.

Nash Equilibria and how to find them for a 2x2 game

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

Wikipedia and other sources have rich collections of information about game theory. This list of game theory terms is basically from Wikipedia, and can serve as a basis for learning more about topics in game theory.

Game Theory Terminology

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

Homework Problem Set: III, involving game theory.

HW Problem Set III

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

Some notes about non-zero-sum games.

Non-Zero-Sum Games

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

Sometimes there is a discrepency between what theory suggests players might do and what when experiments are done with how people behave in practice, things look very different. Here is a game of this type where someone is asked to divide a "gift" fairly, but if he/she does the division in an unacceptable way to the other player, both players get nothings. The example involves "free lunch."

A game where theory and practice don't always allign (Free lunch)

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

Homework Problem Set: II, involving matrix games.

HW Problem Set II

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

Definitions in game theory are not totally set. Different game theory books and papers will define "strategy" in different ways, and similarly the term equilibrium and value for a game will vary somewhat. Definitions are important but at least as important are the concepts and ideas that they are designed to elucidated and chart. Branko Grunbaum (who died in Sept. 2018) has written an interesting article, An Enduring Error, which while not about games (its about "Archimedean polyhedra") is of interest in its own right and as a "warning" about terminology in evolving areas of mathematics.

Definitions and Archimedean polyhedra

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

In the matrix games we have looked at we have assumed that both players are interested in doing well for themselves, and sometimes what they gain is at their opponent's loss and sometimes there are ways to play that benefit both players. However, there are "games," perhaps more accurately choices to be made where the outcomes and payoff will depend of the "state of nature." When on drill for all in a particular spot one may find all or nothing, and the payoff depends on the "state of nature." One can analyze such "games" or decision making situations in a similar way to what we have done for "competitive" games. Nature does not try to make things hard for decision makers.

Games against Nature

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

Michel Balinski, an importasnt contributor to game theory, elections, and apportionment has died.

Michel Balinski (1933-2019)

Balinksi made many contributions to the theory of polyhedra, integer programming, apportionment and voting methods (majority judgement). He taught at the CUNY Graduate Center for several years and supervised doctoral students there.

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

As rich as the theory of zero-sum games is, with its important connections to linear programming, non-zero-sum games have a much richer structure. While some intuitive ideas carry over, "rational" choices often lead to unexpected consequences. Here are some situations to explore the complexities involved.

Exploring non-zero-sum games

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

Here are some practice problems for you to try to make sure you understand the notions of dominating strategy analysis and how to compute an optimal-mixed mixed strategy for a zero-sum game.

Some practice problems - zero-sum matrix games

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

Homework Problem Set: I, involving zero-sum games.

HW Problem Set I

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

Here is a sheet involving some activities associated with zero-sum games.

Some activities involving zero-sum matrix games

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

For those who learn by "practicing" problems here is another collecton of problems about zero-sum games to practice on.

Practice problems II

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

For those who learn by "practicing" problems here is a collecton of problems about zero-sum games to practice on.

Practice Problems I

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

Here are some questions related to games you may be familiar with and the features of these games, to get you thinking about the nature of "games" and why people "play" them.

Game Theory: Questions to think about

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

When a game has a collection of payoff outcomes, one might ask whether it could ever happen that some sequence of payoffs for the game could add up exactly to a particular integer. This discussion leads to some number theory questions but more generally it raises the idea of using a mathematical situation to generate unusual activities or ways to connect to other topics in the K-16 curriculum.

Achieving a particular payoff sum

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

Graph theory is a powerful tool for studying all parts of mathematics, with many applied aspects, and also many interesting research questions within its domain. We will use graph theory ideas regularly in game theory and here is a very brief primer of the subject, for those who may not have seen these ideas previously.

Graph Theory Primer

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

Mathematics has been used to help improve the placement of students in schools they want to attend. Ideas of fairness, efficiency, and "truth inducing" are paramount. These article surveys different ideas and approaches with links to many of the very important technical papers, which are rotten in work of the game theorists David Gale and Lloyd Shapley.

Algorithms for school choice

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

New materials Fall, 2018

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

Not surprisingly the attempt to negotiate a breakup between the UK and the European Union (brexit) has gone down to the "wire." Here is an article about game theory ideas relateed to brexit:

Brexit and game theory

After the agreement just reached (Nov. 25, 2018) it will be interest to see whether the British Parliament and the European Parliament will approve the deal. Here are more game theory ideas related to the situation:

Brexit and game theory after the tentative agreement

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

Despite the fact that students who particiapte in the system of matching medical school grapduates to hospital residencies have not incentive to not be truthful in providing their preferences a study has shown that they, in fact, are often not truthful. Here is a recent account of this reality and what might be done to improve the situation.

Truthfulness in the medical school/residents match

Many new papers continue to be published on the various aspects of school choice and how to improve the systems that exist and might be tried in the future. Here is a recent example.

School choice

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

When a research paper is assigned to a journal for evaluation or being accepted for presentation at a conference various issues of fairness and "optimization" come into play. This paper explores some of the issues involved, that make this particular "matching" problem similar/different to other matching problems.

Assigning papers to be refereed

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

Martin Shubik, the influential game theorist, perhaps best known for the Shapley-Shubik power index involving weighted voting games, has died. Photos and some information about him can be seen here:

Martin Shubik

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

The very distinguished mathematician Lloyd Shapley, who won the Nobel Memorial Prize (joint with Alvin Roth) for his contributions to economics died relatively recently. He is known for the Shapley Value, and (with David Gale) the Deferred Acceptance Algorithm for finding stable marriages in a matching market. In his honor a special edition of the journal Games and Economics has appeared with articles honoring him.

Here is the information about this special issue:

Games and Economic Behavior (Science Direct); Volume 108, Pages 1-614, March 2018

Special Issue in Honor of Lloyd Shapley: Seven Topics in Game Theory; Edited by David K. Levine

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

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

Random permutations and sequences, 1 to n

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

For those who can teach a course dedicated to game theory there are a variety of educational goals with respect to economics and mathematics that can be explored. This article makes some suggestions about attention capturing examples and topics.

Economics related examples for a game theory course

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

New materials Spring, 2018

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

Syllabus for Spring, 2018

Game Theory syllabus 2018

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

Two-sided matchings (markets) is a mathematical attempt to describe how to solve problems where two groups of players (men and women; students and hospitals; students and schools) are being paired by a centralized organization for their mutual benefit. David Gale and Lloyd Shapley, both mathematicians, developed a very appealing collection of ideas that try to make such matchings in a way that are fair, efficient, and encourage the participants to be honest about their views. The ideas of Gale and Shapley have been expanded to other situations and systems by researchs such as Alvin Roth, trained in operations research. Roth is now chairperson of the economics department of Stanford, and he and Shapley won the Nobel Memorial Prize in Economics for their work. Gale was already dead by the time the Prize was awarded, otherwise almost certainly he would have shared in the prize, too.

Some notes on the Gale/Shapley two-sided market model

Stable matchings practice

Stable Matchings (Gale/Shapley)

Two-sided markets

Two-sided markets

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

When one wants to give fair legistlative representation to countries (counties) of unequal population (economic strength) one approach is to specify which groups of "players" can take action (pass a legislative bill). These player groups are called coalitions and sometimes the "winning" coalitions can be specified by giving weights to the players. Those groups (coalitions) whose weight exceeds some quota Q (often floor function (half the sum of the weights) + 1)) are the winning coalitions. Some games represented by specifying winning coalitions can't be "represented" by giving each player a weight and specifying a quota but often players find it helpful to have some numerical measure of their strength to compare with that of other players. Unfortunately, nothing as simple as assigning weights proportional to population will guarantee that having positive weight will give one "power" to influence the outcomes of votes. A dummy is a player with positive weight but who is never a member of a minimal winning coalion. In NY State the weights for players on County Boards of Supervisors are specified by making the weights proportional to Banzhaf power of the players in the associated game.

Voting game activity

Coalition and Weighted Voting Games

Practice problmes involving weighted voting games

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

A bankruptcy situation is one in which claimants ask for amounts in excess of the amount put aside to pay them off. Such problems occur in business, with estates, with dispersing river water (when there is not enough water to meet "treaty" requirements), and raising taxes. Many topics that occur in grades 7-12 are needed to carry out algorithms useful in understanding various fairness concepts for such questions. Ideas related to what claimants gain and lose lie at the hard of the issue.

Bankruptcy practice problems

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

Here are some review problems to practice with regards to topics covered this semester.

Semester review problems

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

We have previously looked at a game known as the utimatum game which examines a person's willingness to share with someone else a "free lunch" opportunity. This paper reviews what is known about the game and offers some new suggestions as to why people who play this game behave as they do. See below "Sharing" for what we looked at earlier.

Article about the ultimatum game

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

These articles survey mathematical ideas related to apportionment.

AMS survey on apportionment I

AMS survey on apportionment II

There are two technical issues that cause apportionment to be "messy." Below sometimes I will refer to either parties (European apportionment) or states (American apportionment) as "states."

a. Ties occur for some of the methods due to "accidents" of the numbers (more likely when one uses small examples with numbers like 400, 200, 100, 50 as "populations" for the states. Ties greatly complicate the "theory."

b. Does each state (party) have to get at least one seat independent of how small its "population" is? Some of the methods (Dean, Adams, Huntington-Hill ) in their "table" (priority list) versions automatically give each state one seat of the h available. When there are more states (parties) than the house size h, then one can't give each state one seat even if one wants to. However, even with 435 seats in the House of Representatives and there are only 50 states, with some "data" for populations, Hamilton, Jefferson, and Webster may not give each state one seat unless one "forces" this to happen. Then there is the issue of what modification of the usual approach to this method one might want to make. I will not address this. If you want the details look at Balinksi and Young's book Fair Representation. When using the table (priority list) method, sometimes one has to "break" a tie by hopefully some fair approach.

We studied six methods: Hamilton (in a category of its own). The other methods are sometimes called divisor methods or rounding rule methods. However, each has two algorithms, one with divisors and rounding rules and the other using a "table" or "priority list." Bias in discussions of apportionment often means that over many examples (method used in many cases), say, small states are favored. (However, there is the technical issue of what it means to be small!) Below dividing by "0" in essence means force a tie between all states (parties) in the "first round."

Brief comparison chart:

Adams, favors small states; always round up; for table divide by "0", 1, 2, 3, ...

Dean, ----, round using ((a)(a+1)/(a + 1/2)) (harmonic mean), for table divide by "0", 2/(3/2), ....

Huntingon-Hill, ...., round using square root (a)(a+1) (geometric mean), for table divide by "0", square root 2, square root 6, ....

Webster (St. Lague) ...... (Balinksi and Young think this is the best choice in terms of bias; Lawrence Ernst is not so sure), round in usual way. for table divide by 1, 3, 5, 7, .... (really by 1/2. 3/2, 5/2, 7/2, .... but only the relative size not the actual numbers in the table matters)

Jefferson (D'Hondt) favors large states, always round down, for table divide by 1, 2, 3, 4, 5, 6, ...

Hamilton is not house monotone or population monotone but can't violate quota.

Other 5 methods are house and population monotone but can violate quota.

Theorem (Balinski and Young) No apportionment is population monotone and obeys quota.

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

If there is a pot of money E to be distributed fairly to claimants whose claims exceed E this is known as the bankruptcy problem. Here are two expository accounts (pdf files) of such problems and their relatives.

American Mathematical Society Feature Column about bankruptcy problems

COMAP Newsletter Consortium article about bankruptcy problems

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

Having seen a variety of appealing apportionment methods one can try following Arrow and see what fairness properties the particular methods obey. One could look at "global" fairness or fairness in the exchange of two seats between states or parties.

Pairwise fairness between states (parties) for apportionment

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

Some homework problems that involve apportionment methods.

Some homework problems

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

The prospect of Great Britain leaving the European Union has resulted in attempts to deal with the power issues between the remaining member countries of the EU after Brexit. A technical article from the ArXiv is linked in this expository account.

Apportionment issues for the European Union post Brexit

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

A survey of basic ideas related to apportionment.

Apportionment

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

Just as different election methods can yield different winners, for the same data different apportionment methods can allocate the seats in legislature in different numbers to parties or states.

Apportionment examples

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

Here is a note about looking at problems that are modeled using apportionment ideas.

Modeling apportionment

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

Divisor methods to solve apportionment problems have been discovered and rediscovered both in the American and European versions of the apportionment problem. Adams, Jefferson, and Webster's methods are illustrated.

Divisor methods

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

Here is an activity to introduce the idea of how to assign "states" with different populations seats in a parliament (house of representatives) with an integer h as the number of its seats. The same mathematical problem arises in deciding how many seats a politcal party should get in the legislature based on the number of votes it receives in an election.

Apportionment activity

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

Here are some materials developed by the NCTM related to ideas about voting methods.

NCTM voting method lesson

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

Here are some election method problems.

Election method problems

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

Here are some practice problems involving some of the methods for deciding elections based on ranked or ordinal ballots.

Practice probhlems involving election methods

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

There are many appealing methods to decide elections based on ranked ballots. Here are some notes about how these methods work.

Various election methods based on ordinal ballots

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

Nash equilibria constitute a subtle topic in the area of non-zero-sum matrix game. This worked example tries to show how the computations go, and the related ideas of prudential and counterprudential strategies for the players of such games.

Worked example related to Nash equilibria

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

If one is voting in an election typically one is only asked to vote for one's favorite choice. This is relatively easy for the voter to do. However, some ballots involve ranking candidates from best, to next best, etc., sometimes allowing for ties. It turns out that when one is asked to do this for many options (say, 10 candidates running in a party primary) doing so in a "consistent manner is not so easy. This activity asks people to pairwise compare a large list of fruit, to probe the complexities of choice behavoior.

Paired comparison activity

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

This activity asks for which textbook should be selected for a college course based on the ranked (ordinal) ballots of 55 voters. Many people are surprised that the same ballots can lead to many different winners using reasonable systems of counting the votes.

Different reasonable election methods can yield different winners for the same ballots

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

There are many entry points to new ideas and concepts dealing with game theory. Once can explore many specific games and get additional background on large themes by looking at specific examples that illuminate many mathematical aspects of the subject. This collection of terms, largely drawn from Wikipedia can be a jumping off point.

Game key words and terminology

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

Here is a brief account of some of the ideas related to Nash equilibria.

Nash equilibria

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

Here is a collection of game theory problems.

Game theory problems

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

As we explore more topics we will see that what is meant by being fair is a very complex issue. Not only does the context seem to change what is meant by fairness but fairness notions have changed with time. This long survey which has many references offers some hints of the complexities involved.

Justice and fairness - survey

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

Some games engender complicated thinking about what to do when faced with a situation. This game involves such a situation which involves sharing a "gift" with another person.

Sharing

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

Suppose one is playing a game against a passive opponent, rather than an opponent who actively opposes one. Such situations are sometimes called games against nature, or decision problems.

Games against nature - decision making

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

Some practice problems involing game theory.

Practice game theory problems

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

Some notes about the contrast between zero-sum and non-zero-sum games.

Contrasting zero-sum with non-zero-sum games

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

Some game theory problems.

Game theory problems

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

A sampler of game theory and fairness situations to give you a flavor of a small subset of the huge number of situations where mathematics has been used to get insight into "conflict" and fairness situaions.

Game theory and fairness sampler of situations

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

Project for a game theory class.

Game Theory project

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

Exercises about zero-sum games.

Zero-sum game exercises

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

A game involving schools competing for honors associated with cleaning up debris from a park.

Earth day game

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

Some thoughts about what numbers can occur as outcomes a zero-sum game. This idea leads to some interesting number theory questions.

Achievable outcomes in games

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

An activity to get one thinking about a special kind of game that can be written down using matrices.

A game theory activity

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

Some questions to get you thinking about games and their nature.

Some questions about games

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

A brief introduction to graph theory, a very powerful mathematical tool, including for ideas related to game theory.

Graph Theory Primer

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

The 2018 Carty Award for the Advancement of Science has been awarded to the game theorists David M. Kreps, Paul R. Milgrom, and Robert B. Wilson. All three are affiliated with Stanford University. Some details about their work are indicated in the announcement of the award below:

Game theorists win Carty Award for 2018

All three use mathematical methods to get insights into a variety of topics in economics.

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

American courts have been lookng into the practice of state legislatures redrawing Congressional district lines in a way that promotes the interest of a particular political party, a practice called gerrymandering. Here is an article All three use mathematical methods to get insights into a variety of topics in economics.about some of the mathematical issues involved.

Some mathematical issues related to gerrymandering

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

You can download some notes about the interface of computer science (complexity theory), game theory and economics that were written by Tim Roughgarden (Stanford). They are somewhat technical in places but also show a variety of settings where game theory interacts with other subjects.

Tim Roughgarden notes on complexity, game theory and economics

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

The National Academy Press publishes many books related to science, computer science, and mathematics. One can buy print versions or download pdf versions for free. Here is a book that goes back some years that has material related to game theory and decision making.

Behavorial Modeling and Simulation

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

New matrials Summer and Fall, 2017

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

This brief article deals with voting in two rounds where the results of the first round are available to voters before the second round is started.

Voting in rounds

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

Here is a very nice surevy of different methods of picking a single winner in a voting situation where there are typically more than 2 candidates (choices) written by Warren Smith.

Survey of single winner election methods

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

Using mathematical tools to get insight into school choice systems continues because a variety of practical and theoretical issues remain. Here is a recent paper dealing with interesting issues.

School Choice

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

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

Gerrymandering

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

Interesting new papers dealing with voting and game theory aspects of elections appear regularly. Two that caught my attention recently are:

Manipulating elections

Manipulating elections with preference reversals

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

When a political party has enough power in a legistlative body it often tries to retain its power by redrawing election district lines for its advantage. Here is an article about how mathematics plays a role here.

Using mathematics to draw electoral district lines

A whimsical comment on choosing a "best" voting system:

Whimsical comment on voting systems

This conference on fair division highlights the names of recent contributors to game theory issues related to fair division, and some of the areas of current intense intestigation.

Conference on Fair Division

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

A recent attempt to compare the virtues of different voting systems appears here:

Voting sytems

Unfortunately, there are lot of abbreviations whose meaning is not always made clear. Some of the alphabet soup can be interpreted with the assistance of the articles index here:

Voting related articles

and as a last resort try a Web search using an appropriate string. In the end what it comes down to is that many systems a lot better than plurality are not "perfect" and so there is continual debate about where to move from plurality voting but rarely any changes that yield systems that are more responsive to what the voters might want. Arrow's Theorem and other theorems point to the difficulty of having voting systems that are "ideal."

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

Independent of whether or not school choice is a good idea (having schools compete for students with the hope that the students get a better education), when such a system is devised it should be "fair" and designed to achieve a better education for students. A recent articles points to a school choice system that was subverted.

DC School Choice

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

Some new materials added starting Spring, 2017.

Syllabus for Spring, 2017

Syllabus

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

Although school choice is often an attempt to undermine public schools by allowing private and religious oriented schools to receive public money mathematics can often be used to improved what large school systems do where arrangements exist to allow students to attend different schools using a "centralized" assignment system. The Top Trading Cycle approach of David Gale and the Deferred Acceptance Algorithm of David Gale and Lloyd Shapley are candidates for use in such schemes. Here is a very recent paper exploring the different aspects of the two systems:

Top Trading Cyles and the Deferred Acceptance Algorithm compared for school choice systems.

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

These notes explore in more detail the issue of pairwise equity between states and how to measure fairness for apportionment problems. Webster and Huntington-Hill are compared via examples.

Pairwise apportionment equity and some worked examples

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

E.V. Huntington (1874-1952) was a mathematics and mechanics professor at Harvard University. Huntington proved that the rounding rule divisor methods (Jefferson, Dean, Webster, Huntington-Hill, and Adams) could be calculated using a table approach. While doing problems using large values of h by hand are a nuisance for small values of h they are invariably easier than the trial and error approach that to some extent is needed for using "divisors." The table approach also makes clearer the issues of ties which can occur even when two states don't have equal populations. Here, an example looked at earlier is solved using the table method approach. The answer for a given problem instance will will be the same whichever method is used. The difference between Jefferson and D'Hondt, is that Jefferson requires each state in the US when apportioning the House of Representatives gets one seat "automatically" (the Constitution requires this) while D'Hondt does not of necessity do this. The table method for Huntington-Hill and Adams automatically give each state one seat. In Europe typically very small parties are not guaranteed a seat in parliament unless they get some minimum percentage of the vote. Some apportionment problems seem to naturally require that each claimant get a "seat" while in other settings this does not seem "required."

Apportionment Via the "table" method

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

An activity to explore the apportionment problem (claimants attempt to get pieces of pie where all pieces must be be a non-negative integer, such as computers, seats in a legistlature, teaching lines, etc.) as well as look at variant versions of apportionment questions for see how they are alike and how they are different.

Apportionment and modeling

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

Here are some notes about the apportionement problem. Claimants ask for different pieces of a "pot" which consists of seats in a legislature, school buses, etc., where only a non-negative number of items can be given to each claimant. This makes the problem much harder than the bankruptcy problem in "practical" terms. Like the bankruptcy problem there are many different ways to be "fair" all of which yield different solutons to the problem instance. There is a theorem due to Michel Balinski and H.P. Young which shows that having a method to solve apportionment problems which is "ideal" is not mathematically possible.

Apportionment

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

Here are some examples which show that different ways of carrying out apportionments can result in different numbers of seats for the different claimants. These different apportionments can be "defended" using different views about what being fair in the apportionment environment means.

Apportionment Examples 1

Apportionment Examples 2

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

Some practice problems involving the bankrupty model, the situation where the amount "owed" claimants is more than the size of the fund that they can be paid off from.

Bankrupty practice

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

This activity probes the nature of the way people take a "fair" action when faced with a choice which allows them various opportunities. This is my "setting" of a situation which in the game theory literature is sometimes called the "ultimatum game."

Activity involving being "fair."

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

An obituary for Kenneth Arrow, who died in 2017 and was a very important figure in economics and mathematical economics.

Obituary for Kenneth Arrow from Nature Magazine

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

Here is a very recent article about a variety of aspects of school choice, which in particular, deals with school choice in New Orleans. There is also lots of more general discussion of Gale/Shapley and Top Trading Cycle ideas and how they related to school choice.

School Choice in New Orleans

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

High School Student Matching for New Yort City

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

A bankruptcy occurs when there are claimants who are asking for money from a fund where the claims exceed the amount in the fund which is available to disperse to the claimants. Traditional bankrupcy problems and estate problems fall in this category as do many other types of situations. Many fairness questions are easier to think about in the bankrupcty setting than in some of the other kinds of fairness questions commonly studied - issues of monotonicity, Pareto optimality, being honest in one's behavior.

Bankruptcy Modeling

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

A collection of review questions of relatively straight-forward problems related to games, espections, matching markets, bankruptcy, and apportionment problems.

Game Theory Course Review Problems

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

A set of problems to solve.

Problems Set 5

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

Some notes about two-sided markets, Gale/Shapley models.

Two-Sided Markets (Gale/Shapley)

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

Here is a very readable, relatively recent account of using 2-sided markets and some of the real world experiences with using them by Alvin Roth (who with Shapley won the Nobel Memorial Prize in Economics in part for this work), and some of this colleagues. There has been a growing use of these models whose roots lie in the work of David Gale and Lloyd Shapely.

Matching Markets

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

The Gale/Shapley Model for 2-sided markets has been used in many "real world situations" and there have been 2-sided markets which were implemented without paying attention to "stability" issues. Here is one technical article about this with lots of references to other places where you can read about "unraveling" of markets where stability is not required.

Unraveling in 2-sided markets

----------------------------------------------------------------------------<

Practive problem for a matching market in a hospital/resident formulation.

Matching market practice

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

Here are some problems and basic definitions regarding matching markets.

Matching markets

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

Centralized markets are increasingly used to pair off or match two groups of players for the benefit of both. For example, there is a cerntralized market to "match" students who need residencies after graduating medical schools and hospitals who need "staff." These markets rely on variants of the Gale/Shapley approach to "stable marriage." There is lots of appealing applied and theoretical mathematics here.

Two-sided markets

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

Some practice problems involving voting and weighted voting games. How do power indices behave as one changes the quota?

Voting Game Practice

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

Here are some notes about voting/weighted voting games. The idea is that if players represent communities with different sizes that they should cast a block of votes based on some measure of the size of the communities (e.g. population or GDP). When weights are assigned proportional to size, sometimes a player can have no influence, that is, not be the member of any minimal winning coaling. This leads to the notion of a power index for a voting/weighted voting game.

Voting and Weighted Voting Games

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

An activity to introduce the idea of voting game or weighted voting game.

Weighted Voting Game Activity

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

The two essays below are not overly technical. The first deals with various aspects of what utilities are and how they can be computed. The issue is raised if it is reasonable to compare utilities between different peopole. The other essay deals with preferences and how they can be studied. Both items were written by Kenneth Binmore, the British game theorist, who has written many books related to game theory. The essays help show how game theory/fairness ideas are related to economics, psychology, and philosophy.

Interpersonal comparison of utilities

Revealed preferences

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

Practice using various voting methods. Can one defend a method which elects a candidate but one who has no first place votes?

Elections method example

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

Some problems involving different election methods applied to the same set of ballots. The important message is that the same ballots can yield different "defendable" winners with differnt appealing methods.

Election methods problems

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

Some notes about different elections methods, plurality, run-off, sequential run-off, Borda Count, Condorcet, Baldwin, Coombs, etc. All these methods have "stories" which suggest they may be appealing methods. However, the disconcerting reality is that different appealing methods can elect different winners.

Different election decision methods

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

Activity involving different election methods for the same set of ballots.

Election methods activity

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

Practice using various voting methods.

Elections method example

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

Parts of this essay on social choice theory are quite technical but if you skip these on first reading you will get a very rich account of the ideas that involved in this area which lies on the boundary of mathematics, economics, and political science. The important role of Kenneth Arrow is mentioned.

Essay on on social choice theory

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

Paul Samuelson, who was the first American to win the Nobel Memorial Prize in Economic Science, described Kenneth Arrow as "the most important theorist of 20th century economics. Arrow died on Feb. 21, 2017 at 95.

Obituary for Kenneth Arrow

You can find out more about Arrow here:

Wikipedia article about Kenneth Arrow

As a new teacher, shortly after I started teaching at York College, I came across Arrow's work, in what has come to be called social choice theory. I was charmed by the "elementary" nature and importance of "Arrow's Theorem," which showed that there was no fair/perfect method of resolving individual preferences into one for a group (e.g. elections). When Walter Meyer and I wrote Graphs, Models, and Finite Mathematics we included a treatment of Arrow's Theorem, and the book, For All Practical Purposes, of which I am a co-author and helped develop, includes ideas about elections and fairness that I think are wonderful topics to show students a domain of theory and practice for mathematics that they rarely are exposed to. Arrow's work, which garnered him the Nobel Memorial Prize in Economics in 1972 had many students who expanded social choice theory, game theory, and mechanism design. While many don't associate work on fairness to be a mathematical subject the work of Arrow and those influenced by him show that it very much is a rich "playground" for the theory and application of mathematics.

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

A perhaps unexpected use of game theory is in understanding animal behavior and the way that species change. When two animals have a fight but have different genetic makeup perhaps the results of such "confrontations" affects which animals survive to reproduce and this changes the genetic makeup of the species. One pioneer of this work was the mathematical biologist John Maynard Smtih (British). Here is a primer (pdf file) that deals with this topic. This general area is called evolutionary biology and there are many examples of game theory thinking here. In particular what has come to be called the Hawk/Dove game (non-zero-sum) helps biologists understand some of the issues. However, the analysis of this game in biological setting raises issues that go beyond the more "vanilla" ones that are often discussed when one analyzes Chicken or Prisoner's Dilemma.

Primer of Evoutionary Biology including a discussion of the Hawk/Dove game.

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

Here is an activity aimed at understanding how, based on ballots which rank the candidates in an "ordinal fashion" (highest ranked to lowest ranked, with no ties), can yield a variety of different winners with reasonable methods for counting the votes. The same ballots can determine many different winners when different decision methods are used.

Election where different reasonable election methods yield different winners.

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

When people vote, grade examination papers, rank skaters in a figure skating competition, etc. it may be necessary for the judges/voters to say which of two alternatives, skaters (candidates, choices) they think is better, and sometimes they may have to say how much better (cardinal versus ordinal comparisons). This activity raises questions about how hard making compared comparisons is, as well as whether people typically have the skill to carry this out. If you rank 7 fruits from "favorite to least favorite" will the results be consistent with your pairwise preferences and will the results be stable, in the sense that if you do the same task in two hours you would get the same results.

Paired-Comparison Activity

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

Here are some key words that come up in game theory as well as a list of distinguished contributors (most of this from Wikipedia). Using these terms as a basis for s search will garner lots of information about these individuals and topics.

Game theory terminology and scholars

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

Some game theory problems.

Some game theory problems.

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

The notion of a Nash equilbirum (named for the great game theorist John Nash), is fundamental to understanding non-zero-sum games. Very general classes of perfect information games have either pure strategy, mixed strategy, or both pure and mixed strategy Nash equilibria. Unfortunately, in many cases playing Nash equilibra stategies does not seem appealing because there are more "attractive" ways to play. Also, the complexity (in the computational sense) of computing all the Nash equilibra for a game is not fully understood.

Nash equilibria

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

Some basic ideas regarding zero-sum and non-zero sum games.

Zero-sum and non-zero-sum games

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

Some game theory problems to work on.

Game theory problems

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

Sometimes a player takes actions in a decision making situation and gets a payoff depending on a "state of nature." Sometimes this is called "games against nature." Perhaps a farmer making a decision about what crops to plant and his/her income depends on which of various things happen with regard to the weather. Nature does not try to "hurt" one the way an active opponent might but there are similar issues as in competitive games about how to "play," or make moves in such situations.

Games against nature and decision making

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

Some practice problems involving the ideas on zero-sum and non-zero sum games.

Game Theory Practice Problems

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

Robert Wilson recent won a prize for his work in game theory. This article about Wilson gives some interesting examples of applications of game theory in a variety of settings.

Robert Wilson and applications of game theory

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

If one has a 2x2 (2 players, two moves for each player) zero-sum game (or a bigger matrix game) with integer payoffs, one can ask when it might be possible to achieve a payoff to Row of a particular size. Using some ideas about diophantine equations one can solve this problem and it provides a context for looking at why solving linear equations is both important and interesting.

Game Theory and Diophantine equations

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

Some problems about zero-sum games.

Zero-sum games

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

Some activities to get started with zero-sum matrix games.

Some activities to get started with zero-sum matrix games

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

When studying games for the first time from a mathematical point of view here some questions and ideas about how to get people thinking about this domain of ideas.

Questions about games and their nature

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

In the early history of game theory the games that were studied were ones where the moves and payoffs were known in advance and a goal was to give advice to people about how to play such games, and to understand what people actually did when they played such games. More recently dynamic games have been studied where some moves no longer are available as the game evolves and where new moves may become available. This web page announces a forthcoming conference (July, 2017) but also has links to former converences so you can see the people who do this work and the kinds of problems they think about.

Dynamic Games

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

Ads are ubiquitous on the Web. The portion of mathematics and economics called mechanism design is concerned with the game theory aspects of pricing ads and the consequences of the ways that auctions for ads are designed. This recent ArXiv article surveys some of the issues and I also have a link for an earlier related item.

Ad Auctions

Mechanism design for ads

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

Several blogs devoted to game theory are worth looking at regularly, not merely for the insights they offer into the material of a course in Mathematical Game Theory.

Alvin Roth's Market Design Blog

Game Theory Tuesdays Blog

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

Here are some problems that are designed to help you become proficient in working with zero sum games. Even if you feel you don't need to actually carry out the solving of these questions, at least read through the questions so that you will have a basis for understanding the types of "computational" questions that come up.

Practice Problems 1: Zero-sum games

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

Here are some brief notes about zero-sum games. Such games usually show payoffs from the Row player's point of view. There are not so many applications of this type of game but the theory is very mathematically appealing and lays the foundations for the more realistic non-zero-sum games. Related to zero-sum games are those with constant sum, which have a similar theory.

Zero-sum games

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

Here is a small sampler of the kinds of problems that game theory specialists have addressed. Some game theorists operate out of mathematics departments but many of them are economists, work for business schools or political science departments. New theory and applications of game theory are being developed regularly.

Game Theory Sampler 2017

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

Graph Theory is a marvelous tool for all parts of the theory and application of mathematics. Game theory is no exception. Here is a brief look at some of the key terms in graph theory.

Graph Theory Primer

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

We will look at various issues related to elections and voting. Some countries elect representatives from individual "local" districts (relatively more common in English speaking countries) and other countries use proportional representation systems. This interesting article (by a political scientist at Stanford, Jonathan Rodden) looks at giving an explanation for why many European countries, to implement their form of democracy, chose to use "proportional" representation." We will look at the mathematics of the apportionment problem (not treated in this article) which concerns how many seats a party gets in a legistlature depending on the percentage of votes that party got in an election.

Why did Western Europe Adopt Proportional Representation?

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

This relatively recent article from the Economist is part of series about how game theory has benefited economics. It deals with the notion of Nash Equilibrium which we study in detail in this course. Nash died shortly after his having won the Noble Memorial Prize in Economics.

Economist article about the Nash Equilibrium

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

Thomas Schelling, the distinguished economist and game theorist, and winner of the Nobel Memorial Prize in Economic has died at 95.

NY Times Obituary for Thomas Schelling

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

Some new materials added starting Fall, 2016.

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

Here is the proceedings of a relatively recent conference on matching markets (which has applications to school choice, matching medical students to residencies, etc.):

Proceedings of a conference on matching markets

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

The American Economic Association has made available several articles from a symposium called: What is Happening in Game Theory. The articles can be downloaded from this web page:

What is Happening in Game Theory

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

Here is a recent article about scheduling tennis matches (and it has uses in related situations) in a manner which is fair. It extends results that applied the Gale/Shapley Stable matching theorem.

Scheduling Tennis Matches

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

Some new materials added starting Summer, 2016.

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

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

Matching refugees to housing

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

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

Matchings when performance is better than expected

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

The National Bureau of Economic Research is having a conference on Market Design on July 26, 2016. The announcement includes a link to a pdf fill which serves as a reading list for the conference, and which has lots of recent papers that sample what is going on in the arena of market design.

Conference Program and link to reading list for Market Design Conference

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

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

NY Times item on Game Theory and Fairness

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

The National Academy of Sciences has published a brief item on Kidney Exhange and mechanism design.

Kidney Exchange and Mechanism Design

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

Real world examples where Condorcet voting is used are relatively rare. Here is an account of one recent example. When two French provences were merged a vote was taken using the Condorcet Method to decide on a name for the merged province.

Use of Condorcet voting in France

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

Here is a discussion on one of the Stackexchange bulletin boards of applications of Game Theory to Computer Science.

Applications of Game Theory to Computer Science

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

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

Some "probing questions" about 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.

Comments about Lloyd Shapley by Alvin Roth

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

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.

Peyton Young's paper about compactness

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.

Activity about 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.

Things to Think About

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

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

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

This open access book about game theory can be downloaded for free.

Free Game Theory book (pdf) to download

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

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

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

Return to Joseph Malkevitch's Home Page