A Practical Introduction to Dynamic Programming

1. Introduction to Dynamic Programming
Dynamic programming is a powerful technique to solve computational problems, which have a recursive substructure and recurring subproblems. The idea is to solve these recursive subcases and store these solutions in a lookup table. When a solved recursive subcase is encountered, the existing solution is accessed using only a constant number of steps. A solution to the initial instance is constructed from the solutions to the sub-cases, typically in a bottom-up manner. Frequently, the computational problems of interest are optimization problems. Common examples include the Shortest Path Problem, the Rod-Cutting Problem, and the Game of Nim. We provide a practical exposition, introducing some examples amenable to the dynamic programming technique. The goal of this tutorial is that the readers can successfully apply the dynamic programming technique. To that end, this tutorial is not a complete treatment of the subject. In particular, issues of computational complexity are largely not discussed here. Readers interested in more advanced expositions should direct their attention to common algorithm analysis texts, such as Sedgewick and Wayne, or CLRS.

1.1 The Game of Nim
We consider the following two-person game, in which players alternate turns. The game begins with a pile of (identical) stones. During a player’s turn, they may remove either or stones from the pile. If a player cannot make a move, that player loses. This game is denoted as a -Nim game, in light of the allowed moves of removing 1, 2, or 3 stones. We define the game of Nim more formally.

Definition 1 (Nim). Let be distinct, and let . The game -Nim is a two player game, which is initialized with a pile of stones. Players alternate removing stones from the pile, where the number of stones each player can remove on their turn lies in the set . A player loses if they cannot make a move on a given turn.

Remark: In -Nim, a player loses if there are no stones left. However, in -Nim, a player loses if there are fewer than 2 stones left on the pile.

We restrict attention to -Nim, with the goal of illustrating the dynamic programming technique to determine for which values of Player 1 will win. Here, we assume both agents play optimally; that is, both players seek to win the game and are able to determine the best move to achieve their goal. We denote to indicate a loss, and to denote a win.

1. We begin by initializing our lookup table to store whether or not Player 1 will win, given a pile with stones. Clearly, if , Player 1 loses. So . Similarly, if , then Player 1 can take all the stones and win in one turn. So .
2. Now suppose there are stones. No matter how many stones Player 1 takes (whether it be 1, 2, or 3 stones), Player 2 takes the remaining stones. So Player 1 always loses. Thus, we set .
3. Suppose there are stones. Suppose Player 1 selects stones. Now Player 2 is the first player in a smaller instance of -Nim with stones. Here, we begin to see the power of dynamic programming in constructing strategies. We have already computed whether Player 2 will win in the smaller instance of Nim with stones, and so we can just look up the result in . Observe that if and only if (i.e., ). So for , Player 1 starts by taking a single stone. Then Player 2 will lose. So .
4. Using similar reasoning as in part (c), we have that .
5. Now what happens if there are stones? Suppose that Player 1 takes stones. So Player 2 is the first player in a smaller instance of -Nim with stones. For each , . So Player 2 will always win. Thus, .

While we can continue building the lookup table, it may be more insightful to look at the entries already present. Observe that and are the only entries with . This leads to the following observation.

Proposition 1.1. In -Nim with stones in the pile, Player 1 has a winning strategy if and only if is not a multiple of 4.

Proof: The proof is by strong induction on . We have the following base cases:

• Case: Suppose . Player 1 has no available moves, and so Player 1 loses.
• Case: Suppose . Player 1 takes all available stones. So Player 2 has no moves and loses. Thus, Player 1 wins.

Now fix , and suppose that the proposition holds for all . We prove true for the case. have the following cases:

• Case: Suppose that is not a multiple of 4. By the Division Algorithm, we may write for some . We show that it is a winning strategy for Player 1 to take stones on their first turn. After Player 1 takes stones, Player 2 takes their turn with stones remaining. Observe that Player 2 is the first player in a smaller instance of -Nim with stones. By the Inductive Hypothesis, Player 2 has no winning strategy, as is a multiple of 4. So Player 1 has a winning strategy, as claimed.
• Case: Suppose that is a multiple of 4. For any , is not a multiple of . Suppose Player 1 removes stones from the pile. Then Player 2 is the first player in a smaller instance of -Nim with stones. As and is not a multiple of , we have by the inductive hypothesis that Player 2 has a winning strategy. Thus, Player 1 does not have a winning strategy, as claimed.

The result follows by induction. QED.

Remark: When working with instances of Nim, it is helpful to employ dynamic programming with the goal of determining the period of the game, or the length of the pattern of wins and losses that repeat within the lookup table. Once this pattern is ascertained, we may appeal to the pattern to decide in constant time who wins the game. More exposition and generalizations of Nim are discussed in Combinatorial Game Theory, and we direct interested readers to look there for more in-depth exposition on Nim.

1.2 Rod-Cutting Problem

In this section, we examine the Rod-Cutting Problem. Let us consider a motivating example. Suppose we have a rod of length , which can be cut into smaller pieces of lengths or These smaller rods can then further be cut into smaller pieces. Now suppose that we can sell rods of length 1 for $1, which we denote . Similarly, suppose that the prices for rods of length are given by and respectively. We make two key assumptions: we will sell all the smaller rods, regardless of the cuts; and that each cut is free. Under these assumptions, how should the rod be cut to maximize the profit? We note the following cuts and the corresponding profits.

• If the rod is cut into five pieces of length , we stand to make .
• If the rod is cut into one piece of length and one piece of length , we stand to make .
• If the rod is cut into two pieces of length and one piece of length , we stand to make .

Out of the above options, cutting the rod into one piece of length 2 and one rod of length 3 is the most profitable. Of course, there are other possible cuts not listed above, such as cutting the rod into one piece of length 1 and one piece of length 4. The goal is to determine the most profitable cut. The Rod-Cutting Problem is formalized as follows.

Definition 2 (Rod-Cutting Problem).

• Instance: Let be the length of the rod, and let be non-negative real numbers. Here, is the price of a length rod.
• Solution: The maximum revenue, which we denote , obtained by cutting the rod into smaller pieces of integer lengths and selling the smaller rods.

Intuitively, the maximum revenue is determined by examining the revenues for the subdivisions and taking the largest. Mathematically, this amounts to the following expression:

We begin by working through an example of utilizing dynamic programming to determine the maximum profit.

Example 1. Suppose we have a rod of length 5, with prices . We proceed as follows.

1. Initialize a lookup table . Now for a rod of length 1, there is only one price: . So we set .
2. Now consider a rod of length 2. There are two options: either don’t cut the rod, or cut the rod into two smaller pieces of length 1. Here, represents the case in which no cuts to a rod of length 2. Now suppose instead we cut the rod up into two smaller pieces each of length 1. We know that the maximum profit for a rod of length 1 is . So the profit of cutting the rod into two smaller pieces each of length 1 is . Now , so we set .
3. Now consider a rod of length 3. Here, we have more options: we can leave the rod untouched, we can divide the rod into smaller pieces of length 1 or length 2; or we can divide the rod into three pieces of length 1. If we do not divide the rod into smaller pieces, the profit is . Now suppose we divide the rod up into smaller pieces of length 2 and length 1. We may now keep this configuration, or further divide the rod of length 2 into two rods each of length 1, as discussed in the previous bullet point. Rather than re-solving this problem, we can simply look up the maximum profit for a rod of length 2 in the lookup table. Recall that and . So the profit from cutting the rod into smaller pieces of length 2 and length 1 is . Now , so we set .
4. Now consider a rod of length 4. We have the following options for the first cut: leave the rod uncut, in which we stand to make profit ; cut the rod into smaller pieces of length 1 and length 3; or cut the rod into two smaller rods, each of length 2. Consider the case in which we cut the rod up into smaller pieces of length 1 and length 3. The natural, though inefficient, approach here is to consider all the ways in which we could cut up the rod of length 3. It turns out that we don’t need to do this, as the maximum revenue attainable from a rod of length 3 was found in the previous bullet point. This is the power of dynamic programming: once a solution to a smaller problem is found, we simply look it up rather than re-solving the smaller problem. Similarly, we can look up the maximum profit for a rod of length 2. So given our cases, we have the following possible profits:
   • The uncut rod of length 4 will result in profit .
   • The rod cut into pieces of length 3 and length 1 will result in profit .
   • The rod cut into two pieces, each of length 2, will result in profit .

   So .

5. Finally, consider our original rod of length 5. We have the following possible initial cuts:
   • We can leave the rod uncut, in which case we will make profit .
   • We can cut the rod into one piece of length and one piece of length 1. The maximum revenue attainable by cutting up a rod of length 4 was determined already. So we can simply look up this solution in . Thus, the profit in this case is .
   • We can cut up the rod into one piece of length 3 and one piece of length 2. By similar argument as above, we may simply look up the maximum revenues attainable from a rod of length 3 and a rod of length 2. So our profit is .

   So . Thus, we set .

We conclude that we stand to make from a rod of length 5.

While the expression

may not seem insightful, it in fact provides an algorithm to compute . Example 1 provides a tangible example of this algorithm. The goal now is to generalize the algorithm from Example 1 to work for any rod of positive integer length any list of prices. We proceed as follows.

1. Initialize the lookup table , and set .
2. We set . Here, represents the case in which no cuts to a rod of length 2, and represents the case in which a rod of length 2 is cut into two rods each of length 1. We note that .
3. We set . Now , and . We have already solved the rod cutting problem for a length 2 rod, so we simply look up in the table rather than re-solving the problem.
4. . As we have already computed , we may look up their respective values in rather than re-computing these values.

Continuing in this manner, we compute , which is the value in after the algorithm terminates.

Remark: This algorithm only provides the maximum revenue. It does not tell us how to achieve that result. As an exercise, modify the algorithm to produce an optimal set of rod cuts.

1.3 Longest Common Subsequence Problem
Solutions to both the Rod-Cutting Problem and Nim utilized dynamic programming techniques, where the lookup table was one-dimensional. In this section, we introduce the Longest Common Subsequence Problem, which is also amenable to the dynamic programming technique. However, unlike the Rod-Cutting Problem and Nim, the lookup table for the Longest Common Subsequence Problem is a two-dimensional table rather than a one-dimensional array. The purpose of this section is to illustrate the usage of multidimensional lookup tables in dynamic programming problems. To this end, the Longest Common Subsequence Problem serves as a tangible example. We begin by formalizing the Longest Common Subsequence Problem.

Definition 3 (Subsequence). Let be a finite set, which we refer to as an alphabet. Let . We say that is a subsequence of if there exists a strictly increasing sequence of indices such that for all .

Example 2. Let , and let . Consider the sequence of indices . So and . Thus, is a subsequence of .

Definition 4 (Common Subsequence).
Let be an alphabet. Let be sequences. We say that is a common subsequence of and if: is a subsequence of , and is a subsequence of . Note that does not have to appear as a subsequence in the same position in both and .

Example 3. Let and . The sequence is a subsequence of both and . Here, appears in at the indices , and appears in at the indices .

Definition 5 (Longest Common Subsequence Problem (LCS)).

• Instance: Let be an alphabet, and let be sequences.
• Solution: A sequence that is common to both and ; and for any other common subsequence of and , .

The naive approach to solving LCS is enumerating all the possible subsequences of and , and recording the longest. Without loss of generality, suppose that . So there are possible index sequences to check, which correspond bijectively to subsequences of . So for large sequences, the brute force and ignorance solution is not a practical solution. The dynamic programming approach provides a linear time algorithm instead.

Dynamic programming works best when optimal solutions to subproblems can be used to construct an optimal solution to the original instance. We first show that LCS exhibits this property.

Theorem 1.1. Let be an alphabet, and let be sequences. Let be a longest common subsequence of and . The following hold:

1. If , then and is a longest common subsequence of and .
2. If and , then is a longest common subsequence of and . Similarly, if and , then is a longest common subsequence of and .

Proof:

1. Let be a common subsequence of and whose last digit does not correspond to the last instance of the character in and . Then can be augmented by appending the character . So every longest common subsequence of and has last character .We now show that is a longest common subsequence of and . Observe that is a common subsequence of and . Suppose to the contrary that there exists a longest common subsequence of and , with . Then can be augmented with to obtain a common subsequence of and . This contradicts the assumption that any longest common subsequence of and has length . So is a longest common subsequence of and .
2. Suppose that . Now suppose that . We show that is a longest common subsequence of and , by contradiction. Let be a longest common subsequence of and of length . Clearly, is a common subsequence of and . Now , contradicting the assumption that was a longest common subsequence of and . So is a longest common subsequence of and . Interchanging the roles of and , we obtain that: if and , then is a longest common subsequence of and .

Theorem 1.1 provides the insights necessary for designing a dynamic programming algorithm to solve LCS. Let be sequences. If , we record the last character and examine the smaller LCS instance with and . If . Otherwise, we need to find the longest common subsequences of and ; and and . These observations yield a natural recurrence to compute the length of the longest common subsequence for a pair of strings:

Using the recurrence as a template, we design an explicit dynamic programming algorithm. We proceed as follows.

1. Let be our input sequences. We initialize a lookup table to be a two-dimensional array, where each cell stores:
   • A natural number corresponding to the length of a longest common subsequence; and
   • A pointer to another cell in the lookup table, which corresponds to the optimal subproblem as specified in Theorem 1.1.

   Now recall that if either of the input sequences have length , the length of the longest common subsequence is . Therefore, we set and for all and all . While our original input sequences may not have length , sequences we encounter in subproblems may indeed have length .

2. We now proceed to fill in the remaining cells in a bottom up manner, row-by-row. Each row is filled left-to-right. The cells are filled as follows.
   • Case 1: Suppose . By Theorem 1.1, any longest common subsequence of and ends with . Furthermore, is a longest common subsequence of and . So we take the following actions:
     • Set ; and
     • Set .
   • Case 2: Suppose . Theorem 1.1 tells us that we need to consider the two subproblems, whose solutions (or at least, their optimal lengths) are stored in: and , respectively. If , we set:
     • 
     • .

   Otherwise, we set:

   • 
   • .

   In order to construct a longest common subsequence from the lookup table , we start at and follow the pointers to the subproblem. Each time some points to as a subproblem, we prepend the character to the front of the longest common subsequence. We stop once the currently visited cell has no pointer to a subproblem.

   Example 4. Let and . By inspection, it is easy to see that any longest common subsequence of and has length . In particular, , and are all longest common subsequences of and . We work through the dynamic programming algorithm to explicitly find a longest common subsequence.

   1. We begin by initializing a lookup table , and filling the first row and column with ‘s. So we have:
      
   2. We now fill Row 1.
      • Consider . Observe that and are different. So is the maximum of and . Thus, . By Case 2 of the algorithm, points to .
      • Consider . Observe that . So , and \newline points to .
      • Consider . Observe that and are different. So is the maximum of and . So , and points to .
      • Consider . Observe that and are different. By similar argument as for and , we set and to point to .
      • Consider . By similar argument as for , and points to .

      The updated lookup table is as follows:

      
   3. We next fill Rows 2-3, omitting the detailed explanation associated with filling Row 1. The completed lookup table is as follows.
      
   4. Finally, we construct a longest common subsequence of and from the lookup table. We start at and follow the arrows, prepending the character at the given index every time we see . So we have the sequence:
      

      After which, we stop, as does not reference any subproblems. So our longest common subsequence is , which we identified at the start of this example.

