HWK 2

6.

a) Each player chooses the outcome the maximizes her payoff. The payoff at the top of the tree is (1 2 3). Most people correctly solved this.

b) This was an open-ended question. Some thoughts on it are given here:
One thing to notice is that since this game is not 0-sum (= a game in which when one wins the other loses by an equal amount), players do not play in order to hurt their opponents, but only to maximize their own payoffs; this could very well cause them to help rather than hurt the other player's scores. This is also the reason why to solve part a) you use a max-max-max type of algorithm. The minimax is a special case of this since min moves happen because the min player wishes to maximize her own outcome (which is the negation of the max player's score). For the same reason there is no real notion of one player winning. In the same way the player will not try to make the other "lose" unless this is to her advantage (to maximize her payoff).
If players 0 and 1 or players 1 and 2 cooperate then the payoff they can gain is (5 4 5). This should be obvious in the first case. But it also is true for the second case (1 and 2 allying if player 0 is aware of this), because then he would wish to take the right branch given that player 1 will then choose the branch that leads to (5 4 5) in order to maximize the payoffs of both her and her ally.
This leads to the question of what should each player in an alliance maximize. There can be a lot of answers to this. The simplest one is that assuming that payoffs are transferable it should maximize the sum of the payoffs to its alliance.
One this that should be noted is that (5 4 5) is a "pareto efficient"; this means that we can't get another set of payoffs in which the payoff of at least one player is better than this and no player is made worse off! (1 2 3) is not. Also note that (5 4 5) is the outcome that mazimizes the sum of payoffs to all players...
The last thought that I would like to share is that unless we have some way of enforcing alliances it is highly unlikely that self-interested agents will want to really ally with other player in this setting. This is because no player will be sure that anyone who moves after him will cooperate. In fact it is not in the interest of the later moving players to cooperate (well unless this is the best they can do for themselves); this is because the last player will only be interest in maximizing his profit and by using an inductive argument we can prove that so will everyone else! Therefore if an alliance is formed the later moving players will "cheat" on their allies.

7.

a) Since the ES player has identified a winning move and he only cares about winning (not by how much), he will not have a reason to choose another move; this move guarantees victory no matter what the other player does.

b) In this case there might be a case in which you want to take a path other than the one the min-max algorithm identifies. But this depends on a lot of factors. If there are several paths that guarantee a draw perhaps one of them is more "promising" (the min-max algorithm will usually only return one of them). By promising I mean a path in which there are a lot of opportunities for the other player to make a mistake. There are also some cases in which you might wish to take a path which does not guarantee you a draw in case there are a lot of traps for the enemy. This is however quite rare indeed: it might happen in cases that a draw is not much preferable compared to a loss and only if the expectation of losing is low anyway. The latter might occur for example if there is only a very specific path that would cause you to lose and it is very difficult (and unlikely) for the opponent to find it. In this setting the problem states that ES wants to win, so we can reasonably assume that draw has a low valuation and therefore this would induce ES to risk and indeed take the more "promising" and riskier path. An example is taking a move that leads to a subtree from which only few nodes are losing (so it would be difficult for the depth limited player to find them) and gives a lot of opportunities for winning.

8.

a) 4.3 is the ratio at which random 3-SAT formulas are the hardest. So 10 would be much easier. The reason why 10 is easier is because instances are so constrained that inconsistencies are discovered quite fast and thus almost all the instances are proven unsatisfiable quite fast. At 4.3 the problem is critically constrained, 50% approximately of the instances are satisfiable. This is harder, since inconsistencies are difficult to discover and if a satisfying assignment does exist it will be hard to find.

b) This was an open-ended question and several answer were accepted. But overall you can't say much about the hardness. The instance is not even k-SAT (not necessarily), so the hardness results for k-SAT do not really apply here!