Publications
Multiagent Evaluation Mechanisms
Joint work with Magdalen Dobson, Ariel Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz
We study evaluation mechanisms that induce multiple agents of differing abilities to behave in desirable ways. We design algorithms to find such mechanisms, and classify the computational complexity of several variants of this problem.
6th World Congress of the Game Theory Society, July 2021.
34th AAAI Conference on Artificial Intelligence, February 2020.
Incomplete Information VCG Contracts for Common Agency
Joint work with Ron Lavi, Elisheva Shamash, and Inbal Talgam-Cohen
We study contract design for welfare maximization in the Common Agency model. Motivated by the significant social inefficiency of standard contracts for such settings, we define and characterize the social efficient class of Incomplete information VCG contracts (IIVCG). Our results reveal an inherent tradeoff between individual rationality (for the principals) and limited liability (for the agent). We design two poly-time algorithm for determining whether a setting has an IIVCG contract with both properties, and computing payments for such settings.
ACM Conference on Economics and Computation (EC), July 2021.
Marketplace Innovation Workshop (MIW), May 2021.
[ arXiv ] [ 18 minute EC talk ]
Contracts with Private Cost per Unit-of-Effort.
Joint work with Paul Dütting, and Inbal Talgam-Cohen
We study principal-agent settings with mixture of hidden action and single-dimensional private type. Our main contribution is an LP-duality based characterization of implementable allocation rules (which maps types to actions). This characterization shares important features of Myerson’s celebrated characterization result (for procurement auctions), but also departs from it in significant ways. We present several applications, including a polynomial-time algorithm for finding the optimal contract with a constant number of actions. This in sharp contrast to recent work on hidden action problems with multi-dimensional private information, which has shown that the problem of computing an optimal contract for constant numbers of actions is APX-hard.
ACM Conference on Economics and Computation (EC), July 2021.
[ Download full paper ] [ 18 minute EC talk ]
Bayesian Analysis of Linear Contracts
Joint work with Paul Dütting, Yingkai Li, and Inbal Talgam-Cohen
We study a generalization of both the classic single-dimensional mechanism design problem, and the hidden-action principal-agent problem of contract theory. In this setting, the principal seeks to incentivize an agent with a private Bayesian type to take a costly action. The goal is to design an incentive compatible menu of contracts which maximizes the expected revenue.
Our main result concerns linear contracts, the most commonly-used contract form in practice. We establish that in Bayesian settings, under natural small-tail conditions, linear contracts provide an O(1)-approximation to the optimal, possibly randomized menu of contracts. This constant approximation result can also be established via a smoothed-analysis style argument. We thus obtain a strong worst-case approximation justification of linear contracts.
[ arXiv full paper ]
© 2021 by Tal Alon.