Expected Utility Approximation on Large Symmetric Simulation-based Games
Jack Yang, Bryce Wiedenbeck
As a discipline that adopts mathematical modeling to study decision making, game theory has wide applications across the field of social sciences. A game in game theory consists of a set of players, a set of strategies for each player, and a utility function that maps the strategies chosen by the players to their payoffs. Often times, analyzing a game requires finding the equilibria, which specifies how the game will be played. Although there exists algorithms for finding equilibria, no good methods have been developed to efficiently analyze large games. As the size of a game grows exponentially to the number of players and strategies, the storage and computation needed for analyzing large games with existing methods are astronomical. Our research seeks to provide a method to efficiently analyze large games. The two main methods we looked at were simplifying storage and computation, and reducing large games to similarly-behaving smaller games.
Some games have innate properties that allow them to be efficiently stored and analyzed. The property that every player have the same payoff matrix is called anonymity. The property that only some strategies affect each others' payoffs is called context-specific independence. One well-studied game representation that exploits both of these two properties to simplify storage and computation is the action graph game (AGG) representation. We devised an algorithm for deviation payoffs computation that yielded exponential saving on computation for a specific subset of AGGs. The algorithm took advantage of certain restrictions we applied on original AGGs. Though the restricted AGGs can only represent a subclass of all games, it still retained a satisfactory expressive power.
Another method used in the analysis of large games is game reduction, which reduces large games to smaller ones to perform analyses on. State-of-the-art game reduction method achieves its goal by grouping players and treating groups of players as individuals. However, this implies significant difficulty in capturing individual deviations. It also requires access to a number of specific payoffs to construct the reduced game. As a potential method of game reduction, and a solution to problems of the existing methods, we attempted player reduction by using Gaussian process reduction, a machine learning technique, to learn a compact functional representation for a given game. Experimented on randomly generated congestion games with quadratic cost functions, the learning method produced more accurate deviation payoff estimations than existing methods. It also handles noises elegantly, and only needs a small proportion of sample payoffs to generalize predictions from.
Literature Cited:
[1] A. Jiang, K. Leyton-Brown, N. Bhat. "Action-graph games." Games and Economic Behavior 71, no. 1, pp. 141-173, 2011.
[2] B. Wiedenbeck, M. P. Wellman. "Scaling simulation-based game analysis through deviation-preserving reduction", in Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, 2012.
[3] B. Wiedenbeck, M. P. Wellman. "Learning Payoffs in Large Symmetric Games." In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015.
