Algorithmic Excursions : Topics in Computer Science II Spring 2016 Week 11 : Zero-Sum Games , Learning Theory and Boosting


We show how the general algorithm presented in the last lecture can be used to approximately solve zero-sum games. Let A be a payoff matrix of a finite 2-player zero-sum game, with n rows. When the row player plays strategy i and the column player plays strategy j, then the payoff to the column player is A(i, j). We assume A(i, j) ∈ [0, 1]. If the row player chooses strategy i from a distribution p over the rows, then the expected payoff to the column player for choosing a strategy j is


    6 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)