Final Questions

Final will contain 20 out of the following 24 questions:

  1. Find all pure Nash equilibria in a given finite two-player game.
  2. Find all pure Nash equilibria in a given finite multiplayer game.
  3. Find all pure strict Nash equilibria in a given finite two-player game.
  4. Find all (pure and mixed) Nash equilibria in a given two-player game where each player has only two strategies.
  5. List all strictly dominating strategies in a given game.
  6. List all weakly dominating strategies in a given game.
  7. List all strictly dominated strategies in a given game.
  8. List all weakly dominated strategies in a given game.
  9. Find all maxmin pure strategies of a given two-player game.
  10. Find all maxmin mixed strategies of a given two-player game.
  11. Find all minmax strategies of a given two-player game.
  12. Find all minmax mixed strategies of a given two-player game.
  13. Find all minmax regret strategies of a given two-player game.
  14. Find all epsilon-Nash equilibria of a given two-player game.
  15. Find subgame perfect equilibrium in an extensive form game.
  16. Find values of the discount factor for which given strategy profile forms a Nash equilibrium in a given iterative game.
  17. Draw a Moore machine representing a given strategy in an iterative game.
  18. Given a potential function of a two-player game. Construct an example of a potential game with the given potential function.
  19. Given a potential game, find its potential function.
  20. Find a Nash equilibrium of a given congestion game.
  21. Give a social network and a set of agents who received free samples, find all agents who eventually will adopt the product.
  22. Given a social welfare function, decide if it satisfies properties of a) unanimity, b) independence of irrelevant alternatives c) dictatorship.
  23. Given an epistemic model, decide which of the given epistemic formulae are true in which of the epistemic worlds of the model.
  24. Decide which of the given epistemic principles are universally true.

Solution for HW8

Your solution has been tested on the following three sample machines

Machine 1

2
C D
1 2
2 2

Machine 2

1
D
1 
1

Machine 3

3
C C D
1 2 3 
2 3 3

These three machines have been played again each other in three games. Each game had 5 iterations. Here are the corrected answers that I was looking for

Machine 1 vs Machine 2: CD DD DD DD DD

Machine 2 vs Machine 3: DC DC DD DD DD

Machine 1 vs Machine 3: CC CC CC CC CC

Homework Assignment 10, due May 4th

THE LAST ASSIGNMENT

For this assignment you will write a Java program that inputs a file with a description of a social network and computes all agents that will eventually adopt the product under threshold diffusion model after samples are given to a specific group of agents.

INPUT DESCRIPTION

The first line of the file will contain a single integer positive number n specifying the total number of agents in the social networks. We use natural numbers to represent these agents. For example, if n=7, then the agents are 0, 1, 2, 3, 4, 5, and 6.

The second line of the input file will contain n numbers of type double separated by spaces that specify threshold values of all agents. For example, if n=3 and the second line contains numbers 1.2 3.4 4.5, then threshold value of agent 0 is 1.2, agent 1 is 3.4, and agent 2 is 4.5.

The third line contains n integer numbers 0 or 1 separated by spaces that specify which agents received free samples and started to use them. For example, if the third line contains numbers 1 0 1, then 0th and 2nd agent received free samples.

The fourth line of the file will contain a single non-negative integer m. It specifies the number of edges in the network.

The rest of the file will contain m lines. Each line will have an integer number followed by a double, followed by an integer number. It specifies the weight assigned to each edge. For example, if a line contains numbers 0 3.2 1, then it means that if agent 0 adopts the product, then it puts peer pressure of 3.2 on agent 1.

OUTPUT DECRIPTION

Your program should print out a single line in the terminal window that lists numbers (in the increasing order) of all agents who either were given the product to start with, or would adopt it as a result of the diffusion.

EXAMPLE

If you are given input file

4
1.0 1.0 1.0 1.0
1 0 0 0
3
0 1.2 1
1 1.2 2 
2 0.8 3 

then your output should be

0 1 2

Use the same submission instruction as before. Good luck!

Homework Assignment 9, due April 27th

For this assignment you will write a Java program that finds a Nash equilibrium of a two-player potential game. Your program must use the iterative algorithm described in class. Namely,

  1. Start with strategy profile (0,0).
  2. Change Alice's strategy to the one that gives the maximal pay-off for Alice given current Bob's strategy. Print out the new strategy profile.
  3. Change Bob's strategy to the one that gives the maximal pay-off for Bob given current Alice's strategy. Print out the new strategy profile.
  4. Goto step 2.

