However, what it you don't want to trust, or can't afford to pay a centralized auctioneer? We are studying automated incentive-compabile negotiation protocols for distributed resource allocations. I know this is a mouthfull but all it is saying is that we are developing algorithms that automated agents can use to negotiate with each other and solve these type of problems. Think of it as moving all buy/sell transaction to the web (we are nearly there) and then using software to decide who to buy what from and at what price. We can show that this will lead to more efficient solutions, that is, everybody wins.
Anyway, our latest paper detailing our efforts is
- Benito Mendoza and José M. Vidal. Approximate Bidding Algorithms for a Distributed Combinatorial Auction (Short Paper). Padgham and Parkes and Müller and Parsons ed.In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, May; 2008.
Distributed allocation and multiagent coordination problems can be solved through combinatorial auctions (CAs). However, most of the existing winner determination algorithms (WDAs) for CAs are centralized. The PAUSE auction is one of a few efforts to release the auctioneer from having to do all the work. The pausebid bidding algorithm generates myopically-optimal bids for agents in a PAUSE auction but its running time is exponential on the number of bids. We present new approximate bidding algorithms that not only run in linear time but also increase the utility of the bidders as result of small decrement in revenue.
Check it out, approximation mechanism let ut achieve 1000-fold speedups at only a small cost in utility.