Many real-world auction and mechanism design settings involve budget constraints for agents. Specifically, an agent's utility from an outcome is given by his value for the outcome minus any payment he makes to the mechanism, as long as the payment is below his budget, and is negative infinity otherwise. This discontinuity in the utility function presents a significant challenge in mechanism design, and classical "unconstrained" mechanisms fail to work in settings with budgets. In this talk we present new techniques and results for mechanism design with budget constraints in Bayesian settings. This talk is based on joint work with David Malec and Azarakhsh Malekian.
Back to Algorithmic Game Theory