Computing the communication costs of item allocation

ABSTRACT

Multiagent systems require techniques for effectively allocating resources or tasks 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 work 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.

REFERENCES

• 1: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 2: E. Grigorieva, P. J.-J. Herings, R. Müller, and D. Vermeulen. The private value single item bisection auction. In METEOR Research Memoranda, number RM/02/035. Maastricht University, 2002.
• 3: Timothy William Rauenbusch , Barbara J. Grosz, Measuring information transmission for team decision making, 2004
• 4: C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27, 1948.
• 5: Y. Shoham and M. Tennenholtz. Rational computation and the communication complexity of auctions. Games and Economic Behavior, 35(1--2):197--211, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Design

Keywords:
auctions, communication, dialogue