Back to search

University of Waterloo

Contracts for Density and Packing Functions

Abstract

dc:description.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. 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. Deo-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 thesis, we answer this open question in positive. Additionally, we provide multiplicative approximation algorithms for functions that are based on hypergraphs and encode packing constraints. This family of functions provides a generalization for XOS functions.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Skitsko, Jacob
Advisor dc:contributor.advisor
  • Pashkovich, Kanstantsin

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/20922

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Skitsko, Jacob. Contracts for Density and Packing Functions. University of Waterloo, 2024. https://hdl.handle.net/10012/20922