Subsidies, Knapsack Auctions and Dantzig’s Greedy Heuristic

Ensthaler, Ludwig und Giebe, Thomas (Februar 2009): Subsidies, Knapsack Auctions and Dantzig’s Greedy Heuristic. SFB/TR 15 Discussion Paper No. 254

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.

• Dokumententyp: Paper
• Keywords: Auctions, Subsidies, Market Design, Knapsack Problem
• Fakultät: Sonderforschungsbereiche > Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems ; Sonderforschungsbereiche > Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems > A7 - Auktionen, Anreizprobleme und Wettbewerb
• Themengebiete: 300 Sozialwissenschaften > 330 Wirtschaft
• JEL Classification: D21, D43, D44, D45
• Sprache: Englisch