Optimal Rates for Feasible Payoff Set Estimation in Games
We study a setting in which two players play a (possibly approximate) Nash equilibrium of a bimatrix game, while a learner observes only their actions and has no knowledge of the equilibrium or the underlying game. A natural question is whether the learner can rationalize the observed behavior by inferring the players' payoff functions. Rather than producing a single payoff estimate, inverse game theory aims to identify the entire set of payoffs consistent with observed behavior, enabling downstream use in, e.g., counterfactual analysis and mechanism design across applications like auctions, pricing, and security games. We focus on the problem of estimating the set of feasible payoffs with high probability and up to precision $ε$ on the Hausdorff metric. We provide the first minimax-optimal rates for both exact and approximate equilibrium play, in zero-sum as well as general-sum games. Our results provide learning-theoretic foundations for set-valued payoff inference in multi-agent environments.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Characterizing the Feasible Payoff Set of OLG Repeated Games
We study the set of (stationary) feasible payoffs of overlapping generation repeated games that can be achieved by action sequences in which every generation of players plays the same sequence of action profiles. First, …
Asymptotic Value of Monitoring Structures in Stochastic Games
This paper studies how improved monitoring affects the limit equilibrium payoff set for stochastic games with imperfect public monitoring. We introduce a simple generalization of Blackwell garbling called weighted garbli…
Reactive learning strategies for iterated games
In an iterated game between two players, there is much interest in characterizing the set of feasible payoffs for both players when one player uses a fixed strategy and the other player is free to switch. Such characteri…
Optimal Private Payoff Manipulation against Commitment in Extensive-form Games
To take advantage of strategy commitment, a useful tactic of playing games, a leader must learn enough information about the follower's payoff function. However, this leaves the follower a chance to provide fake informat…
FormOptimally Deceiving a Learning Leader in Stackelberg Games
Recent results in the ML community have revealed that learning algorithms used to compute the optimal strategy for the leader to commit to in a Stackelberg game, are susceptible to manipulation by the follower. Such a le…