Evolutionary Stable Strategies- Part 2

I. Introduction
In this blog entry, we continue the discussion of the Evolutionary Stable Strategy (ESS) solution concept from my previous blog entry. The definition of the ESS presented in my previous blog entries works well for infinite or sufficiently large populations, but experiences shortcomings for smaller finite populations. We introduce the generalized ESS, which was originally introduced by Mark E. Schaffer in 1988. The generalized ESS accounts for finite populations as well as arbitrary -player games, rather than the two-player games such as those discussed in my previous blog entry. In finite populations, we see that the intuition for ESS is that no player can unilaterally deviate and improve its relative payoff, which leads to spiteful behavior. For a sufficiently large population, we see that the generalized ESS converges to the Nash equilibrium, in which no player can unilaterally deviate and improve its absolute payoff. The generalized ESS will be illustrated with the Cournot duopoly game, as well as an -person Tullock contest.

II. Generalized ESS
Let be the size of the population, and let be a -person game. We denote as the contest size. Recall the definition of an ESS:

Definition (Evolutionary Stable Strategy): A strategy is an Evolutionary Stable Strategy if for every strategy , there exists an such that for every .

This definition of an ESS holds true when and . Let be an ESS and be an alternative strategy. Suppose the majority of the agents play the strategy and a small of the population play . The expected utility of an ESS player is , while a mutant player has expected utility . Following a Darwinian and biological intuition, evolutionary forces select against the strategy with the lower expected payoff.

We now substitute in the expected payoffs for each player. An agent playing the ESS strategy has a chance of being matched up with the mutant, and so has expected payoff in that case. So our optimization problem reduces to:

As , we see that the term disappears, and the mutant player sees to find a best response to , which is the Nash equilibrium condition for an individual player. So for sufficiently large populations, an ESS converges to a Nash equilibrium. This motivates the study of the ESS solution concept, as it relates to neoclassical Game Theory. Additionally, we see that players seek to maximize their relative payoffs. In small populations, this leads to spiteful behavior, with the intuition that being harmed less than other agents can lead to better survival rates than the other agents. Equivocally, no player can unilaterally deviate and improve its relative payoff.

With all this in mind, we seek to formulate a generalized ESS in the same spirit as the original: a strategy is a generalized ESS if enough agents adopt it and a minority of agents adopting the mutant strategy have lower expected utility than agents playing . We have two conditions: the equilibrium condition and the fitness condition, in which the strategy is resistant to a minority of mutants.

Definition (Generalized ESS): Let be a population, from which we draw agents to play a symmetric game of contest size . The strategy is a Generalized ESS iff:

1. In a population with only one mutant, the strategy is a solution for . That is, we compare the payoff of agent playing the mutant strategy to an arbitrary agent playing the generalized ESS , assuming .
2. Suppose there are mutants each playing the strategy . Then there exists an integer such that for every , if exactly mutants are selected to participate in the game, then each mutant’s expected payoff is less than the expected payoff of the remaining agents who play the strategy .

Note that we can rewrite ; that is, the average of all the payoffs of each generalized ESS player (which happen to be the same value).

Let’s consider a couple examples.

Example 1: Consider the following game, with population size . In the previous blog entry, it was shown that is the ESS for this game. Recall that the previous blog entry used the textbook definition, which only holds in the case of infinite populations. Here, we see that both (A, A) and (B, B) result in both players having the same payoff. We check that no player can unilaterally deviate and improve its relative payoff. If both players use the strategy , then one player can deviate to resulting in a payoff of for the player that deviated and a payoff of for the other player. So by deviating from , a player can improve its relative payoff. It follows that is not a solution to ; and thus, not a Generalized ESS.

Now consider . If both agents play and one deviates, the deviating player encounters a payoff of . So is a solution to . Given that there are only two players in this population, the mutant cases have been covered. So is the unique generalized ESS of this game.

Example 2: Consider a second game, with population size . In the previous blog entry, we showed that is a pure ESS, which considered . Under the generalized ESS definition with , we see that a player can unilaterally deviate to and improve its relative performance. So is not a generalized ESS when . Now consider . We see that any mixing between and results in a higher payoff than purely playing . So is not resistant to invasion; and thus, not a generalized ESS. So there are no pure strategies generalized ESS in this game for the population size . By the analysis of the pure strategies, it is intuitive that no such mixed strategies ESS exists, for we apply the analysis component-wise. Formally, we show this by contradiction. As the ESS is symmetric, each player will use the same mixing ratio of for strategy and for strategy ; and thus, incur the same utility. This yields the expected payoff of for playing strategy and for playing strategy . Setting is always false, so the two players will never incur the same utility, which is the contradiction. Thus, no generalized ESS exists for this game given .

III. Cournot Duopoly
The Cournot Duopoly is a standard model in neoclassical Game Theory and Industrial Organization. The simplest of these models considers two identical firms, each of whom produce an identical good in quantities respectively. Let . We have an inverse demand function where is the market price with respect to the quantity of the good supplied. Let with and suppose is given by:

Let’s solve for the Nash equilibrium of this game. Each firm seeks to maximize its profit, which is given by . The first order conditions for each player are:

As the two firms are symmetric, there exists a Nash equilibrium in which each firm produces the same quantity of the good. Thus, we set and solve the first order condition:

So the symmetric Nash equilibrium of this game is for each player to produce of the good. Observe that both firms are making positive profit, as and , firm can produce for a sufficiently small and increase its relative profit compared to . However, such a minor increase in production will decrease both firms’ profits. So in this sense, profit maximization and survival are at odds. In fact, the generalized ESS is for each of the two firms to product . So . It suffices to show that no firm can unilaterally deviate and improve its relative performance. If one player produces for some small , then and firm has payoff .

So firm decreases its relative profit by decreasing production. Now suppose firm produces , for some small . Then and we have . Thus, no firm can unilaterally deviate and improve its relative profit.

IV. Tullock Contest
A Tullock contest is a generalization of a lottery. In the lottery, each player pays a bid upfront for the chance to win some prize of value . The probability of player winning is given by:

In a Tullock contest, we fix a constant , and so each player’s bid is weighted . This yields the probability of player winning as:

So player ‘s expected profit is:

Let’s first derive the symmetric Nash equilibrium of this game. Each player seeks to maximize its expected profit, which yields the first order conditions:

In the symmetric equilibrium, each player bids the same amount . Substituting this into the first order conditions, we obtain:

So when , is the symmetric Nash equilibrium. When , the strategy results in players overpaying. When , we see that the (unique pure strategies) symmetric Nash equilibrium is not a generalized ESS. Intuitively, if player increases its bid slightly from , then ‘s expected payoff increases slightly while the other players’ expected payoffs decrease slightly. This is because the probability of winning shifts slightly in ‘s favor, with respect to the amount of the increase. Formally, we consider the following optimization problem:

Where is the symmetric Nash equilibrium of the Tullock contest. We have the first order condition, which we call (*):

As is a Nash equilibrium, we have that when :

We consider:

Substituting to obtain:

And so when , we have:

As is an interior point, we conclude that does not maximize the relative payoffs. So is not a generalized ESS. We now solve for an ESS by considering the first order condition (12):

As the ESS is symmetric, we set and solve:

So the generalized ESS is , when .

Evolutionary Stable Strategies- Part 1

I. Introduction
Neoclassical models of Game Theory consider fully rational agents, where each agent is perfectly aware of the other agents, their strategy sets, and the payoffs of each strategy profile. Each player is able to examine all possibilities and select a best option, taking into account the other players. The solution concept in Game Theory is the Nash Equilibrium, which intuitively is an outcome where no individual player can unilaterally deviate and strictly improve its outcome. However, more traditional models of Game Theory only examine the equilibrium outcomes, not the underlying dynamics driving them.

Evolutionary Game Theory seeks to provide a more realistic model of human behavior, while encompassing the notion of Darwinian dynamics or survival of the fittest. It has two key differences which separates it from traditional models of Game Theory. First, Evolutionary Game Theory models the dynamics. Rather than focusing solely on the equilibrium, the focus is shifted towards how such an equilibrium comes about, if one even exists. Realistically, there are always dynamics, even if they are negligible. In this sense, the evolutionary framework captures this realism better than the neoclassical framework. The second key difference is the notion of bounded rationality. In Evolutionary Game Theory, individuals are not perfectly rational. This means that not every agent computes every possible payoff, making the best decision. Non-rational agents may ignore certain players or possibilities, or opt to imitate the majority rather than maximize their payoffs. In many competitive situations, it may not be feasible to compute all possible outcomes even in the case of perfect information. Instead, agents start with initial strategies and adapt. The outcomes of the game reward the winners and punish the losers. Agents slowly adapt new and beneficial strategies, factoring in what actions they think the other players might choose. In this sense, agents are more recognizably human. Furthermore, the evolutionary framework yields similar equilibria in many cases as the neoclassical Game Theory model.

There are several important applications of Evolutionary Game Theory, outside of economics and biology. Sociologists and psychologists find applications in studying the prevalent social customs, both in small groups and large societies. Researchers in artificial intelligence, particularly multiagent systems, use Evolutionary Game Theory to study how repeated local interactions amongst arbitrary subsets of players drive the overall state of the system. Within the context of economic networks, Evolutionary Game Theory proves to be a useful tool in studying local interaction and learning.

This blog entry will introduce the evolutionary framework, as well as explore the solution concept of the Evolutionary Stable Strategy, which is a refinement of the Nash Equilibrium. The goal is to introduce textbook formulations of the Evolutionary Stable Strategy, while the next blog entry will discuss adaptations of this concept that frequently arise in the literature. Some familiarity with the basics of Game Theory is advisable, such as my previous blog entry on the subject.

II. Evolutionary Framework
Recall the definition of a normal form game:

Definition 1 [Normal Form Game]. A normal form game is a three-tuple where is the set of players, is player ‘s strategy set, and is player ‘s utility function.

In the neoclassical model, each player in the game is fully rational. Each player selects its strategy simultaneously, and the game is played exactly once. The evolutionary framework, in contrast, has three key assumptions:

1. There is a large population of non-fully rational agents.
2. The game is played multiple times. In a given round, each player selects its strategy simultaneously.
3. Some agents are drawn at random each period to play the game.

The goal of the evolutionary framework is to examine which types of players or strategies survive repeated play, shedding light on which equilibrium is more realistic. Let’s examine a coordination game.

Example 1: Consider the following payoff matrix.

The two pure strategies Nash equilibria of this game are (A, A) and (B, B)- it is easy to check that no player can unilaterally deviate from one of these strategy profiles and improve its payoff. Furthermore, it is clear that players prefer the equilibrium (A, A) to (B, B). However, which of these equilibria is more realistic?

Let’s now apply the evolutionary framework to the coordination game. Let be the finite set of players. At each round, two players are selected at random from $N$ to play the coordination game. The players with the highest payoffs are most likely to survive.

If two players both play A, then their preferred Nash equilibrium is achieved. Suppose player chooses to play B instead, while player maintains the strategy A. Then player has utility while player has utility . As the game repeats, agents playing the strategy B have a comparative advantage over those playing A. Agents playing the strategy A will eventually die out when faced with agents playing strategy B, and the equilibrium (B, B) will arise even though (A, A) is the preferred equilibrium. This phenomenon is captured by Evolutionary Game Theory with the solution concept known as the Evolutionary Stable Strategy (ESS).

III. Evolutionary Stable Strategy
Recall that a strategy profile is a Nash equilibrium if no player can unilaterally deviate and improve its payoff. The Evolutionary Stable Strategy is intuitively a strategy that, if played by a sufficiently large proportion of the population, is resistant to the adoption of a mutant strategy. Recall from Example 1 in the previous section that players adoption the strategy A in the coordination game ended up dying out if the strategy B was adopted by a fraction of the players. In this sense, the strategy A is not resistant to mutations.

Prior to engaging in the technical details, some motivation is first in order. Evolutionary Game Theory originated from mathematical biology rather than economics. This is a reasonable starting point. Suppose we have a population of small insects. Anytime two insects come across a food source, they compete for it, enabling each insect to lay five eggs. Now suppose a mutation is introduced, allowing mutant insects to grow to a larger size. So now we have small insects and large insects. A large insect is only able to lay three eggs after consuming food, as it requires more energy to maintain its size. When two large insects compete, they are each able to lay three eggs. However, when a large insect and a small insect compete, the large insect is able to consume all the food. Even though the small insects are able to reproduce more efficiently, will they survive in the long run with the mutation introduced? The answer is no. Observe that this is the game from Example 1.

While the notion of mutation has clear roots in biology, it also applies to social situations. Language coordinates communication, and it evolves by sufficiently many individuals adopting new terminology. In a market setting, suppose a producer introduces a new good. The profitability of this good is determined by whether sufficiently many customers purchase it. Here, the adopting customers can be viewed as mutants in the population. Other societal conventions such as etiquette, law, and currency have evolved based on the natural dynamics arising from individual interactions amongst agents. The Evolutionary Stable Strategy seeks to capture conventions that arise from such interactions.

We now formalize the notion of the Evolutionary Stable Strategy. A Darwinian and biological intuition suggests that evolutionary forces will select against the mutant strategy if and only if the incumbent strategy has a higher payoff. This is the fitness condition. Formally, consider a two-player game with the mixed strategies set . Suppose that the incumbent strategy is and the mutant strategy is . Let be the proportion of players that are programmed to play . So an agent playing strategy has expected payoff , which is the same expected payoff as if the opponent was playing mixed strategies with probability and with probability . So evolutionary forces favor strategy if and only if:

This is precisely the condition for a strategy to be evolutionary stable.

Definition 2 [Evolutionary Stable Strategies]. A strategy is an Evolutionary Stable Strategy if for every strategy , there exists an such that for every .

Intuitively, is the barrier for invasion. If there are not a sufficient number of mutants, then the incumbent agents dominate and the mutants die out. The evolutionary stable strategies can also be characterized as a subset of strict Nash equilibria. Formally, we have the following theorem.

Theorem 1: Let be the set of evolutionary stable strategies for a two-player game , be the set of Nash equilibria for , and be the best response correspondence of strategy . We have:

Proof: Let , and let be a strategy other than . Let be the barrier to invasion of -mutants against . As is an Evolutionary Stable Strategy, we have for every .

By multilinearity of the expected utilities, we have:

Taking , we have either ; or and . Note that is necessarily a Nash equilibrium; otherwise, there would exist a strategy resulting in higher expected payoff than , contradicting the assumption that .

Conversely, let be a Nash equilibrium satisfying for all , and let . Then we have ; or and . If , then for we have:

And so . Now suppose instead that and . We have:

Multiplying and by a fixed , and multiplying and by yields the result. QED.

While every game has a Nash equilibrium (possibly in mixed strategies), not every game has an Evolutionary Stable Strategy. In fact, deciding if a game has an Evolutionary Stable Strategy is NP-Complete. We consider a couple examples to illustrate this point.

Recall Example 1, shown below. Intuitively, we discussed why (B, B) is evolutionary stable. It is clear that (B, B) is a Nash equilibrium. As , we have that is evolutionary stable. Now while (A, A) is a Nash equilibrium, we have , so A is not stable.

