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

Wednesday, May 25, 2022, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10
and as Online session

Speaker: Katharina Eickhoff 

 

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 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.