UnRAVeL Survey Lecture: Britta Peis: Ascending Auctions and Matroids
Thursday, June 15, 2023, 12:30pm
Location: Computer Science Center, Building E2, ground floor, B-IT room 5053.2
Speaker: Britta Peis
We consider matching markets, where an auctioneer is selling a set of indivisible items E to a set of bidders with private valuations v_j. In an ascending auction, the auctioneer decides on an assignment of items to bidders, together with prices p_i for all items i in E, based on the demand indicated by the bidders throughout the auction.
In the first part of the talk, we consider computability and monotonicity of buyer-optimal Walrasian equilibria in ascending auctions. A price vector p is called "Walrasian", if there exists an assignment under which every bidder j receives a bundle S of maximum payoff v_j(S)-p(S), and, additionally, all items of positive price are sold. Walrasian prices are called "buyer-optimal" if they minimise the total payment of the bidders among all Walrasian prices. It is well-known that buyer-optimal Walrasian prices exist and can be computed efficiently if the valuations v_j are gross-substitute. Moreover, it is known that an ascending auction, which iteratively raises the prices uniformly on items in a so-called "inclusionswise minimal maximal overdemanded set" terminates with buyer-optimal Walrasian prices, and that these overdemanded sets can be computed efficiently with tools from Discrete Convexity. We will see how to compute the desired overdemanded set in each iteration in a simple combinatorial way with the matroid partition algorithm. Moreover, we will use the obtained structural insights to show that the buyer optimal Walrasian prices are monotone in supply and demand.
In the second part of the talk, we consider ascending auctions where the auctioneer is restricted to sell a basis of a matroid to the bidders. It is known that a very natural and simple ascending auction is welfare-maximising and truthful in the sense that the prices coincide with the Vickrey payments. We will provide a simple proof of this result, combined with certain sensitivity results.
(Joint work with Katharina Eickhoff, Niklas Rieken, and Laura Vargas Koch).