Example 2: Consider a second game:

It is easy to verify that (A, A) is the unique Nash equilibrium of this game. In fact, (A, A) is a strict Nash equilibrium, which means that any deviation strictly decreases an agent’s payoff. Now we have and . So for any , we certainly have:

Thus, A is the Evolutionary Stable Strategy for this game. In fact, for any game, its strict Nash equilibria must be Evolutionary Stable Strategies.

Example 3: Consider the matching pennies game, shown below. The unique Nash equilibrium is for each agent to play the mixed strategy of A and B with frequency each. However, it fails to meet the stability condition. Suppose player players instead of . We have . However, .

IV. Conclusion
In this blog entry, we explored the Evolutionary Stable Strategy solution concept, which is a refinement of the Nash equilibrium. In addition to finding Evolutionary Stable Strategies in games, we discussed motivations for this concept in understanding the dynamics that drive equilibria in games. The next blog entry will further discuss refinements and adaptations of the Evolutionary Stable Strategy, with important applications and results.

Algorithmic Game Theory- College Admissions Problem

I. Introduction
This blog entry introduces the College Admissions problem, as well as several algorithmic solutions. The College Admissions problem extends the Stable Marriage problem by allowing for a many-to-one matching. The Stable-Marriage problem is a one-to-one matching problem in which each proposer may be matched with at most single acceptor, and vice-versa: e.g., one man and one woman, one firm and one employee, or one student and one school. More realistically, a firm hires many desirable employees, and a college admits many students. To this end, we extend the notion of a one-to-one matching to allow for a many-to-one matching. The College Admissions problem provides a model allowing for a college to be matched with multiple students, but students may only be matched with one college. This is also more realistic of how firms hire workers. I assume familiarity with the Stable Marriage Problem.

II. Model
The College Admissions problem starts with two disjoint sets: a set of students and a set of colleges. Each student has a strict, transitive preference relation over the set . By convention, if an agent prefers to another agent , then prefers being unmatched than to being matched with . Each college also has a strict, transitive preference relation over . Additionally, each college has a capacity of students it can admit. The solution is a matching between colleges and students, which is formalized as follows:

Definition 2.1 (Many-to-One Matching). Let and be sets. A many-to-one matching from to is a function such that for any distinct and in , we have . Furthermore, if has capacity , then .

Applying this definition to the College Admissions Problem, a Many-to-One matching function relates a college to a subset of students it admits. The matching is further constrained to prohibit a student from being matched with multiple colleges. Lastly, does not allow college to admit more than students.

The definition of a Many-to-One Matching does not account for the actors’ preferences. To this end, the notion of stability will be introduced. Stability in the College Admissions problem is analogous to that in the Stable Marriage problem. First, define the mate function to return a student’s enrolled college: by:

Definition 2.2 (Stable Matching). A Many-to-One Matching of colleges and students is stable if and only if the following conditions hold:

1. For any college and student such that , and prefer being matched with each other to being unmatched.
2. There does not exist a student and college such that , but , if , and for some if .

Intuitively, a stable matching satisfies everyone. So no student-college pair should want to deviate and improve their outcomes. The definition of a stable matching prohibits any condition in which a student-college pair would want to match with each other over their current mates in a given matching. Consider a many-to-one matching . The first condition describes when it is preferable for a student and college not to be matched. The second condition describes then prohibits a student-college and pair not matched by to prefer matching with each other over their mates in . Clearly, must prefer over its mate in to deviate. The analysis of the college takes a little more work due to the fact that it can admit multiple students. If the college has room for (i.e., ), it can and should admit . If has fulfilled its capacity, it must check if is a better choice than one of its already admitted students. If so, replaces its least preferred admitted student with .

Let’s consider an example.

Example 1: Suppose we have five student and three colleges Each student has the preference relation (that is, is the most preferred and is the least preferred). The colleges have the following preferences and capacities:

• College has the preference relation with capacity
• College has the preference relation with capacity .
• College has the preference relation with capacity .

Consider the matching given by , , and Observe that is matched with its top two choices, and and are matched with their top choices. Since has reached its capacity of two students, it cannot deviate and improve its outcome.

Now consider . Observe that gives its top choice, . The only college prefers to is . However, prefers both of its admitted students over and has no room for . Thus, cannot match with another college or which will improve both ‘s outcome and the college’s outcome.

Next, consider . According to ‘s preference relation, it will only match with and . Since and are already matched with , which they prefer to , it follows that will not admit any students in a stable matching.

Finally, consider and . By the above analysis of , and can only match with or . However, both and have filled their admittance capacities. So and cannot be admitted to any college. So there exists no student-college pair which can mutually deviate and match with each other over their mates in . Additionally, any student-college pair that are matched under prefer each other to being unmatched. Thus, is a stable matching.

The definition of the core will be recalled, but I direct readers to my previous blog entry on the Stable Marriage Problem for further exposition on the core.

Definition 2.3 (Core). Let be an allocation. The allocation is said to dominate or block if there exists a coalition such that for every agent , ; and for at least one , . The Core contains the set of allocations such that no other allocation dominates .

Recall from the Stable Marriage Problem that the unique stable one-to-one matching constitutes the core. The result extends to the College Assignment Problem in the case of many-to-one matchings, which is shown below.

Theorem 2.1: Let be the set of students, and let be the set of colleges. Let and let be the core of the College Admissions problem. We have .

Proof: Let be a stable matching. Suppose to the contrary is not in the core. Then there exists a blocking coalition. By the definition of stability, no agent prefers being unmatched to its mate in . So no individual will form a blocking coalition. Note that students only match with colleges, and colleges only match with students. It follows that no coalition consisting solely of students or solely of colleges will form a blocking coalition. Let be a coaliion blocking consisting of both students and colleges. From the definition of a blocking coalition, at least one agent in the coalition strictly improves its outcome. As each agent’s preferences are strict, agent ‘s new mate in the blocking coalition must also strictly improve its outcome over , contradicting the definition of stability. It follows that .

Now let be a core allocation. As no coalition exists blocking , no individual prefers being unmatched to its mate in . So condition (1) of the stable matching is satisfied. Suppose is not a stable matching. Then there exists a student-college pair that would strictly benefit from matching with each other over their mates in . This student-college pair would form a coalition blocking , contradicting the fact that is a core allocation. So . Thus, . QED.

In order to find a stable matching in the College Admissions problem, the Gale-Shapley algorithm is adapted to derive two new algorithms: the Student-Optimal Deferred Acceptance (SODA) and College-Optimal Deferred Acceptance (CODA) algorithms. Recall the Gale-Shapley algorithm favors the proposers. The SODA algorithm is the analogue of the Gale-Shapley algorithm when the students propose, and the CODA algorithm is the analogue of the Gale-Shapley algorithm when the colleges propose. We begin by introducing the SODA algorithm.

III. Student-Optimal Deferred Acceptance
The Student-Optimal Deferred Acceptance algorithm works quite similarly to the Gale-Shapley algorithm. Each student takes a turn proposing to a college. If the college has not fulfilled its quota, it admits the student only if it is preferable to being unmatched. If the college has fulfilled its quota and the student is more preferable than an already admitted candidate, the college admits the student applicant and revokes acceptance to its least preferred admittant. Let’s work through an example using the SODA algorithm.

Example 2: Suppose we have six students and three colleges, with each college having a capacity of . The preferences are as given below:

• Students and with preferences: .
• Students and with preferences: .
• Students and with preferences .
• Colleges and with preferences .
• College with preferences .

The SODA algorithm proceeds as follows:

• Student 1 proposed to College Y. College Y accepted the proposal from Student 1.
• Student 2 proposed to College X. College X accepted the proposal from Student 2.
• Student 3 proposed to College X. College X accepted the proposal from Student 3.
• Student 4 proposed to College Y. College Y accepted the proposal from Student 4.
• Student 5 proposed to College X. College X accepted the proposal from Student 5 and unmatched from Student 3.
• Student 6 proposed to College X. College X rejected the proposal from Student 6.
• Student 6 proposed to College Z. College Z accepted the proposal from Student 6.
• Student 3 proposed to College Z. College Z accepted the proposal from Student 3.

The final matching is .

Let’s examine an implementation.

The Student class models a Student in the College-Admissions Problem. The makeProposals() method is the workhorse of the Student class in the SODA algorithm. The makeProposals() method allows the Student to propose to Colleges in preference order until it makes a match or runs out of Students to which it can propose.

package collegeadmissions;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * This class models a Student in the College-Admissions Problem.
 * The Student class is designed to allow instances to propose in the
 * Student-Optimal Deferred Acceptance algorithm, or respond to College 
 * proposals in the College-Optimal Deferred Acceptance algorithm.
 * 
 * @author Michael Levet
 * @date 01/10/2016
 */
public class Student {

    private ArrayList<College> preferences;
    private College match;
    private String name;
   
    /**
     * @param name The name of this Student
     */
    public Student(String name){
        this.name = name;
        this.preferences = new ArrayList<College>();
    }
    
    /**
     * 
     * @param c The College to insert 
     * @return true if c was successfully inserted, false if c was present in the preference List
     */
    public boolean insertLeastPreferredCollege(College c){
        if(c == null || this.preferences.contains(c)){
            return false;
        }
        
        return this.preferences.add(c);
    }
    
    /**
     * 
     * @param c The College to insert
     * @param preferenceRanking The position in the preference List to insert c
     * @return true if c was successfully inserted, false if c was already present in the preference List
     */
    public boolean insertCollege(College c, int preferenceRanking){
        if(c == null || this.preferences.contains(c)){
            return false;
        }
        
        if(preferenceRanking > this.preferences.size()){
            return this.preferences.add(c);
        }
        
        this.preferences.add(preferenceRanking, c); 
        return true;
    }
    
    /**
     * Determines whether this Student is unmatched and has Colleges to which
     * it has not proposed and with which it is willing to match.
     * 
     * @return true if this Student can make proposals, false otherwise.
     */
    public boolean canMakeProposal(){
        return this.match == null && this.preferences.size() > 0;
    }
    
    /**
     * This method is used in the Student-Optimal Deferred Acceptance algorithm.
     * The Student proceeds by selecting its most preferred College
     * to which it has not already proposed, and makes a proposal.
     * The method terminates when the Student is either matched or
     * runs out of Colleges to which it can propose.
     * 
     * @return true if a College accepts a proposal from this Student, false otherwise
     */
    public boolean makeProposals(){
        College temp = null;
        
        do{
            temp = this.preferences.remove(0);
            System.out.println(this + " proposed to " + temp);
            if(temp.acceptProposal(this)){
                this.match = temp;
                System.out.println(temp + " accepted the proposal from " + this);
                return true;
            }
            
            System.out.println(temp + " rejected the proposal from " + this);
            
        }while(temp != null && this.preferences.size() > 0);
            
        return false;
    }
    
    /**
     * This method unmatches this Student from its current mate.
     * We use this method in the College-Optimal Deferred Acceptance algorithm.
     */
    public void unmatch(){
        this.match = null;
    }
    
    /**
     * This method is used in the College-Optimal Deferred Acceptance algorithm,
     * allowing the Student to process a College's proposal. The Student can
     * accept the College's proposal, unmatching its current mate if necessary;
     * or reject c's proposal.
     * 
     * @param c The College proposing to this Student
     * @return true if this Student accepts c's proposal, false otherwise
     */
    public boolean acceptProposal(College c){
        if(!this.preferences.contains(c)){
            return false;
        }
        
        if(this.match == null){
            this.match = c; 
            return true;
        }
        
        int index = this.preferences.indexOf(c);
        int matchIndex = this.preferences.indexOf((this.match));
        
        if(index < matchIndex){
           this.match.unmatchStudent(this);
           this.match = c;
           return true;
        }
        
        return false;
    }
            
    /**
     * @return College this Student's current mate
     */
    public College getMatch(){
        return this.match;
    }
    
    /**
     * @return String A String representation of this Student
     */
    public String toString(){
        return "Student " + this.name;
    }
}   

The College class models a College in the College-Admissions problem. The relevant method for the SODA algorithm is the acceptProposal() method, which checks several conditions. First, it checks if the College is willing to match with the Student. If not, the College outright rejects the proposal. If the College is willing to match with the student over being unmatched, the acceptProposal() method checks if the College has room; and if so, which (if any) existing Student should be replaced by the proposer.

package collegeadmissions;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * This class models a College in the College-Admissions Problem.
 * The College class is designed to allow instances to propose in the
 * College-Optimal Deferred Acceptance algorithm, or respond to Student 
 * proposals in the Student-Optimal Deferred Acceptance algorithm.
 * 
 * @author Michael Levet
 * @date 01/10/2016
 */
public class College {
   
    private PriorityQueue<Student> matches;
    private ArrayList<Student> preferences;
    private String name;
    private int capacity;
    
    /**
     * @param name The name of this College
     * @param capacity The number of Students this College can admit
     */
    public College(String name, int capacity){
        this.name = name;
        this.preferences = new ArrayList<Student>();
        this.capacity = capacity;

        //ranks Students based on their positions in the preferences List
        //this Comparator ensures that the PriorityQueue is stores Students
        //in order of increasing preference
        Comparator<Student> ranking = new Comparator<Student>(){
            
            public int compare(Student s1, Student s2){
                int indexOne = College.this.preferences.indexOf(s1);
                int indexTwo = College.this.preferences.indexOf(s2);
                
                return indexTwo - indexOne;
            }
        };
        
        this.matches = new PriorityQueue(capacity, ranking);
        
    }
    
    /**
     * 
     * @param s The Student to insert 
     * @return true if s was successfully inserted, false if s was present in the preference List
     */
    public boolean insertLeastPreferredStudent(Student s){
        if(s == null || this.preferences.contains(s)){
            return false;
        }
        
        return this.preferences.add(s);
    }
    
    /**
     * 
     * @param s The Student to insert
     * @param preferenceRanking The order in the preferences List to insert s
     * @return true if s was successfully inserted, false if s was present in the preference List
     */
    public boolean insertStudent(Student s, int preferenceRanking){
        if(s == null || this.preferences.contains(s)){
            return false;
        }
        
        if(preferenceRanking >= this.preferences.size()){
            return this.preferences.add(s);
        }
        
        this.preferences.add(preferenceRanking, s);
        return true;
    }
    
    /**
     * This method is used in the College-Optimal Deferred Acceptance algorithm.
     * A College can make proposals if it has not reached its quota of admitted Students
     * and it has Students to which it has not proposed (and with which it is willing to match).
     * 
     * @return true if this College can make proposals, false otherwise
     */
    public boolean canMakeProposal(){
        return this.matches.size() < this.capacity && this.preferences.size() > 0;
    }
    
    /**
     * @param s The Student to remove from this College's admitted students
     */
    public void unmatchStudent(Student s){
        System.out.println(this + " unmatched from " + s);
        this.matches.remove(s);
    }
    
