URA Seminar - Rian Neogi

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

Title: Budget Feasible Mechanisms

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 5479

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 first explain the required game theoretical concepts of truthfulness, Myerson's lemma, and budget feasibility. Then I will go through some results in budget feasible mechanism design. I will then give some simple mechanisms when the buyers valuation function is additive or submodular.