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.

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.

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.

Bayesian Analysis of Linear Contracts

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.

© 2021 by Tal Alon.