Everyone is welcome to attend the next N&O seminar with Sophie Klumper with the title 'Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents'.
The talk will take place in L017 at CWI, along with zoom support for remote participants. For more information and registration to get the Zoom link via e-mail, please contact Willem Feijen (willem.feijen at cwi.nl), Samarth Tiwari (samarth.tiwari at cwi.nl) or Sven Polak (sven.polak at cwi.nl).
Abstract: 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 optimal 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 k. For k <= 2, we give a mechanism with an approximation guarantee of 2 and a lower bound of 1.18. Finally, we extend our results to different agent types with concave additive valuation functions.
(Joint work with Guido Schäfer)
