An Ascending Polynomial Running Time Vickrey Auction for Selling Bases of an Integer Polymatroid

Consider a single auctioneer who wants to sell multiple units of distinct indivisible items to bidders with private valuations. The set of feasible allocations is constrained to integer base points, which are the integer points of an integer base polyhedron. Each bidder’s valuation is the integer restriction of a sum of nondecreasing, concave single-parameter functions. This seemingly abstract setting is of theoretical relevance and has various interesting applications. In this context, we develop an ascending auction that implements a social welfare-maximizing allocation, charges Vickrey–Clarke–Groves prices, relies only on a single price, is ex-post incentive-compatible, and satisfies unconditional winner privacy. The auction has a polynomial running time in the number of bidders, items, and units; in the case of linear separable valuations it runs even in strongly polynomial time, thereby improving on the literature. Moreover, by relaxing unconditional winner privacy, the auction can be made fully polynomial in the number of bidders, items, units, and integer breakpoints of bidders’ valuations. If we assume that bidders are unit-demand , then our auction is dominant-strategy incentive-compatible and (weakly) group strategy-proof, much like deferred acceptance auctions.