On the (In)approximability of Combinatorial Contracts

Moral hazard and observability

B. Holmström · 1979

Earlier work this paper cites.

An analysis of the principal-agent problem

S. J. Grossman and O. D. Hart · 1983

Earlier work this paper cites.

Clique is hard to approximate within n 1-ε

J. Hastad · 1996

Earlier work this paper cites.

A threshold of ln n for approximating set cover

U. Feige · 1998

Earlier work this paper cites.

Combinatorial auctions with decreasing marginal utilities

B. Lehmann, D. Lehmann, and N. Nisan · 2001

Earlier work this paper cites.

Combinatorial agency

M. Babaioff, M. Feldman, and N. Nisan · 2006

Earlier work this paper cites.

The communication requirements of efficient allocations and supporting prices

N. Nisan and I. Segal · 2006

Earlier work this paper cites.

Linear degree extractors and the inapproximability of max clique and chromatic number

D. Zuckerman · 2006

Earlier work this paper cites.

Computing optimal contracts in combinatorial agencies

Y. Emek and M. Feldman · 2012

Cited alongside, same era.

Delegated search approximates efficient search

J. Kleinberg and R. Kleinberg · 2018

Cited alongside, same era.

How do classifiers induce agents to invest effort strategically?

J. Kleinberg and M. Raghavan · 2020

Cited alongside, same era.

Contracts with private cost per unit-of-effort

T. Alon, P. Dütting, and I. Talgam-Cohen · 2021

Cited alongside, same era.

Combinatorial contracts

P. Dütting, T. Ezra, M. Feldman, and T. Kesselheim · 2021

Cited alongside, same era.

Contracts under moral hazard and adverse selection

G. Guruganesh, J. Schneider, and J. R. Wang · 2021

Cited alongside, same era.

Delegated pandora’s box

C. Bechtel, S. Dughmi, and N. Patel · 2022

Later among the works it cites.

Designing menus of contracts efficiently: The power of randomization

M. Castiglioni, A. Marchesi, and N. Gatti · 2022

Later among the works it cites.

Optimization of scoring rules

Y. Li, J. D. Hartline, L. Shan, and Y. Wu · 2022

Later among the works it cites.

Contracts with information acquisition, via scoring rules

M. Papireddygari and B. Waggoner · 2022

Later among the works it cites.

Multi-agent contract design: How to commission multiple agents with individual outcomes

M. Castiglioni, A. Marchesi, and N. Gatti · 2023

Closest in time.

Equity pay in networked teams

K. Dasaratha, B. Golub, and A. Shah · 2023

Closest in time.