A Simple Adaptive Procedure Converging to Forgiving Correlated Equilibria

<a href="https://embed.stanford.edu/iframe/?url=https%3A%2F%2Fpurl.stanford.edu%2Fhk596cg1085" class="su-underline">Show Content</a>

Abstract/Contents

Abstract: Simple adaptive procedures that converge to correlated equilibria are known to exist for normal form games (Hart and Mas-Colell 2000), but no such analogue exists for extensive-form games. Leveraging inspiration from Zinkevich et al. (2008), we show that any internal regret minimization procedure designed for normal-form games can be efficiently extended to finite extensive-form games of perfect recall. Our procedure converges to the set of forgiving correlated equilibria, a refinement of various other proposed extensions of the correlated equilibrium solution concept to extensive-form games (Forges 1986a; Forges 1986b; von Stengel and Forges 2008). In a forgiving correlated equilibrium, players receive move recommendations only upon reaching the relevant information set instead of all at once at the beginning of the game. Assuming all other players follow their recommendations, each player is incentivized to follow her recommendations regardless of whether she has done so at previous infosets. The resulting procedure is completely decentralized: players need neither knowledge of their opponents’ actions nor even a complete understanding of the game itself beyond their own payoffs and strategies.

Type of resource	text
Date created	June 11, 2020

Author	Hugh Zhang
Advisor	Gabriel Carroll

Subject	Department of Economics
Subject	game theory
Subject	correlated equilibria
Subject	extensive-form games
Subject	one-shot deviation principle
Subject	counterfactual regret minimization
Subject	no regret learning
Genre	Thesis

Related item	Title 2020 John G. Sobieski Award for Creative Thinking
Location	https://purl.stanford.edu/hk596cg1085

Use and reproduction: User agrees that, where applicable, content will not be used to identify or to otherwise infringe the privacy or confidentiality rights of individuals. Content distributed via the Stanford Digital Repository may be subject to additional license and use restrictions applied by the depositor.
License: This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).

Preferred Citation: Hugh Zhang. (2020). A Simple Adaptive Procedure Converging to Forgiving Correlated Equilibria. Stanford Digital Repository. Available at: https://purl.stanford.edu/hk596cg1085

Stanford University, Department of Economics, Honors Theses

Loading usage metrics...