Generalized assignment problem: Truthful mechanism design without money

Salman Fadaei, Martin Bichler

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We propose truthful approximation mechanisms for strategic variants of the generalized assignment problem (GAP) in a payment-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 our strategic variant, bins are held by strategic agents and each agent may hide its willingness to receive some items in order to obtain items of higher values. The model has applications in auctions with budgeted bidders.

Original languageEnglish
Pages (from-to)72-76
Number of pages5
JournalOperations Research Letters
Volume45
Issue number1
DOIs
StatePublished - 1 Jan 2017

Keywords

  • Approximation
  • Generalized assignment problem
  • Mechanism design without money
  • Truthfulness

Fingerprint

Dive into the research topics of 'Generalized assignment problem: Truthful mechanism design without money'. Together they form a unique fingerprint.

Cite this