Auctions for structured procurement

This paper considers a general setting for structured procurement and the problem a buyer faces in designing a procurement mechanism to maximize profit. This brings together two agendas in algorithmic mechanism design, frugality in procurement mechanisms (e.g., for paths and spanning trees) and profit maximization in auctions (e.g., for digital goods). In the standard approach to frugality in procurement, a buyer attempts to purchase a set of elements that satisfy a feasibility requirement as cheaply as possible. For profit maximization in auctions, a seller wishes to sell some number of goods for as much as possible. We unify these objectives by endowing the buyer with a decreasing marginal benefit per feasible set purchased and then considering the problem of designing a mechanism to buy a number of sets which maximize the buyer's profit, i.e., the difference between their benefit for the sets and the cost of procurement. For the case where the feasible sets are bases of a matroid, we follow the approach of reducing the mechanism design optimization problem to a mechanism design decision problem. We give a profit extraction mechanism that solves the decision problem for matroids and show that a reduction based on random sampling approximates the optimal profit. We also consider the problem of non-matroid procurement and show that in this setting the approach does not succeed.