邓小铁_watermark.pdf

1、PreliminariesNash Equilibrium Approximator for One GameNash Equilibrium Function ApproximatorSummaryProvably Bound of Nash EquilibriumApproximatorXiaotie Deng Peking University2023.11.24based onZhaohua Chen,Xiaotie Deng,Wenhan Huang,Hanyu Li,Yuhao Li:On tightness of Tsaknakis-Spirakisdescent methods

2、 for approximate Nash equilibria.Inf.Comput.293:105046(2023)Zhijian Duan,Wenhan Huang,Dinghuai Zhang,Yali Du,Jun Wang,Yaodong Yang,Xiaotie Deng:Is NashEquilibrium Approximator Learnable?AAMAS 2023:233-241Xiaotie Deng Peking UniversityProvably Bound of Nash Equilibrium ApproximatorPreliminariesNash E

3、quilibrium Approximator for One GameNash Equilibrium Function ApproximatorSummary1Preliminaries2Nash Equilibrium Approximator for One GameLower Bound and Upper Bound ResultsTS AlgorithmTight InstancesTightness of DFM Algorithm3Nash Equilibrium Function ApproximatorNash Equilibrium Function Approxima

4、torApplicationGeneralization Bound4SummaryXiaotie Deng Peking UniversityProvably Bound of Nash Equilibrium ApproximatorPreliminariesNash Equilibrium Approximator for One GameNash Equilibrium Function ApproximatorSummaryFinite Normal-Form GamesIn a finite normal-form game,there are several players.Ea

5、ch player has a set of pure strategies.Their joint choices,called their strategy profiles,determine a payoff function for each player.At a play,each player chooses a mixed(i.e.,randomized)strategy,simultaneously and without communication.The goal of each player is to maximize its expected payoff.Xia

6、otie Deng Peking UniversityProvably Bound of Nash Equilibrium ApproximatorPreliminariesNash Equilibrium Approximator for One GameNash Equilibrium Function ApproximatorSummaryNash Equilibrium(NE)Nash equilibrium:a strategy profile that every player cangain no extra payoff by unilterally deviating fro