Computing the communication costs of item allocation
| Title: | Computing the communication costs of item allocation |
| Author: |
Rauenbusch, Timothy W.; Grosz, Barbara; Shieber, Stuart
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: |
rauenbusch-icaps05.pdf (109.6Kb; PDF) 
|
| 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: | http://www.ai.sri.com/~nysmith/organizing/icaps05-workshop/ |
| Terms of Use: | This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:2094440 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5128]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
