EDBT 2026 Demo / reviewers in the wild / expert
Martin Knaack
dblp:328/9009
· DBLP profile ↗
3ranked-venue papers
0as first author
3since 2021 · last 2026
0009-0007-2912-1550ORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 3 · 3 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Strategyproof Mechanisms Without Money for 2-Exchange SystemsabstractMechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem (\gpp), to study the mechanism design questions without payment. The \gpp\ possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem. We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of \gpp, and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed in \cite{DG10}. Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces, in application to mechanism design. Stable matching, while conceptually simple, provides a set of powerful tools to manage and analyze self-interested behaviors of participating agents. Our mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling and online mechanisms. Our work also enriches the stable matching theory with a new knapsack constrained matching model. Javier Cembrano, Max Klimm, Martin Knaack, Arturo Merino |
ESA | 3 |
| 2025 | Generalized Assignment and Knapsack Problems in the Random-Order Model
Max Klimm, Martin Knaack |
IPCO | 2 |
| 2022 | Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint
Max Klimm, Martin Knaack |
APPROX/RANDOM | 2 |