Deposit schemes for incentivizing behavior in finite games of perfect information

We propose a model for finite games with deposit schemes and study how they can be instantiated to incentivize an intended behavior. Doing so is trivial if the deposit scheme can observe all actions taken in the game, as this allows it to simply keep the deposit for a party who does not play the intended strategy. Instead, we consider an abstraction where the deposit scheme is only allowed to probabilistically infer information about what happened during the execution of the game. We consider deposit schemes that are allowed to punish parties by withholding parts of their deposit, and compensate the other players with what is left over. We show that deposit schemes can be used to implement any set of utilities if and only if it is able to essentially infer all information about what happened in the game. We give a definition of game-theoretic security that generalizes subgame perfection for finite games of perfect information by quantifying how much utility a dishonest party loses by deviating from the equilibrium. We show how finding an optimal deposit scheme that ensures game-theoretic security, or showing no such scheme exists, can be stated as a linear program and solved using standard methods. The deposit schemes outputted are optimal in the sense that the size of the largest deposit is minimal. We state some additional desirable properties of deposit scheme and discuss various tradeoffs when deploying such systems in practice. We prove a lower bound on the size of the deposits, showing that the largest deposit must be linear in the security parameter.