Generalized assignment problem: truthful mechanism design without money

DOI10.1016/J.ORL.2016.12.003MaRDI QIDQ1727952zbMATH OpenOpenAlexFDO

Authors Salman Fadaei, Martin Bichler

Publication date 21 February 2019

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.04273

zbMATH Keywords

approximationgeneralized assignment problemtruthfulnessmechanism design without money

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: In this paper, we study a problem of truthful mechanism design for a strategic variant of the generalized assignment problem (GAP) in a both payment-free and prior-free environment. In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, bins are held by strategic agents, and each agent may hide its compatibility with some items in order to obtain items of higher values. The compatibility between an agent and an item encodes the willingness of the agent to receive the item. Our goal is to maximize total value (sum of agents' values, or social welfare) while certifying no agent can benefit from hiding its compatibility with items. The model has applications in auctions with budgeted bidders. For two variants of the problem, namely emph{multiple knapsack problem} in which each item has the same size and value over bins, and emph{density-invariant GAP} in which each item has the same value density over the bins, we propose truthful $4$-approximation algorithms. For the general problem, we propose an $O(ln(U/L))$-approximation mechanism where $U$ and $L$ are the upper and lower bounds for value densities of the compatible item-bin pairs.

Recommendations

• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Truthful generalized assignments via stable matching
• Mechanisms and impossibilities for truthful, envy-free allocations
• A generic truthful mechanism for combinatorial auctions
• scientific article; zbMATH DE number 2163018
• Approximate composable truthful mechanism design
• Truthful randomized mechanisms for combinatorial auctions

Cites work

• scientific article; zbMATH DE number 477584 (Why is no real title available?)
• An approximation algorithm for the generalized assignment problem
• Generalized assignment problem: truthful mechanism design without money
• Manipulation of Voting Schemes: A General Result
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Randomized metarounding (extended abstract)
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Truthful generalized assignments via stable matching
• Truthfulness and approximation with value-maximizing bidders

Cited in

(6)

• A branching algorithm to solve binary problem in uncertain environment: an application in machine allocation problem
• Truthful many-to-many assignment with private weights
• Truthful generalized assignments via stable matching
• Truthfulness in advertising? Approximation mechanisms for knapsack bidders
• Generalized assignment problem: truthful mechanism design without money
• Electronic service matching: failure of incentive compatibility in vickrey auctions

This page was built for publication: Generalized assignment problem: truthful mechanism design without money

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1727952)