2026-08-25T15:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27220 2026-08-25T13:18:18Z ddc:004 open_access

Strategyproof Mechanisms Without Money for 2-Exchange Systems Cembrano, Javier Klimm, Max Knaack, Martin Merino, Arturo mechanism design without money strategyproof mechanisms approximation algorithms 2-exchange systems matchings 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Javier Cembrano and Max Klimm and Martin Knaack and Arturo Merino 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.84 urn:nbn:de:0030-drops-272202 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.84 eng https://creativecommons.org/licenses/by/4.0/legalcode