.png){kind=icon}
.png){kind=icon}
Return
Improved Approximation Algorithms for Combinatorial Contracts with Type Constraints
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0215-8_1.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We introduce a multi-agent combinatorial contract design problem with type constraints. A principal assigns a task to agents divided into.k types. Agents of each type decide whether to exert costly effort. The principal's reward is a non-negative, monotone, and submodular function of the agents exerting effort across all types. Extending prior work by Dutting et al. (2023) on the single-agent-per-type (k = n) case, we allow multiple agents per type, where.n denotes the number of agents. We formulate the contract design as a bi-level optimization problem, which we transform into a single-level subset selection problem using backward induction. We provide a parameterized approximation algorithm using value and demand query oracles, achieving approximation ratios approximately 5 times better than Dutting et al. (2023) under suitable parameter settings.
Keywords:
Combinatorial contracts
Principal-agent model
Approximation algorithms
Submodularity
Journal
C
IF:
0
Papers:
24
Citations:
0