Inverse Game Theory: Learning Utilities in Succinct Games
Inverse Game Theory: Learning Utilities in Succinct Games
复制标题
逆博弈论：简洁博弈中的学习实用工具
DOI：
10.1007/978-3-662-48995-6_30
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Okke Schrijvers
中科院分区：
文献类型：
--
作者：
Volodymyr Kuleshov;Okke Schrijvers
博弈论的核心问题之一是预测代理人的行为。在这里，我们研究这个问题的逆：给定代理人的均衡行为，什么是可能的效用，激励这种行为？我们认为这个问题在任意正规形式的游戏，其中的效用可以表示为一个小数目的参数，如在图形，拥塞，网络设计游戏。在所有这些设置中，我们展示了如何有效地，即在多项式时间内，确定与给定的相关均衡相一致的效用。然而，推断效用和结构元素，图形游戏中的图形一般是NP难的。从理论的角度来看，我们的研究结果表明，合理化的平衡是计算比计算它更容易，从实践的角度来看，从业者可以使用我们的算法来验证行为模型。
One of the central questions in game theory deals with predicting the behavior of an agent. Here, we study the inverse of this problem: given the agents' equilibrium behavior, what are possible utilities that motivate this behavior? We consider this problem in arbitrary normal-form games in which the utilities can be represented by a small number of parameters, such as in graphical, congestion, and network design games. In all such settings, we show how to efficiently, i.e. in polynomial time, determine utilities consistent with a given correlated equilibrium. However, inferring both utilities and structural elements e.g., the graph within a graphical game is in general NP-hard. From a theoretical perspective our results show that rationalizing an equilibrium is computationally easier than computing it; from a practical perspective a practitioner can use our algorithms to validate behavioral models.