Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control
Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control
复制标题
DOI：
--
复制
发表时间：
2007-01
期刊：
影响因子：
--
通讯作者：
Sven Koenig;C. Tovey;Xiaoming Zheng;I. Sungur
中科院分区：
文献类型：
--
作者：
Sven Koenig;C. Tovey;Xiaoming Zheng;I. Sungur
我们研究了将任务分配给协作代理的类似拍卖的算法。为了降低顺序单品拍卖算法的团队成本，我们对其进行了推广，使其在每轮中分配多个额外的任务，从而增加了它们与组合拍卖算法的相似性。我们表明，对于每轮分配的给定数量的额外任务，每个代理每轮只需要提交恒定数量的投标，并且确定获胜者的运行时间在代理数量中是线性的。通信和赢家确定成本不依赖于任务的数量，因此可以扩展到小包大小的大量任务。然后，我们通过经验证明，对于具有容量约束的多代理路由问题，顺序捆绑投标单售（=单件）拍卖算法的团队成本可以大大小于没有捆绑的团队成本。
We study auction-like algorithms for the distributed allocation of tasks to cooperating agents. To reduce the team cost of sequential single-item auction algorithms, we generalize them to assign more than one additional task during each round, which increases their similarity to combinatorial auction algorithms. We show that, for a given number of additional tasks to be assigned during each round, every agent needs to submit only a constant number of bids per round and the runtime of winner determination is linear in the number of agents. The communication and winner determination costs do not depend on the number of tasks and thus scale to a large number of tasks for small bundle sizes. We then demonstrate empirically that the team cost of sequential bundle-bid single-sale (= single-item) auction algorithms can be substantially smaller than that without bundles for multi-agent routing problems with capacity constraints.