Bi-Weekly Talk: Katharina Eickhoff: Computing buyer-optimal Walrasian prices in multi-unit matching markets via a sequence of max flow computations

Mittwoch, 25.05.2022, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10
und als Online Session

Vortragende: Katharina Eickhoff 



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 has a linear (or matroid) valuation function for the items. 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.
For the linear case we show how to compute these buyer-optimal Walrasian prices. We present an ascending auction which iteratively raises the prices on the object 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.
At the moment we are working on the extension of our results to the matroid valuation case.