Treffer: Teaching Nash Equilibrium with Python

The author describes an assignment in an undergraduate game theory course in which students work together in class to develop a computer algorithm to identify Nash equilibria. This assignment builds basic computer science skills while applying game theory knowledge to real-world situations. Students work as a team to delineate the steps and write a program to identify all of the pure-strategy Nash equilibria of the game. They then test this program by creating and solving their own game. This assignment represents an efficient way for undergraduate economics students to gain valuable computer science skills without assuming any pre-existing computer science knowledge, without having to take classes outside of the economics major, and without economics faculty having to restructure entire courses or curricula.

As Provided

AN0162671472;jmd01apr.23;2023Mar28.04:33;v2.2.500

Teaching Nash equilibrium with Python 

The author describes an assignment in an undergraduate game theory course in which students work together in class to develop a computer algorithm to identify Nash equilibria. This assignment builds basic computer science skills while applying game theory knowledge to real-world situations. Students work as a team to delineate the steps and write a program to identify all of the pure-strategy Nash equilibria of the game. They then test this program by creating and solving their own game. This assignment represents an efficient way for undergraduate economics students to gain valuable computer science skills without assuming any pre-existing computer science knowledge, without having to take classes outside of the economics major, and without economics faculty having to restructure entire courses or curricula.

Keywords: Computer science; games in the classroom; game theory; Nash equilibrium

The assignment described in this article combines the hands-on experience of playing and solving a game in the classroom with the development of broadly applicable computer programming skills. This assignment can be implemented by instructors with any level of experience with Python, including none. The concept of a Nash equilibrium is one of the most important definitions that students learn in undergraduate game theory and economics as a whole. At the same time, the definition of a Nash equilibrium is complex, and students often struggle with it. In Games of Strategy ([4]) by Avinash Dixit, Susan Skeath, and David Reiley, Jr., a textbook commonly used in undergraduate game theory courses, the authors provide the following definition of a Nash equilibrium: "A configuration of strategies (one for each player) such that each player's strategy is best for him, given those of the other players" (766). A deep, intuitive understanding that a Nash equilibrium is a set of choices for each player that cannot be improved upon, given what other players have chosen, can be helpful for students as they learn more about economics. The assignment presented here uses in-class teamwork and computer programming to help students internalize this definition.

Instructors have designed many creative and interactive assignments to help students engage with the concepts of game theory. O'Roark and Grant ([9]) use comic books. Alba-Fernández et al. ([3]) use a beauty contest game. McCannon ([7]) uses the Bible. The exercise described in this article uses computer programming.

Experiential learning and classroom activities can be used to solidify students' understanding of key concepts throughout economics (Henderson [5]; Truscott, Rustogi, and Young [12]). These activities range from service learning (McGoldrick [8]), to writing as macroeconomic journalists (Aguilar and Soques [1]), to competing to create the best fiscal policy (Aguilar and Soques [2]). This assignment asks students to act as a programming team to solve a computational problem and provides students with the opportunity to experience a type of work that their eventual career may feature. This type of work takes place every day at social media companies, research labs, financial consulting firms, and a number of other jobs that economics majors may eventually pursue.

Experience with computer science is not only helpful for students because of the increasing digitalization of jobs but also because of the skills that it develops. Students with degrees in economics are already sought after because of their problem-solving skills. Computer programming requires these same skills, as well as communication and abstraction. The ability to break down a problem into lines of code for a computer to process is an excellent complement to the existing economics major's skill set. These problem-solving, communication, and abstraction skills are particularly honed by working with a definition as complex as that of a Nash equilibrium. Students break down the process of identifying a Nash equilibrium into its foundational components and must explain to a computer what they mean.

