论文标题
可划分代理的采购拍卖的预算可行机制
Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents
论文作者
论文摘要
我们考虑具有添加估值功能的采购拍卖的预算可行机制。对于可分割的情况，可以分分分配代理，存在一种最佳机制，并在小型出价者假设下具有近似值保证$ e/（e-1）$。我们在没有小型出价者假设的情况下研究可分裂的案例，但假设代理商的真实成本是受预算的限制。这种环境有助于对商品代表时间的经济状况进行建模，而与预算相比，代理商的真实成本不一定很小。在非试图上，我们给出了一种近似值2.62的机制，改善了不可分割的情况的3。此外，我们对1.25的近似保证给出了下限。然后，我们在更具竞争力的市场中研究问题，并假设代理商对成本效率的价值受到一些$θ\ ge 1 $的限制。对于$θ\ le 2 $，我们给出了一种近似保证2且下限1.18的机制。这两个结果都可以扩展到具有不同代理类型的设置，并具有每种类型的线性封顶估值功能。最后，如果每种代理类型都有一个凹度估值，我们给出了一种机制，近似保证随着代理类型的数量线性增长。
We consider budget feasible mechanisms for procurement auctions with additive valuation functions. For the divisible case, where agents can be allocated fractionally, there exists an optimal mechanism with approximation guarantee $e/(e-1)$ under the small bidder assumption. We study the divisible case without the small bidder assumption, but assume that the true costs of the agents are bounded by the budget. This setting lends itself to modeling economic situations in which the goods represent time and the agents' true costs are not necessarily small compared to the budget. Non-trivially, we give a mechanism with an approximation guarantee of 2.62, improving the result of 3 for the indivisible case. Additionally, we give a lower bound on the approximation guarantee of 1.25. We then study the problem in more competitive markets and assume that the agents' value over cost efficiencies are bounded by some $θ\ge 1$. For $θ\le 2$, we give a mechanism with an approximation guarantee of 2 and a lower bound of 1.18. Both results can be extended to settings with different agent types with a linear capped valuation function for each type. Finally, if each agent type has a concave valuation, we give a mechanism for which the approximation guarantee grows linearly with the number of agent types.