Your program should terminate when neither Alice nor Bob can improve their respective payoffs. For example, if you are given game (defined, as usual, through table of pay-offs) 

3 3
1 1 2 7 -1 2
2 -3 1 1 2 0
3 1 -3 0 1 2

then your output should be

(0,0) (2,0) (2,2) (1,2) (1,1) (0,1)

Note that strategy profile (0,1) is indeed an equilibrium of the game above. Use the same submission instruction as before. Good luck!

Solution for HW 6

Your solution has been tested on the following three sample games

Game 1

2
1 2 3 4 15 5 7 8 9 10

Correct answer for this game is 15, 5.

Game 2

2
1 2 3 4 5 15 7 8 9 10

Correct answer for this game is 9, 10.

Game 3

2
12 1 3 4 5 15 7 8 9 10

Correct answer for this game is 12, 1.

Homework Assignment 8, due April 20th

For this assignment you will write a Java program that plays a finite iterative game between two Moore machines. To keep the implementation simple, we assume that each of the two machines has only two strategies: C and D.

Your program will read the description of a machine from a file. The first line of the file contains a positive integer number n equal to the number of states of the machine. The second line will contain n symbols separated by spaces. Each symbol is either C or D. If i-th symbol is C, then machine plays strategy C in i-th state; if it's D, then the machine plays strategy D. The third line will contain n integer numbers, separated by spaces, showing the new states into which the machine goes if the opponent plays strategy C. For example if 2nd number on this line is 3, then the machine transition from state 2 to state 3 when the opponent plays C. The fourth line will contain n integer numbers, separated by spaces, showing the new states into which the machine transitions if the opponent plays strategy D. For example if 2nd number in this line is 4, then the machine transition from state 2 to state 4 when the opponent plays D. Initial state of the machine is state 1.

For example, the following file describes Grim Trigger Moore machine:

2
C D
1 2
2 2

Your program must read from the command line three arguments. The first two arguments will specify two files with descriptions of Moore machines. The third argument is a nonnegative  integer number specifying number of iterations of the finite iterative game. Your program must output strategies used by each player in each of the iterations. For example:

java HW8hopper grim_trigger.game grim_trigger.game 5
CC CC CC CC CC

Use the same submission instruction as before. Good luck!

Homework Assignment 7, due April 13th

Problem. For which values of the discount factor strategy profile (grim trigger, grim trigger) is a Nash equilibrium of the infinite repeated game based on the following stage game:

cooperate defect
cooperate 1, 2 0,3
defect 2,0 0,0

Turn-in your solution on paper. Show your work.

Solution for HW5

Your solution has been tested on the following three sample games

Game 1

2 2
1 2 7 8
5 6 3 4

Minmax regret strategy for first player are 0 and 1, for the second players it is 1. 

Game 2

2 3
0 3 1 2 0 2
1 1 2 2 0 1

Minmax regret strategy for first player is 1, for the second player these are 0, 1, 2. 

Game 3

3 2
1 1 1 1
2 2 2 2
3 3 3 3

Minmax regret strategy for first player is 2, for the second player these are 0, 1

Homework Assignment 6, due April 6th

Write Java program that uses backward induction algorithm to find pay-off in subgame perfect equilibrium of a given centipede game with 2n steps. 

Centipede Game with 2n steps

Centipede Game with 2n steps

The input file for your program will contain two lines. The first line will contain positive integer n. The second line will list 4n+2 integer values representing pay-offs: a1 b1 a2 b2 a3 b3 .... separated by empty spaces. For example, if your program is given input

2
1 2 3 4 15 5 7 8 9 10

then it should output into the terminal: 15, 5.

Use submission instructions posted earlier.

Solution for HW4

Your solution has been tested on the following three sample games

Game 1

2 2
1 3 2 2
2 2 3 1

Maxmin strategy for first player is 1, for the second players is 0. 

Game 2

2 2
1 3 2 2
1 2 3 1

In this game first player's maxmin strategies are 0 and 1. Second player's maxima strategy is 0.

Game 3

