The standard minimax algorithm calculates worst$-$case values in a zero$-$sum two player game,

i$.$e$.$ a game for which in all terminal states s$,$ the utilities for players A $($MAX$)$ and B $($MIN$)$ obey

$($s$)+($s$)=0.$ In this zero$-$sum setting, we know that $($s$)=-($s$),$ so we can think of player$$

B as simply minimizing $.$

In this problem, you will consider the non$-$zero$-$sum generalization, in which the sum of the two

players' utilities is not necessarily zero. The leaf utilities are now written as pairs $(,).$ In this$$

generalized setting, A seeks to maximize $,$ the first component, while B seeks to maximize$$

$,$ the second component.

Consider the non$-$zero$-$sum game tree below. Note that left$-$pointing triangles $($such as the root

of the tree$)$ correspond to player A$,$ who maximizes the first component of the utility pair,

whereas right$-$pointing triangles $($nodes on the second layer$)$ correspond to player B$,$ who

maximizes the second component of the utility pair.