Mathematical Game Theory (Notes)

Prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

email:

web page:

The materials below were developed for both graduate and undergraduate courses taught under the title "Game Theory." The philosphy of these courses is to cover as broad a range of topics with a game theory flavor as possible. It it generally easier to get a deeper knowledge of a subject X where one has seen the key ideas and some of the major results than it is to start off reading in a book devoted only to the content of topic X.

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

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

Generic Syllabus

Syllabus

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

New matrials Summer and Fall, 2017

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

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

Manipulating elections

Manipulating elections with preference reversals

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

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

Using mathematics to draw electoral district lines

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

Whimsical comment on voting systems

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

Conference on Fair Division

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

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

Voting sytems

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

Voting related articles

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

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

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

DC School Choice

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

Some new materials added starting Spring, 2017.

Syllabus for Spring, 2017

Syllabus

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

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

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

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

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

Pairwise apportionment equity and some worked examples

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

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

Apportionment Via the "table" method

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

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

Apportionment and modeling

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

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

Apportionment

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

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

Apportionment Examples 1

Apportionment Examples 2

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

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

Bankrupty practice

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

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

Activity involving being "fair."

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

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

Obituary for Kenneth Arrow from Nature Magazine

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

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

School Choice in New Orleans

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

High School Student Matching for New Yort City

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

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

Bankruptcy Modeling

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

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

Game Theory Course Review Problems

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

A set of problems to solve.

Problems Set 5

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

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

Two-Sided Markets (Gale/Shapley)

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

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

Matching Markets

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

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

Unraveling in 2-sided markets

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

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

Matching market practice

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

Here are some problems and basic definitions regarding matching markets.

Matching markets

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

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

Two-sided markets

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

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

Voting Game Practice

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

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

Voting and Weighted Voting Games

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

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

Weighted Voting Game Activity

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

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

Interpersonal comparison of utilities

Revealed preferences

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

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

Elections method example

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

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

Election methods problems

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

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

Different election decision methods

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

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

Election methods activity

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

Practice using various voting methods.

Elections method example

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

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

Essay on on social choice theory

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

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

Obituary for Kenneth Arrow

You can find out more about Arrow here:

Wikipedia article about Kenneth Arrow

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

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

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

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

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

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

Election where different reasonable election methods yield different winners.

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

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

Paired-Comparison Activity

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

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

Game theory terminology and scholars

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

Some game theory problems.

Some game theory problems.

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

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

Nash equilibria

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

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

Zero-sum and non-zero-sum games

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

Some game theory problems to work on.

Game theory problems

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

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

Games against nature and decision making

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

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

Game Theory Practice Problems

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

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

Robert Wilson and applications of game theory

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

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

Game Theory and Diophantine equations

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

Some problems about zero-sum games.

Zero-sum games

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

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

Some activities to get started with zero-sum matrix games

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

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

Questions about games and their nature

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

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

Dynamic Games

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

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

Ad Auctions

Mechanism design for ads

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

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

Alvin Roth's Market Design Blog

Game Theory Tuesdays Blog

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

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

Practice Problems 1: Zero-sum games

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

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

Zero-sum games

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

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

Game Theory Sampler 2017

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

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

Graph Theory Primer

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

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

Why did Western Europe Adopt Proportional Representation?

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

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

Economist article about the Nash Equilibrium

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

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

NY Times Obituary for Thomas Schelling

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

Some new materials added starting Fall, 2016.

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

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

Proceedings of a conference on matching markets

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

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

What is Happening in Game Theory

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

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

Scheduling Tennis Matches

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

Some new materials added starting Summer, 2016.

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

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

Matching refugees to housing

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

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

Matchings when performance is better than expected

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

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

Conference Program and link to reading list for Market Design Conference

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

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

NY Times item on Game Theory and Fairness

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

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

Kidney Exchange and Mechanism Design

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

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

Use of Condorcet voting in France

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

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

Applications of Game Theory to Computer Science

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

Syllabus for 2016

Syllabus

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

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

Game Theory and energy consumputon

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

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

A matching problem with 10 stable matchings!

A practice problem involving Gale/Shapley

A practice problem involving Gale/Shapley

Some notes on Gale/Shapley

Some "probing questions" about Gale/Shapley

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

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

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

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

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

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

Bankruptcy practice problems

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

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

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

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

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

American Mathematical Society Feature Column article about bankruptcy questions

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

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

Bankruptcy Problems and Methods

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

Practice Problems for the Final.

Practice Problems for the Final

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

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

Comments about Lloyd Shapley by Alvin Roth

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

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

Peyton Young's paper about compactness

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

Example of gerrymandering

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

Different ways to gerrymander

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

Homework Assignment 5: Spring 2016

Homework Assignment 5

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

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

Coalitonal Games

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

Template for a Banzhaf Power Index Calculation with 4 players

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

Some practice problems involving weighted voting:

Weighted voting and power indices

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

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

"Whither Game Theory?

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

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

