DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.84

Strategyproof Mechanisms Without Money for 2-Exchange Systems

Authors: Javier Cembrano, Max Klimm, Martin Knaack, and Arturo Merino

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We study a mechanism design problem in which a ground set of items E is distributed among self-interested agents. The existence of an item is private information of the agent owning it. A mechanism takes as input a set of reported items together with their intrinsic weights and returns a feasible set of items. A mechanism is strategyproof if no agent can increase the total weight of their items in the solution by withholding a subset of their items from the mechanism. It is α-approximate if the total weight of items selected is at least an 1/α-fraction of the total weight of an optimal solution. Our main result is a 6.018-approximate strategyproof mechanism for feasibility constraints defined by a 2-exchange system. This class of independence systems is defined by a combinatorial exchange condition and includes, for example, b-matchings in general graphs, intersections of strongly base-orderable matroids, and unit interval scheduling. This constant approximation generalizes and improves over a logarithmic approximation for matchings. We also obtain a strategyproof mechanism with logarithmic approximation for generalized assignment instances, where items represent compatibilities between jobs and machines. While prior work focused on the special case in which each agent controls a single job, we provide the first logarithmic approximation guarantee for the general setting in which agents may control multiple jobs. We finally provide improved approximation guarantees for matching instances with binary weights, beating the 2-approximation given by a simple greedy mechanism for any finite number of agents and showing a strict separation between deterministic and randomized mechanisms for the case of two agents.

Cite as

Javier Cembrano, Max Klimm, Martin Knaack, and Arturo Merino. Strategyproof Mechanisms Without Money for 2-Exchange Systems. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cembrano_et_al:LIPIcs.ESA.2026.84,
  author =	{Cembrano, Javier and Klimm, Max and Knaack, Martin and Merino, Arturo},
  title =	{{Strategyproof Mechanisms Without Money for 2-Exchange Systems}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{84:1--84:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.84},
  URN =		{urn:nbn:de:0030-drops-272202},
  doi =		{10.4230/LIPIcs.ESA.2026.84},
  annote =	{Keywords: mechanism design without money, strategyproof mechanisms, approximation algorithms, 2-exchange systems, matchings}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.49

Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint

Authors: Max Klimm and Martin Knaack

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract

This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature c of the submodular function. For the extreme cases c = 0 corresponding to a modular objective, it matches a previously known and best possible robustness factor of 1/2. For the other extreme case of c = 1 it yields a robustness factor of ≈ 0.35 improving over the best previously known robustness factor of ≈ 0.06.

Cite as

Max Klimm and Martin Knaack. Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{klimm_et_al:LIPIcs.APPROX/RANDOM.2022.49,
  author =	{Klimm, Max and Knaack, Martin},
  title =	{{Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.49},
  URN =		{urn:nbn:de:0030-drops-171711},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.49},
  annote =	{Keywords: submodular function, knapsack, approximation algorithm, robust optimization}
}

Search Results

Documents authored by Knaack, Martin

Strategyproof Mechanisms Without Money for 2-Exchange Systems

Abstract

Cite as

Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint

Abstract

Cite as

Thanks for your feedback!

Could not send message