Title: | Multiagent Coordination Using a Distributed Combinatorial Auction |

Author: | José M. Vidal |

Book Tittle: | AAAI Workshop on Auction Mechanism for Robot Coordination |

Month: | July |

Year: | 2006 |

Poster: | Here |

Abstract: | Combinatorial auctions are a great way to represent and solve distributed allocation problems. Unfortunately, most of the winner determination solutions that exists are centralized. They require all agents to send their bids to a centralized auctioneer who then determines the winners. The PAUSE auction, in contrast, is an increasing-price combinatorial auction in which the problem of winner determination is naturally distributed amongst the bidders. Furthermore, the bidders' have an incentive to perform the required computations. But, until now, no bidding algorithm for the auction existed. We provide a bidding algorithm for agents in a PAUSE auction, the pausebid algorithm. It always returns the bid that maximizes the bidder's utility. In effect, pausebid is a the distributed counterpart to the existing centralized winner determination algorithms, from which we borrow several proven techniques. Our test results show that a system where all agents use pausebid finds the revenue-maximizing solution at least 95% of the time. Run time, as expected since this is an NP-complete problem, remains exponential on the number of items. |

Cited by 1

@InProceedings{vidal06a, author = {Jos\'{e} M. Vidal}, title = {Multiagent Coordination Using a Distributed Combinatorial Auction}, booktitle = {{AAAI} Workshop on Auction Mechanism for Robot Coordination}, year = 2006, month = {July}, abstract = { Combinatorial auctions are a great way to represent and solve distributed allocation problems. Unfortunately, most of the winner determination solutions that exists are centralized. They require all agents to send their bids to a centralized auctioneer who then determines the winners. The PAUSE auction, in contrast, is an increasing-price combinatorial auction in which the problem of winner determination is naturally distributed amongst the bidders. Furthermore, the bidders' have an incentive to perform the required computations. But, until now, no bidding algorithm for the auction existed. We provide a bidding algorithm for agents in a PAUSE auction, the pausebid algorithm. It always returns the bid that maximizes the bidder's utility. In effect, pausebid is a the distributed counterpart to the existing centralized winner determination algorithms, from which we borrow several proven techniques. Our test results show that a system where all agents use pausebid finds the revenue-maximizing solution at least 95\% of the time. Run time, as expected since this is an NP-complete problem, remains exponential on the number of items. }, cluster = {16414258313793794495}, url = {http://jmvidal.cse.sc.edu/papers/vidal06a.pdf}, poster = {http://jmvidal.cse.sc.edu/papers/vidal06a-poster.pdf}, keywords = {multiagent combinatorial auctions} }Last modified: Wed Mar 9 10:16:32 EST 2011