...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical logic quarterly: MLQ >A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
【24h】

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications

机译：一类可表达的边际贡献网及其应用

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets (MC-nets), introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC-nets are a rule-based formalism, in which rules take the form pattern -> value, where "pattern" is a Boolean condition over agents, and "value" is a numeric value. Ieong and Shoham showed that, for a class of what we will call "basic" MC-nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC-net rules. We present read-once MC-nets, a new class of MC-nets that is provably more compact than basic MC-nets, while retaining the attractive computational properties of basic MC-nets. We show how the techniques we develop for read-once MC-nets can be applied to other domains, in particular, computing solution concepts in network flow games on series-parallel networks.
机译：从计算机科学的角度来看，联盟游戏提出了许多重要问题，其中的关键是如何紧凑地表示这种游戏，以及如何有效地计算采用这种表示的解决方案概念。由Ieong和Shoham引入的边际贡献网（MC-nets）是联盟游戏中最简单，最具影响力的代表方案之一。 MC-net是一种基于规则的形式主义，其中规则采用模式->值的形式，其中“模式”是代理的布尔条件，而“值”是数字值。 Ieong和Shoham指出，对于一类我们称为“基本” MC网络的系统，其中模式被约束为文字的结合，边际贡献网络允许轻松地计算诸如Shapley值之类的解决方案概念。但是，存在非常自然的联盟游戏类别，需要成倍数量的此类基本MC-net规则。我们提出了一次读取型MC-网络，这是一类新型的MC-网络，被证明比基础MC-网络更紧凑，同时保留了基础MC-网络的吸引人的计算特性。我们将展示我们为一次读取的MC-net开发的技术如何可以应用于其他领域，尤其是在串行-并行网络上的网络流游戏中的计算解决方案概念。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号