Whether economics undergraduates become financial consultants, political advocates, or go on to graduate school, a basic knowledge of computer science is helpful for success (Takemura [11]). These skills are increasingly important in economics as computation, technology, and mathematics become a greater part of the discipline (Marshall and Underwood [6]). But for most economics majors, it is not feasible to add a computer science major, both because of their already full academic plates and because demand for computer science classes is increasing (Soper [10]). Nor is it practical for most economics departments to devote faculty resources to a "Computer Science for Economics" elective. As such, if faculty want to ensure that economics majors are exposed to computer programming, this material needs to be incorporated into our existing curriculum. This article describes an assignment that can be used in a variety of undergraduate or master's-level microeconomic courses to cement students' understanding of the concept of a Nash equilibrium. The assignment could be used in undergraduate introductory and intermediate microeconomic theory courses and game theory courses, as well as in master's and MBA courses on microeconomics and game theory.

In the assignment, students first work as a group to identify the pure-strategy Nash equilibrium in a simultaneous discrete-choice game, often referred to as a matrix game. Following this, students break down the process into discrete steps, designing an algorithm that will eventually become a computer program. Finally, students test the algorithm using a game that they create themselves. The majority of students in the class in which I implemented this assignment had no prior computer science experience but, after working through the game and algorithm as a group in class, were able to write a program in Python to correctly identify the Nash equilibria in any two-player matrix game.

To begin the assignment, the instructor presents the class with a standard matrix game with two players. In this particular game, the two players are planning a Thanksgiving meal. The first player is bringing the main dish, and the second player is bringing a side dish. The available strategies and payoffs of this game are described in table 1. A Nash equilibrium in this game is a choice of a main dish and a side dish such that neither player wishes to bring a different dish, given the other player's choice. The class proceeds to check each cell of the matrix for the characteristics of a Nash equilibrium. As they move through this process, the instructor asks students to identify the step-by-step process used and takes notes on the board as the students name the steps. The instructor and class then use these steps to draft an algorithm (in words) for identifying a Nash equilibrium using cell-by-cell inspection. The students then use this pseudocode to write a computer program in the programming language Python in order to find any Nash equilibria in pure strategies in a two-player matrix game. The instructor and the class work together to outline the algorithm, and then students independently implement their own program. To test their algorithm, students design their own matrix game. The only requirement for their game is that it has two players, and each player has enough choices so as to make the game tedious—but possible—to solve by hand. The assignment introduces as little new terminology as possible so as to require as little computer science overhead as possible. Students turn in a description of their game, their Python code, the output that the code creates, and a discussion of the results.

Table 1. In-class game matrix.

<table><thead><tr><td /><td /><td>Player 2 (2nd Friend)</td></tr><tr><td>Mashed potatoes</td><td>Macaroni & cheese</td><td>Broccoli</td></tr></thead><tbody valign="top"><tr><td>Player 1 (1st Friend)</td><td>Roast Beef</td><td char=".">3, 1</td><td char=".">2, 3</td><td char=".">10, 2</td></tr><tr><td>Turkey</td><td char=".">4, 5</td><td char=".">3, 0</td><td char=".">6, 4</td></tr><tr><td>Meatloaf</td><td char=".">2, 2</td><td char=".">5, 4</td><td char=".">12, 3</td></tr><tr><td>Lasagna</td><td char=".">5, 6</td><td char=".">4, 5</td><td char=".">9, 7</td></tr></tbody></table>

This assignment can be implemented effectively by instructors with little to no experience with Python. The use of pseudocode to describe the steps of the algorithm is more important than the specific programming language, and it is a concept that instructors can introduce without any specific programming experience. The Python code needed to implement the assignment can be found on my Web site, www.aoluedtke.com. Additionally, figure 1 provides a fully annotated version of the Python code that directly matches each section of the code with the pseudocode described in the "Assignment" section of this article.

Graph: Figure 1. Annotated code with pseudocode.

