Files
Abstract
In game theory, we have three major categories of repeated games: repeated games with perfect monitoring, repeated games with imperfect public monitoring, and repeated games with imperfect private monitoring. Among them, repeated games with imperfect private monitoring are the hardest instances because players lack reliable information shared by all. If each player's action on the equilibrium path is given by an automaton with finite number of states, then the equilibrium in a repeated game with imperfect private monitoring is called a finite state equilibrium. Given k players, we apply the partially observable Markov decision process (POMDP) to a repeated game with imperfect private monitoring and analyze the complexity of verifying a finite state equilibrium. This framework is new and has significant applications in markets such as secret price cutting among firms.