Suppose that an @math -simplex is partitioned into @math convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance @math from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant @math uses @math queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant @math uses @math queries. We show via Kakutani's fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies. We also partially extend our results to games with multiple players, establishing further query complexity bounds for computing approximate well-supported equilibria in this setting.
A basic model of commitment is to convert a game in strategic form into a “leadership game” where one player commits to a strategy to which the other player chooses a best response, with payoffs as in the original game. This paper studies subgame perfect equilibria of such leadership games for the mixed extension of a finite game, where the leader commits to a mixed strategy. In a generic two-player game, the leader payoff is unique and at least as large as any Nash payoff in the original simultaneous game. In non-generic two-player games, which are completely analyzed, the leader payoffs may form an interval, which as a set of payoffs is never worse than the Nash payoffs for the player who has the commitment power. Furthermore, the set of payoffs to the leader is also at least as good as the set of correlated equilibrium payoffs. These observations no longer hold in leadership games with three or more players. The possible payoffs to the follower are shown to be arbitrary compared to the simultaneous game or the game where the players switch their roles of leader and follower. Curiously, the follower payoff is not so arbitrary in typical We study the performance of Fictitious Play, when used as a heuristic for finding an approximate Nash equilibrium of a two-player game. We exhibit a class of two-player games having payoffs in the range [0, 1] that show that Fictitious Play fails to find a solution having an additive approximation guarantee significantly better than 1 2. Our construction shows that for n × n games, in the worst case both players may perpetually have mixed strategies whose payoffs fall short of the best response by an additive quantity 1 2-O(1 n1-δ) for arbitrarily small δ. We also show an essentially matching upper bound of 1 2 - O(1 n). Fictitious play is a natural dynamic for equilibrium play in zero-sum games, proposed by Brown [6], and shown to converge by Robinson [33]. Samuel Karlin conjectured in 1959 that fictitious play converges at rate O(t -- 1 2) with respect to the number of steps t. We disprove this conjecture by showing that, when the payoff matrix of the row player is the n × n identity matrix, fictitious play may converge (for some tie-breaking) at rate as slow as a#x3A9;(t -- 1 n). In economics, most noncooperative game theory has focused on equilibrium in games, especially Nash equilibrium and its refinements. The traditional explanation for when and why equilibrium arises is that it results from analysis and introspection by the players in a situation where the rules of the game, the rationality of the players, and the players' payoff functions are all common knowledge. Both conceptually and empirically, this theory has many problems. In The Theory of Learning in Games Drew Fudenberg and David Levine develop an alternative explanation that equilibrium arises as the long-run outcome of a process in which less than fully rational players grope for optimality over time. The models they explore provide a foundation for equilibrium theory and suggest useful ways for economists to evaluate and modify traditional equilibrium concepts. Abstract : In the paper, demonstration is made of the validity of an iterative procedure suggested by George W. Brown for a two-person game. This method corresponds to each player choosing in turn the best pure strategy against the accumulated mixed strategy of his opponent up to then. 