Subsidies, Knapsack Auctions and Dantzig’s Greedy Heuristic

Ludwig Ensthaler and Thomas Giebe

Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems from Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich

Abstract: A budget-constrained buyer wants to purchase items from a shortlisted set. Items are differentiated by quality and sellers have private reserve prices for their items. Sellers quote prices strategically, inducing a knapsack game. The buyer’s problem is to select a subset of maximal quality. We propose a buying mechanism which can be viewed as a game theoretic extension of Dantzig’s greedy heuristic for the classic knapsack problem. We use Monte Carlo simulations to analyse the performance of our mechanism. Finally, we discuss how the mechanism can be applied to award R&D subsidies.

Keywords: Auctions; Subsidies; Market Design; Knapsack Problem (search for similar items in EconPapers)
JEL-codes: D21 D43 D44 D45 (search for similar items in EconPapers)
Date: 2009-02
New Economics Papers: this item is included in nep-cta
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://epub.ub.uni-muenchen.de/13298/1/254.pdf (application/pdf)

Related works:
Working Paper: Subsidies, Knapsack Auctions and Dantzig's Greedy Heuristic (2009)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:trf:wpaper:254

Access Statistics for this paper

More papers in Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems from Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich Geschwister-Scholl-Platz 1, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Tamilla Benkelberg ().