摘要翻译:
在Agent之间分配稀少的资源以使全局效用最大化,通常在计算上是有挑战性的。本文研究了资源使Agent在随机环境中执行行为的问题,将其建模为马尔可夫决策过程(MDPs),从而将资源束的值定义为给定这些资源时可实现的最优MDP策略的期望值。提出了一种同时解决资源分配和策略优化问题的算法。这使得我们可以避免显式地在许多资源包上表示实用程序,从而导致计算复杂性的大幅(通常是指数级)降低。然后,我们将该算法应用于自利代理的环境中,设计了一个用于资源分配的组合拍卖。我们通过表明它可以在几分钟内最优地解决一个简单的组合资源分配技术需要代理枚举多达2100个资源束和拍卖者解决一个NP完全问题的问题,从而证明了我们的方法的有效性。
---
英文标题:
《Resource Allocation Among Agents with MDP-Induced Preferences》
---
作者:
D. A. Dolgov, E. H. Durfee
---
最新提交年份:
2011
---
分类信息:
一级分类:Computer Science 计算机科学
二级分类:Multiagent Systems 多智能体系统
分类描述:Covers multiagent systems, distributed artificial intelligence, intelligent agents, coordinated interactions. and practical applications. Roughly covers ACM Subject Class I.2.11.
涵盖多Agent系统、分布式人工智能、智能Agent、协调交互。和实际应用。大致涵盖ACM科目I.2.11类。
--
一级分类: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中的材料。
--
---
英文摘要:
Allocating scarce resources among agents to maximize global utility is, in general, computationally challenging. We focus on problems where resources enable agents to execute actions in stochastic environments, modeled as Markov decision processes (MDPs), such that the value of a resource bundle is defined as the expected value of the optimal MDP policy realizable given these resources. We present an algorithm that simultaneously solves the resource-allocation and the policy-optimization problems. This allows us to avoid explicitly representing utilities over exponentially many resource bundles, leading to drastic (often exponential) reductions in computational complexity. We then use this algorithm in the context of self-interested agents to design a combinatorial auction for allocating resources. We empirically demonstrate the effectiveness of our approach by showing that it can, in minutes, optimally solve problems for which a straightforward combinatorial resource-allocation technique would require the agents to enumerate up to 2^100 resource bundles and the auctioneer to solve an NP-complete problem with an input of that size.
---
PDF链接:
https://arxiv.org/pdf/1110.2767