Abstract:
The Budget-feasible Mechanism (BFM) design problem is one of the classic issues in computational economics. It can be regarded as a twin problem to the 0-1 knapsack problem, with significant theoretical research implications and broad applications. Since its inception, the problem has been studied for over fifteen years and has attracted significant attention from many renowned scholars both domestically and internationally. This article classifies existing work on BFM design based on various dimensions, including the types of value functions considered, the auction formats employed, and the assumptions made about sellers’ information. Furthermore, it reviews the performance bounds achievable by BFMs for different types of value functions. The article also introduces several representative BFM design frameworks and their main design ideas. Finally, we summarize the existing literature and offer prospects for future work in the area of BFM design.