C&O Reading Group - Rian Neogi

Monday, July 17, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title: Budget Feasible Mechanisms : Part II

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 can supply at item at an incurred cost of c_i to themself, and the buyer wants to optimize over their own valuation for the set of items bought. 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.

In the second part of the talk, I will complete the proof of the Jalay-Tardos paper that gives a budget feasible mechanism when the buyer's valuation function is submodular. If time permits, I will talk about some simple lower bounds in budget feasible mechanism design.