CS Paper Radar

The Complexity of Continuous Contract Design over Polymatroids

Max Klimm, Paul Lippke, Philipp Warode

cs.GT ·submitted 2026-11-03 14:04 UTC · v1
theorycode/data

Abstract

We study optimal contracts when an agent allocates continuous effort subject to polymatroid capacity constraints. Effort produces a linear expected reward and incurs a cost. With binary outcomes and limited liability, the principal chooses a single reward share. For linear costs, an optimal contract can be computed in polynomial time. For quadratic costs, the agent has a unique best response computable by polynomially many submodular minimizations, yet optimizing the principal's share is NP-hard even for explicitly represented cut-based rank functions. With $n$ activities, the best-response path can have $2^{n-O(\log n)}$ breakpoints even when each reward coefficient and each rank value is an integer representable in $O(n\log n)$ bits. The construction also answers a question of Allman, Lo, and McCormick on polynomial bit length for source-sink monotone two-parameter minimum cuts. Despite this complexity, an optimal contract for quadratic costs always exists with a share of at most $1/2$. Consequently, $O(1/\varepsilon)$ best-response computations suffice for a $(1-\varepsilon)$-approximation. For rational quadratic costs on explicitly described rational polytopes containing zero, this gives a fully polynomial-time approximation scheme. More generally, a share of at most $1/p$ suffices for continuous convex costs homogeneous of degree $p>1$, on any compact convex action set containing zero. For general convex costs with an exact value and bounded-subgradient oracle, we obtain an oracle approximation scheme using approximate best responses and a supplied lower bound on positive welfare.

Comment
89 pages, 6 figures. The Lean 4 formalization is at https://github.com/philippwarode/contract-design-polymatroids-lean

Closest papers

Nearest neighbours by meaning across the whole index.

Settling the Complexity Landscape of Multi-Agent Contracts with Binary Actions

cs.GT ·2026-09-28 ·Michal Feldman, Maya Schlesinger, Shay Shani
similarity 0.71
Abstract

We study the computational complexity of optimal contract design in the multi-agent binary-action model, focusing on gross-substitutes reward functions and related classes. While additive rewards admit an FPTAS and general submodular rewards admit only constant-factor approximation, the complexity within the intermediate class of gross substitutes has remained largely open. We uncover a fine-grained approximation landscape within this class. We first show that the optimal contract problem is APX-complete even for OXS rewards - a strict subclass of gross substitutes rewards, ruling out a PTAS for gross substitutes unless $\mathsf{P}=\mathsf{NP}$. In contrast, for weighted matroid rank functions (WMRFs) - another natural subclass of gross substitutes - we obtain an EPTAS and show that no randomized FPTAS exists in general. We further identify the special case of partition (weighted) matroid rank functions, for which we obtain an FPTAS. This stands in contrast to the multi-agent multi-action setting, where no PTAS exists even for unweighted partition matroid rank functions. Finally, we consider the broader class of ultra reward functions. While ultra rewards retain the tractability of gross substitutes in a related combinatorial contract model with a single agent, we show a sharp contrast in the multi-agent model: no polynomial-time randomized algorithm using value queries can achieve a $2^{o(n)}$-approximation in expectation. Together, our results reveal several qualitatively distinct computational regimes within and beyond gross substitutes, and identify submodularity as a crucial ingredient for the approximability of multi-agent contracts.

0.32

Approximating Combinatorial Contracts with Arbitrary Costs

cs.GT cs.DS ·2026-09-18 ·Xiaotie Deng, Hanyu Li, Chenghua Liu
theory similarity 0.67
Abstract

We study single-agent combinatorial contracts under linear payments. Under a reward share $α\in[0,1]$, an agent chooses a subset $S$ of $n$ hidden actions, generating reward $f(S)$ at cost $c(S)$, to maximize $αf(S)-c(S)$, while the principal receives $(1-α)f(S)$. For nonnegative additive rewards and monotone supermodular costs, Dütting et al. (SODA 2026) proved an exponential supply-query lower bound for exact optimization and left open whether a representation-independent approximation is possible. We resolve this question in a stronger form, removing all structural assumptions on the cost function: for nonnegative additive rewards, arbitrary normalized nonnegative set costs, and every $\varepsilon\in(0,1)$, we give a deterministic $(1-\varepsilon)$-approximation using $O(n\log(n+1)/\varepsilon)$ supply queries, with query complexity independent of numerical bit lengths and breakpoint separation. More generally, the same guarantee and asymptotic query complexity hold for normalized monotone subadditive rewards and arbitrary normalized nonnegative costs under exact best-response and value-query access. The key idea is a cost-independent, reward-side scale certificate. The algorithm tries all singleton rewards as candidate anchors; one of them brackets the optimal retained share within a factor $n^2$. Geometric search and monotonicity of the induced response reward then yield the approximation without enumerating best-response breakpoints.

