Computing the communication costs of item allocation

DSpace/Manakin Repository

Computing the communication costs of item allocation

Citable link to this page


Title: Computing the communication costs of item allocation
Author: Rauenbusch, Timothy W.; Grosz, Barbara; Shieber, Stuart ORCID  0000-0002-7733-8195

Note: Order does not necessarily reflect citation order of authors.

Citation: Timothy W. Rauenbusch, Stuart M. Shieber, and Barbara J. Grosz. Computing the communication costs of item allocation. In Bradley J. Clement, editor, Proceedings of the ICAPS-05 Workshop on Planning and Scheduling, pages 15-21, Monterey, CA, June 6-10 2005.
Full Text & Related Files:
Abstract: Multiagent systems require techniques for effectively allocating resources or tasks to among agents in a group. Auctions are one method for structuring communication of agents’ private values for the resource or task to a central decision maker. Different auction methods vary in their communication requirements. This paper makes three contributions to the understanding the types of group decision making for which auctions are appropriate methods. First, it shows that entropy is the best measure of communication bandwidth used by an auction in messages bidders send and receive. Second, it presents a method for measuring bandwidth usage; the dialogue trees used for this computation are a new and compact representation of the probability distribution of every possible dialogue between two agents. Third, it presents new guidelines for choosing the best auction, guidelines which differ significantly from recommendations in prior work. The new guidelines are based on detailed analysis of the communication requirements of Sealed-bid, Dutch, Staged, Japanese, and Bisection auctions. In contradistinction to previous work, the guidelines show that the auction that minimizes bandwidth depends on both the number of bidders and the sample space from which bidders’ valuations are drawn.
Published Version:
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search