Robust Multi-unit Auction Protocol against False-name Bids
William E. Walsh, Makoto Yokoo, Katsutoshi Hirayama, and Michael P. Wellman
17th International Joint Conference on Artificial Intelligence (IJCAI-2001), 2001.


We describe two market-inspired approaches to propositional satisfiability. Whereas a previous market-inspired approach exhibited extremely slow performance, we find that variations on the pricing method with a simplified market structure can improve performance significantly. We compare the performance of the new protocols with the previous market protocol and with the distributed breakout algorithm on benchmark 3-SAT problems. We identify a tradeoff between performance and economic realism in the new market protocols, and a tradeoff between performance and the degree of decentralization between the new market protocols and distributed breakout. We also conduct informal and experimental analyses to gain insight into the operation of price-guided search.