Computing buyer-optimal Walrasian prices in multi-unit matching markets via a sequence of max flow computations.

Abstract:  Given a market where discrete indivisible items of different types are sold to a set of buyers. There is a given supply of each type and each buyer has a given (maximum) demand. Each buyer valuates the items linearly in our setting. We aim for competitive prices, i.e. prices such that an allocation exists where every buyer gets one of his preferred bundles. The prices should be as small as possible and as much as possible should be sold.

We show how to compute these buyer-optimal Walrasian prices. We present an ascending auction which iteratively raises the prices on the goods in the left-most min cut in some associated auxiliary flow network. Given this prices, we can compute an allocation where as much as possible is sold. The structural insights obtained from our flow-based approach furthermore lead to several interesting insights regarding the sensitivity analysis of our ascending auction.

Posted on Jul 4, 2022 in ACGO, Seminars