The assignment is designed to require as little time in introducing computer science topics as possible. No additional Python packages are required, so there is no complicated header needed at the top of the students' code. The class participants to whom this assignment was first introduced were able to complete it within three lecture hours devoted to background and outlining the algorithms. It could be done with less time in class if the instructor wants to leave more work for the students to complete independently. Additionally, this assignment is easier to grade than a traditional game theory problem set. Grading is discussed in more detail in later sections. Resources to assist instructors with the implementation of this assignment are discussed in the third section, "Tips and Resources for Instructors."

Not only did students in the undergraduate game theory class in which this assignment was implemented perform well on this assignment—all but two students received a B or better—they also felt that it improved their resumes and job prospects. Multiple students reported discussing this project with potential employers in interviews for jobs and internships. Students also seemed to legitimately enjoy the assignment. At the end of the semester, students in this course had several options for their final project, one of which was an extension of the assignment described here. The final project assignment required them to write a new computer program that built on what they had produced previously. The vast majority of students chose to complete this option for their final project. One student even mentioned it on my teaching evaluation for the course as her favorite aspect of the class.

To best prepare students for life after college—whatever form that may take—we should expose them to computer programming at some point during their economics major study. This article describes an assignment that accomplishes this by having students work together and rely on one another without requiring any prior computer science experience on the students' part and with little extra work for instructors. Assignments of this type will become increasingly necessary as departments are doing more with less.

The next section describes the assignment in detail, including the game the students solve as a group, the process for creating an algorithm from the steps students suggest, and an outline of the Python code that identifies the Nash equilibria in a two-player matrix game. The following section describes some tips and resources for instructors, including potential Python compilers that allow students to begin writing and running code quickly. The final section concludes.

Assignment

To begin the assignment, the instructor describes to the class a simultaneous-choice game with two players. Such games can be represented as a table, or matrix, that describes the payoffs to each player associated with each of their possible choices. The two players in this game are organizing a Thanksgiving dinner and choosing the main course and a side dish. Player 1 is bringing the main course, and Player 2 is bringing a side dish. The payoffs to each player for each combination of strategies are enumerated in table 1. The instructor and the class then check each cell of the matrix for the characteristics of a Nash equilibrium by asking questions like, "Is Player 1 happy with his choice to bring roast beef if Player 2 brings mashed potatoes?" This procedure for identifying any Nash equilibrium of the game is often referred to as "cell-by-cell inspection" (Dixit, Skeath, and Reiley [4], 95). As the class moves through this process, the instructor writes each step of the process on the board, e.g., "Starting with the first row, one column at a time, check each cell." After the class solves the Thanksgiving game, they use these steps to outline an algorithm that could be written in computer code. They do this by first outlining the steps of the algorithm in pseudocode. Table 2 contains examples of student descriptions and the corresponding pseudocode. The purpose of pseudocode is to allow the writer to outline code without the specific syntax of a programming language. As such, the examples of pseudocode presented in table 2 are merely suggestions, and instructors can adapt them to their classes.

Table 2. Student descriptions and pseudocode.

<table><thead><tr><td>Student descriptions</td><td>Pseudocode</td></tr></thead><tbody valign="top"><tr><td>"Check each row" "Check each column"</td><td>for each row: for each column:</td></tr><tr><td>"Can Player 1 be made better off (given Player 2's choice)?"</td><td>check if row player can be made better off</td></tr><tr><td>"Can Player 2 be made better off (given Player 1's choice)?"</td><td>check if column player can be made better off</td></tr><tr><td>"If neither has a better option (given the other's choice), this is a Nash equilibrium."</td><td>if neither can be: label as equilibrium</td></tr><tr><td>"If either has a better option (given the other's choice), this is not a Nash equilibrium."</td><td>if any can be: label as not an equilibrium</td></tr></tbody></table>