    /**
     * This method is used in the College-Optimal Deferred Acceptance algorithm.
     * This College proposes to Students in preference order until it has fulfilled
     * its quota or runs out of Students to which it can propose.
     * 
     * @return true if this College added a Student to its matches, false otherwise
     */
    public boolean makeProposals(){
        boolean madeMatch = false;
        
        while(this.preferences.size() > 0 && this.matches.size() < this.capacity){
            Student temp = this.preferences.remove(0);
            System.out.println(this + " proposed to " + temp);
            
            if(temp.acceptProposal(this)){
                this.matches.add(temp);
                madeMatch = true;
                System.out.println(temp + " accepted proposal from " + temp);
                continue;
            }
            
            System.out.println(temp + " rejected proposal from " + temp);
                    
        }
        
        return true;
    }
    
    /**
     * This method is used in the Student-Optimal Deferred Acceptance algorithm,
     * allowing the College to process a Student's proposal. The College may accept
     * the proposal, unmatching its current mate if necessary; or reject the proposal.
     * 
     * @param other The Student proposing to this College
     * @return true iff this College accepted the proposal
     */
    public boolean acceptProposal(Student other){
        int index = this.preferences.indexOf(other);
        if(index == -1){
            return false;
        }
        
        if(this.matches.size() == this.capacity){
            int indexOther = this.preferences.indexOf(this.matches.peek());
            if(index < indexOther){
                Student revoked = this.matches.poll();
                System.out.println(this + " unmatched from " + revoked);
                revoked.unmatch();
                this.matches.add(other);
                return true;
            }
            
            return false;
        }
        
        this.matches.add(other);
        return true;
    }
    
    /**
     * @return PriorityQueue<Student> The admitted Students for this College
     */
    public PriorityQueue<Student> getMatches(){ 
        return this.matches;
    }
    
    /**
     * @return A String representation of this College
     */
    public String toString(){
        return "College " + this.name;
    }
}

For completeness, the MatchMaker and CollegeAdmsisions classes allow executing the algorithms.

MatchMaker.java

package collegeadmissions;

/**
 * This class accepts a List<Student> and List<College>, and allows
 * for the Student-Optimal Deferred Acceptance and College-Optimal 
 * Deferred Acceptance algorithms to be executed on the inputs
 * 
 * @author Michael Levet
 * @date 01/10/2016
 */
import java.util.List;

public class MatchMaker {
    
    private List<Student> students;
    private List<College> colleges;
    
    public MatchMaker(List<Student> students, List<College> colleges){
        this.students = students;
        this.colleges = colleges;
    }
    
    public void sodaMakeMatches(){
        boolean newProposalMade = false;
        
        do{
            newProposalMade = false;
            for(Student s : students){
                if(s.canMakeProposal()){
                   newProposalMade = s.makeProposals();
                }
            }
        }while(newProposalMade);
    }
    
    public void codaMakeMatches(){
        boolean madeMatch = false;
        
        do{
            madeMatch = false;
            
            for(College c : colleges){
                if(c.canMakeProposal()){
                    madeMatch = c.makeProposals();
                }
            }
        }while(madeMatch);
    }
}

CollegeAdmissions.java

package collegeadmissions;

/**
 *
 * @author Michael Levet
 * @date 01/10/2016
 */
import java.util.*;
public class CollegeAdmissions {

    
    public static void main(String[] args) {
        System.out.println("Executing the SODA Algorithm:");
        sodaMakeMatches();
        
        System.out.println("\n\nExecuting the CODA Algorithm:");
        codaMakeMatches();
    }
    
    public static void codaMakeMatches() {
        List<Student> students = new ArrayList<Student>();
        List<College> colleges = new ArrayList<College>();
        
        College c0 = new College("X", 2);
        College c1 = new College("Y", 2);
        College c2 = new College("Z", 2);
        colleges.add(c0);
        colleges.add(c1);
        colleges.add(c2);
        
        for(int i = 0; i < 6; i++){
            Student s = new Student((i+1) + "");
            students.add(s);
            
            if(i != 0 && i != 3){
                s.insertLeastPreferredCollege(c0);
                s.insertLeastPreferredCollege(c2);
                s.insertLeastPreferredCollege(c1);
            }
        }
        
        Student s0 = students.get(0);
        Student s3 = students.get(3);
        
        s0.insertLeastPreferredCollege(c1);
        s0.insertLeastPreferredCollege(c0);
        s0.insertLeastPreferredCollege(c2);
        s3.insertLeastPreferredCollege(c1);
        s3.insertLeastPreferredCollege(c0);
        s3.insertLeastPreferredCollege(c2);
        
        int[] prefs1 = new int[]{1, 4, 2, 5, 0, 3};
        int[] prefs2 = new int[]{0, 3, 1, 4, 2, 5};
        
        for(int i:prefs1){
            c0.insertLeastPreferredStudent(students.get(i));
            c1.insertLeastPreferredStudent(students.get(i));
        }
        
        for(int i:prefs2){
            c2.insertLeastPreferredStudent(students.get(i));
        }
        
        MatchMaker matchMaker = new MatchMaker(students, colleges);
        matchMaker.codaMakeMatches();
        
        for(Student s : students){
            System.out.println(s + " is matched with " + s.getMatch());
        }
        
        for(College c : colleges){
            System.out.println(c + " is matched with " + c.getMatches());
        }
    }

    public static void sodaMakeMatches(){
        List<Student> students = new ArrayList<Student>();
        List<College> colleges = new ArrayList<College>();
        
        College c0 = new College("A", 2);
        College c1 = new College("B", 1);
        College c2 = new College("C", 1);
        colleges.add(c0);
        colleges.add(c1);
        colleges.add(c2);
        
        for(int i = 0; i < 5; i++){
            Student s = new Student((i+1) + "");
            students.add(s);
            c0.insertLeastPreferredStudent(s);
            c1.insertStudent(s, 0);
            for(College c:colleges){
                s.insertLeastPreferredCollege(c);
            }
        }
        
        c2.insertLeastPreferredStudent(students.get(0));
        c2.insertLeastPreferredStudent(students.get(1));
        
        MatchMaker matchMaker = new MatchMaker(students, colleges);
        matchMaker.sodaMakeMatches();
        
        for(Student s : students){
            System.out.println(s + " is matched with " + s.getMatch());
        }
        
        for(College c : colleges){
            System.out.println(c + " is matched with " + c.getMatches());
        }
    }
    
}

A proof of algorithm correctness will be provided.

Theorem 3.1: The SODA algorithm terminates, resulting in a stable matching that is student-optimal.

Claim 3.1.1: The SODA algorithm terminates.

Proof: Suppose that some student is unmatched after iteration . It follows that each college in to which has proposed has either rejected outright, or accepted ‘s proposal and later unmatched from . If a college outright rejected , then need not propose to again. If accepted ‘s initial proposal and later unmatched from , then is matched with a second student such that . Furthermore, for any that was matched with, it is necessary that (otherwise, as is rational, it would not have unmatched from ). Agent prefers to be unmatched than to match with any college to which it did not propose prior to iteration (otherwise, would have proposed to one of these colleges prior to iteration ). Thus, need not be considered again by the algorithm. By consideration of all students, the algorithm must terminate. QED.

Claim 3.1.2: The SODA algorithm produces a stable matching.

Proof: Let be the matching returned by the SODA algorithm. Suppose to the contrary that it is not stable. By the algorithm, no student will propose to a college with which it would not match. Similarly, any college will reject the proposal from a student if it would prefer to remain unmatched over matching with the student. Thus, there exists a student and college such that , but , if , and for some if .

By the SODA algorithm, would have proposed to prior to its current mate in the matching. If after the algorithm terminates, then would would have accepted 's proposal, a contradiction. If after the algorithm terminates; then by the algorithm, would unmatch from its least preferred mate in and mate with , a contradiction. It follows that the matching must be stable. QED.

Claim 3.1.3: The matching produced from the SODA algorithm is student-optimal.

Proof: Let be the matching returned by the SODA algorithm. Suppose to the contrary that is not student-optimal. Let be a second stable matching which weakly improves the students’ outcomes, and let be a student such that . Then would have proposed to prior to under the SODA algorithm. Since , prefers to match with over being unmatched. However, unmatched from or outright rejected in the algorithm, implying that prefers to . Without loss of generality, suppose this was the first instance of a rejection or unmatching in the SODA algorithm. As this is the first instance of rejection or unmatching, there exists a student . Furthermore, as this is the first instance of rejection or unmatching, each student in can have no stable partner better than . It follows that prefers to , and so form a coalition blocking , contradicting the stability of . It follows that is student-optimal. QED.

Claims 3.1.1, 3.1.2, and 3.1.3 together imply Theorem 1. Claim 3.1.3 also yields an important corollary.

Corollary 3.1.3: The SODA algorithm returns the same matching regardless of the order in which the students propose to the colleges.

Remark: When each college has capacity $1$, this is exactly the Stable-Marriage problem. Recall the definition of a strategy proof mechanism is one in which truthfully revealing one’s preferences is a weakly dominant strategy. The Stable-Marriage problem has no strategy-proof mechanism, which was shown in my previous blog entry. Therefore, the result extends to the many-to-one matching case. So while in the SODA algorithm, it is optimal for students to truthfully reveal their preferences, this is not the case for the colleges as demonstrated in the example from my previous blog entry. Furthermore, the colleges receive their worst core allocations under the SODA algorithm. This generalizes the result of the Gale-Shapely algorithm, which will be proven next.

Theorem 3.1.2: Under the SODA algorithm, each college receives its least preferred core allocation.

Proof: Let be the stable matching returned by the SODA algorithm. Suppose to the contrary that there exists a second stable matching that grants each college its least preferred core allocation. Let be a college such that prefers strictly to . If , then any student in would have proposed to under the SODA algorithm. As , would have admitted at least one of these students. Thus, necessarily. As strictly prefers its allocation in over that in , there exists a student in . As is student-optimal, forms a coalition blocking , contradicting the stability of . QED.

IV. College-Optimal Deferred Acceptance
The College-Optimal Deferred Acceptance (CODA) algorithm is the analogue of the Gale-Shapley algorithm in which the colleges do the proposing rather than the students. The algorithm proceeds similarly as the SODA algorithm. It begins by selecting a college with open slots. If there exist students with whom will match, proposes to them in order of preference. A student may accept a proposal or reject it. If a student is matched with a different college than the one proposing, the student must unmatch from its present mate before accepting a proposal from a new mate. Let’s work through an example of the CODA algorithm.

Example 3: Recall the six students and three colleges from Example 2. The CODA algorithm proceeds as follows:

• College X proposed to Student 2. Student 2 accepted proposal from Student 2.
• College X proposed to Student 5. Student 5 accepted proposal from Student 5.
• College Y proposed to Student 2. Student 2 rejected proposal from Student 2.
• College Y proposed to Student 5. Student 5 rejected proposal from Student 5.
• College Y proposed to Student 3. Student 3 accepted proposal from Student 3.
• College Y proposed to Student 6. Student 6 accepted proposal from Student 6.
• College Z proposed to Student 1. Student 1 accepted proposal from Student 1.
• College Z proposed to Student 4. Student 4 accepted proposal from Student 4.

The final matching is .

Recall the sample code in Section III. The makeProposals() method in the College class is the workhorse of this algorithm. A given College proposes to Students one at a time in preference order until it has either filled its quota or runs out of Students to which it can propose. Each Student can either outright reject a College’s proposal, or accept the proposal. If the Student is already matched with another College, it must unmatch from its current mate to accept a new proposal. The acceptProposal() method in the Student class handles this logic by checking if the Student is willing to match with the proposing College, and whether the proposing College is more preferable to the Student’s current mate. A College that is unmatched may propose again to any remaining Students in its preference list.

We now examine a proof of algorithm correctness for the CODA algorithm, which is analogous to that of the SODA algorithm.

Theorem 4.1: The CODA algorithm terminates, resulting in a stable matching that is college-optimal.

Claim 4.1.1: The CODA algorithm terminates.

Proof: Suppose there exists an unmatched college at iteration . By the CODA algorithm, each student to which has proposed either outright rejected the proposal, or accepted the proposal then later unmatched from . And so each student to which has already proposed is matched with a college more preferable than or unmatched. Therefore, will be rejected if it proposes to these students again. Since , has proposed to all the students with whom it is willing to match. Therefore, has no available options. By considering all such colleges, it follows that the CODA algorithm terminates. QED.

Claim 4.1.2: The CODA algorithm produces a stable matching.

Proof: Let be the matching returned by the CODA algorithm. Suppose to the contrary that is not stable. Colleges will only propose with whom they are willing to match, and students will only accept proposals from colleges with which they are willing to match. So no individual agent will form a blocking coalition by itself. So there must exist a student and college such that but and prefer each other to their current mates in . Under the CODA algorithm, would have proposed to . If , then would have been added to under the CODA algorithm. But since was not added to , it follows that . Let be 's least preferred match. Since blocks , . Under the CODA algorithm, would have proposed to prior to and would have accepted, contradicting the fact that . It follows that must be stable. QED.

Claim 4.1.3: The matching produced by the CODA algorithm is college-optimal.

Proof: Let be the matching returned by the CODA algorithm. Suppose to the contrary that there exists a second stable matching which weakly improves upon the colleges’ outcomes. Let such that . Then there exists a student such that prefers to its least preferred mate . Then under the CODA algorithm, would have proposed to prior to . However, must have rejected . Without loss of generality, suppose this is the first instance of rejection. As is stable, prefers being matched with over being single. So must be matched with another college under . Since this is the first instance of rejection, it follows that can have no better set of mates than . So forms a blocking coalition of , contradicting the stability of . QED.

Remark: Just as the SODA algorithm is not strategy proof, neither is the CODA algorithm. Furthermore, the CODA algorithm grants the students their worst stable matching, analogously to the SODA algorithm with respect to the colleges. This final result will now be proven.

Theorem 4.1.2: Under the CODA algorithm, each student receives its least preferred core allocation.

Proof: Let be the stable matching returned by the CODA algorithm. Suppose to the contrary that there exists a second stable matching granting each student its least preferred core allocation. Let be a student such that strictly prefers its mate in over its mate in . As is college-optimal, blocks , contradicting the stability of . QED.

V. Conclusion
In this blog entry, the notion of a one-to-one matching was extended to a many-to-one matching. Two extensions of the Gale-Shapley algorithm were explored, including the Student-Optimal Deferred Acceptance and College-Optimal Deferred Acceptance algorithms. We examined sample implementations, as well as proofs of correctness for these algorithms. The College-Admissions problem has an important extension, where Students signal their viabilities to colleges through the use of test scores. In certain approaches, Students may benefit by under-performing on certain tests. So the matching problem can be extended to design a mechanism rewarding students for doing their best on tests. Additionally, the natural question arises of how to extend the many-to-one matching problem to the case of many-to-many matchings.

Game Theory: Mixed-Strategies and Zero-Sum Games

I. Introduction
In my previous blog entry, the normal form game and Nash equilibrium were introduced. Attention was restricted to pure strategies. As will be illustrated below, not every finite, normal form game has a pure strategies Nash equilibrium. The notion of mixed strategies extends the notion of pure strategies, allowing players to assign probabilities to each pure strategy. This extension provides for the existence of a mixed strategies Nash equilibrium in every finite, normal form game. Additionally, zero sum games and prudent strategies will be discussed.