2 2
1 1 2 3
1 2 3 1

In this game first and second players' maxmin strategies are 0 and 1. 

Midterm Questions

Midterm will include 10 out the following 14 questions. Each out of the 10 questions will have the same weight.

  1. Find all pure Nash equilibria in a given finite two-player game.
  2. Find all pure Nash equilibria in a given finite multiplayer game.
  3. Find all pure strict Nash equilibria in a given finite two-player game.
  4. Find all (pure and mixed) Nash equilibria in a given two-player game where each player has only two strategies.
  5. List all strictly dominating strategies in a given game.
  6. List all weakly dominating strategies in a given game.
  7. List all strictly dominated strategies in a given game.
  8. List all weakly dominated strategies in a given game.
  9. Find all maxmin pure strategies of a given two-player game.
  10. Find all maxmin mixed strategies of a given two-player game.
  11. Find all minmax strategies of a given two-player game.
  12. Find all minmax mixed strategies of a given two-player game.
  13. Find all minmax regret strategies of a given two-player game.
  14. Find all epsilon-Nash equilibria of a given two-player game.

Solution for HW3

Problem 1. Nash Equilibria: ((1, 0), (1, 0)), ((0, 1), (0, 1)), ((1/3, 2/3), (2/3 ,1/3)).

Problem 2. Your submission has been tested on the following three games:

Game 1

2 2
0 0 3 3
0 0 1 1

Expected output

3 3

Game 2 (classroom example)

3 3 
13 3 1 4 7 3 
4 1 3 3 6 2
-1 9 2 8 8 -1

Expected output

3 3

Game 3

3 3
1 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 1 1

Expected output

1 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 1 1

Average Score for HW3: 7.9/10

Homework Assignment 5, due March 2

Problem 1. Write a Java program that finds all minmax regret strategies of both players in a two-player game. Use the game file format, command line syntax, and the submission instruction from the previous assignments.

Homework Assignment 4, due February 23rd

Problem 1. Write a Java program that finds all maxmin strategies of both players in a two-player game. For example, for game

3 3
1 1 2 4 3 7
1 2 3 5 4 8
0 3 10 6 20 9

your program should print in the terminal window 

Maxmin strategies of the first player: 0, 1,
Maxmin strategies of the second player: 2

Use the game file format, command line syntax, and the submission instruction from Homework Assignment 2.

Solution for HW2

This sample code finds all Nash equilibria in a given game. It is only a partial solution to Homework Assignment 2 because it does not find strict equilibria. 

Your submission has been tested on the following three games:

Game 1

2 3
0.0 0.0 1.0 1.0 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0

This game has one strict Nash equilibria: (0,1) and three Nash equilibria: (0,1), (1,0), and (1,2).

Game 2

2 2
2.0 1.0 0.0 0.0
0.0 0.0 1.0 2.0

This is Battle of Sexes game that has two Nash equilibria: (0,0) and (1,1). Both of the are strict. 

Game 3

2 2
1.0 0.0 0.0 1.0
0.0 1.0 1.0 0.0

This is a variation of the matching pennies game that has no Nash equilibria.

Homework Assignment 3, due February 16th

Problem 1.  Find all pure and mixed Nash equilibria of the following game. Submit your answer and the solution on paper.

1, 3 1, 1
0, 0 3, 1

Problem 2. Write a Java program that applies iterative strictly dominated strategy elimination algorithm to a given matrix of a two-player game. For example, when run on a file containing game

3 3
3.0 4.0 1.0 1.0 2.0 2.0
0.0 0.0 0.0 0.0 0.0 0.0
2.0 2.0 1.0 1.0 4.0 3.0

your program should print in the terminal window the following reduced game:

3.0 4.0 2.0 2.0
2.0 2.0 4.0 3.0

Use the game file format, command line syntax, and the submission instruction from Homework Assignment 2.

Homework Assignment 2, due Thursday February 9th

For this assignment that you need to write a Java program that reads pay-off table of a two-player strategic game and prints out all Nash equilibria and all strict Nash equilibria of this game. Keep in mind that each strict Nash equilibrium is also just a Nash equilibrium.

Input Format. Your program should read from a file. The first line of the input file will contain two positive integers representing the number of strategies of the first and second player accordingly. The rest of the file will contain pay-off matrix one row per line with spaces used as separators. For example, the input file for prisoner's dilemma look like this:

