Mechanism Design for Multiple Item Procurement Using a Distributed Ellipsoid Algorithm

We study a problem in a procurement setting in which an Original Equipment Manufacturer (OEM) wants to procure a set of items from a set of suppliers. Each supplier incurs a cost for supplying any subset/bundle of items, and each supplier's cost information is known only to him. The goal is to determine (i) an efficient allocation of suppliers to items and (ii) appropriate payments for suppliers. We formulate the problem of determining which supplier should supply what items as an integer program. We develop a method, which is based on the ellipsoid method, that solves the dual of the linear relaxation of the problem in polynomial time. We also show that the linear relaxation has an integral optimal solution