A pure-strategy Nash equilibrium in this type of game consists of a choice by each player such that, given one player's choice, the other player cannot improve his payoff by changing his choice. Consider the first cell, with payoffs [3, 1]. Given that Player 1 is choosing to bring roast beef, Player 2 can improve his payoff from 1 to 3 by switching to bringing macaroni and cheese rather than mashed potatoes. As such, the first cell is not a Nash equilibrium. The middle cell in the third row, with payoffs [5, 4], represents the only pure-strategy Nash equilibrium in this game: Player 1 brings meatloaf, and Player 2 brings macaroni and cheese. There are several ways to identify the pure-strategy Nash equilibria in a matrix game, including cell-by-cell inspection, iterated removal of dominated strategies (in certain circumstances), and best-response analysis.

Of these, the method that students struggle with the most is cell-by-cell inspection. This method requires some of the deepest knowledge of the Nash equilibrium definition and, at the same time, is well-suited for computers. To find all Nash equilibria using cell-by-cell inspection, each cell of the matrix is checked to see if it meets the definition of a Nash equilibrium. The algorithm that the students write visits each cell of their game matrix and checks to see if either player can be made better off, given the other player's choice. If neither player can be made better off, the algorithm records that cell as an equilibrium. If either player can be made better off, the algorithm records that cell as not an equilibrium. Every cell of the matrix is visited and labeled as "equilibrium" or "not." In order to achieve this, students must write an algorithm that (1) visits each cell, (2) queries the payoffs for each player, (3) compares them to the relevant other payoffs, and (4) makes the correct determination about the equilibrium status of that cell. The pseudocode for this is as follows:

Figure 1 provides a fully annotated version of the Python code that implements this assignment. Each line of the pseudocode above is matched to the specific Python language that accomplishes that step.

The Python code to find all pure-strategy Nash equilibria consists of three main components: reading in a matrix of payoffs, checking each cell for the characteristics of a Nash equilibrium, and printing out the cells that are equilibria. Taken together, these components force students to break down their real-world scenario into the foundational elements of a game: payoffs and equilibrium. The class and the instructor work collectively to come up with pseudocode, which the instructor writes on the board, and then he or she types and explains the actual Python code on the classroom computer display. Because the students had no prior experience with programming, with the correct code displayed on the projection screen, the translation onto their own computers was sufficiently difficult to present a challenge, but students felt comfortable enough to try and fail a few times before they got it entirely correct.

Instructors who wish to introduce as little Python terminology as possible to complete this assignment may choose to use Python's innate matrix structure rather than import a package like Numpy, which might have more elegant and complex matrix operations. While the innate matrix structure requires the use of a cumbersome number of brackets and parentheses, it saves at least an extra day of explaining how to import Python packages, which would add nothing to the students' understanding of game theory. If, however, an instructor wanted to include the use of packages in this assignment, Numpy would represent a good introductory example. In this article, I provide code for using Python's innate matrix structure and no imported packages. The code to input the game matrix for the game represented in table 1 can be found at the top of figure 1.

Each pair of numbers represents the payoffs to Player 1 and Player 2, respectively. The instructor can provide students with this code to input the matrix for the game they solve as a class. When students write their own matrix game to test the code, they can then use this code as a template for inputting their own game matrix independently.

The final task of the computer program is to print any cells that are Nash equilibria in an output window. I chose to make the output process a separate task of the algorithm rather than to have it print the Nash equilibria as it found them. This serves two purposes: (1) it makes the algorithm more modular so that students can use portions of it for other projects; and (2) it allows each portion of the algorithm to be introduced separately. This method requires the use of a second matrix, the same size as the game matrix, that contains the equilibrium "label" for each cell. As the algorithm determines the equilibrium status of each cell, it stores the appropriate label in the label matrix. When the equilibrium-identification portion of the algorithm is completed, the label matrix contains the equilibrium status of each cell. To print out any Nash equilibria, the algorithm must now parse the label matrix and print out any cells of the game matrix that correspond to a label of "equilibrium." Every label starts out as a "0." If it is a Nash equilibrium, the label is switched to a "1," and if it is not a Nash equilibrium, the label is switched to a "2." This allows students to practice the critical computational skill of converting qualitative information ("is a Nash equilibrium") into numerical data ("1"). The pseudocode for printing out any Nash equilibrium cells is as follows:

