Strategyproof mechanisms without money for independence systems.

Abstract: 
We consider mechanisms without money for combinatorial independence systems. We are given an independence system where the ground set of items is partitioned into sets owned by strategic agents. Each item has a weight that is the private information of the agent owning it. A mechanism takes an independence system, the weights, and the partitioning as input and returns an independent set; it is strategyproof if no agent can increase the total weight of their items in the solution by reporting lower weights of their items to the mechanism or withholding a subset of their items from the mechanism, and it is \alpha-approximate if the total weight of items selected is an \alpha-fraction on the total weight of an optimal solution.

In this talk, we will first address the case where the independence system is defined by a knapsack constraint. In this setting, we give the first strategyproof deterministic mechanism achieving a constant approximation (equal to the square of the golden ratio), and we improve the best known approximation guarantee for randomized mechanisms from 576 to 2. We will then construct a 6.018-approximate strategyproof mechanism for independence systems satisfying a combinatorial condition that is fulfilled, e.g., by b-matchings, intersection of strongly base-orderable matroids, and unit interval scheduling. This generalizes and improves over a logarithmic approximation for matchings and yields an O(\log k)-approximate strategyproof mechanism for generalized assignment with k jobs, providing the first non-trivial approximation for this setting. Finally, we will briefly discuss mechanisms with improved constant approximations for special cases such as unweighted matchings and knapsack with unit-density items.

Posted on Sep 22, 2025 in ACGO, Seminars