TY - JOUR
T1 - An LP approach for solving two-player zero-sum repeated Bayesian games
AU - Li, Lichun
AU - Langbort, Cedric
AU - Shamma, Jeff
N1 - Funding Information:
Manuscript received February 19, 2018; revised August 3, 2018; accepted November 20, 2018. Date of publication December 7, 2018; date of current version August 28, 2019. This work was supported in part by the NSF project #504958 and in part by the AFOSR/MURI project #FA9550-10-1-0573. Recommended by Associate Editor H. Sandberg. (Corresponding author: Lichun Li.) L. Li is with the FAMU-FSU College of Engineering, Tallahassee, FL 32311 USA (e-mail:,lichunli@eng.famu.fsu.edu).
Funding Information:
This work was supported in part by the NSF project #504958 and in part by the AFOSR/MURI project #FA9550-10-1-0573.
Publisher Copyright:
© 2019 Institute of Electrical and Electronics Engineers Inc.. All rights reserved.
PY - 2019/9
Y1 - 2019/9
N2 - This paper studies two-player zero-sum repeated Bayesian games in which every player has a private type that is unknown to the other player, and the initial probability of the type of every player is publicly known. The types of players are independently chosen according to the initial probabilities, and are kept the same all through the game. At every stage, players simultaneously choose actions, and announce their actions publicly. For finite horizon cases, an explicit linear program is provided to compute players’ security strategies. Moreover, this paper shows that a player’s sufficient statistics, which is independent of the strategy of the other player, consists of the belief over the player’s own type, the regret over the other player’s type, and the stage. Explicit linear programs, whose size is linear in the size of the game tree, are provided to compute the initial regrets, and the security strategies that only depends on the sufficient statistics. For discounted cases, following the same idea in the finite horizon, this paper shows that a player’s sufficient statistics consists of the belief of the player’s own type and the antidiscounted regret with respect to the other player’s type. Besides, an approximated security strategy depending on the sufficient statistics is provided, and an explicit linear program to compute the approximated security strategy is given. This paper also obtains a bound on the performance difference between the approximated security strategy and the security strategy, and shows that the bound converges to 0 exponentially fast.
AB - This paper studies two-player zero-sum repeated Bayesian games in which every player has a private type that is unknown to the other player, and the initial probability of the type of every player is publicly known. The types of players are independently chosen according to the initial probabilities, and are kept the same all through the game. At every stage, players simultaneously choose actions, and announce their actions publicly. For finite horizon cases, an explicit linear program is provided to compute players’ security strategies. Moreover, this paper shows that a player’s sufficient statistics, which is independent of the strategy of the other player, consists of the belief over the player’s own type, the regret over the other player’s type, and the stage. Explicit linear programs, whose size is linear in the size of the game tree, are provided to compute the initial regrets, and the security strategies that only depends on the sufficient statistics. For discounted cases, following the same idea in the finite horizon, this paper shows that a player’s sufficient statistics consists of the belief of the player’s own type and the antidiscounted regret with respect to the other player’s type. Besides, an approximated security strategy depending on the sufficient statistics is provided, and an explicit linear program to compute the approximated security strategy is given. This paper also obtains a bound on the performance difference between the approximated security strategy and the security strategy, and shows that the bound converges to 0 exponentially fast.
KW - Bayesian game
KW - Linear programming optimization
UR - http://www.scopus.com/inward/record.url?scp=85058176147&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85058176147&partnerID=8YFLogxK
U2 - 10.1109/TAC.2018.2885644
DO - 10.1109/TAC.2018.2885644
M3 - Article
AN - SCOPUS:85058176147
SN - 0018-9286
VL - 64
SP - 3716
EP - 3731
JO - IRE Transactions on Automatic Control
JF - IRE Transactions on Automatic Control
IS - 9
M1 - 8567999
ER -