C&O Reading Group - Rian Neogi

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

Title: Budget Feasible Mechanisms

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 this talk, I will go through some results in budget feasible mechanism design. I will talk about the notions of truthfulness, budget feasibility and Myerson's lemma. I will then give some simple mechanisms when the buyers valuation function is additive or submodular.