Project
AA3-5
Tropical Mechanism Design
Project Heads
Project Members
Sylvain Spitz (TU since 01/21, HU until 12/20)
Project Duration
01.01.2019 – 30.09.2022
Located at
TU (since 01/21), HU (until 12/20)
Description
We study the design of revenue-maximizing mechanisms for selling multiple items. Applying a duality framework, there is a one-to-one correspondence between optimal mechanisms and certain tropical polynomials and rational functions that we want to study via ideas from algebraic statistics.
TOPIC AND BACKGROUND OF THE PROJECT
The question of how to sell one item to multiple bidders in a revenue-maximizing auction is well understood since the work of Roger Myerson in the 1980s. It is used in many applications and on online platforms such as eBay. But if we want to sell multiple items at once, the problem becomes substantially harder and not much is known about the optimal auction mechanism.
DETERMINISTIC AUCTION MECHANISMS
Typically, an auction mechanism asks the participants for their bids and then allocates the items to the bidders as well as a price they have to pay. This method is called a deterministic auction mechanism. In contrast, we could introduce a lottery for some (or all) items and, after collecting the bids, allocate the items to the bidders up to a certain probability. Observations suggest that in general a revenue-maximizing auction has to introduce such lotteries. All the more so it is interesting to find cases, in which a deterministic auction is optimal.
Giannakopoulos and Koutsoupias examined the case, where the valuations, that each bidder has for the items, are drawn according to an uniform distribution. They showed, that the optimal auction mechanism for this setting and up to 6 items is deterministic and they conjectured that this holds true for an arbitrary number of items. We will explore their conjecture as well as their approach by applying other methods, especially from tropical geometry. In fact, the utility function of a deterministic auction corresponds to a tropical polynomial. Moreover, we want to use the insights we get by this method, to better understand the general case.
Straight Jacket Auction and Generalized Permutahedra
The deterministic mechanism given by Giannakopoulos and Koutsoupias is called the Straight Jacket Auction (SJA). It consists of a certain price schedule (p1,…,pn), where pk designates the price for any bundle of k items. Such a price schedule divides the n-cube in regions depending on the term which maximizes the utility function u(x) = max{ Σj∈J xj – p|J] | J ⊂ {1,…,n} }. The regions are marked on the right by UJ, where J is the bundle of items that attain the maximum utility. Their volumetric properties are essential for the computation of the prices and the proof of optimality of the mechanism.
The regions are in fact covector cells of the tropical polynomial u(x) intersected with the n-cube. They can also be classified as (products of) generalized permutahedra, which is useful since those polytopes come up in a variety of applications and are therefore well studied. This way, we were able to derive multiple volume formulae for the regions, which link them to a counting problem about the number of certain bipartite graphs, Delzant polytopes and Lorentzian polynomials.
The SJA-prices are known to be optimal for up to 6 items and conjectured to be optimal in general. We contribute to this conjecture by showing that the prices indeed satisfy some necessary optimality conditions and that there are no other symmetric and strictly submodular price schedules satisfying those conditions.
Computation of SJA-prices
The prices for the Straight-Jacket-Auction are not easy to compute. We used our insights to implement an algorithm using HomotopyContinuation.jl to calculate the prices for up to 12 items (before known for up to 6).
Selected Publications
- Michael Joswig and Max Klimm and Sylvain Spitz, Generalized permutahedra and optimal auctions, arxiv:2108.00979, 2021
- Michael Joswig, The Cayley trick for tropical hyper surfaces with a view toward Ricardian economics, Homological and computational methods in commutative algebra, 107-128, 2017.
- Paul Dütting and Felix Fischer and Max Klimm, Revenue Gaps for Static and Dynamic Posted Pricing of Homogenous Goods, arXiv:1607.07105, 2019.
Poster
Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.