Lukasiewicz Games A Logic-Based Approach to Quantitative Strategic Interactions
Lukasiewicz Games A Logic-Based Approach to Quantitative Strategic Interactions
复制标题
Lukasiewicz Games 基于逻辑的定量战略互动方法
DOI：
10.1145/2783436
复制
发表时间：
2015
影响因子：
0.5
通讯作者：
Marchioni E
中科院分区：
文献类型：
--
作者：
Marchioni E
布尔博弈为研究多智能体相互作用提供了一个简单、紧凑且在理论上有吸引力的抽象模型，在这种情况下，参与者将采取战略性行动，试图实现个人目标。然而，对布尔博弈的一个标准批评是，布尔目标引发的偏好关系的严格二分法不可避免地淡化了此类战略互动的性质：玩家被假设对满足其目标的所有结果无关紧要，而对所有不满足其目标的结果无动于衷。虽然已经提出了各种建议来克服这一限制，但其中许多建议要求在游戏中包含非逻辑结构，以捕捉非二分偏好。在本文中，我们介绍了Łukasiewicz游戏，它通过允许使用Łukasiewicz逻辑指定目标来克服这一限制。通过将目标表示为Łukasiewicz逻辑的公式，我们可以为玩家表示一类比使用经典布尔逻辑可能的更丰富的效用函数：我们可以表示在[0，1]n上具有有理系数的每个连续分段线性多项式函数以及它们在{0，1/k，…上的有限值限制，(k−1)/k，1}n，从而得到了纯逻辑框架下非二分偏好结构的表示。在介绍了Łukasiewicz游戏的形式框架后，我们给出了一些详细的工作实例来说明该框架，并研究了它们的一些理论性质。特别地，我们给出了有限和无限Ł-ukasiewicz对策的纳什均衡存在性的一个逻辑刻画。最后，我们简要讨论了计算复杂性的问题。
Boolean games provide a simple, compact, and theoretically attractive abstract model for studying multiagent interactions in settings where players will act strategically in an attempt to achieve individual goals. A standard critique of Boolean games, however, is that the strictly dichotomous nature of the preference relations induced by Boolean goals inevitably trivialises the nature of such strategic interactions: a player is assumed to be indifferent between all outcomes that satisfy her goal, and indifferent between all outcomes that do not satisfy her goal. While various proposals have been made to overcome this limitation, many of these proposals require the inclusion of nonlogical structures into games to capture nondichotomous preferences. In this article, we introduce Łukasiewicz games, which overcome this limitation by allowing goals to be specified usingŁukasiewicz logics. By expressing goals as formulae of Łukasiewicz logics, we can express a much richer class of utility functions for players than is possible using classical Boolean logic: we can express every continuous piecewise linear polynomial function with rational coefficients over [0, 1]nas well as their finite-valued restrictions over {0, 1/k, …, (k− 1)/k, 1}n. We thus obtain a representation of nondichotomous preference structures within a purely logical framework. After introducing the formal framework of Łukasiewicz games, we present a number of detailed worked examples to illustrate the framework, and then investigate some of their theoretical properties. In particular, we present a logical characterisation of the existence of Nash equilibria in finite and infinite Łukasiewicz games. We conclude by briefly discussing issues of computational complexity.