• Non-Zero-Sum Games
Alice is taking a class taught by Bob called \Arti cial Intelligence." Bob has three ways he can teach the class: \Hard," \Medium" or \Easy." Alice has three ways she can take the class: \Hard Working," \Work-ing" and \Hardly Working." For each of them, there are pros and cons. For instance, it’s easy for Bob
to teach an Easy class or a Hard class, but hard to balance the two. Obviously Alice doesn’t like to work hard, but she realizes that she might have to in order to learn something. Bob is happy to teach a hard class to students who are willing to work hard, but if the students don’t work hard, they punish Bob by giving him bad teaching evals!1 All of these things considered gives rise to the following table of rewards. These are written as (A; B) where A is Alice’s reward and B is Bob’s reward:
Hard
Medium
Easy
Hard
(9; 9)
(6; 5)
(2; 1)
Working
(5; 7)
(8; 6)
(4; 2)
Hardly
(3; 1)
(5; 2)
(4; 4)
1. If Bob assumes that Alice will optimize her own reward (i.e., Bob assume’s Alice is an optimal agent), how should he teach the class, supposing that Bob plays rst? If Alice assumes Bob is an optimal agent, how hard should she work?
2. We discussed the minimax algorithm in class for zero-sum games. What must we change in order to make minimax work for non-zero-sum games?
3. Draw a game tree for this problem supposing that Bob goes rst. Propagate values up through the tree using (the non-zero-sum variant of) minimax search.
4. Alice is clearly a good student (see question one), but once in a while we get students who aren’t quite as dilligent :(. It makes sense for Bob to model his class as a distribution over types of stu-dents. Suppose Bob believes that 40% of his class will work hard, 45% will work, and 15% will hardly work. Draw the expectimax tree for this setting, concentrating only on Bob’s reward, and compute expected node values. What is Bob’s expected reward for this setting and which type of class should he teach?
1Yes, this implies that any bad teaching reviews must be due to shortcomings of students, not of professors!
1
