Dear all, this is a reminder for Britta Peis's talk with the title "Ascending Auctions and Matroids" taking place today at 12:30 in the B-IT room 5053.2. Please find the details below --- Abstract --- 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). ---------------- Part of the programme of the research training group UnRAVeL is a series of lectures on the topics of UnRAVeL’s research thrusts algorithms and complexity, verification, logic and languages, and their application scenarios. Each lecture is given by one of the researchers involved in UnRAVeL. This years topic is "Biggest Milestones - Research at Its Peak", UnRAVeL professors will present the most important milestone of their respective research. All interested doctoral researchers and master students are invited to attend the UnRAVeL lecture series 2023 and engage in discussions with researchers and doctoral students. Next week we have a talk from Gerhard Lakemeyer with the title "The Situation Calculus as Lingua Franca for Reasoning about Action" We are looking forward to seeing you at the lectures. Kind regards, Jan-Christoph for the organisation committee