Manipulations in Two-Agent Sequential Allocation with Random Sequences
Manipulations in Two-Agent Sequential Allocation with Random Sequences
复制标题
DOI：
--
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Yuto Tominaga;Taiki Todo;M. Yokoo
中科院分区：
文献类型：
--
作者：
Yuto Tominaga;Taiki Todo;M. Yokoo
顺序分配是将不可分割的项目以分散的方式分配给智能体的最基本模型之一，在该模型中，智能体根据预定义的智能体优先级顺序（序列）从剩余的项目中依次选择自己喜欢的项目。近年来，关于智能体操作的算法问题也得到了研究，例如在给定的附加效用函数下，验证给定的一束物品是否可实现以及最大化个人效用的计算复杂性。在本文中，我们考虑了一个稍微改进的模型，该模型将选择过程分成几轮，每个智能体在每轮中只获得一个项目，并且每轮的顺序是均匀随机确定的。很自然地，即使在两个代理的情况下，也很难找到一个有利可图的操作，因为由于随机化，操纵者必须考虑相对于轮数的指数级多的可能序列。然而，令我们惊讶的是，无需对指数衰减的效用进行任何探索，就可以计算出最优操作。此外，对于一般的加法实用程序，虽然需要一些探索，但它仍然可以在多项式时间内完成，相对于轮数。
Sequential allocation is one of the most fundamental models for allocating indivisible items to agents in a decentralized manner, in which agents sequentially pick their favorite items among the remainder based on a pre-defined priority ordering of agents (a sequence). In recent years, algorithmic issues about agents' manipulations have also been investigated, such as the computational complexity of verifying whether a given bundle of items is achievable and maximizing one's utility under a given additive utility function. In this paper we consider a slightly modified model, where the selection process is divided into rounds, each agent obtains exactly one item in each round, and the sequence per round is determined uniformly at random. It is natural to expect that finding a profitable manipulation is difficult even for the case of two agents, since a manipulator must consider exponentially many possible sequences with respect to the number of rounds due to randomization. To our surprise, however, an optimal manipulation can be computed without any exploration for exponentially decaying utilities. Furthermore, for general additive utilities, although some exploration is required, it can still be done in polynomial time with respect to the number of rounds.