Using Linear Programming in a Business-to-Business Auction Mechanism

Business to business interactions are largely centered around contracts for procurement or for distribution. Negotiations and sealed bid tendering are the most common techniques used for price discovery and generating the terms and conditions for contracts. Sealed bid tenders collect bids (that is private information between the two companies) and then pick a winning bid/s from among the submitted bids. The outcome of such interactions can be analyzed based on the theory of sealed bid auctions and have been studied extensively [7]. In contrast, negotiations tend to be more dynamic where a buyer (supplier) might be interacting with several suppliers (buyers) simultaneously and the contractual terms being negotiated with one supplier might directly impact the negotiations with another. An approach that is often used for this setting is to design an interactive mechanism where based on a "market signal" such as price for each item, the agents can propose bids based on a decentralized private cost model. A general setting for decentralized allocation is one where there are multiple agents with a utility function for the different resources and the allocation problem is to distribute the resources in an optimal way. A key difference from classical optimization is that the utility functions of the agents are private information and are not explicitly known to the decision maker. The key requirements for such a design to be practical are: (i) convergence to an "equilibrium solution" in a finite number of steps, and (ii) the "equilibrium solution" is optimal for each of the agents, given the market signal. One approach for implementing such mechanisms is the use of primal-dual approaches where the resource allocation problem is formulated as a linear program and the dual prices are used as market signals |2, 3, 8, 1, 4, 6|. Each agent can then use the dual price vector to propose a profit maximizing bid, for the next round, based on her private cost model. Here, the assumption is that the agents attempt to maximize their profits in each round. This assumption is referred to as the myopic best response |5|. In a procurement setting with a single buyer and multiple suppliers, the buyer uses a linear program to allocate her demand by choosing a set of cost minimizing bids and then use the dual price variables to signal the suppliers. In order to guarantee convergence a large enough price decrement is used on all non-zero dual prices in each iteration. In this paper we explore an alternate design where, the market signal provided to each supplier is based on the current cost of procurement for the buyer. Each supplier is then required to submit new bid proposals that reduce the procurement cost (assuming other suppliers keep their bids unchanged) by some large enough decrement d > a. We show that, for each supplier, generating a profit maximizing bid that decreases the procurement cost for the buyer by at least d can be done in polynomial time. This implies that in designs where the bids are not common knowledge, each supplier and the buyer can engage in an "algorithmic conversation" to identify such proposals in a polynomial number of steps. In addition, we show that such a mechanism converges to an "equilibrium solution" where all the suppliers are at their profit maximizing solution given the cost and the required decrement d. At the heart of this design lies a fundamental sensitivity analysis problem of linear programming - given a linear program and its optimal solution, identify the set of new columns such that any one of these columns when introduced in the linear program reduces the optimum solution by at least d