TODAY UnRAVeL Survey Lecture: "Biggest Milestones"
by Kassing, Jan-Christoph
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
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.
Jan-Christoph for the organisation committee