2 2
-2.0 -2.0 0.0 -3.0
-3.0 0.0 -1.0 -1.0

 An input file for Rock-Paper-Scissors game looks like this 

3 3
0.0 0.0 -1.0 1.0 1.0 -1.0
1.0 -1.0 0.0 0.0 -1.0 1.0
-1.0 1.0 1.0 -1.0 0.0 0.0 

Algorithm. Implement the most straightforward algorithm that uses several nested loops to test each strategy profile.

Execution. Your program must run from the command line. The name of the file with the description of the game will be passed as the argument. The name of the Java class and the name of the file in which you write the code should have form HW2hopper and HW2hopper.java, where "hopper" should be your last name. Here is an example of the command line that will be used on a hypothetical assignment submitted by Grace Hopper:

> java HW2hopper prisoners.game 

Output. Your program must output in the terminal window the list of all equilibria and, separately, the list of all strict equilibria. The format of a single equilibrium is (r,c), where positive integer r is the row number and positive integer c is the column number of the cell in which the equilibrium is achieved. If the game has no equilibria of the given type, output ``none". For example, in case of prisoner's dilemma, the output is

> java HW2hopper prisoners.game
The list of Nash equilibria: (1,1),
The list of strict Nash equilibria: (1,1),

In case of Rock-Paper-Scissors:

> java HW2hopper rps.game
The list of Nash equilibria: none 
The list of strict Nash equilibria: none

In case of defined in class Battle-of-Sexes game:

> java HW2hopper bos.game
The list of Nash equilibria: (1,1), (2,2), 
The list of strict Nash equilibria: (1,1), (2,2),

Submission. Follow this link to submit your code using password "game". Grace Hopper would submit a single java file HW2hopper.java. Do not submit .class file.  If you re-submit the same file several times, I will only grade the most recent version. In addition, print out your code on paper and submit this printout in class.

Homework Assignment 1, due Thu Feb 2nd, no penalty till 9th

Problem 1. The following matrix describes two party strategic game in which first player has strategies a1 and a2 and the second player has strategies b1 and b2. Find all Nash equilibria of this game.

b1 b2
a1 1, 4 3, 2
a2 2, 3 4, 1

Problem 2. For which values of variable x, the matrix below describes a game with two Nash equilibria? 

b1 b2
a1 1, x 3, 2
a2 2, 3 x, 1

Average Score: 8.7/10

Syllabus

Foundations of Multiagent Systems 

 

VASSAR COLLEGE

 

Course Description. An introduction to game theory, a mathematical theory of conflict and cooperation between rational agents, with emphasis on computational aspects and applications to security and network analysis. The course also provides an overview of other topics at the intersection of theoretical computer science and economics, such as mechanism design, auctions, judgment aggregation, and diffusion in social networks.

Instructor. Pavel Naumov (pnaumov@vassar.edu). Office Hours: TuTh 3-4pm. SP 104.1.

Assignments. Weekly assignment will usually be posted on this page before the beginning of each Thursday class meeting. It will be due by the end of the class next Thursday, unless specified otherwise. Late assignments will be subject to 20 percent penalty. No assignment will be accepted more than 48 hours after it is due except for medical circumstances. Weekly assignments will contain non-programming and/or programming problems. 

Collaboration. All assignments must be done independently. Violations of this policy will be treated as cheating.

Tests. Midterm and regularly scheduled final examination will contain only non-programming problems. You will be given at least one week notice before the midterm.

Final Grade. Your final score in this course will be the weighted total of assignments (50%),  midterm exam (20%), and the final exam (30%). If your final total score is at least 80% of the course total, then you are guaranteed to get at least B.

Communication. Please, check your Vassar e-mail regularly.  The class mailing list will be used for class cancellation notices. The best way to reach me is via e-mail.

Attendance Policy. Regular  class attendance is highly recommended. You are responsible for learning any class material that you have missed.

Required Textbook. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Yoav Shoham and Kevin Leyton-Brown, Cambridge University Press; 1 edition, 2008. PDF can be downloaded here.

Recommended Textbook. A Course in Game Theory, Martin J. Osborne and Ariel Rubinstein, MIT Press 1994. PDF can be found online.