Budget-Feasible Contracts
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916810444505088 |
|---|---|
| author | Feldman, Michal Gal-Tzur, Yoav Ponitka, Tomasz Schlesinger, Maya |
| author_facet | Feldman, Michal Gal-Tzur, Yoav Ponitka, Tomasz Schlesinger, Maya |
| contents | The problem of computing near-optimal contracts in combinatorial settings has recently attracted significant interest in the computer science community. Previous work has provided a rich body of structural and algorithmic insights into this problem. However, most of these results rely on the assumption that the principal has an unlimited budget for incentivizing agents, an assumption that is often unrealistic in practice. This motivates the study of the optimal contract problem under budget constraints.
In this work, we study multi-agent contracts with binary actions under budget constraints. Our contribution is threefold. First, we show that all previously known approximation guarantees on the principal's utility extend (asymptotically) to budgeted settings. Second, through the lens of budget constraints, we uncover insightful connections between the standard objective of maximizing the principal's utility and other relevant objectives. Specifically, we identify a broad class of objectives, which we term BEST (BEyond STandard) objectives, including reward, social welfare, and principal's utility, and show that they are all equivalent (up to a constant factor), leading to approximation guarantees for all BEST objectives. Third, we introduce the price of frugality, which quantifies the loss due to budget constraints, and establish near-tight bounds on this measure, providing deeper insights into the tradeoffs between budgets and incentives. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01773 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Budget-Feasible Contracts Feldman, Michal Gal-Tzur, Yoav Ponitka, Tomasz Schlesinger, Maya Computer Science and Game Theory The problem of computing near-optimal contracts in combinatorial settings has recently attracted significant interest in the computer science community. Previous work has provided a rich body of structural and algorithmic insights into this problem. However, most of these results rely on the assumption that the principal has an unlimited budget for incentivizing agents, an assumption that is often unrealistic in practice. This motivates the study of the optimal contract problem under budget constraints. In this work, we study multi-agent contracts with binary actions under budget constraints. Our contribution is threefold. First, we show that all previously known approximation guarantees on the principal's utility extend (asymptotically) to budgeted settings. Second, through the lens of budget constraints, we uncover insightful connections between the standard objective of maximizing the principal's utility and other relevant objectives. Specifically, we identify a broad class of objectives, which we term BEST (BEyond STandard) objectives, including reward, social welfare, and principal's utility, and show that they are all equivalent (up to a constant factor), leading to approximation guarantees for all BEST objectives. Third, we introduce the price of frugality, which quantifies the loss due to budget constraints, and establish near-tight bounds on this measure, providing deeper insights into the tradeoffs between budgets and incentives. |
| title | Budget-Feasible Contracts |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2504.01773 |