Matthias Buttkus

dblp:215/3798 · DBLP profile ↗
← Back
3ranked-venue papers
0as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 1 since 2021
YearPublicationVenuePosition
2021 Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions
abstract
We consider the problem of posting prices for unit-demand buyers if all $n$ buyers have identically distributed valuations drawn from a distribution with monotone hazard rate. We show that even with multiple items asymptotically optimal welfare can be guaranteed. Our main results apply to the case that either a buyer's value for different items are independent or that they are perfectly correlated. We give mechanisms using dynamic prices that obtain a $1 - Θ\left( \frac{1}{\log n}\right)$-fraction of the optimal social welfare in expectation. Furthermore, we devise mechanisms that only use static item prices and are $1 - Θ\left( \frac{\log\log\log n}{\log n}\right)$-competitive compared to the optimal social welfare. As we show, both guarantees are asymptotically optimal, even for a single item and exponential distributions.
Alexander Braun 0002, Matthias Buttkus, Thomas Kesselheim
ESA2
2020 On Limitations of Structured (Deterministic) DNNFs
Beate Bollig, Matthias Buttkus
Theory Comput. Syst.2
2019 On the Relative Succinctness of Sentential Decision Diagrams
Beate Bollig, Matthias Buttkus
Theory Comput. Syst.2