Budget feasible mechanisms for procurement auctions with divisible agents (Q6164502): Difference between revisions

In this article, the authors study budget feasible mechanisms for procurement auctions with additive valuation functions. In the case, where agents can be allocated fractionally, there exists an optimal mechanism with approximation guarantee \(\frac{e}{e-1}\) under the small bidder assumption. The authors consider also the divisible case, without the small bidder assumption, but assume that the true costs of the agents are bounded by the budget. More precisely, a mechanism with an approximation guarantee of 2.62, improving the result of 3 for the indivisible case is considered. In Section 4, the authors introduce a setting in which the agents' efficiencies (i.e. value over cost ratios) are bounded by some \(\theta >1\). The extended results to a model in which agents may have different types, the reader may find in Section 5. For the entire collection see [Zbl 1515.91014].