Rounding rule apportionment: Jefferson, Webster, and Adams

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

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

Obituary for Lloyd Shapley

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

Comments on the death of Lloyd Shapley

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

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

More notes on Apportionment Problems

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

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

Election Methods Practice

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

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

Homework 4: Elections

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

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

Evolution of Cooperation

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

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

Apportionment Problems

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

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

Different Kinds of Election Ballots

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

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

Paired Comparison Activity

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

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

American Mathematical Society Feature Column about voting and elections

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

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

Brief descriptions of some important voting methods

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

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

Practice different methods for finding the winner of an election

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

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

Election Activity

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

Homework 3: 2016

Homework 3

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

Some more game theory problems for practicing basic ideas.

Game Theory Practice

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

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

John Nash

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

List of Wikipedia biographies of game theorists.

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

List of game theorists who have Wikipedia articles.

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

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

Prisoner's Dilemma

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

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

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

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

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

Nash Equilibria

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

Homework Assignment 2: Spring 2016

Homework Assignment 2

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

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

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

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

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

Practice problems involving zero-sum matrix games

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

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

12th European Meeting on Game Theory

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

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

Non-zero Sum Games

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

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

Games Against Nature and Non-Zero Sum Games

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

Homework Assignment 1: Spring, 2016

Homework Assignment 1: 2016

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

Game Theory Project: Spring 2016

Game Theory Project 2016

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

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

ArXiv Preprint Server

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

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

Practice: Zero-Sum Matrix Games

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

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

Activity about Zero-Sum Matrix Games

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

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

Mathematics of Elections Activity

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

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

Game Theory search strings for Wikipedia or the web

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

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

Brief introduction to graphs and digraphs

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

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

Things to Think About

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

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

Game Theory Sampler

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

Some course information

Course Information

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

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

Free Game Theory book (pdf) to download

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

Some new materials added for Spring, 2015.

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

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

Game Theory Related to the Greek Debt Crisis

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

Some new materials added for Fall, 2014.

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

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

Game Theory web site (Italy)

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

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

Jean Tirole

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

Some new materials added for Summer, 2014.

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

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

Obituary for Harold Kuhn

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

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

Stony Brook Center for Game Theory

25th Anniversity: Stony Brook Game Theory Center

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

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

The work of Tayfun Sonmez and Utku Unver

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

Some new materials added for Fall, 2013.

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

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

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

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

Some new materials added for Summer, 2013.

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

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

Games - open access game theory journal

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

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

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

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

Modeling Situations in Game Theory and Fairness

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

Some new materials added for Spring, 2013.

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

Syllabus, Spring 2013

Syllabus

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

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

Game Theory Sampler

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

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

Course Information and Game Theory blogs

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

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

Some questions related to the game theory environment

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

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

Game Theory Terminology - Wikipedia

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

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

Practice Problems: Zero-Sum Games

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

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

Matrix games - the zero-sum case

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

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

Game Theory Journals

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

Mathematics and Statistics, Game Theory

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

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

Practice Problems-2: Zero-Sum Games

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

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

Graph Theory Primer

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

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

Practice Problems-3: Non-Zero-Sum Games

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

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

Notes on Nash equilibria and Non-Zero-Sum Games

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

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

Practice Problems-4: Elections and Election Methods

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

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

Thematic Approaches to Mathematical Modeling

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

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

Weighted voting and power indices

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

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

Summatory Review of Game Theory and Equity Problems

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

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

Apportionment I

Apportionment II

Apportionment III

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

AMS Feature Column on Apportionment

Second AMS Feature Column on Apportionment

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

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

Notes about some apportionment problem methods

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

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

Notes about some apportionment problem methods

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

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

Practice Problems Involving Apportionment

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

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

Bankruptcy Problem Modeling

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

Some new materials added for Fall, 2012.

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

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

Nobel Memorial Prize in Economics, 2012

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

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

International Society on Dynamic Games

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

Some new materials added for Summer, 2012.

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

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

Exercises, Problem Solving, and Modeling

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

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

Poll on Course Topics in a Game Theory Course

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

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

Apportionment I

Apportionment II

Apportionment III

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

AMS Feature Column on Apportionment

Second AMS Feature Column on Apportionment

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

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

Template for a Banzhaf Power Index Calculation with 4 players

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

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

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

Cost Allocation: Fairness of Improving a Road

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

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

Bankruptcy Problem Methods - Practice

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

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

Election Methods Practice

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

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

Gale-Shapley Algorithm - Practice

Gale-Shapley Algorithm - Practice 2

Gale-Shapley Algorithm - Practice 3

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

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

Two-Side Markets

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

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

Alvin Roth's Market Design Blog

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

Blog devoted to economics, computer science and game theory

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

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

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

More matrix game problems - two players

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

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

Zero-sum matrix game problems - two players

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

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

Two person zero-sum matrix games

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

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

Chronology of Game Theory

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

Return to Joseph Malkevitch's Home Page