Bi-Weekly Talk: Katharina Eickhoff: Faster Ascending Auctions

Wednesday, February 07, 2024, 10:30am

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

Speaker: Katharina Eickhoff



We study ascending auctions for computing minimal Walrasian prices (i.e.

prices that admit a stable allocation of all items) in markets where indivisible items with multiplicities are sold to buyers with individual, non-decreasing, and gross substitutes valuations. Finding the sets on which the ascending auction increases the prices boils down to a submodular function minimization problem. We provide faster and simpler algorithms to find these sets.

In the biweekly meeting, I will present algorithms for unit demand valuations, additive valuations with demand and finally gross substitute valuations.

The talk is based on joint work with Thomas McCormick, Britta Peis, Niklas Rieken, Laura Vargas Koch and Lázló Végh.