Search Results

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.