II. Mixed-Strategies
In this section, we introduce the notion of mixed-strategies. One important motivator for mixed-strategies is that not every game has a pure strategies Nash equilibrium. Consider the matching pennies game:

In any pure strategy profile, one player incurs utility and the other player incurs utility . The player incurring utility can unilaterally deviate by switching its choice to improve its utility. This inverts the payoffs- the first player incurs utility while the second player incurs utility . Iterating on the above argument, we see that no Nash equilibrium exists in pure strategies.

Mixed Strategies: Let be a normal form game. Let . A mixed strategy is a sequence and a probability distribution where player selects strategy with probability . Note that . The set of mixed strategies for player is denoted , where is the simplex in . That is, .

Note that pure strategies are a special case of mixed strategies. The mixed extension will now be defined, to formalize the notion of games with mixed strategies. A mixed strategies Nash equilibrium in a normal form game is equivalent to a pure strategies Nash equilibrium in a mixed extension.

Mixed Extension: Let be a normal form game. The mixed extension of is the three-tuple , where .

The notion of mixed strategies is rather unintuitive from a behavioral perspective, as a normal form game is played simultaneously. So how is a mixed strategies Nash equilibrium formulated? Recall that each player is a rational, utility maximizing agent that is aware of the structure of the game. Each player still seeks to mix its strategies in such a way to maximize its utility. In mixing strategies, a player runs the risk that another player can take advantage of a given mixing. Thus, in a Nash equilibrium, each player mixes strategies such that is indifferent to whichever pure strategy ends up being played. That is, ‘s expected utility for each of ‘s pure strategies in the mixing is the same. This is formalized as follows.

Theorem 2.1: Let be a normal form game. A mixed strategy profile is a mixed strategy Nash equilibrium if and only if, for each player , the following two conditions are satisfied:

1. Every pure strategy which is given positive probability by yields the same expected payoff against ; that is, .
2. Every pure strategy which is given probability zero by yields no more than the pure strategies that are assigned positive probability: .

Proof: Suppose first that the mixed-strategy profile satisfies conditions (1) and (2). Let . If unilaterally deviates by shifting positive probability to a strategy given zero probability in , then ‘s utility does not increase by condition (2). Let be the set of strategies given positive probability by . By condition (1), each pure strategy in results in the same expected utility . Thus, any mixing of strategies in results in expected utility:

Thus, player cannot unilaterally deviate and improve its outcome, so is a mixed strategies Nash equilibrium.

Conversely, suppose is a mixed-strategies Nash equilibrium. As no player can unilaterally deviate and improve its outcome, condition (2) follows immediately. Suppose to the contrary that condition (1) does not hold. Let and such that the . If , then player could assign more weight to in and improve its outcome. Similarly, if , then player could assign less weight to in and improve its outcome. Either occurrence contradicts the assumption that is a mixed-strategies Nash equilibrium. QED.

Example 1: Let’s now use Theorem 2.1 to find a mixed-strategies Nash equilibrium for the Matching Pennies game. Player mixes strategies such that Player is indifferent to and . Suppose Player plays with probability and with probability . Player ‘s payoff from playing is . Player ‘s payoff from playing is . In equilibrium, Player is indifferent between playing and . Setting . By symmetry, we have Player mixing between and with frequencies as well.

In addition to guaranteeing the existence of a Nash equilibrium, mixed strategies are also useful in selecting realistic Nash equilibria. Consider the following example.

Example 2: Consider a traffic routing game on the following network. The weight of each edge denotes the latency cost of traversing that edge. The variable denotes the number of players traversing the edge , and the variable denotes the number of players using the edge . So for example, if , then the latency cost of is for every each of the players. Each player starts at and ends at , seeking to minimize latency.

Suppose there are players in the game. Denote as the number of players choosing the path , as the number of players choosing the path , and as the number of players choosing . Consider first the pure strategies Nash equilibrium of . Both the edges and have players traversing them, and so have latency costs . Players of each type incur latency cost . If a player of type unilaterally deviates, he increases the latency cost of the edge to , resulting in a total latency cost of . By similar argument, players of type and cannot unilaterally deviate and decrease their costs as well.

While and is a pure strategies Nash equilibrium, it is unlikely the players will end up playing this strategy profile. However, this pure strategies equilibrium does provide the probabilities for a mixed strategies equilibrium. As the game is symmetric, there exists a Nash equilibrium in which each player selects the same strategy. Suppose each player selects the mixed strategy with probabilities . We apply Theorem 2.1 to verify this mixed strategy profile, denoted , is a mixed-strategies Nash equilibrium.

First, observe that . Consider each of the pure strategies .

• Suppose player plays the pure strategy . Under , , , and . So .
• Suppose player plays the pure strategy . Under , , and . So .
• Suppose player plays the pure strategy . Under , and . So .

Thus, is a mixed-strategies Nash equilibrium.

III. Zero-Sum Games
In this section, we examine zero-sum games. Intuitively, in a zero sum game, each player’s gain (or loss) is exactly balanced with those of the other players. For example, cutting a larger slice of cake for one person leaves less cake for the others. This notion is formalized as follows:

Zero-Sum Games: Let be a normal form game. is said to be a Zero-Sum Game if for every strategy profile .

Recall the Matching Pennies game from the previous section. In any strategy profile, one player earns utility while the other player earns utility . Thus, the Matching Pennies game is a zero-sum game. Another example of a zero-sum game is Rock-Paper-Scissors. The winner of the game earns utility while the loser earns utility . In the event of a tie, each player earns utility .

So how are zero-sum games solved? We can solve zero-sum games in the same manner as any other normal form game. Of particular interest, however, are prudent strategies. Intuitively, players who play prudently seek to minimize potential losses. We define prudent strategies as follows:

Prudent Strategies: Let be a finite, normal form game. A prudent strategy of player is a mixed strategy that satisfies .

Note that the definition of prudent strategies did not restrict to zero-sum games. We discuss them in the context of zero-sum games; however, as they are most useful here. In the case of a two-player game, saddle points are equivalent to prudent strategies. We define a saddle point as follows.

Saddle Point: Let be a two-player zero-sum game. A saddle point is a strategy profile satisfying for all , all , and each .

In order to test for saddle points in finite games, we convert the payoff matrix into a mathematical matrix from linear algebra. As we are considering zero sum games, define the matrix to be a real-valued matrix where , . That is, represents the amount Player 1 wins and Player 2 loses when the pure strategy profile is played. A saddle point is a minimum of row and a maximum of column . Let’s consider an example of finding a saddle point.

Example 3: Consider the two-player, zero-sum game given by the following payoff matrix.

We begin by converting the payoff matrix to an algebraic matrix:

The row minima are ; and the column maxima are . Observe that row two and column two have the same value: . So is a saddle point with payoff .

Example 4: Consider the two-player, zero-sum game given by the following payoff matrix.

We begin by converting the payoff matrix to an algebraic matrix:

The row minima are for row one, and for column one. The column maxima are for column one, and for column two. So there are no pure strategy saddle points for this game.

We solve this game by determining the mixed strategies Nash equilibria. Suppose Player 2 plays with probability and with probability . If Player 1 plays , his expected payoff is . If Player 1 plays , his expected payoff is . Setting . So Player 2 plays with probability and with probability in equilibrium.

We now solve for Player 1’s mixed equilibrium strategies. Suppose Player 1 plays with probability and with probability . Then Player 2’s expected payoff from playing is . Player 2’s expected payoff from playing is . Setting yields . So Player 1 plays with probability and with probability in equilibrium.

When considering mixed strategies or infinite games with compact (closed and bounded) strategy sets (such as mixed extensions of normal form games), saddle points are guaranteed to exist. This is due to a result in real analysis known as the Weierstrass Extreme Value Theorem, which states that a continuous function over a compact set achieves both a maximum and a minimum.

It is easy to verify that a pure-strategy saddle point is a Nash equilibrium in a finite zero-sum games. This verification is presented in the following theorem to build intuition. The logic is analogous in the case of infinite games (such as mixed extensions of finite zero-sum games).

Theorem 3.1: Let be a two-player zero-sum game and let be the associated matrix. Suppose is a saddle point. Then constitutes a Nash equilibrium of .

Proof: As is the maximum of column , a unilateral deviation from Player 1 will result in payoff for some . It follows that , so Player 1 cannot unilaterally deviate and improve its outcome. For Player 2, as is a zero-sum game and by construction of the matrix . So if Player 2 unilaterally deviates, the payoff will be since . And so Player 2 cannot unilaterally deviate and improve its outcome. Thus, is a Nash equilibrium. QED.

The Nash equilibria of zero-sum games can be characterized in terms of prudent strategies. Intuitively, each player seeks to minimize its opponent’s payoff. As a zero-sum game is being considered, this leaves more for the individual. This notion is formalized as follows:

Theorem 3.2: In any finite, two-person zero-sum game, the following conditions hold:

1. If is a mixed strategies Nash equilibrium, then is a prudent strategy of player and:

     (2)

2. If is prudent for each , then is a mixed-strategies Nash equilibrium.

Proof: Suppose first that is a mixed strategies Nash equilibrium. Now suppose to the contrary that for some , is not prudent. It follows that there exists a strategy guaranteeing a better result than . Consider the mixed strategy profile , where is a best response to . We thus have . As is a best response to , we have . As is a best response to and the game is zero-sum, it follows that . Chaining the inequalities together implies , a contradiction. It follows that is prudent for both players.

It will now be shown that (2) holds. Note that for any function and fixed , we have . Taking the max of both sides maintains this inequality. Thus:

Similarly, as is a saddle point, we have:

And so:

Thus, (2) holds.

Conversely, suppose is prudent for each . As is prudent, it solves . So player cannot unilaterally deviate and improve its payoff. Thus, is a mixed-strategies Nash equilibrium. QED.

Game Theory: Normal Form Games- Part 1

I. Introduction

Game Theory is a mathematical field that studies how rational agents make decisions in both competitive and cooperative situations. It has widespread applications in economics, political science, psychology, biology, computer science, and data science. Some of the applications include radio spectrum auctions, voting, and organ donations. This tutorial introduces the basic strategic form game, also known as the normal form game. Attention will be restricted to pure strategies.

II. Model
In this section, we formally define the normal form game. Let’s begin with some intuition. A normal form game has a set of players. Each player has a set of strategies. These players each select a strategy and play their selections simultaneously. In this manner, no player is responding to another’s selection. Furthermore, we think of the players’ strategies as setting the rules of the game. Finally, the selection of strategies results in payoff or utility for each player. Each player’s goal in a game is to maximize utility, and each player is aware of the structure of the game; that is, the other players’ strategy sets and payoffs. The normal form game will now be formally defined.

Normal Form Game: A normal form game is a three-tuple where is the set of players, is player ‘s strategy set, and is player ‘s payoff or utility function. The sequence of strategies is referred to as a strategy profile.

In addition to the assumptions that the players are economically rational and play at the same time, it is also assumed that the structure of the game is perfectly known. In other words, each player knows every player’s strategy set and utility function.

Let’s examine an example of a normal form game, the standard Prisoner’s Dilemma.

Example 1 (Prisoner’s Dilemma): In this game, the police have two accomplices of a crime in separate rooms. They are each offered a deal: implicate the other prisoner and earn a reduced sentence if the other player remains silent. If both players remain silent, they each end up in jail for two years. If both players implicate each other, they each go to jail for five year.

Formally, we have two players . Each player has the strategy set , and the utility function of the form . If both players play Quiet, they each earn utility of ; and if both play Fink, they each earn utility of . If one player plays Quiet and the other Fink, they earn utilities of and respectively.

We represent the normal form game using the following matrix known as a payoff matrix. Player ‘s strategies are on the left-side while Player ‘s strategies are on the top of the matrix. Each cell represents the payoffs of the form for the selected strategies and .

Not every normal form game can be represented as a matrix. When we have more than two players or continuous strategies, tables are not very helpful. Let’s consider a second example of a normal form game: the Cournot duopoly.

Example 2 (Cournot Duopoly): In this game, we have two players again: . Each player is a firm producing the same, identical good. The market sets the price for the good based on the total amount produced by the two firms. The two firms compete in the quantities of the good they each produce, incurring a fixed cost for each unit of good produced. Each firm seeks to maximize its own profit. Suppose the inverse demand function (the price function) is given as follows where :

Each firm has the strategy set , indicating the quantity of the good it can produce. Each firm also has the utility function of the form given by . Since the strategies are uncountable, it is pointless to construct a payoff matrix to help in analyzing the game.

III. Solving Games and Nash Equilibrium
Recall that each player in a given game seeks to maximize its utility. How do agents select strategies? What is the solution concept for a game? The first notion of comparison is rather intuitive and straight-forward. We refer to it as strategy dominance. Basically, if strategy yields at least as good a payoff as strategy regardless of the other agents’ strategy selections, then why would the player ever choose strategy ? We first introduce the following notation. Let . We denote . Now we formalize the notion of desirable strategies by defining a Best Response.

Best Response: Let and let . The strategy is a best response of player against if for every .

We denote as ‘s best response correspondence against , or the set of all ‘s strategies that are best responses to . Note that every element of solves .

Let’s consider an example with a new game, a voting game.

Example 3 (Voting Game): Suppose we have three players, and two candidates . Each player can vote for exactly one of or , so , for all . The three players cast their votes simultaneously. Players and incur utility if wins and utility if wins. Player incurs utility if wins and utility if wins.

Observe that for any , . If , player selecting incurs the same utility of as selecting . Otherwise, if player selects and at least one player of selects , then player incurs utility while selecting $late B$ may result in utility if only one of the players in selects . In fact, we can say more strongly that for player , voting for is a weakly dominant strategy. This is formally defined as follows.

Dominated Strategies: The strategy is weakly dominated if there exists a second strategy such that: for every , with strict inequality for at least one . We say that is strictly dominated if the strict inequality holds for all .

Now that we have some notion of how a player compares its strategies, the next step is to discern how the players select their strategies in anticipation of each other. The solution concept is the Nash equilibrium. Formally, the Nash equilibrium is defined as follows.

Nash Equilibrium: The strategy profile is said to be a Nash Equilibrium if for every .

Intuitively, a strategy profile is a Nash equilibrium if no player can unilaterally change its strategy and improve its outcome. Let’s apply this reasoning to deduce the Nash equilibrium for the Prisoner’s Dilemma game from Example 1, with the payoff matrix included below. If the two players both select Quiet, then they each incur utility of . One of the players can unilaterally deviate, playing Fink instead, decreasing its utility to while the other player’s utility is decreased to . So (Quiet, Quiet) is not a Nash equilibrium. Consider (Fink, Quiet). Player can unilaterally deviate, playing Fink instead of Quiet to improve its payoff from to . By symmetry, (Quiet, Fink) is not a Nash equilibrium. Finally, consider (Fink, Fink). By previous analysis, a single player unilaterally changing from Fink to Quiet will decrease its payoff from to . So no player can unilaterally deviate from (Fink, Fink). Thus, (Fink, Fink) is the Nash equilibrium of the Prisoner’s Dilemma.

