Title: On Equilibrium Computation in Biased Games with Quadratic Penalties.
Abstract: Biased games were recently introduced by Caragiannis et al. as an extension of strategic-form games that can represent psychological biases of players towards certain pure strategies. They showed that for any number of players, and for a wide range of penalty functions that penalize players for deviating from their biases, a biased game admits a mixed-strategy equilibrium. We initiate the study of algorithms for finding approximate equilibria in two-player biased games. This problem is at least as hard as the analogous problem for bimatrix games, which has received much attention. For a natural subclass of two-player games with $L^2_2$ penalty functions, we characterize best responses and show how they can be computed by a strongly polynomial combinatorial algorithm. Building on this, we design the first polynomial-time algorithm that achieves a non-trivial approximation guarantee for these games. Furthermore, we study the existence of pure equilibria and we prove that games with bias functions in this class can have at most one pure equilibrium.
Publication Year: 2015
Publication Date: 2015-09-07
Language: en
Type: preprint
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot