On Market-Inspired Approaches to Propositional Satisfiability
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 1152-1159.
Abstract
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.
@inproceedings{ijcai2001p153,
title = {On Market-Inspired Approaches to Propositional Satisfiability},
author = {Walsh, William E. and Yokoo, Makoto and Hirayama, Katsutoshi and Wellman, Michael P.},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {1152--1159},
year = {2001},
url = {https://ijcai.org/proceedings/2001/153},
}
TY - CPAPER TI - On Market-Inspired Approaches to Propositional Satisfiability AU - Walsh, William E. AU - Yokoo, Makoto AU - Hirayama, Katsutoshi AU - Wellman, Michael P. T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 1152 EP - 1159 UR - https://ijcai.org/proceedings/2001/153 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