The first concern is whether every game has a Nash equilibrium. The answer is yes, but not necessarily in pure strategies. A pure strategy is the selection of a single strategy from the set which player always uses. The Nash equilibrium of (Fink, Fink) is the pure strategy Nash equilibrium for the Prisoner’s Dilemma. Nash equilibria are guaranteed to exist in mixed strategies, which will be introduced later. Additionally, we note that in a symmetric game (that is, a game where each player has the same strategy set and utility function), there exists a Nash equilibrium where each player selects the same strategy. The equilibrium of (Fink, Fink) in the Prisoner’s Dilemma is actually a symmetric Nash equilibrium.

The problem of computing Nash equilibria is difficult. Formally, it is a complete problem for the complexity class PPAD. This means that given an arbitrary game, there is (believed to be) no efficient procedure to compute a Nash equilibrium for an arbitrary game. Additionally, a game may have multiple Nash equilibria. Enumerating all such equilibria as well as selecting the most realistic equilibria are both difficult problems of interest. We examine two strategies to help compute pure strategies Nash equilibria: leveraging games with continuous strategy sets and the elimination of dominated strategies.

III.A Leveraging Continuity. Recall Example 2, the Cournot Duopoly. Each player’s strategy set is , an amount to produce. Furthermore, each player has the same utility function, so this game is symmetric. Therefore, we solve for a symmetric Nash equilibrium. Each player seeks to solve . We consider the first partial derivative of with respect to , as player cannot vary , and set it to to identify potential maximizers: . Solving for yields:

As this game is symmetric, there exists a Nash equilibrium where each player selects the same strategy. So we set: and solve:

Note that if , then is player ‘s best response.

III.B Elimination of Dominated Strategies. Recall the approach in reasoning the Nash equilibrium for the Prisoner’s Dilemma. Checking each strategy profile to determine if it is a Nash equilibrium is tedious. We prove a simple lemma, upon which the approach of eliminating dominated strategies is based.

Lemma 3.1: Let . Suppose . If strictly dominates , then will not play in any Nash equilibrium.

Proof: If strictly dominates , then for every . If plays , then can unilaterally deviate and choose instead. So will never play in a Nash equilibrium.

The procedure below is the same regardless if attention is restricted to strictly dominated strategies or weakly dominated strategies. Note that Lemma 3.1 is not a necessary condition of weakly dominated strategies. However, a Nash Equilibrium found in a game produced from eliminating weakly dominated strategies is also a Nash Equilibrium in the original game. This will be proven later. Let’s begin by examining the procedures.

Iterated Elimination of Strictly (Weakly) Dominated Strategies: The procedure begins by accepting a game where each player’s strategy set is finite. While there is a player with strategies such that strictly (weakly) dominates , set . Consider with the updated at the next iteration of the procedure.

We apply the Iterated Elimination of Strictly Dominated Strategies to the Prisoner’s Dilemma, eliminating Quiet for the two respective players. This yields the sole strategy profile (Fink, Fink), which we recognize as the Nash Equilibrium for the game.

Now let’s apply the Iterated Elimination of Weakly Dominated Strategies to the game given by the following payoff matrix. Observe first this game has three Nash equilibria: , and .

Observe that Player does not have a dominant strategy in this game. However, dominates both and for Player . We remove from Player ‘s strategy set and consider the reduced game:

In this new game, dominates for Player . So we eliminate to obtain the following game:

Player will play in this new game, yielding the Nash equilibrium .

The Elimination of Weakly Dominated Strategies suffers from the fact that the order in which strategies are eliminated may result in a different Nash Equilibrium. This is due to the fact that weak dominance only requires one strict inequality, while strict dominance requires all strict inequalities. Consider again the above game:

If we instead eliminated first from Player ‘s strategy set initially, we would eliminate from Player ‘s strategy set at the next iteration. This would result in finding the Nash equilibrium . By exhaustion, it is possible to verify that the Nash equilibrium cannot be found by eliminating weakly dominated strategies.

These algorithms do not always yield pure strategies equilibria, but they do reduce the search spaces considerably. Eliminating a strictly dominated strategy preserves all Nash equilibria in a game. We have already seen that this is not the case when eliminating weakly dominated strategies. However, in a game derived from eliminating a weakly dominated strategy has a Nash equilibrium, which is also a Nash equilibrium in the original game. Let’s prove these results formally.

I begin with the following Lemma:

Lemma 3.2: Let be a finite game and let be the game produced by eliminating a strictly dominated strategy in . Then and have the same set of Nash equilibria.

Proof: Let be a game and suppose the strategy is eliminated from player ‘s strategy set by the algorithm. Let be the resulting game. Let be a Nash equilibrium for . Player cannot unilaterally deviate in and improve its outcome. As is strictly dominated, player will not deviate to in . As every player has the same strategy set in and , no other player can unilaterally deviate and improve its outcome. It follows that is a Nash equilibrium of .

Conversely, suppose is a Nash equilibrium of . By Lemma 3.1, does not appear in any Nash equilibrium of . It follows immediately that is a Nash equilibrium of .

It follows that and have the same set of Nash equilibria. QED.

Theorem 3.1: Let be a finite game. Let be the sequence of games produced by the Iterated Elimination of Strictly Dominated Strategies. For every , and have the same set of Nash equilibria.

Proof: Theorem 3.1 follows immediately by applying induction and Lemma 3.2.

Lemma 3.3: Let be a game and let be the game produced by eliminating a weakly dominated strategy in . Then every Nash equilibrium in is also a Nash equilibrium in .

As is a finite game, it has a Nash equilibrium. Suppose that was eliminated from player ‘s strategy set in the construction of . Suppose to the contrary that there exists a Nash equilibrium of that is not a Nash equilibrium of . As deviating from in and is equivalent for , only player can unilaterally deviate and improve its outcome. The only such option is for to deviate in is , contradicting the assumption that was eliminated as a weakly dominant strategy. QED.

Applying induction and Lemma 3.3 immediately implies the correctness of the Iterated Elimination of Weakly Dominated Strategies.

IV. Conclusion
In this tutorial, the normal form game was introduced. In addition, the Nash equilibrium was defined and we explored ways to compute pure strategies Nash equilibria. The next tutorial will explore the role of mixed strategies.

Dijkstra’s Algorithm

I. Introduction
This tutorial will introduce Dijkstra’s algorithm, including a proof of correctness and time complexity analysis.

Dijkstra’s algorithm is used to find the shortest path between two vertices of a graph. More formally, we fix a starting vertex in the graph, vertex . Dijkstra’s algorithm then returns the shortest path from vertex to every other vertex in the graph. We assume the graph is weighted and has no negative weights.

II. Breadth-First Traversal
Dijkstra’s algorithm is an adaptation of the breadth-first traversal algorithm. So it is important to first understand the breadth-first traversal (BFS) algorithm. The BFS algorithm accepts a graph and initial vertex . The algorithm then manages a queue, which dictates the order to visit the vertices. It then visits each of ‘s neighbors, pushing them onto the queue as they are visited. Then as long as the queue is non-empty, we poll a vertex, mark it as visited, and add all of its unvisited neighbors to the queue.

Let’s consider an example. Given the graph below and the starting vertex , we examine the order in which the vertices are visited. While you can choose to visit neighbor vertices in any order, I will visit them from lowest label to highest label.

Start at the initial vertex and mark it as visited. Now we visit each neighbor in the order , mark them as visited, and push each onto the queue respectively. So the queue is now: .

Next, we poll from the queue, leaving . We have that ‘s neighbors are , all of which have been visited. So we do nothing. Next, poll from the queue. We push its unvisited neighbors- onto the queue, marking them as visited along the way. This leaves .

Notice now that the vertices in have no unvisited neighbors in the graph. So the order the vertices are visited by the algorithm is: .

III. Dijkstra’s Algorithm
Dijkstra’s Algorithm works similarly as the BFS algorithm. We begin with a weighted graph where is the weight function , as well as an initial vertex . That is, each edge has a non-negative weight. With each vertex, we associate a distance marker which denotes the distance from , as well as the predecessor in the shortest path found by the algorithm. This allows us to not only find the distance of the shortest path for any vertex , but to explicitly access the path as well.

We begin by starting at , and marking every other vertex as having distance infinity from . We visit each neighbor of and: first set ‘s distance marker to then ‘s predecessor to . Then, we push vertex adjacent to onto a priority queue. The priority queue orders vertices by their distance markers. Finally, we mark the initial vertex as visited. No marked vertex can be used in future iterations.

Now, while the priority queue still has elements, we do the following. First, poll a vertex from the priority queue. For each unmarked neighbor of , we check if . If this condition is satisfied, we update ‘s distance marker to . Next, we update ‘s predecessor to , then update ‘s position in the priority queue.

After visiting all of ‘s neighbors, we mark as visited.

Let’s work through an example. Consider the following graph, and suppose we want vertex as the root.

We start by setting . Then we set ‘s and ‘s predecessor to . Next, we push and into the priority queue, which is ordered: . Finally, we mark as visited.

Now poll from the priority queue. We note , so we discard . Now consider . Since , we discard . We mark as visited. The priority queue now contains and no other vertices are unvisited. After polling , the algorithm terminates.

The lengths of the shortest paths are as follows:

• 
• 
• 
• 

Now let’s examine an implementation. We design the Dijkstra’s class to accept a Graph and construct a shortest-path tree. We use HashMaps to store the predecessor of each vertex in the shortest paths, and to store the distances from the initial vertex to every other vertex in the graph.

We begin by visiting each of initialVertex’s neighbors, updating their distances from initialVertex, and pushing them onto the PriorityQueue. We then mark initialVertex as visited and proceed with the rest of the algorithm. The processGraph() method handles the remainder of the algorithm. It polls the first vertex from the PriorityQueue and updates the distances as necessary to each of its unvisited neighbors. It then removes and re-adds any updated neighbors to the PriorityQueue to update their positions. In this way, the unvisited vertex with the smallest distance from initialVertex is polled from the PriorityQueue.

The getPathTo() and getDistanceTo() methods return the path and distance respectively from initialVertex to a chosen vertex in the graph. The getPathTo() method starts at the target vertex and traces the predecessors back to initialVertex.

import java.util.*;

/**
 * 
 * @author Michael Levet
 */
public class Dijkstra {
    
    private Graph graph;
    private String initialVertexLabel;
    private HashMap<String, String> predecessors;
    private HashMap<String, Integer> distances; 
    private PriorityQueue<Vertex> availableVertices;
    private HashSet<Vertex> visitedVertices; 
    
    
    /**
     * This constructor initializes this Dijkstra object and executes
     * Dijkstra's algorithm on the graph given the specified initialVertexLabel.
     * After the algorithm terminates, the shortest a-b paths and the corresponding
     * distances will be available for all vertices b in the graph.
     * 
     * @param graph The Graph to traverse
     * @param initialVertexLabel The starting Vertex label
     * @throws IllegalArgumentException If the specified initial vertex is not in the Graph
     */
    public Dijkstra(Graph graph, String initialVertexLabel){
        this.graph = graph;
        Set<String> vertexKeys = this.graph.vertexKeys();
        
        if(!vertexKeys.contains(initialVertexLabel)){
            throw new IllegalArgumentException("The graph must contain the initial vertex.");
        }
        
        this.initialVertexLabel = initialVertexLabel;
        this.predecessors = new HashMap<String, String>();
        this.distances = new HashMap<String, Integer>();
        this.availableVertices = new PriorityQueue<Vertex>(vertexKeys.size(), new Comparator<Vertex>(){
            
            public int compare(Vertex one, Vertex two){
                int weightOne = Dijkstra.this.distances.get(one.getLabel());
                int weightTwo = Dijkstra.this.distances.get(two.getLabel());
                return weightOne - weightTwo;
            }
        });
        
        this.visitedVertices = new HashSet<Vertex>();
        
        //for each Vertex in the graph
        //assume it has distance infinity denoted by Integer.MAX_VALUE
        for(String key: vertexKeys){
            this.predecessors.put(key, null);
            this.distances.put(key, Integer.MAX_VALUE);
        }
        
        
        //the distance from the initial vertex to itself is 0
        this.distances.put(initialVertexLabel, 0);
        
        //and seed initialVertex's neighbors
        Vertex initialVertex = this.graph.getVertex(initialVertexLabel);
        ArrayList<Edge> initialVertexNeighbors = initialVertex.getNeighbors();
        for(Edge e : initialVertexNeighbors){
            Vertex other = e.getNeighbor(initialVertex);
            this.predecessors.put(other.getLabel(), initialVertexLabel);
            this.distances.put(other.getLabel(), e.getWeight());
            this.availableVertices.add(other);
        }
        
        this.visitedVertices.add(initialVertex);
        
        //now apply Dijkstra's algorithm to the Graph
        processGraph();
        
    }
    
    /**
     * This method applies Dijkstra's algorithm to the graph using the Vertex
     * specified by initialVertexLabel as the starting point.
     * 
     * @post The shortest a-b paths as specified by Dijkstra's algorithm and 
     *       their distances are available 
     */
    private void processGraph(){
        
        //as long as there are Edges to process
        while(this.availableVertices.size() > 0){
            
            //pick the cheapest vertex
            Vertex next = this.availableVertices.poll();
            int distanceToNext = this.distances.get(next.getLabel());
            
            //and for each available neighbor of the chosen vertex
            List<Edge> nextNeighbors = next.getNeighbors();     
            for(Edge e: nextNeighbors){
                Vertex other = e.getNeighbor(next);
                if(this.visitedVertices.contains(other)){
                    continue;
                }
                
                //we check if a shorter path exists
                //and update to indicate a new shortest found path
                //in the graph
                int currentWeight = this.distances.get(other.getLabel());
                int newWeight = distanceToNext + e.getWeight();
                
                if(newWeight < currentWeight){
                    this.predecessors.put(other.getLabel(), next.getLabel());
                    this.distances.put(other.getLabel(), newWeight);
                    this.availableVertices.remove(other);
                    this.availableVertices.add(other);
                }
                
            }
            
            // finally, mark the selected vertex as visited 
            // so we don't revisit it
            this.visitedVertices.add(next);
        }
    }
    
    
    /**
     * 
     * @param destinationLabel The Vertex whose shortest path from the initial Vertex is desired
     * @return LinkedList<Vertex> A sequence of Vertex objects starting at the 
     *         initial Vertex and terminating at the Vertex specified by destinationLabel.
     *         The path is the shortest path specified by Dijkstra's algorithm.
     */
    public List<Vertex> getPathTo(String destinationLabel){
        LinkedList<Vertex> path = new LinkedList<Vertex>();
        path.add(graph.getVertex(destinationLabel));
        
        while(!destinationLabel.equals(this.initialVertexLabel)){
            Vertex predecessor = graph.getVertex(this.predecessors.get(destinationLabel));
            destinationLabel = predecessor.getLabel();
            path.add(0, predecessor);
        }
        return path;
    }
    
    
    /**
     * 
     * @param destinationLabel The Vertex to determine the distance from the initial Vertex
     * @return int The distance from the initial Vertex to the Vertex specified by destinationLabel
     */
    public int getDistanceTo(String destinationLabel){
        return this.distances.get(destinationLabel);
    }
    
    
    public static void main(String[] args){
        Graph graph = new Graph();
        Vertex[] vertices = new Vertex[6];
        
        for(int i = 0; i < vertices.length; i++){
            vertices[i] = new Vertex(i + "");
            graph.addVertex(vertices[i], true);
        }
        
        Edge[] edges = new Edge[9];
        edges[0] = new Edge(vertices[0], vertices[1], 7);
        edges[1] = new Edge(vertices[0], vertices[2], 9);
        edges[2] = new Edge(vertices[0], vertices[5], 14);
        edges[3] = new Edge(vertices[1], vertices[2], 10);
        edges[4] = new Edge(vertices[1], vertices[3], 15);
        edges[5] = new Edge(vertices[2], vertices[3], 11);
        edges[6] = new Edge(vertices[2], vertices[5], 2);
        edges[7] = new Edge(vertices[3], vertices[4], 6);
        edges[8] = new Edge(vertices[4], vertices[5], 9);
        
        for(Edge e: edges){
            graph.addEdge(e.getOne(), e.getTwo(), e.getWeight());
        }
        
        Dijkstra dijkstra = new Dijkstra(graph, vertices[0].getLabel());
        System.out.println(dijkstra.getDistanceTo("5"));
        System.out.println(dijkstra.getPathTo("5"));
    }
}

