Title: Contracts for Functions Based on Graphs
| Speaker: | Kanstantsin Pashkovich |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: We study contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a contract with several agents, whose actions the principal is unable to observe. The principal is able to see only the outcome of the agents' collective actions; and the outcome is either a success or failure. All agents that decided to exert effort incur costs, and so naturally all agents expect a fraction of the principal's reward as a compensation. The principal needs to decide what fraction of their reward to give to each agent so that the principal's expected utility is maximized. One of our focuses is on the case when the principal's reward function is supermodular and is based on some graph. Recently, Deo-Campo Vuong et.al. showed that for this problem it is impossible to provide any finite multiplicative approximation or additive FPTAS unless P= NP. On a positive note, Deo-Campo Vuong et.al. provided an additive PTAS for the case when all agents have the same cost. Der-Campo Vuong et.al. asked whether an additive PTAS can be obtained for the general case, i.e for the case when agents potentially have different costs. In this work, we answer this open question in positive.
Joint work with Jacob Skitsko.