CombOpt ReadingGroup - Rian Neogi-Multidimensional Budget-feasible mechanism design

In budget-feasible mechanism design, there is a set of items U. A buyer wishes to purchase a set of items from the sellers of maximum value, where the value of a subset S of items is provided by a valuation function v. Each element e is held by a distinct seller, who incurs a private cost c_e for supplying her item. The buyer also has a budget of B on the total payments made to the sellers. The private costs c_e are known only to the sellers, and not to the buyer. Each seller e reports a cost r_e to the mechanism, which may or may not be equal to her true cost c_e. As a result, a seller may choose to misreport her cost if she sees that she is better off when doing so (for example, the mechanism might be giving her a higher payment under the misreported cost). 

Budget-feasible mechanisms have been well-studied over the past 15 years. In this talk, we will introduce a generalization of the setting, where each agent can now hold multiple items. This generalizes the problem into what is known as a multi-parameter domain, which brings about several complications, including strong impossibility results with respect to the typical benchmark of the algorithmic optimum. In lieu of these impossibility results, we propose a novel benchmark for the setting. We prove positive results with respect to this new benchmark, qualitatively matching prior results in single-parameter budget-feasible mechanism design.

This is joint work with Kanstantsin Pashkovich and Chaitanya Swamy, and is to appear in EC 2026.