And my graph implementation:

Vertex.java

import java.util.ArrayList;

/**
 * This class models a vertex in a graph. For ease of 
 * the reader, a label for this vertex is required. 
 * Note that the Graph object only accepts one Vertex per label,
 * so uniqueness of labels is important. This vertex's neighborhood
 * is described by the Edges incident to it. 
 * 
 * @author Michael Levet
 * @date June 09, 2015
 */
public class Vertex {

    private ArrayList<Edge> neighborhood;
    private String label;
    
    /**
     * 
     * @param label The unique label associated with this Vertex
     */
    public Vertex(String label){
        this.label = label;
        this.neighborhood = new ArrayList<Edge>();
    }
    
    
    /**
     * This method adds an Edge to the incidence neighborhood of this graph iff
     * the edge is not already present. 
     * 
     * @param edge The edge to add
     */
    public void addNeighbor(Edge edge){
        if(this.neighborhood.contains(edge)){
            return;
        }
        
        this.neighborhood.add(edge);
    }
    
    
    /**
     * 
     * @param other The edge for which to search
     * @return true iff other is contained in this.neighborhood
     */
    public boolean containsNeighbor(Edge other){
        return this.neighborhood.contains(other);
    }
    
    /**
     * 
     * @param index The index of the Edge to retrieve
     * @return Edge The Edge at the specified index in this.neighborhood
     */
    public Edge getNeighbor(int index){
        return this.neighborhood.get(index);
    }
    
    
    /**
     * 
     * @param index The index of the edge to remove from this.neighborhood
     * @return Edge The removed Edge
     */
    Edge removeNeighbor(int index){
        return this.neighborhood.remove(index);
    }
    
    /**
     * 
     * @param e The Edge to remove from this.neighborhood
     */
    public void removeNeighbor(Edge e){
        this.neighborhood.remove(e);
    }
    
    
    /**
     * 
     * @return int The number of neighbors of this Vertex
     */
    public int getNeighborCount(){
        return this.neighborhood.size();
    }
    
    
    /**
     * 
     * @return String The label of this Vertex
     */
    public String getLabel(){
        return this.label;
    }
    
    
    /**
     * 
     * @return String A String representation of this Vertex
     */
    public String toString(){
        return "Vertex " + label;
    }
    
    /**
     * 
     * @return The hash code of this Vertex's label
     */
    public int hashCode(){
        return this.label.hashCode();
    }
    
    /**
     * 
     * @param other The object to compare
     * @return true iff other instanceof Vertex and the two Vertex objects have the same label
     */
    public boolean equals(Object other){
        if(!(other instanceof Vertex)){
            return false;
        }
        
        Vertex v = (Vertex)other;
        return this.label.equals(v.label);
    }
    
    /**
     * 
     * @return ArrayList<Edge> A copy of this.neighborhood. Modifying the returned
     * ArrayList will not affect the neighborhood of this Vertex
     */
    public ArrayList<Edge> getNeighbors(){
        return new ArrayList<Edge>(this.neighborhood);
    }
    
}

Edge.java

/**
 * This class models an undirected Edge in the Graph implementation.
 * An Edge contains two vertices and a weight. If no weight is
 * specified, the default is a weight of 1. This is so traversing
 * edges is assumed to be of greater distance or cost than staying
 * at the given vertex.
 * 
 * This class also deviates from the expectations of the Comparable interface
 * in that a return value of 0 does not indicate that this.equals(other). The
 * equals() method only compares the vertices, while the compareTo() method 
 * compares the edge weights. This provides more efficient implementation for
 * checking uniqueness of edges, as well as the fact that two edges of equal weight
 * should be considered equitably in a pathfinding or spanning tree algorithm.
 * 
 * @author Michael Levet
 * @date June 09, 2015
 */
public class Edge implements Comparable<Edge> {

    private Vertex one, two;
    private int weight;
    
    /**
     * 
     * @param one The first vertex in the Edge
     * @param two The second vertex in the Edge
     */
    public Edge(Vertex one, Vertex two){
        this(one, two, 1);
    }
    
    /**
     * 
     * @param one The first vertex in the Edge
     * @param two The second vertex of the Edge
     * @param weight The weight of this Edge
     */
    public Edge(Vertex one, Vertex two, int weight){
        this.one = (one.getLabel().compareTo(two.getLabel()) <= 0) ? one : two;
        this.two = (this.one == one) ? two : one;
        this.weight = weight;
    }
    
    
    /**
     * 
     * @param current
     * @return The neighbor of current along this Edge
     */
    public Vertex getNeighbor(Vertex current){
        if(!(current.equals(one) || current.equals(two))){
            return null;
        }
        
        return (current.equals(one)) ? two : one;
    }
    
    /**
     * 
     * @return Vertex this.one
     */
    public Vertex getOne(){
        return this.one;
    }
    
    /**
     * 
     * @return Vertex this.two
     */
    public Vertex getTwo(){
        return this.two;
    }
    
    
    /**
     * 
     * @return int The weight of this Edge
     */
    public int getWeight(){
        return this.weight;
    }
    
    
    /**
     * 
     * @param weight The new weight of this Edge
     */
    public void setWeight(int weight){
        this.weight = weight;
    }
    
    
    /**
     * Note that the compareTo() method deviates from 
     * the specifications in the Comparable interface. A 
     * return value of 0 does not indicate that this.equals(other).
     * The equals() method checks the Vertex endpoints, while the 
     * compareTo() is used to compare Edge weights
     * 
     * @param other The Edge to compare against this
     * @return int this.weight - other.weight
     */
    public int compareTo(Edge other){
        return this.weight - other.weight;
    }
    
    /**
     * 
     * @return String A String representation of this Edge
     */
    public String toString(){
        return "({" + one + ", " + two + "}, " + weight + ")";
    }
    
    /**
     * 
     * @return int The hash code for this Edge 
     */
    public int hashCode(){
        return (one.getLabel() + two.getLabel()).hashCode(); 
    }
    
    /**
     * 
     * @param other The Object to compare against this
     * @return ture iff other is an Edge with the same Vertices as this
     */
    public boolean equals(Object other){
        if(!(other instanceof Edge)){
            return false;
        }
        
        Edge e = (Edge)other;
        
        return e.one.equals(this.one) && e.two.equals(this.two);
    }   
}

Graph.java

import java.util.*;

/**
 * This class models a simple, undirected graph using an 
 * incidence list representation. Vertices are identified 
 * uniquely by their labels, and only unique vertices are allowed.
 * At most one Edge per vertex pair is allowed in this Graph.
 * 
 * Note that the Graph is designed to manage the Edges. You
 * should not attempt to manually add Edges yourself.
 * 
 * @author Michael Levet
 * @date June 09, 2015
 */
public class Graph {
    
    private HashMap<String, Vertex> vertices;
    private HashMap<Integer, Edge> edges;
    
    public Graph(){
        this.vertices = new HashMap<String, Vertex>();
        this.edges = new HashMap<Integer, Edge>();
    }
    
    /**
     * This constructor accepts an ArrayList<Vertex> and populates
     * this.vertices. If multiple Vertex objects have the same label,
     * then the last Vertex with the given label is used. 
     * 
     * @param vertices The initial Vertices to populate this Graph
     */
    public Graph(ArrayList<Vertex> vertices){
        this.vertices = new HashMap<String, Vertex>();
        this.edges = new HashMap<Integer, Edge>();
        
        for(Vertex v: vertices){
            this.vertices.put(v.getLabel(), v);
        }
        
    }
    
    /**
     * This method adds am edge between Vertices one and two
     * of weight 1, if no Edge between these Vertices already
     * exists in the Graph.
     * 
     * @param one The first vertex to add
     * @param two The second vertex to add
     * @return true iff no Edge relating one and two exists in the Graph
     */
    public boolean addEdge(Vertex one, Vertex two){
        return addEdge(one, two, 1);
    }
    
    
    /**
     * Accepts two vertices and a weight, and adds the edge 
     * ({one, two}, weight) iff no Edge relating one and two 
     * exists in the Graph.
     * 
     * @param one The first Vertex of the Edge
     * @param two The second Vertex of the Edge
     * @param weight The weight of the Edge
     * @return true iff no Edge already exists in the Graph
     */
    public boolean addEdge(Vertex one, Vertex two, int weight){
        if(one.equals(two)){
            return false;   
        }
       
        //ensures the Edge is not in the Graph
        Edge e = new Edge(one, two, weight);
        if(edges.containsKey(e.hashCode())){
            return false;
        }
       
        //and that the Edge isn't already incident to one of the vertices
        else if(one.containsNeighbor(e) || two.containsNeighbor(e)){
            return false;
        }
            
        edges.put(e.hashCode(), e);
        one.addNeighbor(e);
        two.addNeighbor(e);
        return true;
    }
    
    /**
     * 
     * @param e The Edge to look up
     * @return true iff this Graph contains the Edge e
     */
    public boolean containsEdge(Edge e){
        if(e.getOne() == null || e.getTwo() == null){
            return false;
        }
        
        return this.edges.containsKey(e.hashCode());
    }
    
    
    /**
     * This method removes the specified Edge from the Graph,
     * including as each vertex's incidence neighborhood.
     * 
     * @param e The Edge to remove from the Graph
     * @return Edge The Edge removed from the Graph
     */
    public Edge removeEdge(Edge e){
       e.getOne().removeNeighbor(e);
       e.getTwo().removeNeighbor(e);
       return this.edges.remove(e.hashCode());
    }
    
    /**
     * 
     * @param vertex The Vertex to look up
     * @return true iff this Graph contains vertex
     */
    public boolean containsVertex(Vertex vertex){
        return this.vertices.get(vertex.getLabel()) != null;
    }
    
    /**
     * 
     * @param label The specified Vertex label
     * @return Vertex The Vertex with the specified label
     */
    public Vertex getVertex(String label){
        return vertices.get(label);
    }
    
    /**
     * This method adds a Vertex to the graph. If a Vertex with the same label
     * as the parameter exists in the Graph, the existing Vertex is overwritten
     * only if overwriteExisting is true. If the existing Vertex is overwritten,
     * the Edges incident to it are all removed from the Graph.
     * 
     * @param vertex
     * @param overwriteExisting
     * @return true iff vertex was added to the Graph
     */
    public boolean addVertex(Vertex vertex, boolean overwriteExisting){
        Vertex current = this.vertices.get(vertex.getLabel());
        if(current != null){
            if(!overwriteExisting){
                return false;
            }
            
            while(current.getNeighborCount() > 0){
                this.removeEdge(current.getNeighbor(0));
            }
        }
        
        
        vertices.put(vertex.getLabel(), vertex);
        return true;
    }
    
    /**
     * 
     * @param label The label of the Vertex to remove
     * @return Vertex The removed Vertex object
     */
    public Vertex removeVertex(String label){
        Vertex v = vertices.remove(label);
        
        while(v.getNeighborCount() > 0){
            this.removeEdge(v.getNeighbor((0)));
        }
        
        return v;
    }
    
    /**
     * 
     * @return Set<String> The unique labels of the Graph's Vertex objects
     */
    public Set<String> vertexKeys(){
        return this.vertices.keySet();
    }
    
    /**
     * 
     * @return Set<Edge> The Edges of this graph
     */
    public Set<Edge> getEdges(){
        return new HashSet<Edge>(this.edges.values());
    }
    
}

IV. Analysis of Dijkstra’s Algorithm
In this section, we analyze the correctness and complexity of Dijkstra’s Algorithm. The design of this algorithm leverages the optimal substructure exhibited by the shortest path problem. Formally, a problem is said to exhibit the optimal substructure property if an optimal solution contains within it solutions to the present optimal subproblems. We prove this formally.

Claim 1: Let be a connected graph and let . Let be a shortest path. Then for any pair of vertices , it follows that contains a shortest path.

Proof: Suppose to the contrary. Let be a shortest path such that for vertices , that the sub-path in is not a shortest path. Let be a shortest path. We replace the sub-path in with to obtain an path shorter than , a contradiction.

Any proof of correctness for Dijkstra’s Algorithm leverages the optimal substructure problem. The main idea is this: when the algorithm marks a vertex as visited, ‘s distance marker is the length of any shortest path from the initial vertex to .

Before proving Dijkstra’s algorithm, define be the shortest path metric on the graph. That is, for any pair of vertices and in the graph, is the length of any shortest path.

Theorem 1: Let be a connected graph. Dijkstra’s algorithm terminates. Let be the initial vertex used by the algorithm. Upon termination, the distance computed by the algorithm is equal to for every vertex .

We begin by showing the algorithm terminates.

Claim 2: Dijkstra’s algorithm terminates.

Proof: Suppose to the contrary that the algorithm does not terminate. Then the priority queue always has an element. This implies that there is always some unvisited vertex in the graph added to the priority queue after polling a vertex from the priority queue. This contradicts the assumption that the graph is finite. QED.

Claim 3: Upon termination, the distance computed by the algorithm is equal to for every vertex .

Proof: The proof is by induction on the number of vertices polled from the priority queue. When no elements have been polled from the priority queue, we have correctly computed . Suppose the claim holds true for the first elements polled from the priority queue. Let be the th vertex polled from the priority queue.

Suppose that . By the algorithm, is computed using only the previous marked vertices (the previously polled vertices and the initial vertex ). Then an unmarked vertex must be present in any shortest path from to . Let be the path computed by the algorithm. Let be a shortest path containing . Without loss of generality, suppose is the first unmarked vertex in . By Claim 1, the sub-path in is a shortest path. It is necessary that since is along a shortest path. It follows that ‘s predecessor would have visited and pushed it onto the priority queue. So would have been polled from the priority queue before , a contradiction.

It follows that the algorithm correctly computes the lengths of the shortest paths for all vertices . QED.

Theorem 2: Dijkstra’s Algorithm runs in time, where is the number of edges and is the number of vertices in the graph.

Proof: Suppose we use a heap where the key can be updated as the priority queue. Polling the vertex with the smallest distance marker from the heap takes time. For each polled vertex, we must evaluate all of its neighbors. While a vertex can have at most neighbors, there are total neighbors to be considered. When evaluating a vertex’s neighbor, updating the distance takes time. However, updating the vertex’s position in the heap takes time. So the runtime is . Since in the case of a connected graph, we have the runtime is . QED.

