Truthful multi-unit procurements with budgets

DOI10.1007/978-3-319-13129-0_7MaRDI QIDQ2936978zbMATH OpenOpenAlexFDO

Authors Hau Chan, Jing Chen

Publication date 7 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

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

zbMATH Keywords

approximationbudget-feasible mechanismoptimal mechanismprocurement auction

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) (n)-person games, (n>2) (91A06) Cooperative games (91A12) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We study procurement games where each seller supplies multiple units of his item, with a cost per unit known only to him. The buyer can purchase any number of units from each seller, values different combinations of the items differently, and has a budget for his total payment. For a special class of procurement games, the {em bounded knapsack} problem, we show that no universally truthful budget-feasible mechanism can approximate the optimal value of the buyer within $lnn$, where $n$ is the total number of units of all items available. We then construct a polynomial-time mechanism that gives a $4(1+lnn)$-approximation for procurement games with {em concave additive valuations}, which include bounded knapsack as a special case. Our mechanism is thus optimal up to a constant factor. Moreover, for the bounded knapsack problem, given the well-known FPTAS, our results imply there is a provable gap between the optimization domain and the mechanism design domain. Finally, for procurement games with {em sub-additive valuations}, we construct a universally truthful budget-feasible mechanism that gives an $O(fraclo{g}^{2}nloglogn)$-approximation in polynomial time with a demand oracle.

Recommendations

• Budget feasible procurement auctions
• Coverage, matching, and beyond: new results on budgeted mechanism design
• Budget feasible mechanism design, from prior-free to Bayesian
• Budget feasible mechanisms for procurement auctions with divisible agents
• Worst-case mechanism design via Bayesian analysis

Cited in

(8)

• Truthful aggregation of budget proposals
• Ex-post optimal knapsack procurement
• Bayesian optimal knapsack procurement
• Collusion-proof mechanisms for multi-unit procurement
• Budget feasible procurement auctions
• Budget feasible mechanisms on matroids
• Budget feasible mechanisms for procurement auctions with divisible agents
• Partial allocations in budget-feasible mechanism design: bridging multiple levels of service and divisible agents

This page was built for publication: Truthful multi-unit procurements with budgets

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