WE Walsh, M Yokoo, K Hirayama, and MP Wellman
Artificial Intelligence, 144:125–156, 2003.
Copyright © 2003 Published by Elsevier Science Inc. All rights reserved.
Abstract
We describe three market-inspired approaches to propositional satisfiability. The first is based on a formulation of satisfiability as production on a supply chain, where producers of particular variable assignments must acquire licenses to fail to satisfy particular clauses. Experiments show that although this general supply-chain protocol can converge to market allocations corresponding to satisfiable truth assignments, it is impractically slow. We find that a simplified market structure and a variation on the pricing method can improve performance significantly. We compare the performance of the three market-based protocols with distributed breakout algorithm and GSAT on benchmark 3-SAT problems. We identify a tradeoff between performance and economic realism in the market protocols, and a tradeoff between performance and the degree of decentralization between the market protocols and distributed breakout. We also conduct informal and experimental analyses to gain insight into the operation of price-guided search.
Revised and extended version combining material from two prior conference papers
- MarketSAT: An extremely decentralized (but really slow) algorithm for propositional satisfiability (WE Walsh and MP Wellman). In Seventeenth National Conference on Artificial Intelligence, pages 303–309, August 200
- On market-inspired approaches to propositional satisfiability (WE Walsh, M Yokoo, K Hirayama, and MP Wellman). In Seventeenth International Joint Conference on Artificial Intelligence, pages 1152–1158, August 2001.
