Multiagent Evaluation Mechanisms

Collaboration 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

Collaboration 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.

Collaboration 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.

© 2021 by Tal Alon.