.png){kind=icon}
返回
Allocating Indivisible Objects With a Parallel Method Insensitive to Identities
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2017.2764093.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Sequential allocation is a decentralized mechanism for allocating indivisible objects to agents, in which agents sequentially pick their favorite objects among the remainder based on a pre-defined priority ordering of agents (a sequence). The problem of choosing the best sequence of agents to achieve the optimal social welfare has been investigated and conjectured to be NP-hard. We propose a simple parallel allocation protocol that is insensitive to agents' identities. In every round of the parallel allocation process, every agent asks for an object among those that remain, and every reported object will be allocated randomly to an agent reporting it. Supposing additive utilities and independence between the agents, we compare the average (and worst-case) social welfare achieved by a parallel protocol and a sequential protocol. Theoretical and empirical results show that parallel protocol outperforms a sequential protocol (even when the best sequence of agents is applied). We also show that under the parallel mechanism, some manipulation problems (e.g., finding a successful strategy for a target set and finding an optimal strategy under some scoring function) can be solved in polynomial time.
Keyword:
Distributed resource allocation
parallel protocol
social welfare
manipulation problem
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.6
论文数:
9.8W
被引数:
29.4W
机构
引用论文
A tractable multiple agents protocol and algorithm for resource allocation under price rigidities.png)
APPLIED INTELLIGENCE
APPLIED INTELLIGENCEIF3.5
PREAI
分享收藏 没有更多内容
没有更多内容