درباره رویکرد بازارمحور از صدق پذیری گزاره ای

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.

Multiple agents must often engage in activities with complex, interrelated dependencies. These dependenciesmay arise from contention for limited resources, scheduling constraints, or direct dependencies of activity on the results of other agents’ activities. Often, such problems of choosing activities, allocating resources, determining schedules, and composing results from individual agents’ actions can be modeled as constraint satisfaction problems (CSPs). As members of the class of NP-complete problems, CSPs are widely considered to be intractable. Even the best algorithms for NP-complete problems generally require exponential time in the worst case. The problem of solving CSPs in the multiagent context is further complicated by their decentralized nature, which imposes constraints on the distribution of information and authority among participants. In a decentralized system, the information state of an individual is considered private, and is disseminated only by voluntary communication acts. This contrasts with centralized systems, in which it is generally assumed that a single entity (the “center”) can obtain knowledge of the entire information state, for example by compelling communication. Decentralization constraints clearly restrict the computations performed by individual participants. Yokoo and Hirayama [34,36] formalize CSPs with decentralization constraints as distributed constraint satisfaction problems (DisCSPs) and, with others, have designed a variety of effective algorithms, such as the distributed breakout (DB) algorithm [35]. These approaches are generally distributed adaptations of centralized algorithms, and can perform very effectively. Markets provide another model of decentralized systems with clearly delineated boundaries of knowledge and lines of communication. Typically, participants (agents) maintain knowledge of only resources of direct interest, and interact with other agents only indirectly through market institutions, such as auctions. The market-based approach has become increasingly popular in recent years, as evidenced by the growing prevalence in the AI literature of research in the design and analysis of computational market systems and their underlying mechanisms. Markets have been proposed to solve a diversity of problems, with climate control [33], power load management [32], allocating computational servers [22], multicommodity flow [29], and belief aggregation [12] being just a sample. Shoham and Tennenholtz [19] directly pose the question “What can a market compute, and at what expense?” They provide answers for some interesting cases, applying concepts from economic mechanism design and communication complexity. Different behavioral assumptions can support conclusions about additional cases. For instance, over fifty years ago, Samuelson [13] considered how markets could decentralize the solution of linear programming problems. More generally, adopting market protocols in the framework of general equilibrium theory can be seen to yield a computational model capable of solving convex programming problems [3]. However, none of these lines of analysis provide answers with respect to the sort of combinatorial optimization problems of most interest in AI and multiagent systems research. To address this gap, we examine here the possibility of using markets to solve propositional satisfiability (SAT) problems in a decentralized manner.We refer to a market protocol applied to the solution of SAT problems as a MarketSAT protocol. As the original NP-complete problem, SAT is considered fundamental, has been thoroughly studied, and indeed remains the object of active research. Studies in AI have led to a greater understanding of its difficulty [4], and steady improvements in centralized algorithms, starting with the success of GSAT [18]. We begin our exploration of market-inspired approaches to SAT by showing how to transform SAT to a supply chain formation problem. We can then employ a previouslydeveloped market protocol for general supply chain formation problems [24,25,27], thus obtaining a MarketSAT protocol. In Section 2 we describe the supply chain formation problem and show how to reduce SAT to supply chain formation in the context of an NP-completeness proof. In Section 3 we describe the Original MarketSAT protocol (MS-O), based on the supply chain formation market protocol we previously developed. We experimentally evaluate MS-O in Section 4 and find that, while MS-O can solve SAT problems, it is prohibitively slow. In Section 5 we develop variant MarketSAT protocols to address the performance shortcoming of MS-O. In Section 6 we discuss the intuition behind the price-guided search of the MarketSAT protocols and show that they are incomplete. In Section 7 we evaluate the protocols along different dimensions. In Section 7.1 we describe experiments with the variant MarketSAT protocols. These experiments show that the variants perform significantly better than Original MarketSAT, but not as well as distributed breakout. We also investigate possible causes for the performance discrepancies. We further evaluate the protocols in terms of degree of decentralization (Section 7.2) and economic interpretation (Section 7.3), identifying tradeoffs between these dimensions and performance.We conclude in Section 8.

We showed that supply chain formation is NP-complete by transforming SAT problems into task dependency networks. We also showed that we can then solve SAT problems using a distributed market protocol for supply chain formation. That a market protocol designed for other purposes can be fairly directly applied to SAT problems provides existential evidence for highly decentralized market-inspired solution methods to general classes of combinatorial problems. Moreover, it is intriguing that the original MarketSAT protocol succeeds without explicit search state or randomization. However, in practice, the performance of original MarketSAT, based directly on task dependency networks, is impractically slow. We can improve the performance of theMarketSAT protocols by simplifying the market structure. The pricing method also significantly affects performance, with the differential pricing protocol roughly seven times better than uniform pricing, and comparable in performance to GSAT. However, the differential pricing protocol is less justifiable in terms of rational economic agent behavior. Although the variant MarketSAT protocols perform significantly better than the original MarketSAT, the less decentralized distributed breakout algorithm still outperforms the differential pricing MarketSAT by a factor of three to four. We found that the fraction of simultaneous, satisfying neighbor flips does not explain the difference in performance across MarketSAT protocols, as originally conjectured. However, the evidence suggests that MarketSAT with uniform pricing performs worse than with differential pricing because the former attributes costs to satisfied clauses while the latter does not. Evidence further suggests that distributed breakout solves problems faster than MarketSAT with differential pricing because the former requires fewer rounds to produce a flip. An informal analysis suggests that the price-guided search of the MarketSAT protocols works because the protocols resemble the centralized breakout algorithm. We might cautiously apply this intuition to the operation of SAMP-SB in general task dependency networks, but further analysis is necessary to properly account for a broader class of structures. We have identified tradeoffs in terms of runtime performance, decentralization, and the plausibility of assumed agent behaviors. Understanding these tradeoffs is necessary to make informed engineering decisions about the appropriateness and applicability of alternate decentralized approaches to a particular problem environment. The market approach has the benefit of providing a price-based interface for an agent to evaluate and direct its behavior in the context of its broader decision making. To better understand and further develop market approaches to complex coordination problems, we must explicitly incorporate a model of the agents’ economic motivations in the context of the problem to be solved. Future work should also investigate extension of the protocols to optimization problems, and include a deeper analysis of strategic agent behavior.