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.