0.26

Welfare in Envy-free Contracts: When Agents Have Sparse Interests

cs.GT ·2026-11-08 ·Junjie Chen, Cong Chen, Takuro Yamashita
similarity 0.66
Abstract

We study welfare maximization under envy-free contracts, where a principal assigns tasks and offers success-contingent payments to heterogeneous agents with hidden effort. For unit-demand agents, we establish a sharp complexity boundary: the problem is polynomial-time solvable when each agent is interested in at most two tasks, but NP-hard with at most three interests. Our algorithm analyzes tree-structured dependencies among forced assignments and reduces optimization to maximum-weight independent set in a perfect graph. When agents may receive multiple tasks, no polynomial-time constant-factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Finally, with homogeneous success probabilities and rewards, we establish a welfare- and revenue-preserving equivalence between unit-demand contract design and envy-free pricing. This yields polynomial-time welfare maximization without restricting interests, while revenue maximization remains NP-hard.

0.11

Fair Allocation with Dichotomous Preferences over Item Complements

cs.GT cs.DS ·2026-10-11 ·Soumyajit Pyne, Vignesh Viswanathan, Wenhao Yang, Yair Zick
similarity 0.66
Abstract

We study the problem of fair allocation when agents have dichotomous submodular preferences over groups of, rather than individual, items. These preferences naturally extend existing models, and have a natural interpretation in settings such as course allocation. We show that this seemingly minor extension results in computational intractability barriers: computing a utilitarian or Nash-optimal allocation with item complements is NP-hard. However, when agents' complementary bundles have size at most $k$, there exist poly-time algorithms that compute $\frac1k$-$\texttt{maxUSW}$ allocations and approximate Nash-welfare-maximizing allocations. While PO+EF-1 allocations may not exist in the complementary preference setting, it is possible to compute $\frac1{k+1}$-approximately $\texttt{maxUSW}$ EF-X allocations in polynomial time; furthermore, these allocations offer each agent $i$ a utility of at least $\frac{\texttt{MMS}_i - k}{k+1 + \frac1n}$, where $\texttt{MMS}_i$ is agent $i$'s maximin share guarantee. While the standard dichotomous binary submodular setting admits simple sequential techniques for computing fair and efficient allocations, our results for the complements setting require more complex tools from combinatorial optimization.

0.19

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

cs.DS ·2026-10-19 ·Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee +2 more
theory similarity 0.63
Abstract · 70 Pages

We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $α_{GW}+\tildeΩ(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on $α_{GW}$ is optimal up to $\mathrm{polylog}(d)$ factors. Here, $α_{GW} \approx 0.878$ is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of $α_{GW} + \tildeΩ(1/\sqrt{d})$. Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a ``soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of $1 \pm ε$ while subsampling to an average degree of only $\tilde{O}(1/ε)$. This is the first example of a CSP in which the optimal advantage on degree-$d$ instances is asymptotically smaller than $O(1/\sqrt{d})$ [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of ``nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.

0.15

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.63
Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

0.25

Uniqueness, Proximity, and Scaling in Atomic Splittable Polymatroid Congestion Games

cs.GT ·2026-11-19 ·Tobias Harks
theory similarity 0.63
Abstract · 41 pages

We give a polynomial-time algorithm for exact equilibrium computation in atomic splittable polymatroid congestion games with integral ranks and rational player-specific affine latencies with positive slopes. The algorithm first computes equilibria of associated integer-splittable games, in which demands are allocated in multiples of a common packet size. For arbitrary polymatroid bases, no polynomial-time algorithm for these discrete equilibria was previously known. We provide such an algorithm and use progressively finer packets to recover the continuous equilibrium exactly. Our proof uses the multiple-exchange theorem of Oki and Schwarcz (2025) to obtain two exchange matchings that yield equilibrium proximity under changes of packet sizes and ranks, independently of cost coefficients. We then bound the matching deficiency caused by rank changes and construct compatible submodular rank roundings. Together these give a polynomial-time packet-halving algorithm using polynomially many submodular-function minimizations and exact rational arithmetic. The analysis rests on a uniqueness theorem of independent interest: for arbitrary real polymatroid ranks and continuously differentiable, strictly increasing, convex latencies, we prove uniqueness of equilibria, resolving a previously open problem.

0.37

Computing Equilibria in Integer Programming Games with Shared Constraints

cs.GT math.OC ·2026-10-03 ·Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini
similarity 0.63
Abstract

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

0.41