To test the code that they produce, students create their own two-player simultaneous-choice game and then run the code that the class builds on this game. I encouraged students to be creative in the design of their games because, when they delineate each step of the solution process using their own terms instead of mine or the textbook's, they gain a deeper grasp of the economic meaning of them. To complete the assignment, students turn in the following elements: (1) a description of their game, (2) their Python code, (3) the output when their code is run, and (4) a discussion of the solution of the game. It may be the case that the game that students create does not have any Nash equilibria in pure strategies.

In the description of the game, students specify who the players are, what choices are available to them, and what the payoffs for each possible outcome are. In this description, they also include the matrix that represents their game. Students turn in their Python code as a Python file so that the instructor can run it to ensure that it works correctly. In their discussion of the solution found by their code, students explain whether any of the Nash equilibria are socially optimal, whether they make sense in the context that the students originally envisioned, what would need to change about the game to achieve a different outcome, and any other observations that the students wish to share. Students turn in two files: one is a typed document containing the description of the game, the output of the Python code, and the discussion, and the second is their Python code.

In addition to building teamwork, communication, computation, and abstraction skills, this assignment forces students to carefully consider what constitutes a good example of a simultaneous discrete-choice game and, thus, what would make a good test question about simultaneous discrete-choice games. No matter how many times I tell my students that the best way to prepare for a test is to create their own practice questions, they do not believe it until they are forced to do it. This is one way to accomplish that.

Tips and resources for instructors

This assignment can be adapted to fit into most assignment types and grading categories. I used it as one of five homework assignments throughout the semester. Depending on how much can be covered together in class and how much is left for the students to complete independently, in conjunction with the level of programming experience of the students, this assignment can be a small classwork assignment, a homework assignment, a large term project, or even an extra credit assignment. In order to receive a perfect score on this assignment, students had to turn in all components, explain all components of their game, correctly identify any Nash equilibria of their game—both in their description of the game and computationally—and discuss the appropriate outcomes. It is easy for the grader to identify the components of the game in the description (e.g., "players," "choices," "payoffs," "equilibria") and the discussion (e.g., "social optima," "potential changes"). The only numerical component that requires checking is the correct identification of the Nash equilibria. This can be done very quickly by copying their game matrix and label matrix into the instructor's code and running it. If their list of equilibria matches the instructor's, they correctly identified them.

To easily run Python code on a classroom computer and on the students' computers without having to install many new software packages, I recommend making use of online Python editors and compilers, such as Jupyter Notebook or Google Colaboratory. Alternatively, if an instructor prefers to use an application that does not require an Internet connection, I recommend the Python editor and compiler, Thonny. It is easy for students to install and use without complicated installation procedures and works well for small, pedagogical applications such as this one.

The actual Python code for the example represented in table 1 is replicated in its entirety in figure 1. Additionally, figure 1 matches each line of the pseudocode presented in the "Assignment" section with the lines of Python code that implement it.

The assignment was designed to allow for expansions and further applications later in the semester if the students expressed interest. Students were given a slate of choices for their final project in the class, and one of the options was to complete another programming assignment. Specifically, I asked students to modify their code to randomly generate a game matrix and use their existing code to find any Nash equilibria. There are many possible expansions to this assignment, and I encourage instructors to create their own.

Conclusion

In this article, I present an assignment for undergraduate game theory students. In the assignment, students work together as a class to identify Nash equilibria in a game and outline an algorithm for replicating this process in any similar matrix game. They then write a computer program in Python that finds all the pure-strategy Nash equilibria of their game and test this code by creating their own game based on their lives. The assignment is designed to take only three to six hours of instruction, so it can be added to most undergraduate game theory courses without faculty needing to dramatically restructure their courses. Experience with computer programming is swiftly becoming necessary for most careers that an economics graduate would pursue. This assignment efficiently provides students with a workable knowledge of programming in Python.

By Allison Oldham Luedtke

Reported by Author