Title: An O(log log n)-approximate budget-feasible mechanism for subadditive valuations
| Speaker: | Rian Neogi |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract:In the setting of budget feasible mechanism design, a buyer wants to purchase items from a set of agents. Each agent holds one item, and incurs a cost of c_i upon supplying the item to the buyer. The buyer wants to maximize the value of the set of items that are bought from the sellers. The buyer has a budget B on the total payments made to the sellers. The cost c_i is private information that the buyer doesn't have access to. The goal is to design a mechanism that is truthful, in the sense that the sellers do not have incentive to deviate from reporting their true costs, and budget feasible, in the sense that the total payments made to the sellers is within some budget B, and that outputs a set whose value is a good approximation to the algorithmic optimum, OPT = max{v(S) : c(S)<=B}.
In this talk, I will present our recent work that obtains an O(log log n)-approximate budget-feasible mechanism when the valuation function is subadditive. This is joint work with Kanstantsin Pashkovich and Chaitanya Swamy.