Mathematical Game Theory (Notes)
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
The materials below were developed for both graduate and undergraduate courses taught under the title "Game Theory." The philosphy of these courses is to cover as broad a range of topics with a game theory flavor as possible. It it generally easier to get a deeper knowledge of a subject X where one has seen the key ideas and some of the major results than it is to start off reading in a book devoted only to the content of topic X.
Game Theory, here, refers primarily to the analysis using mathematical tools of conflict situations as they arise in business, economics, and political science. The subject was "put on the map" by the work of the mathematician John Von Neumann and the economist Oskar Morgenstern. However, there will also be a brief treatment of what have come to be called combinatorial games. Nim is perhaps the best known of such games. These ideas are related to a mathematical understanding of games such as chess and Go.
--------------------------------------------------------------------------------
Generic Syllabus
Syllabus
---------------------------------------------------------------------------
New materials Fall, 2022
--------------------------------------------------------------------------
Introducing election methods that go beyound using a ballot where candidates (choices) are not ranked and the winner is chosen using the counting system where the winner is the candidate with the largest number of votes have been slow to be accepted. After the "insurrection" on January 6, 2021 attempts to reform election methods to be able to better express the "will of the people" have been come harder. Many articles are starting to appear that deal with election reform and which sometimes point out the insights that mathematics provides, specifically Arrow's Theorem and the Satterthwaite-Gibbard Theorem.
--------------------------------------------------------------------------
Syllabus for Spring, 2022
Game Theory syllabus 2022
---------------------------------------------------------------------------
Slides, rather skeletal, reviewing topics we covered this semester as a way to help you study for the final.
Review Slides for this semester's work (rather skeletal)
Review for the final which will not cover Gale/Shapely ideas.
Final examination review
---------------------------------------------------------------------------
Slides from Session 13 dealing with one-sided and two-side markets; Gale/Shapley stable marriage model
Gale/Shapley Stable Marriage type problems
These notes discuss some common errors student make in thinking about game theory/fairness problems.
Cmmon errors in thinking about game theory/fairness problems
---------------------------------------------------------------------------
Slides(Class 12) about coalitonal games and two-sided markets, Gale/Shapley "marriage" model.
Slides dealing with coalitional games and the Gale/Shapley Stable "Marriage" model
An expository account of using Gale/Shapley to study school choice problems.
School Choice - AMS Feature Column
This essay provides a homage to Lloyd Shapley for his many contributions to mathematics and in particular the theory of games.
Homage to Llyod Shapley for his many contributions to mathematics especially game theory
This essay deals with the mathematics of two types of matching (marriage problems), the first due to Philip Hall and the second the Gale/Shapley model, whose most famous application is pairing medical school graduates who need residency placements with hospitals who need their residency positions filled.
Expository account of Philip Hall's "marriage" theorem and the Gale/Shapley stable marriage model
A template to help design Gale/Shapley stable matching examples.
Template for carryng out Gale/Shapley stable marriage problems
Some notes about the Gale/Shapley stable marriage problem (two-sided market).
Two-Side Market notes; Gale/Shapley Marriage Problem
A variate of the Gale/Shapley model looks one-side markets. In this model one side of the market ranks the items to be allocated, say college dorm rooms, but the "rooms" don't rank the students who occupy them. A key idea here is the notion of a top-trading cycle, which as also been used in school choice allocation problems.
Allocation of objects in a one-side market (students assigned to dormitory rooms)
---------------------------------------------------------------------------
Here are slides about bankruptcy problems and coalitional game - games in characteristic function form.
Slides from Session 11: Bankruptcy and Coalitional Games
This essay deals with the Aumann-Machler "talmudic" method of solving banruptcy problems. Idea: divide the claims in half, and first use the money in the estate to pay off half the claims using "Maimonides gain" method and if there is more money to go around, the remaining half-claims are paid off using "Maimonides loss."
Talmudic algorithm for solving bankruptcy problems
---------------------------------------------------------------------------
The essay below appeared as part of the Feature Column Series of the AMS and deals with bankruptcy problems.
Bankruptcy Problems - Expository Survey
The slides below treat the apportionment model, algorithms for apportionment and fairness issues related to apportionmnet; bankruptcy models are introduced and discussed (a pot of money to pay off claimants is not large enought to meet all of the claims - how can one fairly reimburse the claimants?).
Slides Session 10; Apportionment and Bankruptcy
This essay treats reimbursing claimants when there is not enough to distribute to meet all of the claims.
Bankruptcy models - what to do when claims exceed the "estate" to pay off the claims
Some sample bankruptcy problems to consider using different approaches that one has learned about.
Practice problems involving the bankruptcy model
When showing K-12 students traditional topics in arithmetic and algebra student interest in learning these ideas can often be radically improved by showing that there are situations that occur in the "real world" that use mathematics that affect their lives. Fairness questions typically provide students with interesting contexts. Here bankruptcy problems are tied to skills often taught without contexts in mathematics classrooms.
Using contexts is a powerful tool for teaching mathematical ideas
This essay explores how coalitions might share the savings/costs they make by working together, perhaps in conjunction with working on a waste water treatment project.
Cost sharing
Non-zero-sum games offer a "laboratory" for doing experiments and theoretical investigations about what consists of "rational" behavior when playing 2x2 matrix games.
Non-zero-sum matrix games sometimes offer features that don't seem intuitive.
--------------------------------------------------------------------------
The slides below offer a comprehensive look at the apportionment problem - given a positive integer h number of objects to distribute to claimants, how to fulfill the claims by giving non-negative integer amounts to the claimants that sum to h.
Slides Class 9-Aportionment problems - theory and algorithms
This essay offers some comparisons in using different methods to carry out apportionment of a positive integer amount to claimants.
Several apportionment methods compared
This essay discusses some basic ideas related to the apportionment problem - distributing a positive integer amount in non-negative integer amounts to claimants.
Basic Apportionment
When a quantity changes one can express the change as an absolute change or relative change. Often the choice is made to highlight some "point" and "consumers" need to be careful about the effect on them of the way change is expressed.
Absolute versus relative change
Weighted voting issues discussed in an example context.
Weighted voting examples
--------------------------------------------------------------------------
Here is an expository account of apportionemnt that I originally wrote as two Feature Columns for the American Mathematical Society, but now combined by Warren Smith and posted on the Range Voting Website.
Expository account of apportionment (Originally AMS Feature Columns)
These notes from our 8th class deal with power indices of weighted voting games (and more generally coalition games) and apportionment. The Apportionment Problem concerns how to assign parts of a positive integer collection of size h (perhaps computer systems; new faculty lines at a college, etc.) to claimants where the piece assigned to a claimant must be a non-negative integer.
Slides Class 8 - power indices and apportionment
Here is a brief activity related to the apportionment problem.
Apportionment Activity
A brief essay about the nature of the apportionment problem.
Apportionment modeling ideas
One collection of algorithms to carry out the solution of apportionment problems are know as divisor methods. This essay takes a look at some examples.
Divisor methods for apportionment-including ideas related to the Webster, Adams, and Jefferson methods
In trying to find "fair" apportionment methods various approaches have been looked at. Here the idea of basing fairness on comparing how two claimants are treated with respect to each other is discussed.
Pairwise equity for claimants in apportionment
--------------------------------------------------------------------------
Class 7 dealt with election methods, fairness axioms one might hope good elections would obey (work of Kenneth Arrow), issues related to "insincere voting," (Gibbard-Satterthwaite), and weighted voting (examples include the Electoral College in the US and voting systems used by the European Union).
Slides from Class 7 which deal with elections, axioms for fairness of elections methods, and weighted voting
This essay (not mine) deals with examples showing how different voting methods can violate axioms of fairness for election voting methods, in the spirit of those proposed by Kenneth Arrow.
Examples involving violating fairness axioms by various election methods
When you practice examples related to computing the power of "players" in weighted voting games using the Banzhaf or Shapley/Shubik power indices these templetes may make it easier to carry out the computations.
Template for computing Banzhaf Power Index
Template for computing the Shapley/Shubik Power Index
Another example illustrating Nash equilibria for matrix games. If one is looking for ALL Nash equilibria one must check for both pure strategy equilibria and mixed strategy equilibria.
Example involving Nash Equilibra for a 2x2 matrix game
--------------------------------------------------------------------------
The slides from our 6th session are here, and deal with elections, distance, and weighted voting.
Session 6 slides-elections and weighted voting
This essay deals with voting issues where the players cast blocks of votes (e.g. the electoral college or various legislative bodies in the European Union). Actions get taken by groups of players called coalitons. Often a weight is assigned to a player. The goal is to fairly assign weights to the players. This situation is known as weighted voting.
Coaliton games and weighted voting
Here are some notes and practice problems involving weighted voting.
Weighted voting notes and some practice problems
While not directly related to the course this essay (written as part of a series for the American Mathematical Society's Feature Column) deals with some details about taxicab distance/geometry.
Feature Column Article about Taxicab Geometry
--------------------------------------------------------------------------
Here are the slides from Session 5 which deal with games against nature, utility, and elections.
Slides from Session 5; Utility, games and elections
Somewhat lengthy notes about the mathematical theory of elections.
Notes about the mathematical theory of elections
While IRV (Instant Run-off Voting) is often claimed to always be better than using plurality, there are examples where the outcome of using IRV seems not to be what the voters might have hoped for.
Plurality and IRV (sequential run-off) compared in an example
In many election situations one merely needs to use the ballots to select a winner but in some settings one wants to actually rank all of the choices from the best to the least best. This essay looks at how to handle this case.
Sometimes one needs a ranking of all the candidates rather than picking just a winner
While the mathematical aspects of studying elections is in many ways more elementary than that of game theory more broadly defined, there are lots of new terminology to learn. This glossary defines and looks at some of the more commonly used terms and methodologies.
Glossary of terms that arise in looking at elections mathematically
While manty feel that when there is a Condorcet winner that candidate (choice) be elected but in some elections the case of the Condorcet winner being selected seems troublesome to some people.
Should a Concorcet winner when there is one always be society's choice?
Here are some elections involving ordinal ballots to try out various election methods on and to see from your personal perspective which methods seem more or less appealing.
Practice in using different election methods
Given a collection of ordinal ballots there a many diffenent approaches to trying to get a winner who seems to be the "choice" of the group. This essay looks in brief at a variety of such election decision methods.
Brief descriptions of some appealing voting methods
Given a collection of ordinal ballots it is interesting to see how different methods of counting the votes (election decision method such as plurality, Borda Count, etc.) give rise to different winners as a way to try to "judge" which vote counting mathematics are better than others.
Election with 3-different winners
This essay looks at a 2x2 matrix game and computes the Nash Equilibria for it, as well as some other notes about this concept.
Example involving computing Nash Equilibrium
--------------------------------------------------------------------------
Here are slides for the materials covered in Class 4, which deal with zero-sum and non-zero sum games as well as "stable values" or equilibria for such games - Nash equilibria - and how to find them.
Slides from our 4th class - Game Theory and elections anticipated
Many technical terms have arisen to describe and investigate the mathematical theory of games. There are also many scholars who have and are contributing to game theory and fairness models. Here is a sample of such terms and individuals for those of you who want to explore things in more detail.
Game Theory terminology and contributors
Here are some practice problems involving matrix games.
Some practice problems involving game thoery
This activity anticipatess using "paired-comparisons" when making decisions about how to rank alternatives that might be involved in constructing an ordinal ballot for an election (or other decision environment. The activity probes the extent to which people can actually carry out the tasks that fairness models assume they are capable of doing.
Paired comparison activity
The idea of a Nash Equilibrium, due to John Nash, generalizes the notion of a "value" for a zero-sum game. When in a two person game a player plays a Nash Equilibrium and his/her opponent deviates from his/her action associated with this equilibrium the player who "deviates" can't get a better outcome. Remember, that a game may have many Nash equilibria. Furthermore their may be Pareto improvements over the payoffs associated with a Nash equilibrium.
Nash equilibria
The "free-lunch game" looks at the issue of whether or not the advice that game theory my provide the "players" in a game is related to what people actually do when they play such games. The field of "behavioral game theory" deals with conducting experiments to see what people with different characteristics (gender, age, religion, nationality, etc.) do when they play games of perfect information. This particular game involves people's willingness to share in a "fair" manner.
Game involving sharing
Games against nature explore the idea that one can play a "game" against an "opponent' who does not actively try to help or or harm one. This essay deals with making decisions under uncertainy or playing games agains "nature." For example, a farmer may have to decide what crops to grow for the coming season with the payoff depending on the weather and other factors beyound the control of the farmer.
Games against nature - decision making
Making decisions based on expected value seems like a reasonable approach to decision making. However, we often make decisions where our expected value is negative, such as when we very sensibly buy life insurance. This note offers some examples to try to foster thinking about the meaning of this important concept.
Expected value
Using digraphs to explore when matrix games have stable values (pure strategy equilibiria)is a useful tool for studying matrix games. This kind of a graph is sometimes called a motion diagram.
Motion diagram for matrix games
--------------------------------------------------------------------------
Slides for Session 3, which deal with using randomization and probability ideas to understand optimal play of a zero-sum 2x2 game with no "stable point" and some thoughts about modeling elections.
Session 3 slides
--------------------------------------------------------------------------
Here are some slides that support what I covered in the second session of our class.
Slides Session 2
Here is an essay about non-zero sum games in anticipation of what will talk about during future classes.
Non-Zero-Sum Games
This file provides some notes about zero-sum matrix games.
Zero-Sum Matrix Games
This file provides some notes about the notion of dominating row/column for zero-sum games.
Dominating Rows or Columns in Matrix Games
Some notes and practice involving zero-sum game ideas.
Zero-Sum game problems
--------------------------------------------------------------------------
Slides for Remote First class
--------------------------------------------------------------------------
Here is a primer of a very useful tool for modeling problems in all disciplines and there is a rich theoreticlal literature about graphs as well. There are many unsolved problems in this area for students at all levels.
Very brief intoduction to graph theory (dots and lines diagrams)
This additional note shows some how to use some graph theory as a model.
Example of modeling with a graph
----------------------------------------------------------------------------
This handout suggests a variety of questions to think about to understand the nature of the concept of a game.
Questions about games and their nature
----------------------------------------------------------------------------
Sampler of fairness and game theory situations, illustrating the variety of ideas/concepts we will treat.
Sampler of fairness and game theory situations
----------------------------------------------------------------------------
There are many newspaper and TV stories about the "partisan" quality of redistricting plans that have been carried out by state legislatures aften the 2020 Census. Even states that did not gain or lose seats due to the apportionment process (Huntington-Hill's method) can redistrict due to population shifts that were shown by the census. Current districts may not have the approximately equal populations that courts require for "fair districts."
As of early 2022, several states have redrawn legestlative and House of Representative district lines. Already, lawsuits have been filed that some of this redistricting is "partisan," and in some cases courts have agreed that they are partisan.
---------------------------------------------------------------------------
New materials Fall, 2021
The mathematical ecnomomist Muriele Niederle has won the Morgenstern Prize for 2021.
Muriel Niederle's web page at Standord University
----------------------------------------------------------------------------
New materials Summer, 2021
The primary to determine the person who would run on the Democratic ticket for mayor of New York City was held on June 22, 2021. Many articles dealing with the fact that ranked ballots allowing as many as 5 choices was being used have appeared in the NY Times. In the short run the practical implication is that the winner of the election will take quite some time to determine. Newspaper reports that X was ahead of Y by Z% don't mean much because unless one candidate gets a majority (unlikely with so large a field of canddiates) what matters is the rankings by people who voted for candidates who got relatively few first place votes. The vote counting system eliminates candidates with few first place votes, transfers these ballots to lower ranked candidates and repeats the process.
Use of matching market ideas (defferred algorithm of Gale/Shapley or top trading cycle) for school choice is growing and researchers are reporting on the behavorior of these markets compared with the old systems in place. The article below looks at school choice in Guangzhou, China.
School choice in China
----------------------------------------------------------------------------
New materials Spring, 2021
----------------------------------------------------------------------------
This is the syllabus for the Spring 2021 version of the course, to be taught remotely.
Game Theory syllabus 2021
----------------------------------------------------------------------------
Slides for a presentation about matching markets, showing the top-trading cycle algorithm of David Gale for assigning dormitory rooms to students. Students have prefrences about the rooms but the rooms don't "rate" the students.
Slides from Remote Session 14 - Matching markets, including top trading cycles
----------------------------------------------------------------------------
Slides from the review session.
Slides for review session
New York City will be using sequential run-off (IRV) for primaries and elections in the upcoming election cycle. This brief note provides some examples that contrast IRV, which need not elect a Condocet winner, with Condorcet (when there is a winner) and plurality.IRV can elect a candidate who loses 2-way votes with all the other candidates.
Examples contrasting IRV (sequential run-off), plurality and Condorcet
These slides deal with coalition games in characteristic function form - such games are often used to model cost allocation and cost sharing problems. They also deal with the Gale/Shapley deferred acceptance algorithm for finding male/female optimal stable marriages for a matching market.
Slides from Remote Session 12-Games in characteristic function form and the Gale-Shapley deferred acceptance algorithm
These notes deal with commen mistakes that occurred on problem sets that were submitted.
Common errors on homework problems
----------------------------------------------------------------------------
Here are two expository articles about "market design" rooted in the work of Llyod Shapley and David Gale's work on "college admission." The basic idea being to pair people in two disjoint groups in a stable manner based on their preference rankings for the elements of the other group.
Matching Markets and School Choice
Two marriage theorem results - Gale-Shapley Matching Markets
----------------------------------------------------------------------------
Slides about fairness axioms and methods to compute the solution of bankruptcy problems based on various appealing fairness ideas.
Slides from Remote Session 11 - Estate settlements and bankruptcy problems
Review for the final examination.
Final examination review
----------------------------------------------------------------------------
If you are interested in mathematical modeling and applications of mathematics you might find this report of value - a joint project of SIAM (Society for Industrial and Applied Mathematics) and COMAP (Consortium for Mathematics and Its Applications). It also contains some notes about bankruptcy.
Mathematical modeling report (GAIMME) of SIAM/COMAP)
----------------------------------------------------------------------------
One of the concerns of mathematics education is the delivery of "mathematical content" to students K - graduate school. The tools of this delivery involve various approaches: using contexts, mathematical modeling, problem solving, assigning exercises, word problems, practice problems, have students work on "open ended" problems, etc. This essay tries, in an informal way, to deal with my view of thesee distinctions between approaches to mathematics education. A bankruptcy problem is used to help differentiate the different "terms."
At attempt to clairify modeling, using contexts, exercises, and word problems, etc. in mathematics education
----------------------------------------------------------------------------
Bankruptcy problems deal with claims agains a "pot" (money, river water, antibiotics, etc.) set aside to deal with those claims, but where the pot is not big enough (too small) to settle the claims in full. 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 as well as some introductory but more "technical" notes. Also, some practice problems to test your understanding of the different methods.
AMS Feature Column article about bankruptcy problems
COMAP Consoritum article about bankruptcy
COMAP Consortium article about bankruptcy-Followup to prior COMAP article
Some notes about the "bankruptcy" model and different approaches to paying off the claims
Some some worked examples of bankruptcy problems using a variety of solution methods
Notes about the "talmudic" method to solve a bankruptcy problem
Some practive bankruptcy problems
----------------------------------------------------------------------------
Remote slides from Session 10 which provide examples and background related to the apportionment model - how to assign claimants a positive integer number of items that must add to the positive integer number h (house size), which are to be "distributed" to the claimants fairly based on their claims. The same "data" is used to solve the problem using the table method for D'Hondt, Webster, and Adams. Also, there is discussion of how to settle claims against an estate E when the claims exceed the value E. Disaster relief, collecting tax, and water rights can be thought of as questions of this kind. Many different "fairness" approaches are looked at (Maimonides gain and liss, concede and divide, Shaplely, etc.), which typically give different amounts to the claimants.
Slides from Remote Session 10 - Apportionment, Estate settlements and bankruptcy problems
----------------------------------------------------------------------------
The essay below shows a small worked example where the table method is used to apportion the same situation using Adams, D'Hondt (Jefferson), and Webster's Saint-Lague) methods.
Worked example comparing D'Hondt, Webster, and Adams
Notes and examples related to the apportionment problem indicating how the table method can be used to make it easier to solve divisor method apportionment (Webster; usual rounding), Adams (always round up, ceiling functin9o), Jefferson (D'Hondt)always round down, floor function)) problems. Basic Idea: positive integer h divided into integer shares based on claims.
Notes on apportionment
Remote slides from Session 9 which provide examples and background related to the apportionment model - how to assign claimants a positive integer number of items that must add to the positive integer number h (house size), which are to be "distributed" to the claimants fairly based on their claims.
Slides from Remote Session 9 - Apportionment
Here is the firth set of homework problems to be submitted.
Fifth Collection of Homework Problems - Apportionment
----------------------------------------------------------------------------
The block of essays below try to explore the many facets of the apportionment problem - claimants are assigned some positive integer share of a positive integer h (fixed) number of items so that the shares add to h and fairly represent the claims of the players on the h items available. The classic example being how to divide up the 435 seats in the US House of Representatives among 50 claimant states based on the populations the states as determined via the Census.
Apportionment Activity
Basic ideas regarding apportionment
Using the apportionment model
Divisor methods for apportionment
Pairwise player equity for apportionment
----------------------------------------------------------------------------
The slides here (Remote Session 8) cover examples involving power indices for weighted voting as well as provide an introdcution to the problem of how claimants can be apportioned a part of a fixed positive integer h number of items (seats in a legislature) based on "claims," such as population.
Remote Slides, Session 8; Weighted voting and apportionment
For background about apportionment (written for the Feature Column of the American Mathematical Society) you may find these two expository essays of use. The two essays appear in combined form on the Range Voting site (link belw) also. Some of the links don't currently work unforunately, but for the most part this does not interfere with the discussions.
Apportionment I
Apportionment II
Two Previous items combined - Apportioment Introduction - On Range Voting site
---------------------------------------------------------------------------
Linked below are two expository articles I wrote for the feature column of the American Mathematical Society that deal with elections and voting games (weighted voting)
Expository article about weighted voting and voting games
Expository article about elections and voting, including axiomatic work of Kenneth Arrow
----------------------------------------------------------------------------
This templete will help with practicing computatons of the Banzhaf value for games with 4 players.
Banzhaf value template for four player weighted voting games (16 lines)
This templete will help with practicing computatons of the Shapley-Shubik value for games with 3 and 4 players.
Shapley-Shubik value template for three and four player weighted voting games (6 and 24 lines)
Some practice problems related to weighted voting - voting situations where players cast blocks of votes. The unintuitive reality to get used to is that weights are often not clearly related to the power players exert in such games.
Some practice problems related to weighted voting
A brief essay about games where coalitions of players can take action when they cast a block of votes which add to more than or equal to some quota - weighted voting game.
Voting games
Slides for Remote session 7, which deal with elections, weighted voting, and coalition games.
Remote Slides, Session 7; Elections and weighted voting
----------------------------------------------------------------------------
Here is the fourth set of homework problems to be submitted.
Fourth Collection of Homework Problems - Elections
----------------------------------------------------------------------------
A brief exposition of mathematical ideas related to elections.
Brief exposition of mathematical ideas related to voting methods
A long exposition of mathematical ideas related to elections.
Detailed exposition of mathematical ideas involving voting
This example is designed to probe the idea that when there is a Condorcet winner that person should be elected. While some find electing a Condorcet winner when there is one, not all scholars of elections agree.
When there is a Condorcet winner Z should Z be the "society" choice?
Practice problems involving ordinal ballot elections using different methods of picking a winner based on the ballots.
Practice problems using different election methods
----------------------------------------------------------------------------
This collection of slides reviews ideas relatedd to how to play 2x2 non-zero-sum games; discusses an election where 5 different reasonable methods give rise to 5 different winners (the voters have ranked 5 different choices without ties), and introduces weighted voting. Perhaps unintuitively, a player can have a positive weight in a weighted voting "game" (each player casts a block of votes, the player's weight) where to take action a coalition must have a majority or more of the total weight of the players and yet have no influence because that player is never a member of a minimally winning coalition. This a coalition which can take action but when any of its players leave the coalition than action cannot be accomplished.
Slides from Remote Presentation 6-Game Theory, elections and weighted voting
----------------------------------------------------------------------------
A glossary of commonly used terms in the mathematical theory of elections (work in progress) including names for some of the commonly used fairness properties that are considered desirable for an election decision method.
A glossary of terms/concepts from the mathematical theory of elections
----------------------------------------------------------------------------
This note gives a worked out example of computing Nash equilibria for a 2x2 matrix game.
A worked example involving Nash equilbria for a 2x2 game
----------------------------------------------------------------------------
These are the slides from the fifth Remote Presentation and deal with non-zero-sum games and elections. A survey is given of different election decision methods based on both cardinal and ordinal ballots. There is also a discussion of the theorems of Kenneth Arrow and Gibbard-Satterthwaite. Loosely speaking these theorems support the notion of mathematical insights into the fact that there are no "perfect" voting or elections systems. There are no methods of choosing a winning choice or ranking when there are 3 or more choices that obey all the fairness conditions one would like to see satisfied. Any reform will violate someone's favorite fairness condtion.
Remote Session 5 Slides-Game Theory and Elections
----------------------------------------------------------------------------
Below are slides for a public lecture I gave at York in 2016 about the mathematical theory of elections.
Slides for an expository talk about elections (2016)
----------------------------------------------------------------------------
There are many sources of additional information about game theory/fairness models. This list of terminology and famous practioners of these areas of knowledge may be useful and doing more explorations on your own.
A collection of game theory terms and a list of noted practitioners of game theory and fairness models
----------------------------------------------------------------------------
One approach to providing prefences about choices or alternatives is to compare the items you must vote on or rank in pairs. This is not always as easy to do as one might think. If many comparisons are made people are not alway consistent in the sense that they might prefer A to B, B to C but prefer C to A. When this happens most people will go back and adjust their preferences so they are "transitive." Obeying "transitivity" is a kind of consistency rule that individuals usually feel is desirable.
Some activites involving comparing pairs of items to obtain a ranking
----------------------------------------------------------------------------
While oftem when there are more than two canididates, plurality does not seem to always pick a "reasonable choice," sometimes IRV (sequential run-off voting) seems to do "worse" than plurality.
Sometimes IRV (sequential run-off) does not choose a "sensible" winner
In the essay below examples show that for some appealing methods of conducting elections, including run-off and IRV (sequential run-off) more support can harm a candidate. Thus, these methods are not "monotone."
Some appealing methods including IRV are not monotone
----------------------------------------------------------------------------
Some years ago I devised this relatively small example which shows that different reasonable methods of deciding the winner of an election can result in different winners. How can one choose among such methods the "best" one?
Different reasonable election decision methods yield different winners
----------------------------------------------------------------------------
In voting/election situations sometimes one seeks a winner based the ballots and sometimes one seeks to rank the candidates/alternatives for the group. This essay looks at this distinction.
Finding a winner and/or finding a ranking
----------------------------------------------------------------------------
Homework Problems 3: Game Theory
Third collection of Homework Problems: Game Theory
----------------------------------------------------------------------------
This brief note provides ranked(ordinal) ballots for an election with 3 choices (candidates). Thinking about who "deserves" to win the election based on the ballots encourages one to think beyond plurality (person with largeest number of first place votes wins) voting and think about other ways to choose the winner of elections with more than two candidates.
Three candidate election
----------------------------------------------------------------------------
This expository/historical essay about "conflict" game theory may be a useful complement to what we are learning about in class.
Introduction to basic game theory: AMS Feature Column
----------------------------------------------------------------------------
These are the slides from the fourth Remote Presentation and deal with non-zero-sum games and elections. Included is a discussion of diffent types of ballots for elections.
Remote Session 4 Slides-Game Theory and Elections
----------------------------------------------------------------------------
Motion diagrams are a tool involving digraphs to look for stable points (pure strategy Nash equilibria) in zero-sum and non-zero-sum matrix games.
Motion diagrams for zero-sum and non-zero-sum games
----------------------------------------------------------------------------
These are the slides from the third Remote Presentation and deal with non-zero-sum games and elections.
Remote Session 3 slides - Non-zero-sum games and modeling elections
---------------------------------------------------------------------------
Homework Problems 2: Game Theory
Second Collection of Homework Problems: Game Theory
----------------------------------------------------------------------------
The notion of a Nash equilibrium (named for John Nash) is fundamental in game theory. To prove the existence of Nash equilibria in a broad array of games requires rather technical mathemaitcs and even when Nash equilibria are known to exist for a game sometimes they are hard to compute. This essay tries to get at the important ideas in an intuitive way using examples.
Ideas related to Nash equilibria
----------------------------------------------------------------------------
Scholars in psychology and other fields have found it useful to explore the nature of cooperative behavior by using game theory. This particular example is especially interesting and I call it the "free-lunch" game.
Game to explore cooperative behavior
----------------------------------------------------------------------------
Some practice problems for you think about related to game theory.
Game theory practice problems
----------------------------------------------------------------------------
These notes treat games against natue (decision making) and provide a brief introduction to the theory of non-zero sum games.
Games against nature and brief intoduction to non-zero-sum games
----------------------------------------------------------------------------
Slides for Second Remote Session, which deal with matrix games, and slides about elections that were not yet discussed.
Remote Session 2 slides - Matrix games and modeling elections
----------------------------------------------------------------------------
Course project - game theory and equity.
Course Project (GameTheory/Equity Models)
----------------------------------------------------------------------------
Homework Problems: Matrix Games
Problem Set I: Matrix Games
----------------------------------------------------------------------------
When trying to "solve" a matrix game it is nearly always worth the time to check if their are dominating rows and/or dominating columns. Eliminating the DOMINATED rows or columns gives an "equivalent game" for the purposes of solving the game (finding way to play the game optimally for each player) with a simpler structure. This activity involves practice with this notation.
Activity involving dominating rows/columns
----------------------------------------------------------------------------
When one plays a 2x2 matrix game one gets a sequence of integer outcomes for the payoffs from the individual plays of the game. Suppose you are asked if is there a way this sequence of payoffs can ever sum to a specific integer P. What about summing to P after exactly some specific number of plays of the game? This type of question has little practical value but it does lead to some interesting questions in number theory - ideas involving the solution of equations in integers, known as diophantine equations.
Payoffs achievable from a sequence of plays of a game
----------------------------------------------------------------------------
Some notes and questions related to zero-sum matrix games.
Zero-Sum matrix games
----------------------------------------------------------------------------
Some practice problems involving zero-sum games.
Zero-Sum game practice
----------------------------------------------------------------------------
For those interested in more detail about combinatorial games you might consider looking at these two survey articles I wrote some time ago, posted on the American Mathematical Society web pages. These two articles can be read indpendently of each other. if you want to find out more about Chomp you can also look at the link provided. The version of Chomp in this article is a bit different from what I described in class.
First part of article about combinatorial games
Second part of aricle about combinatorial games
Brief descripition of the combinatorial game chomp
----------------------------------------------------------------------------
The slides from Remote Presentation 1. Only about 2/3 of this was covered in class. The remaining part will be covered in our next session. These slides deal with combinatorial games, "political and economic" games, and the beginning of how to solve zero-sum 2x2 matrix games.
Remote Slides 1 - 2021
----------------------------------------------------------------------------
An activity about matrix games.
Activity about matrix games
----------------------------------------------------------------------------
An activity about elections
Activity about elections
----------------------------------------------------------------------------
Here is a primer of a very useful tool for modeling problems in all disciplines and there is a rich theoreticlal literature about graphs as well. There are many unsolved problems in this area for students at all levels.
Very brief intoduction to graph theory (dots and lines diagrams)
----------------------------------------------------------------------------
This handout suggests a variety of questions to think about to understand the nature of the concept of a game.
Questions about games and their nature
----------------------------------------------------------------------------
Sampler of fairness and game theory situations.
Sampler of fairness and game theory situations
----------------------------------------------------------------------------
Please complete this questionaire and email it to me. (You can just answer the questions and send a text file or scan and send an image of the completed form.)
Student questionaire to be filled out
----------------------------------------------------------------------------
Jordan Ellenberg at the University of Wisconsin in Madison has written an expository article about gerrymandering. The issue is that after each state is assigned its "fair" number of seats based on the 2020 census, the highly politicized state legislatures get to draw the district lines for new Congressional districts. Without safeguards these lines can be drawn to advantage one political party over another. Mathematics can be used to try to imporove the fairness of what is done.
Essay about gerrymandering
----------------------------------------------------------------------------
New materials Summer, 2020
This long article provides an introductory look at using ordinal ballots for conducting elections and discusses an appealing new method, called split cycle, which elects a Condorcet winner when there is one. The method, of course, is subject to Arrow's Theorem but it obeys many appealing properties.
Survey of election methods including discussion of a new method called split cycle
----------------------------------------------------------------------------
This long preprint is technical but also raises many important issues related to selecting a "stable marriage" that makes sense in practical situations where Gale/Shapley ideas are used to model the matching situation but where the size of the sets to matched present challenges in using the "classical" approaches. Lots of recent bibliographic listings.
Stable marriage
----------------------------------------------------------------------------
The evolutionary game theorist William Sandholm has died (1970-2020). Information about some of his works are here:
William Sandholm-papers
A set of lecture notes about games is linked below:
Sandholm Game Theory Notes
----------------------------------------------------------------------------
This newspaper column looks at some game theory models to understand behavior during the current pandemic.
Game theory look at the covid pandemic
----------------------------------------------------------------------------
New materials Spring, 2020
----------------------------------------------------------------------------
This is the syllabus for the Spring 2020 version of the course.
Game Theory syllabus 2020
----------------------------------------------------------------------------
Slides for last remote class with material about stable marriage (two-side-market) along the lines developed by David Gale and Llyod Shapley and one sided markets with a very brief treatment of the top trading cycle algorithm. Finally, a few very brief thoughts about mathematics education issues.
Remote session primarily about matching markets and stable marriage
----------------------------------------------------------------------------
Review questions for the final.
Review Problems for the final
These are the slides from the Remote Session Review, some of the examples changed to HOPEFULLY correct ERRORS in the original version of the slides.
Slides from Remote Review Session
These notes call attention to some common errors that showed up during grading homeworks that you might want to use as you look at the review problems - this set of notes is about 2-person zero-sum and non-zero-sum games.
Common mistakes in solving zero-sum and non-zero-sum games
You might find this expository article about games of use:
Expository AMS Feature column article about game theory
----------------------------------------------------------------------------
Homework 5: Game Theory/Fairenss
Home Work 5 - Apportionment Problems
----------------------------------------------------------------------------
Below are a cluster of items related to the idea of a centralized "market" for two-sided matchings, Gale-Shapely models. Two disjoint sets of "people" rank each other (e.g. hospitals looking for residents and medical school graduates looking for residencies) and the goal is to pair the two groups in a "stable" way. Applications include school choice and pairing legal school graduates and judges seeking clerks, kidney exchanges, etc. Two of the items are expository articles prepared for the feature column of the American Mathematical Society.
Notes about stable matchings: Gale-Shapley matching ideas
AMS Feature Column treatment of Gale/Shapley stable marriage ideas using the school choice context
AMS Feature Column about marriage theorems in mathamatics - one of which is the Gale/Shapley stable marriage theorem; the other (treated at the start of the article) is related to Philip Hall's systems of distinct representatives theorem.
----------------------------------------------------------------------------
Slides for Remote Session 6, which deal with more about the bankruptcy modeling - distriubting money from an estate when the estate will not cover all of the claims; cost sharing and profit sharing models, involving the coalition form of a game; two-sided matching markets - stable marriage ideas related to work of Gale, Shapley, and Roth with applications in school choice and pairing hospitals needing residents and medical school graduates. The basic idea is pairing two groups of players using a centralized market to use the player preferences to create stable pairings/"marriages."
Remote Session 6, slides
----------------------------------------------------------------------------
The two essays below are almost identical but due to notational issues I have written them as separate items. One deals with coalitions that form to try to share profits and the other deals with coalitions that form to try to share costs.
Coalition games to share costs
Coalition games to share profits
----------------------------------------------------------------------------
Slides for Remote Session 5, which deal with the bankruptcy modeling. This involves distributing to claimants an amount which is smaller than the sum of their claims. Also, the start of a look at how coalitions form in games with many players.
Remote Session 5, slides
----------------------------------------------------------------------------
Bankruptcy problems deal with claims agains a "pot" (money, river water, 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. Also, some practice problems to test your understanding of the different methods.
AMS Feature Column article about bankruptcy problems
COMAP Consoritum article about bankruptcy
COMAP Consortium article about bankruptcy-Followup to prior COMAP article
Bankruptcy problems - practice
----------------------------------------------------------------------------
Here is worked example comparing how Jefferson/D'Hondt which are similar in philosphy work in the US and Europsean version of apportiomment questions when the table method is used, and how this comparies with doing a version of the problem using the round down rounding rule
Remote Session 4, slides
----------------------------------------------------------------------------
Slides for Remote Presentation 4; treats the table method for apportionment and other aspects of how to choose one divisor/table method over another using fairness ideas; introduces the bankruptcy model - what amount should claimants get when the sizes of the claims add to more than the "estate," used to pay off the claims.
Comparison example for D'Hondt and Jefferson using the table method approach
---------------------------------------------------------------------------
To fully understand some of the issues related to Huntingon's two-state fairness comparisons it is helpful to realize the complexities involved in comparing relative and absolute changes in a quantity. This essay tries to raise some of the issues involved.
Relative and absolute change
----------------------------------------------------------------------------
Below are templaes for four divisor methods implemented using rank-index tables, for each of 4 methods, with 3 candidates and 4 candidates: D'Hondt/Jefferson, Webster, Huntington-Hil and Adams (so 8 different templates in all. You can use these to practice your skill at using the table method for doing 3 and 4 claimant examples with relatively small house sizes h. Huntington-Hill and Adams force each state to get at least one seat automatically. The commonly looked at method for which there is no template is Dean's Method, which is based on the Harmonic Mean.
Template Table for Huntington-Hill 3 states
Template Table for Huntington-Hill 4 states
Template Table for D'Hondt/Jefferson 3 states
Template Table for D'Hondt/Jefferson 4 states
Template Table for Webster 3 states
Template Table for Webster 4 states
Template Table for Adams 3 states
Template Table for Adams 4 states
----------------------------------------------------------------------------
Slides that give a proof that when one prepares a table to implement the Webster Method (rank-index) approach the table should have rows where the original claims (population of claimants) are divided by 1, 3, 5, ..... The proof involves some symbolism and work with inequalities.
Proof of table approach to Webster's apportionment method
----------------------------------------------------------------------------
These slides discuss the way that apportionment problems can be approached with a round rule method or an equivalent method, which I call the table method, but usually called the rank-index approach. This procedure is computationally more transparent for small values of the house size h that is being apportioned.
Slides for Remote Session 3; Apportioment using either rounding rules or table method
----------------------------------------------------------------------------
"Slides" for Remote Session 2 (Some loose ends about axiomatic ideas related to the Satterhwaite-Gibbard result (elections with many cadidates encourage strategic voting), power indices of weighted voting games, floor and ceiling function, the apportionment problem, Hamilton's and Webster's methods for apportionment, other divisor/rounding rule methods, brief discussion of the Balinski/Young Theorem).
Slides Remote Session 2; Power indicees and apportionment
----------------------------------------------------------------------------
Here are some notes about various aspects of the apportionment problem to complement other essays that are available below.
Appoortionment note
----------------------------------------------------------------------------
This essay raises some issues concerning weighted voting and helping players who are involved in such situations to understand the "power/influence" relationships involved. There are also "theoretical questions" for those who are interested in mathematical questions that go beyond using weighted voting as a nifty modeling/context situation for K-16 education. Hillary Clinton won the popular vote in the 2016 election but lost in the Electoral College so there is a lot of discussion about what might happen in the Electoral College in the 2020 Presidential election. Also, with Britain no longer part of the European Union the power relations between the remaining countries has to be redefined.
Voting games and weighted voting games
----------------------------------------------------------------------------
"Slides" for Remote Session 1 (Review of elections methods, axiomatic ideas related to voting (Arrow-Satterhwaite-Gibbard results, fairness axioms for voting, rational for weighted voting and the need for power indices because "power" and weight are not related; a voter can have positive weight but no power. There are slides about apportionment but I did not get to these in this session and will do so in remote session 2.
Slides remote session 1; elections and weighted voting
----------------------------------------------------------------------------
Those expository articles that appeared in the Feature Column of the American Mathematical Society that I wrote may prove to be helpful with some of the ideas that we are learning about.
Mathematical approaches to voting
Elections - methods and fairness issues
Voting games 1
Voting games 2
Apportionment 1
Apportionment 2
----------------------------------------------------------------------------
Apportionment turns out to have a surprisingly rich collection of approaches to finding a solution to how to assign each claimant (be it a state in the US or a party in Europe) to a share of the seats in a legislature or parliament. Many other kinds of apportionment questions can also be solved by methods of the kind that have been developed (for example, distributing a present of computer systems to the different schools in a school district). This essay looks at approaches to fairness for the apportionment problem that involves fairness for pairs of claimants. Other approaches involve "global optimization" but these approaches will not be discussed. While the theory invovled is quite complex, the algorithms for pairwise fairness methods involve nothing more than arithmetic!
Pairwise equity for claimants in an apportionment situation
----------------------------------------------------------------------------
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
---------------------------------------------------------------------------
So called divisor methods (based on rounding rules) were developed in Europe and America for problems related to apportioning seats in a "parliament" (legistlature) based on population in the US or party vote in Europe. Later the mathematician E.V. Huntington showed an easier approach for algorithms to solve apportionment problems using tables. More recently the late Michel Balinski and H.P. Young wrote extensively about this mathematical model.
Divisor methods for apportionment
----------------------------------------------------------------------------
This activity introduces apportionment problem ideas - claimants have different size claims against a positive integer prize, and must be awarded non-negative integer amounts that add up to the prize.
Apportionment activity
----------------------------------------------------------------------------
Some notes related to the apportionment model.
Appoortionment model
----------------------------------------------------------------------------
A legistlature has an integer number of seats h (perhaps 47). In an election the parties competing for seats in the legislature have various fractions of the total vote (perhaps 3/10, 2/10, 4/10, and 1/10). How many seats should each party get? This problem sounds simple but is very complex because of the issue of dealing with the fractional parts of the exact fair share. Ten percent of 47 is 4.7. How many seats should be awarded to the party entitled to this fair share? Assigning States in the US seats in the House of Representatives is very similar. There are many other examples and there is a fascinating theory of how to deal with such problems. Traditionally, this problem is called the Apportionment Problem.
Apportionment
----------------------------------------------------------------------------
Some practice problems involving coalition, voting, and weighted voting games.
Practice problems involing coalition and weighted voting games
----------------------------------------------------------------------------
Here is a template for calculating the Shapley/Shubik Power Index.
Template Shapley-Shubik Power Index
----------------------------------------------------------------------------
Here is a template for calculating the Banzhaf Power Index.
Banzhaf power index template
----------------------------------------------------------------------------
This is a brief introduction to weighted voting games (coalitional games), such as used in most NY counties, the European Union, and the electoral college. There is a brief account of how to compute the "power" of the players in such games. The most important power indices are those that are due to Banzhaf and Shapley/Shubik but Coleman's Power Index is easier to understand and compute. Templates to help practice how to compute these power indices are available on this web page.
Coalition and Weighted voting games
Similar material is here:
Weighted voting and voting games
----------------------------------------------------------------------------
Some elections using ordinal ballots don't have a Condorcet winner, someone who can beat all of the other candidates in a two-way race. However, even when there is a Condorcet winner some scholars argue that this person may not "deserve" to win. Here is a look at this issue.
Is Condorcet the best voting method?
----------------------------------------------------------------------------
While in America plurality voting is used almost exclusingly to decide elections there are in fact many appealing methods, nearly all of which are surperior to plurality and don't ask much more of the voters in terms of the ballot they must produce. Here are some examples.
Sampler of election decison methods
----------------------------------------------------------------------------
Homework 4: Elections
Some homework problems involving elections
----------------------------------------------------------------------------
There are many different appealing methods for taking a set of ranked (ordinal) ballots and deciding who should win. Here is a chance to practice some of these methods and perhaps to invent some new ones.
Practice problems involving election decision methods
----------------------------------------------------------------------------
Exercises, contexts, problem solving, etc. are commonly used terms in mathematics edcuation. This essay tries to offer some views about how these terms compare and contrast. An example using a bankruptcy situation is used to illustrate some of the different aspects of these terms.
Contexts, Exercises, Modeling, Problem Solving compared
----------------------------------------------------------------------------
While for zero-sum games it is good advice to play these games in terms of taking actions that lead to a Nash Equilibrium, this is not good advice for non-zero sum games. The notions of prudential and counterprudential strategies are one approach that offers "alternative" advice as to how to play other than then actions leading to a Nash Equilibrium. Here is an exmaple which shows some calculations in looking at these alternative approaches.
Alternatives to playing Nash Equilibirum strategy
----------------------------------------------------------------------------
This activity is designed to show that when people grade or produce preferences among choices they must make it is not always obvious that they have the skill to do this in a consistent way.
Paired comparison activity
----------------------------------------------------------------------------
These notes provide a work in progress glossary to the terms that people who delve in the world of mathematical insightes into elections/voting might come across.
Elections/voting glossary
----------------------------------------------------------------------------
Appealing election methods sometimes can seem less appealing when they produce results in particular elections that seem unintuitive or show that different methods yield different a winner for the same voter input. This essay collects some elections that display perhaps unexpected behavior when diffent methods are used.
Troubling elections
----------------------------------------------------------------------------
Many people are surprised when different appealing methods of deciding elections select different winners. This election is designed to display this phenomenon.
Same ballots, different winners
----------------------------------------------------------------------------
Starting in 2021, NYC will be using IRV (sequential run-off) as its election method. Voters will present their choices using ordinal (ranked ballots). This discussion is related to the fact that there are some elections where many people would argue pluralit voting does better than sequential run-off.
An election where IRV (sequential run-off produces "unappealing" results
----------------------------------------------------------------------------
In many voting situations one is picking a single winner but in other cases one is trying to rank a collection of choices (perhaps best film of the year). This essay explores some issues related to this distinction.
One winner compared with finding a ranking
----------------------------------------------------------------------------
There are lots of entry points to augment what we are studying in game theory. One such approach is to look at resources on Wikipedia. Here is a list of some terms that you can find there augmented by a list of some important practitioners of game theory and fairness modeling. Some of the individuals listed are still alive and active researchers and others are now deceased.
Game theory terminology
----------------------------------------------------------------------------
Homework 3: Game Theory
Home Work 3 - Game Theory
----------------------------------------------------------------------------
Voting and elections are big aspect of modern life in America. Not only are their national elections for President and Congress (House of Representatives and Senate), but statewide elections and municipal elections. Elections take place in schools and colleges. There is also voting for best picture, best athlete and other ranking or selection environments. Mathematics has long played a role in finding insight into how to take individual opinions and choices and amalgmaate them into a choice for a group of individuals. However, systematic study of this circle of ideas is surprisingly recent, with much credit due to Kenneth Arrow for his important work. This topic should be, but is not, a topic in K-12 education. This essay provides an introduction to some of the issues for electing a single winner or producing a rankng for a group based on the input of a collection of individuals. The issue of electing members for a committee has lots of mathematics, too, but is not specifically discussed here.
An indtroduction to the mathematics of elections and voting - Beyond Plurality Voting
----------------------------------------------------------------------------
John Nash proved an important theorem about equilbria in general games, in particular those where zero-sum does not hold. How Nash equilbira are defined and computed for simple cases is explored here.
Nash equilibria
----------------------------------------------------------------------------
Now zero-sum games are much more subtle to play and analyze that zero-sum games. This famous game is designed to explore the extent to which people are willingly cooperate with other people.
Free lunch and sharing behavior
----------------------------------------------------------------------------
An election example involving 3 candidates designed to show some of the unintended effects of the system that will be used in NYC for local elections starting in 2021.
Some unexpected aspects of using a sequential run-off election system
----------------------------------------------------------------------------
Here are some more practice problems to try out related to finding optimal spinners for the players in a zero-sum matrix game.
Practice problems involving zero-sum games
----------------------------------------------------------------------------
Homework 2: Game Theory
Home Work 2 - Game Theory
----------------------------------------------------------------------------
Zero-sum games are very artificial so it is nature to generalize to 2x2 matrix games where the payoffs to players need not add to zero. Unfortunately, many of the nice results from zero-sum games don't carry over, but there is a very natural notion of an equilibrium outcome which generalizes ideas we saw for zero-sum games. This is the idea due to John Nash, and now known as the Nash Equilibrium. Here are two items that deal with non-zero sum games. The first version below is a slightly updated version of the second.
Non-zero-sum Games Slightly Updated
Non-zero-sum Games
Non-zero-sum game activity
----------------------------------------------------------------------------
We have looked at games where two players actively compete against each other. However, sometimes a player (Row) makes choices (decision maker) and "nature chooses" an alternative that affects what Row's payoffs are from his/her actions. For example Row may have the choice of planting a variety of different crops where the payoff will depend on "nature providing" a very wet, wet, normal rain, dry or very dry season. This note explores some of these ideas.
Making decisions and games against nature
----------------------------------------------------------------------------
Here are some practice problems to try out related to finding optimal spinners for the players in a zero-sum matrix game.
Practice problems involving zero-sum games
----------------------------------------------------------------------------
Some notes about zero-sum matrix games.
Zero-sum matrix games
----------------------------------------------------------------------------
Sometimes in analyzing a 2-person zero-sum matrix game the game matrix can be simplified by eliminating dominated rows or columns. Rational players would never play such dominated rows and columns. These notes provide some examples to practice on.
Dominating rows/columns analysis of matrix games
----------------------------------------------------------------------------
Homework 1: Problems related to zero-sum games and how to play them optimally.
Home Work 1
----------------------------------------------------------------------------
This is a description of a project that can be carried out related to game theory and fairness modeling.
Game Theory Course Project
----------------------------------------------------------------------------
A cluster of activities involving zero-sum games and elections using ranking ballots. In voting situations it is of interest to understand the structure of those candidates who wins two-way votes between canddiates. For this, it is helpful to have templates to represent the restults of the 2-way reaces. Here there is a diagram for use with reporting the results of two-way races when there are 5 candidates. Alternatively, one can use this for recording wins and losses in a 5-play tournament.
A voting/election and game theory activity
Game Theory activity
Template for 5 candidate two-way races
----------------------------------------------------------------------------
This activity introduces one to the idea of 2-player zero-sum matrix games. Each player can take certain actions which lead to payoff to the players where what one player gain the other player loses. The underlying question is if there is an optimal way to play these games by both players and how one can tell when a game is fair.
Zero-sum matrix game activity
----------------------------------------------------------------------------
Here are some discussion questions related to different types of games, as a way to lead up to a mathematical discussion of the taxonomy of games and how to approach studying them mathematically.
Questions about games and their nature
----------------------------------------------------------------------------
For modeling situations in game theory, decision making and fairness issues, being able to represent information with a dots/lines geometric diagram called a graph is often helpful. Here is a very brief introduction to the ideas of graph thoery.
Very brief introduction to graph theory
----------------------------------------------------------------------------
This is a sampler of the kinds of problems related to game theory and modeling fairness situations that can be studied with relatively elementary mathematical tools (that is, don't use Calculus).
Game Theory and Fairness Modeling Sampler
----------------------------------------------------------------------------
New materials Summer, 2019 and Fall, 2019
----------------------------------------------------------------------------
What is often called the Shapley power index for a weighted voting game is often also called the Shapley/Shubik Index, honoring the contribution of the late Martin Shubik to this work. Here is a page of testimonials about Shubik's work as a game theorist and economist. Unlike Shapley, who was a mathematician, Shubik was an economist.
Tributes to Martin Shubik
----------------------------------------------------------------------------
As the use of school choice models widdens a variety of intriguing variants of how to implement systems with appealing properties are emerging. This article looks at some ways to try to improve what one can accomplish.
School choice with reserves
---------------------------------------------------------------------------
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
------------------------------------------------------------------------------
This article deals with some of the practical aspects of using Gale/Shapley ideas for matching high school students and schools in New York City, and Nobel Prize winner, Alvin Roth, is one of the co-authors of this paper.
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