An approximation algorithm with additive error for extensive-form, pure Stackelberg games with a chance player

Abstract

Substantial work has gone into finding techniques for solving real-world sized Nash games. Stackelberg Equilibria is another important solution concept for game theory models relevant to Computer Science, but much less progress has been made for solving very large Stackelberg games. This thesis is a step in that direction, presenting an algorithm which can find an OPT −ǫ approximate solution to the NP-Hard problem of perfect information, extensive-form, pure-strategy Stackelberg games with chance nodes in O(bǫ−2|V |); where b is the maximum branching factor of the game tree and |V | is the number of nodes in the tree. ǫ-Reachability is compared both theoretically and through simulations to a previous folly polynomial approximation algorithm, which we’ll refer to as FPTAS. FPTAS runs in O(b(|h∅| ǫ )2)|V |), where |h∅| is the height of the game tree. In simulations, this extra |h∅| factor proves an extremely limiting variable in relation to the run-time of ǫ-Reachability for even moderate values of |h∅|. This is likely to prevent FPTAS from being feasible on tall game trees - a likely feature of real-world extensive-form games. As both algorithms are linear in non-chance and quadratic in chance nodes, they both are sensitive to the frequency of chance nodes. Again, though, FPTAS’s dependence on |h∅| is likely to cause its run-time to grow much more quickly than ǫ-Reachability as the proportion of chance nodes increases.