Market protocols for decentralized supply chain formation.

Abstract

In order to effectively respond to changing market conditions, business partners must be able to rapidly form supply chains. This thesis approaches the problem of automating supply chain formation---the process of determining the participants in a supply chain, who will exchange what with whom, and the terms of the exchanges---within an economic framework. In this thesis, supply chain formation is formalized as task dependency networks. This model captures subtask decomposition in the presence of resource contention---two important and challenging aspects of supply chain formation. In order to form supply chains in a decentralized fashion, price systems provide an economic framework for guiding the decisions of self-interested agents. In competitive price equilibrium, agents choose optimal allocations with respect to prices, and outcomes are optimal overall. <italic>Approximate </italic> competitive equilibria yield approximately optimal allocations. Different market protocols are proposed for agents to negotiate the allocation of resources to form supply chains. In the presence of resource contention, these protocols produce better solutions than the greedy protocols common in the artificial intelligence and multiagent systems literature. The first protocol proposed is based on distributed, progressive, price-based auctions, and is analyzed with non-strategic, agent bidding policies. The protocol often converges to high-value supply chains, and when competitive equilibria exist, typically to approximate competitive equilibria. However, complementarities in agent production technologies can cause the protocol to wastefully allocate inputs to agents that do not produce their outputs. A subsequent decommitment phase recovers a significant fraction of the lost surplus. Alternatively, the problem can be solved with a combinatorial auction protocol, which ensures that agents do not receive partial allocations. A combinatorial protocol is analyzed with various strategic bidding policies, and empirically compared with the distributed, price-based protocol according to various economic metrics. The distributed, price-based protocol can also be used to solve propositional satisfiability problems. Although the performance of the most direct implementation is slow, variants perform well compared with non-market algorithms.