发帖
雷达卡
摘要翻译：
最优性的概念自然地出现在应用数学和计算机科学的许多与决策有关的领域。在这里，我们将这个概念放在三种形式化的上下文中考虑，这三种形式化用于多智能体系统推理的不同目的：策略博弈、CP-网和软约束。为了联系这些形式中的最优性概念，我们引入了对战略博弈概念的自然定性修改。然后我们证明了CP-网的最优结果正是这类对策的纳什均衡。这使得我们可以使用博弈论的技术来搜索CP网的最优结果，反之亦然，可以使用为CP网开发的技术来搜索所考虑的博弈的纳什均衡。然后，我们将软约束领域中使用的最优性概念与策略博弈的一个推广，称为图形博弈中使用的最优性概念联系起来。特别地，我们证明了对于一类包含加权约束的自然软约束，每个最优解既是Nash均衡又是Pareto有效的联合策略。对于另一个方向的自然映射，我们证明了Pareto有效联合策略与软约束的最优解是一致的。
---
英文标题：
《Comparing the notions of optimality in CP-nets, strategic games and soft
constraints》
---
作者：
Krzysztof R. Apt, Francesca Rossi, Kristen Brent Venable
---
最新提交年份：
2008
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science 计算机科学
二级分类：Computer Science and Game Theory 计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
---
英文摘要：
The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints.
---
PDF链接：
https://arxiv.org/pdf/0711.2909
京公网安备 11010802022788号