Auction Theory- Revenue Equivalence Theorem

I. Introduction
This blog entry introduces the Revenue Equivalence Theorem and its applications. The Revenue Equivalence Theorem is one of the most celebrated results in auction theory and mechanism design. Recall from my previous blog entry that the auctioneer expects the same revenue when comparing the symmetric first and second price auctions, where the players’ distributions are drawn from continuous probability distribution. The natural question arises regarding when two auction formats yield the same expected revenue for the auctioneer. The Revenue Equivalence Theorem provides conditions to answer this question. This theorem’s power extends beyond determining the seller’s expected revenue in symmetric auctions. It also enables us to derive symmetric equilibrium bidding strategies in auctions where both the number of bidders is known and uncertain. In many cases, applying the Revenue Equivalence Theorem provides a simpler approach to derive the symmetric equilibrium bidding function in comparison to solving the optimization problem.

II. Revenue Equivalence Theorem
In this section, we introduce and prove the Revenue Equivalence Theorem. Let’s begin by defining the class of auctions which are revenue equivalent. These auctions are referred to as standard auctions.

Standard Auction: Considerf a bidder auction and fix with . The auction is standard if the highest bidders are all awarded an item.

The auctions discussed in my previous blog entries, such as the first-price and second-price auctions, are all standard auctions with . That is, only the highest bidder wins an item.

The Revenue Equivalence Theorem will now be introduced.

Theorem 1 (Revenue Equivalence Theorem): Let be a standard auction, and suppose each player’s valuations are independent and identically distributed according to a continuous probability distribution . Suppose each player is risk neutral. Then any symmetric and increasing equilibrium bidding strategy , such that the expected payment of a bidder with valuation is , yields the same expected revenue for the seller.

Proof: Let be a standard auction. Define to be the random variable describing player ‘s payment given valuation . Let be a symmetric and increasing equilibrium bidding strategy such that for all players whose valuations . Suppose each player bids according to . Define as the probability that the highest valuation is . We have player ‘s expected profit by bidding for some given below. That is, player bids according to some valuation .

Player seeks to maximize his profit. We consider the first order conditions, differentiating with respect to :

As the joint strategy profile of each bidder submitting constitutes a Bayesian Nash Equilibrium, it follows that player maximizes his profit when submitting , or equivocally . So we have:

Integrating both sides over the interval yields:

Recall that by assumption . Note as well that:

Thus,

Observe that the final result does not depend on the particular auction. Revenue equivalence follows. QED.

Let’s now apply the Revenue Equivalence Theorem to determine the seller’s expected revenue.

Example: Consider a standard auction with bidders whose valuations are independent and identically distributed according to the uniform distribution over . That is, the density function is . We have by the Revenue Equivalence Theorem that the expected payment of a bidder with valuation is:

As the seller does not know each player’s valuations, the seller calculates the expected value for each possible . That is, given the winner, we calculate how much the seller expects to receive from this bidder. This yields:

The last step is to choose the winning bidder. By symmetry, this can be done in ways. By rule of product, we multiply this by the expected payment of the winning bidder to get the expected revenue of the seller:

III. Applications of Revenue Equivalence Theorem- Fixed Number of Bidders
The Revenue Equivalence Theorem’s power extends beyond testing an auction to determine its expected payoff for the seller and expected payments of the bidders. It can also be used to derive symmetric and increasing equilibrium bidding strategies, both in situations when the number of bidders is known and uncertain. We start with examples of standard, symmetric auctions with a fixed number of bidders.

Example: Consider the symmetric, all-pay auction with players. In the all pay auction, each player pays his or her bid regardless of winning the object. Let be the symmetric and increasing equilibrium bidding strategy. Note that a player with value will always pay nothing. By the Revenue Equivalence Theorem, we thus have:

In order to appreciate the power of the Revenue Equivalence Theorem, let’s contrast this approach with that of solving the profit maximization problem. Observe that for the all-pay auction, the profit maximization for a given bidder is shown below. The bidder always pays his bid, but receives valuation only with probability , where is the value associated with bid .

We consider the first order conditions:

In equilibrium, we have . Thus, we have:

Integrating both sides over , noting , yields:

This is the function given by applying the Revenue Equivalence Theorem.

Example: Consider a -player war of attrition game, where the players compete for a prize. Each player stays in the game and incurs a cost associated with the time of play. The game terminates when one player drops out. Equivocally, each player submits a bid and pays the cost of the lowest bid. Lastly, suppose that each player’s valuations are independent and identically distributed according to the density function . We seek to derive the symmetric equilibrium bidding strategy in this game.

We first derive the expected payment for an individual player . If the player is a winner, he expects to pay the lowest bid. If he loses, then he pays his bid. Let’s first calculate the payment for losing. Player ‘s probability of winning is . So the probability that his opponent bids higher than is given by . So if player loses, he expects to pay .

If player wins, he expects to pay player ‘s bid. Player with valuation bids . The probability that player has valuation is . So if player wins, he expects to pay:

Noting that:

So we have:

We next check if the conditions of the Revenue Equivalence Theorem hold. By assumption, both players’ valuations are independent and identically distributed. We also have the item awarded to the highest bidder, and we expect a player with valuation to pay nothing in the symmetric and increasing equilibrium. Lastly, we assume both players are risk neutral. That is, they seek to maximize their expected payoffs. Thus, the hypotheses of the Revenue Equivalence Theorem hold, so we have:

We differentiate both sides to get:

It follows that:

We integrate both sides over the interval , noting that to get the equilibrium bid function:

Example: Consider the -player losers pay auction. In this auction, the bidder with the highest valuation wins the item and pays nothing, while the losing bidders each pay their respective bids. Suppose the bidders’ valuations are independent and identically distributed according to the density function . We seek to derive the equilibrium bidding strategy in this auction.

Our first step is to check that the conditions of the Revenue Equivalence Theorem are satisfied. We assume that bidders are risk neutral. By assumption, bidders’ valuations are independent and identically distributed. The highest bidder wins the auction, and a player with valuation expects to pay . Thus, the hypotheses of the Revenue Equivalence Theorem hold, and we have:

We note as well that a player’s expected payoff is . Recall that is the probability that is the highest valuation. So . Thus, we have:

It follows that:

IV. Applications of Revenue Equivalence Theorem: Uncertain Number of Bidders
In this section, we examine how to leverage the Revenue Equivalence Theorem to derive a symmetric equilibrium bidding strategy in the case where there is uncertainty about the number of bidders participating in the auction.

We first extend the framework to discuss this model. Consider the set of potential players , each of whom have independent and identically distributed valuations given by the density function . Let be the set of actual bidders. Define as the probability player assigns to bidding against opponents. That is, denotes the probability player assigns to there being participants in the auction.

In order to apply the Revenue Equivalence Theorem, we need each symmetry of the bidders. In order to achieve this, each player’s beliefs about the number of bidders in the auction must be the same. That is, for each , must be the same for each bidder.

We now define as the probability that players all have valuation no more than . In other words, if there are players, then is the probability that player wins. Without knowing the number of bidders a priori, player ‘s probability of winning with valuation is simply a weighted sum, considering the probability of having opponents times the probability of winning with opponents:

We apply this definition of to obtain player ‘s profit when bidding :

Observe that this is the same formula from the proof of the Revenue Equivalence Theorem. So in the case of multiple bidders, we have:

Now let’s consider an example.

Example: We seek to determine the symmetric equilibrium bidding strategy in the first-price auction with an uncertain number of players. Suppose instead we have a second price auction. By the Revenue Equivalence Theorem, each bidder has the same expected payment in the two auctions. We begin by calculating this expected payment in the second price auction, which is easier to compute than the expected payment in the first price auction under this framework. Recall that in the second price auction, it is a Nash equilibrium for each player to bid his or her valuation. Thus, consider for a fixed the probability that player wins times the expected second highest bid. We then consider for all such . We multiply the expected bid for a fixed by ; and by rule of sum, add them up:

Recall from the first price auction that , where is the symmetric equilibrium bidding strategy in the first price auction. In the case where the number of bidders are known to be , we have by prior result that:

By the Revenue Equivalence Theorem, we have that:

Substituting in the result for and dividing both sides by , we obtain the symmetric equilibrium bidding function for the first price auction with an uncertain number of bidders:

Auction Theory: Post-Auction Resale

I. Introduction
This blog entry extends the model of auctions introduced in my prior blog entry by introducing the possibility of post-auction resale. In this model, the winning bidder can sell the item to the losing bidders at a fixed price. Initially, this mechanism may seem to favor the highest bidder, giving him or her the power to extort additional profit from the losing bidders. In the case of the first-price auction, the post-auction resale mechanism results in the same equilibrium bids and outcome as in the standard symmetric first-price auction. Similarly, the post-auction resale mechanism makes little sense to employ in the case of the second-price auction.

II. Auction Resale Problem
We consider the symmetric, sealed bid, first-price auction where each bidder’s valuation is drawn from the probability distribution given by , for some . Let be the symmetric equilibrium bidding function in the case of the first-price auction. Recall from my prior blog entry that:

The auctioneer begins by holding the auction. Then, after the auction, each player’s bid is made public. The winning bidder then decides whether or not to sell the item. If the winning bidder chooses to sell the item after the auction, he then decides upon a price after the auction. Any of the other bidder can then choose to accept the item at price or to reject this item. Note that the possibility of post-auction resale is known to all bidders a priori. We seek to determine how the winning bidder should set the price , as well as how the losing bidder should respond.

In order to analyze this mechanism, we consider the post-auction resale mechanism as a dynamic game. We apply dynamic programming, which is referred to as backward induction in game theory, to find the equilibrium strategies. In particular, this equilibrium is a subgame perfect Nash equilibrium, which induces a Nash equilibrium at every subgame.

We start by examining the last subgame, the post-auction resale. Let player be the winning bidder, and let be a player with the second highest bid. By monotonicity of the bidding strategies, we have , where are the bidders’ respective valuations. Let be the fixed price at which player chooses to sell the item. As the bids are public information, player will set , player ‘s bid. Player will purchase the item from player if and only if . If player purchases the item from player , then player ‘s profit is . As player will not own the item if he resells it, player does not obtain valuation from winning the item in the auction. Since , it follows that . So player has no incentive to resell the item.

Since the winning bidder has no incentive to resell the item after the auction, each bidder will submit his or her bid in an attempt to win and keep the item. Thus, each player should bid in the subgame perfect Nash equilibrium, then the winner should opt not to resell the item and a losing bidder should purchase the item if and only if is less than its valuation.

The above proof holds as well in the second price auction with the possibility of post-auction resale, noting that the winning bidder’s profit upon successful resale is . So the subgame perfect Nash equilibrium is for each player to bid his or her valuation, and for the winner not to resell the item after the auction.

We can more strongly say that there exists no incentive compatible, individually rational mechanism for the winning bidder to use to liquidate the item post-auction. This follows from the fact that no player will pay more than his or her valuation for the item, so the maximum payoff the winning bidder can obtain in choosing to liquidate the item post auction is in the case of the first price auction or in a second price auction, where is the valuation of the second highest bidder.

The Lambda Auction

I. Introduction
This blog entry introduces the -auction. Intuitively, the -auction is a mix between the first and second price auctions. Formally, the auctioneer fixes a value and awards the item to the highest bidder , who pays a convex combination of his or her bid and the second highest bid.

In order to study the -auction, we adopt the framework presented in my previous entry introducing auction theory. That is, the auction consists of bidders, each with a private valuation drawn from the probability distribution given by , for some Each bidder submits his or her bid in a sealed manner. This blog entry focuses on the symmetric case, where each player’s valuation is drawn from the same probability distribution . Furthermore, each player’s valuation is independent of the other players’ valuations. The symmetric equilibrium bidding function will be derived, and then verified to be an equilibrium bidding function.

II. Derivation of Symmetric Equilibrium Bidding Strategy
In this section, the symmetric equilibrium bidding strategy will be derived for the auction. The next section will verify that the derived bidding strategy indeed constitutes an equilibrium bidding strategy.

The goal of each bidder is to maximize his or her expected payoff. Each bidder’s valuation is fixed, and so a given player can only vary his or her bid. As we are considering the symmetric case, each player’s value is drawn from the probability distribution given by for some fixed . Suppose player has valuation . The probability that some player has valuation less than is given by . As each player’s valuation is independent, we multiply each to get as the probability that the remaining players each have valuation less than . That is, describes the probability that player has the highest valuation given that he has valuation . Define .

Let’s now define the optimization problem each bidder seeks to solve. We start by assuming that the symmetric equilibrium bidding function is continuous, differentiable, and strictly increasing. Consider first the term . By symmetry, we expect each player to bid according to in equilibrium. As is strictly increasing and continuous, it is invertible. So denotes the valuation associated with if were an equilibrium bid. As no player will bid more than his or her valuation, denotes the probability that player has the highest bid. We thus have as the expected payment under the first price auction, pro-weighted according to .

We then subtract out from the weight of the expected second highest bid. Observe that the integral calculates the expected highest bid of the remaining players, limiting the highest valuation to .

The next step is to consider the first order conditions, differentiating with respect to . Note that by the Fundamental Theorem of Calculus, We then differentiate as noted by the term .

Note that in the symmetric equilibrium, each player applies the same strategy. So we substitute and . We then multiply out by to get:

Expanding out and collecting terms yields:

This differential equation looks very similar to that in my previous blog entry for deriving the symmetric equilibrium bid in the first price auction. The constant in the term requires extra steps to solve the differential equation. Let , so . Then . Substituting in for yields:

We cancel out the and terms, leaving:

We note that by the product rule. So integrating both sides yields:

Note that . We simplify , integrating by parts. Let and . So

Plugging this expression into yields:

III. Verification of Symmetric Equilibrium Bidding Strategy
In this section, we verify that the function derived in the previous section actually constitutes a symmetric Bayesian Nash equilibrium.

Theorem 1: In a symmetric -auction where the valuations for each player are independent and identically distributed, the symmetric Bayesian Nash equilibrium occurs when each player bids according to the bidding function:

Proof: Consider player , and suppose player bids . Let be the valuation for to be an equilibrium bid. If player bids , then the second highest bidder could bid , resulting in a loss for player if he wins the object. If instead player wins the object, player pays nothing. So player won’t bid more than .

Denote the expected profit of player with valuation and bid as . Observe that the expected profit of bidding is:

It suffices to show that for all .

Consider:

Factoring out terms, we obtain:

Observe that . So . It follows that if (which is equivalent to ), then .

Now suppose . Thus, . Consider again:

We note that:

And evaluate the integral with coefficient by parts to obtain:

Applying this result and the Fundamental Theorem of calculus yields:

Recall from the derivation of that:

We consolidate:

With the last equality obtained integrating by parts. We thus have:

Observe that describes the area under the rectangle of width whose top-right vertex is at the point . As is monotone, this rectangle potentially covers area above . The integral covers exactly the area under for the same interval. Thus, we have:

Which implies that:

Whenever . Thus, whenever , player expects to profit less than by bidding . Thus, is an equilibrium bidding strategy. QED.