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.
- T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, 1991. Google ScholarDigital Library
- 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.Google Scholar
- T. W. Rauenbusch. Measuring Information Transmission for Team Decision Making. PhD thesis, Harvard University, 2004. Google ScholarDigital Library
- C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27, 1948.Google Scholar
- Y. Shoham and M. Tennenholtz. Rational computation and the communication complexity of auctions. Games and Economic Behavior, 35(1--2):197--211, 2001.Google Scholar
Index Terms
- Computing the communication costs of item allocation
Recommendations
Weighted proportional allocation
Performance evaluation reviewWe consider a weighted proportional allocation of resources that allows providers to discriminate usage of resources by users. This framework is a generalization of well-known proportional allocation by accommodating allocation of resources proportional ...
Efficiency and price discovery in multi-item auctions
Distributed multi-item auctions offer great opportunities for integrating fragmented online auction markets into larger markets with more efficient outcomes. We extend the theory of multiitem ascending auctions in a multi-unit demand scenario. We show ...
The Impact of Discrete Bidding and Bidder Aggressiveness on Sellers' Strategies in Open English Auctions: Reserves and Covert Shilling
In practice, the rules in most open English auctions require participants to raise bids by a sizeable, discrete amount. Furthermore, some bidders are typically more aggressive in seeking to become the "current bidder" during competitive bidding. Most ...
Comments