Budget Feasible Mechanisms

Rian Neogi

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 doesnt 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 Myersons lemma. I will then give some simple mechanisms when the buyers valuation function is additive or submodular.

Date
Jul 10, 2023 1:00 PM
Location
MC6029 or Zoom