More Like this

1. On the (In)approximability of Combinatorial Contracts. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

   https://doi.org/10.4230/LIPIcs.ITCS.2024.44  

   Ezra, Tomer; Feldman, Michal; Schlesinger, Maya (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   We study two recent combinatorial contract design models, which highlight different sources of complexity that may arise in contract design, where a principal delegates the execution of a costly project to others. In both settings, the principal cannot observe the choices of the agent(s), only the project’s outcome (success or failure), and incentivizes the agent(s) using a contract, a payment scheme that specifies the payment to the agent(s) upon a project’s success. We present results that resolve open problems and advance our understanding of the computational complexity of both settings. In the multi-agent setting, the project is delegated to a team of agents, where each agent chooses whether or not to exert effort. A success probability function maps any subset of agents who exert effort to a probability of the project’s success. For the family of submodular success probability functions, Dütting et al. [2023] established a poly-time constant factor approximation to the optimal contract, and left open whether this problem admits a PTAS. We answer this question on the negative, by showing that no poly-time algorithm guarantees a better than 0.7-approximation to the optimal contract. For XOS functions, they give a poly-time constant approximation with value and demand queries. We show that with value queries only, one cannot get any constant approximation. In the multi-action setting, the project is delegated to a single agent, who can take any subset of a given set of actions. Here, a success probability function maps any subset of actions to a probability of the project’s success. Dütting et al. [2021a] showed a poly-time algorithm for computing an optimal contract for gross substitutes success probability functions, and showed that the problem is NP-hard for submodular functions. We further strengthen this hardness result by showing that this problem does not admit any constant factor approximation. Furthermore, for the broader class of XOS functions, we establish the hardness of obtaining a n^{-1/2+ε}-approximation for any ε > 0. 

   more » « less
2. Learning in Online Principal-Agent Interactions: The Power of Menus

   https://doi.org/10.1609/aaai.v38i16.29691  

   Han, Minbiao; Albert, Michael; Xu, Haifeng (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study a ubiquitous learning challenge in online principal-agent problems during which the principal learns the agent's private information from the agent's revealed preferences in historical interactions. This paradigm includes important special cases such as pricing and contract design, which have been widely studied in recent literature. However, existing work considers the case where the principal can only choose a single strategy at every round to interact with the agent and then observe the agent's revealed preference through their actions. In this paper, we extend this line of study to allow the principal to offer a menu of strategies to the agent and learn additionally from observing the agent's selection from the menu. We provide a thorough investigation of several online principal-agent problem settings and characterize their sample complexities, accompanied by the corresponding algorithms we have developed. We instantiate this paradigm to several important design problems — including Stackelberg (security) games, contract design, and information design. Finally, we also explore the connection between our findings and existing results about online learning in Stackelberg games, and we offer a solution that can overcome a key hard instance of previous work. 

   more » « less
3. Contract Design for Afforestation Programs

   Immorlica, Nicole; Li, Wanyi; Lucier, Brendan (July 2020, AI For Social Good Workshop)

   Trees on farms provide environmental benefits to society and improve agricultural productivity for farmers. We study incentive schemes for afforestation on farms through the lens of contract theory, designing conditional cash transfer schemes that encourage farmers to sustain tree growth. We capture the tree growth process as a Markov chain whose evolution is affected by the agent’s (farmer) actions – e.g., investing costly effort or cutting the tree for firewood. The principal has imperfect information about the agent’s costs and actions taken, and wants to maximize long-run tree survival with minimal payment. We show how to calculate the optimal contract structure in our model: notably, it can involve time-varying payments and may incentivize the agent to join the program but abandon it prematurely. 

   more » « less
4. A Truthful Cardinal Mechanism for One-Sided Matching

   https://doi.org/10.1137/1.9781611975994.129  

   Abebe, Rediet; Cole, Richard; Gkatzelis, Vasilis; Hartline, Jason D. (January 2020, ACM-SIAM Symposium on Discrete Algorithms)

   We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of n agents needs to be matched to a set of n heterogeneous items. Each agent i has a value vij for each item j, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the ordinal preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full cardinal preferences of the agents, i.e., all of the vij values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest. 

   more » « less
5. Canals, climate, and corruption: The provisioning of public infrastructure under uncertainty

   https://doi.org/10.1111/ecpo.12196  

   Vallury, Sechindra; Leonard, Bryan (July 2021, Economics & Politics)

   null (Ed.)

   We develop a two-stage model to study the strategic interaction between a politician (the principal) and a bureaucrat (the agent) over the level of infrastructure provision with uncertainty about possible weather shocks. The bureaucrat chooses how much effort to contribute to infrastructure maintenance and the politician offers either a lump-sum wage (non-corrupt) contract or proportional bribe (corrupt) contract to induce effort. The degree of uncertainty about weather shocks, the size of the fixed wage, and the level of external monitoring to detect corruption all interact to affect (a) the politician's choice of contract and (b) whether this choice improves infrastructure outcomes. Our results suggest that curbing corruption is most likely to yield improvements in infrastructure provision when climate uncertainty is low and when bureaucratic wages are relatively high. If climate uncertainty is high, increasing monitoring has an unambiguous negative effect on infrastructure provision. Previous literature has focused either on public goods provision but not corruption or on bribery in a regulatory context that lacks public goods provision. We extend both literatures by analyzing how bribes between government officials affect a principal's ability to more effectively incentivize public goods provision by her agent. 

   more » « less