we-solve (beta)

Econ-22 · economics · computer science · Computational economics

Strongly polynomial computation of an optimal finite contract

LLM status Open unverified

Statement

ECON-011 | P | Explicit published open question, at source date

Definitions and formal target

A risk-neutral principal offers nonnegative payments $t_j$ for outcomes $j=1,\ldots,m$. Hidden action $a\in\{1,\ldots,n\}$ has cost $c_a\geq0$ and outcome probabilities $q_{aj}$; one action has zero cost. Principal rewards are $r_j\geq0$. All data are rational and ties favor the principal.

\[ \max_{a,t\geq0}\sum_jq_{aj}(r_j-t_j) \quad\text{subject to}\quad \sum_jq_{aj}t_j-c_a\geq\sum_jq_{bj}t_j-c_b\quad\forall b. \] Does this optimization admit a strongly polynomial algorithm: polynomially many arithmetic operations in $n,m$, independent of numerical bit lengths, with intermediate encodings polynomial in input length?

Clarifications and required assumptions

For every action $a$, $q_{aj}\geq0$ and $\sum_jq_{aj}=1$. Both parties maximize expected monetary payoff. Limited liability is $t_j\geq0$. The zero-cost action provides an outside option of at least zero because payments are nonnegative. Weak incentive inequalities are valid under the stated principal-favorable tie rule. An action that cannot be induced is omitted from optimization. "Strongly polynomial" bounds arithmetic-operation counts by a polynomial in $n,m$ and requires polynomial-size intermediate rational encodings; it does not mean total bit runtime ignores the cost of reading the input.

Variants and changes of scope

Regularity. Fix a precise restriction on $q,c,r$ before asking for a restricted algorithm. Fixed dimension. Fix $n$ or $m$ independently of input length; this is another complexity regime. Participation/ties. A positive reservation utility or adversarial tie-breaking changes the program and may require strict inducement. Large outcome space. An implicitly encoded outcome space is not the explicit $n\times m$ input here. General strongly polynomial linear programming would imply a solution, but the source does not establish an equivalence.

Audit conclusion and source relationship

The source explicitly asks the strongly polynomial question after stating ordinary polynomial-time solvability. The revised citation pins the checked 2024 preprint; it avoids treating ambiguous journal-year metadata as the date of that version.

References and exact source roles

[S1] Paul Dütting, Michal Feldman, and Inbal Talgam-Cohen (2024 preprint). Algorithmic Contract Theory: A Survey. arXiv:2412.16384v1, 20 December 2024. Journal DOI: 10.1561/0400000113; Foundations and Trends in Theoretical Computer Science 16(3--4), 211--412. The date here identifies the checked preprint, without conflating journal-year conventions.

Verified locator / source role: Section 3.1, computational discussion immediately after Observation 3.3.

https://arxiv.org/html/2412.16384v1

Common conventions: Additional-source status and mathematical conventions

Of the 100 supplied ECON entries, 65 distinct problems appear here; 32 close matches refine earlier entries, and three duplicate questions map to existing entries. Appendix app:audited-crosswalk lists every destination. The attachment's P/R/S/U distinctions and source audits are retained. Its precise mathematical formalizations are editorial unless the individual audit says otherwise. Candidate subsidy targets ECON-004--006 retain their U flags; the resolved approval-core question ECON-007 updates OP-0202 above. The following supplied conventions govern both this part and the attributed ECON refinements elsewhere in the catalogue, subject to local restrictions.

Parameterized questions. A problem family lists inputs that must be fixed before an instance is evaluated: population, horizon, policies, information, data law, model class and welfare weights. These are required choices, not quantities the citations are assumed to specify. Undefined applications should not be treated as identified estimands.

Indices and integrability. Sets of agents, firms and regions are finite unless a population measure is explicitly used. $i,j$ index units, $r$ regions, $t$ dates and $h$ horizons. $\mathbb E$ and $\Pr$ refer to the declared population and law; $\mathbf1\{A\}$ is an indicator. Every displayed expectation and discounted sum needs existence in the stated domain. Infinite horizons use a discount in $(0,1)$ and a convergence condition; finite horizons may use discount one.

Optimization and existence. A displayed $\max$, $\min$, or $\arg\max$ is conditional on attainment. For finite feasible menus this is immediate; general spaces need continuity and compactness/coercivity or another existence argument. Without attainment, the target is the supremum/infimum and arbitrarily near-optimal feasible choices. $\inf\varnothing=+\infty$. Empty feasibility and an unidentified target are different issues.

Potential outcomes. $Y_i(z)$ is the outcome under a specified intervention, not the observed conditional mean among people choosing $z$. In binary comparisons $\Delta Y_i=Y_i(1)-Y_i(0)$. Specify assignment, treatment versions, compliance, information and observation horizon. Interference is allowed under a full policy vector; compressed exposure notation needs a justified mapping. No interference, consistency and overlap are substantive assumptions, not automatic consequences of notation.

Populations and observation. Fix baseline eligibility and population weights. Conditioning on post-policy employment, survival, relocation or program uptake can change the population being compared. Death is not ordinary loss to follow-up; outcomes truncated by death need a composite convention, joint survival target, or explicitly defined survivor stratum. Fertility-changing interventions need a population functional rather than an unexplained fixed descendant cohort. Measurement and missingness models must be supplied.

Identification. A structural model $m\in\mathcal M$ implies observable law $P_m$ and target $\theta(m)$. Identification means \[ P_{m_1}=P_{m_2}\ \Longrightarrow\ \theta(m_1)=\theta(m_2) \quad\text{for all }m_1,m_2\in\mathcal M . \] Without identification, the target is \[ \Theta(P;\mathcal M)=\{\theta(m):m\in\mathcal M,\ P_m=P\}. \] Writing $\theta(P)$ before establishing identification can hide incompatible latent models. Confidence sets additionally need a sampling law, confidence level, asymptotic sequence and uniformity class. Point identification, coverage and informative precision are separate properties.

Mediation. Total effects of randomized assignment are distinct from cross-world natural indirect effects. Belief/effort-channel effects require a meaningful mediator intervention and additional measurement, exclusion or mediation assumptions. Randomization of the initial policy alone does not supply those assumptions. Report bounds or interventional alternatives when the stronger target is unsupported.

Equilibrium. A counterfactual $W(z)$, $p(z)$, or $\mu_t^z$ requires individual optimization, feasibility, government/resource budgets, market clearing and state-transition laws. State equilibrium existence and selection, or report ranges over compatible equilibria. Initial-state integration includes subsequent endogenous transitions; current-state integration must use the policy-dependent distribution. Reduced-form invariance after policy is not assumed.

Welfare accounts. Scores, utility, health, dollars and ecological quantities require explicit conversion before addition. Fees, taxes, subsidies, wages and extortion payments are transfers between parties; distributional weights can make them welfare relevant, but their face value is not automatically a resource loss. State ownership, geographic boundaries, foreign-income weights and fiscal finance. Do not add profits to household welfare already including dividends, or count land capitalization and the underlying benefit twice. A benefit-cost expression must distinguish gross benefits from net welfare and subtract every real cost exactly once.

Derivatives and risk. Log derivatives require positive arguments; local responses require admissible perturbations and specified equilibrium branches. Differentiation under expectations needs regularity/domination, and boundaries may allow only one-sided derivatives. Risk uses a specified law; ambiguity uses a declared nonempty law set on a common history space. Adaptive policies must be nonanticipative. A robust criterion is an editorial choice unless attributed explicitly.

Scope overlaps. Allocation, collective choice, contracts, household bargaining and coordinated policy overlap economics with optimization and game theory. They are retained because they appeared in the original catalogue; no claim of a strictly game-theory-free selection is made.

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Econ-22-A2 · Exploration · LLM-generated · gpt 6 astra pro ·

GPT 6 Astra Pro attempt on Econ-22

Strongly polynomial optimal finite contracts

D86-21: research attempt and adversarial verification

9 October 2026

Tools. Web browsing: YES. Exact rational computation: YES.

FORMAL RESTATEMENT

Fix integers $n,m\ge1$. The explicit rational input consists of $q_{aj}\ge0$ with $\sum_{j=1}^m q_{aj}=1$ for each action $a\in[n]$, costs $c_a\ge0$ with $\min_a c_a=0$, and rewards $r_j\ge0$. A contract is $t\in{\mathbb{R}}_+^m$. The agent maximizes $q_a\cdot t-c_a$; among maximizing actions, the agent chooses one maximizing the principal's payoff $q_a\cdot(r-t)$. Thus the target is \[ \max_{a\in[n],\ t\ge0}q_a\cdot(r-t) \quad\text{subject to }(q_a-q_b)\cdot t\ge c_a-c_b\quad(b\in[n]). \] An exact algorithm must output a rational optimal contract and an action realizing this objective. The question is whether one algorithm uses at most $\operatorname{poly}(n,m)$ arithmetic operations and comparisons, independently of numerical bit lengths, while every intermediate rational encoding has length polynomial in the total input length $L$.

Conventions and stress points. The action and outcome arrays are explicit. The $a=b$ incentive constraint is redundant. Empty feasibility for a particular action is allowed; that action is omitted. Strong polynomiality does not eliminate the cost of reading or writing binary numbers. Principal-favorable ties are essential for using weak inequalities and for attainment at incentive boundaries. Individual rationality follows from the zero-cost action and nonnegative payments. No strictly positive reservation utility or strict implementation requirement is added.

QUICK LITERATURE/CONTEXT CHECK

Paul Dütting, Michal Feldman, and Inbal Talgam-Cohen, Algorithmic Contract Theory: A Survey, arXiv:2412.16384v1 (20 December 2024), explicitly asks the strongly polynomial question in Section 3.1 after Observation 3.3. That section presents the linear-programming approach; Section 3.3 treats binary-action and binary-outcome cases. Checked primary survey: https://arxiv.org/html/2412.16384v1.

The proofs below reproduce the LP reduction and establish restricted algorithms and a specified-action embedding. They do not claim that the survey proves an equivalence between unrestricted optimal-contract computation and general linear programming, nor that the present embedding establishes such an equivalence.

ATTACK PLAN

Proof track. Isolate minimum-payment implementation for each action, derive sparse optimal witnesses, and seek a dimension-independent basis-selection method. Check the two-action and fixed-dimension cases explicitly.

Disproof track. Test whether optima can fail to exist under favorable ties; try to encode arbitrary rational inequalities inside a target action's incentive constraints; examine whether such an encoding actually forces a global optimal-contract algorithm to solve the target problem.

Tools and roles. Rational LP gives ordinary polynomial-time computation; compact objective sublevels prove attainment; nonnegative orthants exclude lineality; active-constraint rank bounds payment support; determinant bounds control exact encodings; likelihood-ratio comparisons solve two actions; zero-sum row embeddings enforce probability normalization; explicit tie comparisons distinguish inducibility from principal-optimal behavior.

Tiny cases. With one action, its cost is zero and $t=0$ is optimal. With one outcome all action distributions coincide, so $t=0$ and a zero-cost action are optimal. If every cost is zero, $t=0$ attains $\max_a q_a\cdot r$, an upper bound on every nonnegative-payment contract's profit.

WORK

Theorem (LP characterization and attainment): For each action $a$, let \[ C_a=\min\{q_a\cdot t:t\ge0,\ (q_a-q_b)\cdot t\ge c_a-c_b\ (b\ne a)\}, \] with $C_a=+\infty$ if the feasible set is empty. Every finite $C_a$ is attained. The optimal principal payoff is \[ \max_{a:C_a<\infty}(q_a\cdot r-C_a). \] It is attained by a rational contract and computable in polynomial bit time using rational linear programming.
Proof: For a fixed feasible $a$, a payment on an outcome with $q_{aj}=0$ can be set to zero. Its contribution to every incentive row is $-q_{bj}t_j\le0$, so removing it weakly increases the row's left side; the objective is unchanged. Let $t^0$ be any feasible payment vector after these deletions and set $B=q_a\cdot t^0\ge0$. Among feasible vectors with the same zero coordinates and objective at most $B$, every remaining coordinate satisfies $0\le t_j\le B/q_{aj}$. This is a nonempty closed bounded set in a finite-dimensional space. The continuous objective therefore attains its minimum there, which is also its minimum over the original feasible set: any better original vector could be cleaned in the same way and would belong to this set.

For any fixed $t$, precisely the actions satisfying the weak inequalities are agent best responses. Maximizing over those feasible actions yields exactly the principal-favorable tie rule. Hence maximizing over all feasible pairs $(a,t)$ is equivalent to the original behavioral problem. Optimizing first over $t$ for each $a$ yields the displayed finite maximum. A zero-cost action is feasible at $t=0$, so the set being maximized over is nonempty and the optimal profit is nonnegative.

Use the rational LP theorem in the following form: a finite-dimensional linear program with rational coefficients can, in time polynomial in its binary encoding length, be classified as infeasible, unbounded, or finite-optimal; in the last case it returns a rational optimal solution of polynomial encoding length. Here each program has $m$ nonnegative variables and $n-1$ rational incentive rows, hence encoding length polynomial in $L$. Its objective is nonnegative on the feasible set, so it is never unbounded below. The attainment argument verifies that a finite infimum is an optimum. Solving the $n$ programs and comparing their rational objective values proves the ordinary bit-complexity assertion. This theorem does not bound the arithmetic count independently of coefficient lengths. ∎

Theorem (Sparse optimal payments and fixed dimensions): Whenever an action is inducible, one minimum-payment contract for it has at most $n-1$ positive coordinates. It can be chosen as a vertex of its feasible payment polyhedron. For each fixed $n$, and separately for each fixed $m$, optimal contracts have strongly polynomial arithmetic algorithms, with the exponent permitted to depend on that fixed parameter.
Proof: Set coordinates with $q_{aj}=0$ to zero, as above. The minimum-payment face with these zero coordinates is compact: if $C_a$ is the minimum, all remaining coordinates are bounded by $C_a/q_{aj}$. A nonempty compact polytope has an extreme point. One elementary proof is to successively minimize each coordinate on the current compact minimizing face; after all coordinates have been fixed the remaining point is extreme. Let $t$ be such a point. It is also a vertex of the original feasible payment polyhedron: if it were a strict convex combination of two feasible points, both would have the same optimal objective, and both would have zero in every coordinate where $t$ is zero and nonnegativity applies. They would therefore belong to the compact optimal face, contradicting extremality.

Let $J=\{j:t_j>0\}$ and $k=|J|$. On these coordinates the tight incentive rows must have rank $k$. Otherwise choose a nonzero direction supported on $J$ annihilating every tight row. Sufficiently small moves in both signs preserve positive coordinates and all strictly slack rows, producing two distinct feasible points with midpoint $t$. This contradicts the vertex property. There are at most $n-1$ incentive rows, so $k\le n-1$.

For fixed $n$, enumerate supports $J$ with $|J|=k\le\min(m,n-1)$ and choices of $k$ incentive rows. Solve the square system making those rows tight, reject singular systems, set coordinates outside $J$ to zero, and check feasibility exactly. Include the all-zero candidate. At least one optimal vertex appears, by the rank argument. The number of candidates per target action is at most \[ \sum_{k=0}^{\min(m,n-1)}\binom{m}{k}\binom{n-1}{k}, \] which is polynomial in $m$ when $n$ is fixed. The same expression is polynomial in $n$ when $m$ is fixed. Each candidate uses polynomially many arithmetic operations for elimination, verification, and objective comparison; the additional factor $n$ for target actions remains polynomial. Clearing denominators and applying the determinant expansion bounds every candidate numerator and denominator by a polynomial number of input bits. Exact elimination can be performed with these polynomial-size intermediate encodings. The enumeration is not polynomial with a parameter-independent exponent when both $n$ and $m$ vary. ∎

Theorem (Two-action formula): Suppose the actions are $0,1$, with $c_0=0<c_1=c$. Write $d_j=q_{1j}-q_{0j}$ and $J=\{j:d_j>0\}$. If $J=\varnothing$, action 1 is not inducible. Otherwise \[ C_1=c\min_{j\in J}\frac{q_{1j}}{d_j}. \] A minimizing index $j^*$ yields the contract $t_{j^*}=c/d_{j^*}$ and all other payments zero. The global optimum is the larger of $q_0\cdot r$ and $q_1\cdot r-C_1$. The arithmetic count is $O(m)$, and encodings have polynomial bit length.
Proof: The sole constraint for action 1 is $\sum_jd_jt_j\ge c$. If no $d_j>0$, its left side is nonpositive. If there are positive coefficients, deleting payments with $d_j\le0$ weakly improves feasibility and weakly reduces expected payment. For a feasible vector supported on $J$, \[ q_1\cdot t =\sum_{j\in J}\frac{q_{1j}}{d_j}d_jt_j \ge\left(\min_{j\in J}\frac{q_{1j}}{d_j}\right)c. \] The stated single payment attains equality and binds the incentive constraint. Action 0 has minimum payment zero. Theorem Theorem (LP characterization and attainment) gives the comparison of profits, including the favorable tie rule. Computing the ratios and finding their minimum takes $O(m)$ arithmetic operations. The formula uses only a constant number of operations on each rational coefficient. If both costs are zero, the all-zero contract is optimal, as checked above. ∎

An exact embedding into specified-action inducibility

The following reduction explains why the fixed-action LP need not be combinatorially simple. Its limited conclusion is important.
Proposition (Embedding arbitrary nonnegative-variable feasibility): Given $A\in{\mathbb{Q}}^{r\times d}$ and $b\in{\mathbb{Q}}^r$, $d\ge1$, one can construct a rational contract instance with strictly positive outcome probabilities and nonnegative costs, one of them zero, together with a distinguished action $*$, such that \[ \exists x\in{\mathbb{R}}_+^d:Ax\ge b \quad\Longleftrightarrow\quad \text{action $*$ is weakly inducible}. \] The construction uses polynomially many arithmetic operations and polynomial-size rational encodings. It concerns a specified action, not selection of a globally optimal action.
Proof: Append the $d$ inequalities $x_j\ge0$ to the row list; denote the resulting pairs by $(a_\rho,b_\rho)$, where $a_\rho\in{\mathbb{Q}}^d$. For each row form \[ \widetilde a_\rho=(a_{\rho1},\ldots,a_{\rho d},-\sum_{j=1}^d a_{\rho j})\in{\mathbb{Q}}^{d+1}, \] whose coordinates sum to zero. Put $m=d+1$, $q_*=(1/m,\ldots,1/m)$, and \[ \lambda_\rho=\frac{1}{2m(1+\max_j|\widetilde a_{\rho j}|)},\qquad q_\rho=q_*-\lambda_\rho\widetilde a_\rho. \] Every $q_\rho$ has sum one and each coordinate is strictly larger than $1/(2m)$, so it is a probability vector with full support. Let \[ C=\max(0,\max_\rho\lambda_\rho b_\rho),\quad c_*=C,\quad c_\rho=C-\lambda_\rho b_\rho\ge0. \] If $C=0$, the distinguished action has zero cost. If $C>0$, a maximizing row action has zero cost. Set rewards to zero, since they play no role in inducibility.

The distinguished action's inequality against $\rho$ is exactly \[ \lambda_\rho\widetilde a_\rho\cdot t\ge\lambda_\rho b_\rho, \quad\text{or}\quad a_\rho\cdot x\ge b_\rho, \qquad x_j=t_j-t_m. \] The appended rows imply $x_j\ge0$. Thus any implementing $t\ge0$ yields a solution of the original system. Conversely, a feasible nonnegative $x$ yields an implementing contract by $t_j=x_j$ for $j\le d$ and $t_m=0$. There are $r+d+1$ actions and $d+1$ outcomes. The displayed formulas use polynomially many rational sums, products, comparisons, and divisions, with denominator bit lengths bounded polynomially in the input length.

In fact, for fixed $x$ every representing payment vector has $t_j=x_j+t_m$ and $t_m\ge0$, so $q_*\cdot t=(\sum_jx_j)/m+t_m$. Consequently minimum payment for $*$ corresponds to minimizing $\sum_jx_j$ over the original nonnegative feasible set, with $t_m=0$ at an optimum. ∎

Why this is not a full hardness equivalence. A globally optimal contract is allowed to induce another action. In the construction above, rewards are zero, so a zero-payment contract inducing a zero-cost action is always globally optimal, regardless of whether $*$ is inducible. Thus this particular construction cannot use a global optimal-contract oracle to decide the original feasibility question. A reward/implementation gadget forcing the required selection, without introducing an easier incentive instrument, has not been proved here. Treating Proposition Proposition (Embedding arbitrary nonnegative-variable feasibility) as an equivalence for the question in Section 1 would be an invalid quantifier substitution.

VERIFICATION

Exact two-action test. Let $q_0=(3/4,1/4)$, $q_1=(1/4,3/4)$, $c_1=1/4$, and $r=(0,2)$. The formula gives $t=(0,1/2)$, expected payment $C_1=3/8$, and agent utilities $1/8$ under both actions. Principal profits at this contract are $3/8$ for action 0 and $9/8$ for action 1, so favorable ties select action 1. The zero contract gives profit $1/2$. The optimal profit is therefore $9/8$. 
\begin{lstlisting}[language=Python] from fractions import Fraction as F q0=(F(3,4),F(1,4)); q1=(F(1,4),F(3,4)) c=F(1,4); r=(F(0),F(2)); t=(F(0),F(1,2)) dot=lambda x,y:sum(a*b for a,b in zip(x,y)) assert dot(q0,t)==dot(q1,t)-c==F(1,8) assert dot(q1,t)==F(3,8) assert dot(q0,tuple(r[j]-t[j] for j in range(2)))==F(3,8) assert dot(q1,tuple(r[j]-t[j] for j in range(2)))==F(9,8) assert dot(q0,r)==F(1,2) print('two-action contract: exact utility, payment, and tie checks passed') \end{lstlisting}

Adversarial audit. Zero-probability outcomes are removed only for the fixed target action, where their incentive coefficients are nonpositive. The optimum-face argument separately proves existence of a vertex before enumerating bases; sparsity alone would not justify enumeration of tight rows. The zero-cost action need not be unique. Rewards being nonnegative does not make every action inducible. The embedding explicitly preserves row sums, positivity, and the zero-cost convention, but does not preserve the identity of the globally optimal action. No iteration bound is inferred from output sparsity.

FINAL

LABEL: UNRESOLVED.

Strongest fully proved partial result. Optimal contracts are attained and rational, and ordinary polynomial bit-time computation reduces to $n$ explicit LPs. There are sparse optimal contracts with at most $n-1$ positive payments; fixed-action-count and fixed-outcome-count versions have strongly polynomial arithmetic algorithms. Two actions admit the displayed closed form. Arbitrary rational linear feasibility embeds into specified-action inducibility, with its scope limitation proved explicitly.

Exact first gap. No parameter-independent polynomial arithmetic bound is established for selecting optimal payment bases across all actions when both $n$ and $m$ vary. Conversely, the specified-action embedding does not force a global contract optimizer to expose feasibility of that action and therefore does not prove an equivalence or an impossibility result for the literal question.

Three next targets. First, exploit the probability-difference structure to build a polynomial arithmetic basis-selection algorithm that avoids the enumeration in Theorem Theorem (Sparse optimal payments and fixed dimensions). Second, test a reward gadget that makes a distinguished action globally optimal exactly when an encoded feasibility system has a solution, while preserving limited liability and zero-cost participation. Third, seek a strongly polynomial dual separation method for the family of implementation LPs using their common probability matrix rather than solving them independently.

Minimal obstruction. A counterexample cannot simply be an instance without an optimum: attainment is proved. Any hard family escaping the restricted algorithms must allow both the number of actions and the number of outcomes to grow. Superpolynomial behavior of one LP method, or large magnitudes of optimal payments, is not by itself a disproof of a strongly polynomial arithmetic algorithm.

Go to contribution →

Econ-22-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-22

Exact contracts on an affine line of outcome distributions

Problem D86-21. Status: unresolved. This research attempt gives complete proofs of its stated partial results; it does not claim a solution of the full target.

Recap and what is already known

Action $a$ has rational cost $c_a\geq0$ and outcome distribution $q_a$; one action has zero cost. The principal's rational outcome rewards $r_j$ are nonnegative. A contract $t\geq0$ pays $t_j$ at outcome $j$. The agent maximizes $q_a\cdot t-c_a$, with ties favoring the principal. The target asks for an optimal contract with a number of arithmetic operations polynomial in the numbers $n,m$ of actions and outcomes, independent of numeric bit lengths, and polynomial-size intermediate encodings.

The survey [survey], Section 3.1, gives the minimum-payment LP approach, ordinary polynomial-time solvability, and the at-most-$n-1$-nonzero-payments observation. Those facts are not novel contributions of this attempt. We rederive the support fact and develop an explicit strongly polynomial algorithm when the distributions lie on an affine line. This restriction allows arbitrarily many actions and outcomes but does not cover general technologies.

Why sparse payments alone do not settle the target

For a candidate action $a$, put $B_{bj}=q_{aj}-q_{bj}$ and $d_b=c_a-c_b$ for $b\ne a$. Its minimum-payment problem is \[ \min q_a\cdot t\quad\text{subject to }Bt\geq d,\quad t\geq0. \]
Lemma (The known support bound, with degeneracy allowed): If action $a$ is weakly inducible, its minimum-payment problem has an optimal solution with at most $\operatorname{rank}(B)\leq n-1$ positive coordinates.
Proof: The objective is nonnegative on the feasible set. A bounded-below linear objective on a nonempty polyhedron attains its infimum; apply the standard finite-dimensional LP attainment theorem. Among optima choose one, $t$, with minimum support. If its supported columns of $B$ are dependent, choose a nonzero vector $z$ supported there with $Bz=0$. For sufficiently small positive and negative $\epsilon$, $t+\epsilon z$ remains nonnegative and feasible. Optimality forces $q_a\cdot z=0$, since otherwise one sign improves the objective. Choose a sign and increase its magnitude until the first positive coordinate becomes zero. Such a finite endpoint exists in at least one direction because $z\ne0$. This gives another optimum with strictly smaller support, a contradiction. Thus the supported columns are independent. ∎
Proposition (Fixed number of actions): For every fixed $n$, an optimal finite contract can be found by a strongly polynomial algorithm whose arithmetic-operation count is $m^{O(n)}\operatorname{poly}(n)$ and whose intermediate encodings are polynomial in input length. This is not a uniform strongly polynomial bound when $n$ varies.
Proof: For each $a$, the feasible polyhedron lies in the nonnegative orthant and therefore has no lines. A nonempty optimal face has a vertex. At a vertex with $k$ positive coordinates, the active incentive inequalities restricted to these coordinates must have rank $k$; otherwise a small two-sided feasible perturbation contradicts being a vertex. In particular $k\leq n-1$. Enumerate each support of size $k\leq n-1$ and each choice of $k$ incentive rows; solve the resulting square system when nonsingular and check all original inequalities and nonnegativity. Include $t=0$ separately. At least one optimal vertex is encountered for every inducible action. Gaussian elimination on matrices of size at most $n-1$ and all comparisons use a number of operations bounded as stated. Cramer's-rule determinant bounds give polynomial input-bit length for all candidates. Select the action/payment candidate maximizing $q_a\cdot(r-t)$.

To justify the tie rule, every candidate action is a utility maximizer for its contract. If another tied action would give the principal more, principal-favorable tie breaking realizes at least the candidate payoff. Conversely every actual contract/action outcome is feasible in the corresponding LP. Thus maximizing candidate payoffs attains exactly the optimal realizable payoff. ∎

An unrestricted-outcome but one-dimensional technology

Theorem (Affine-line contract algorithm): Suppose the distributions have a rational representation \[ q_a=q^0+\theta_a d,\qquad \sum_jd_j=0, \] where all $q_a$ are probability vectors. If $d\ne0$, an optimal contract can be computed using $O(n^2+nm)$ arithmetic operations, with polynomial-size intermediate rational encodings. At most one outcome receives a positive payment. If all $q_a$ coincide, the zero contract is optimal. The affine-line hypothesis itself can be tested, and such a representation found if it exists, with $O(nm)$ arithmetic operations.
Proof: First take $d\ne0$ and set $x=d\cdot t$. The incentive inequalities for $a$ reduce exactly to \[ (\theta_a-\theta_b)x\geq c_a-c_b\quad\text{for every }b. \] Intersect these half-lines to obtain a closed interval $I_a$, possibly empty or unbounded. A zero coefficient with a positive right side makes it empty. This takes $O(n)$ operations for each $a$. Since $d$ is nonzero and sums to zero, both $\{j:d_j>0\}$ and $\{j:d_j<0\}$ are nonempty. Define \[ \alpha_a^+=\min_{d_j>0}\frac{q_{aj}}{d_j},\qquad \alpha_a^-=\min_{d_j<0}\frac{q_{aj}}{-d_j}. \] Both numbers are nonnegative. For $x\geq0$, every $t\geq0$ with $d\cdot t=x$ satisfies $q_a\cdot t\geq\alpha_a^+x$: for $d_j>0$ this holds termwise; for $d_j\leq0$, $q_{aj}\geq0\geq\alpha_a^+d_j$. Equality is achieved by selecting a minimizing outcome $j$ and setting $t_j=x/d_j$, all other payments zero. For $x\leq0$ the analogous bound and one-outcome construction give minimum payment $\alpha_a^-(-x)$. In particular at $x=0$ the zero contract achieves minimum payment zero. Thus the exact minimum-payment cost as a function of $x$ is \[ C_a(x)=\begin{cases}\alpha_a^+x,&x\geq0,\\ \alpha_a^-(-x),&x\leq0.\end{cases} \] It is nondecreasing away from zero on either half-line. Consequently choose $x_a=0$ if $0\in I_a$, the left endpoint if $I_a\subset(0,\infty)$, or the right endpoint if $I_a\subset(-\infty,0)$. The endpoint is finite whenever needed. This remains optimal if a slope vanishes. Realize $x_a$ by the one-outcome payment described above, calculate $q_a\cdot r-C_a(x_a)$, and maximize over nonempty $I_a$. The preceding proposition's tie argument applies unchanged and proves global optimality. There is at least one nonempty interval because zero payment induces a minimum-cost action.

All intervals require $O(n^2)$ comparisons and divisions; all slope minima, rewards, and output comparisons require $O(nm)$ more. Endpoints are ratios of input costs and $\theta$ differences, and payments are products and ratios of a bounded number of these rational quantities. Sums in rewards have at most $m$ terms. Their encodings are polynomial in total input length.

For recognition, choose $q^0$ as one input row. If every row is equal, there is no variation in expected payment or reward across actions. A minimum-cost action is always chosen, and zero payment maximizes principal payoff. Otherwise choose a nonzero row difference $d=q_b-q^0$, and one coordinate $j_0$ with $d_{j_0}\ne0$. Set $\theta_a=(q_{aj_0}-q^0_{j_0})/d_{j_0}$ and check every coordinate of $q_a=q^0+\theta_a d$. This proves and tests the hypothesis using $O(nm)$ operations, and the same encoding bounds apply. ∎

Example (A checked instance with interior action): Let the two outcome rewards be $(0,10)$ and let success probabilities and costs of the three actions be $(0,0),(1/2,1),(1,3)$. The minimum payments for the three actions are respectively $0,1,4$ in expectation: inducing the middle action requires success-minus-failure payment in $[2,4]$, and inducing the high action requires it at least $4$. The corresponding maximum principal payoffs are $0,4,6$. A payment of $4$ on success and zero on failure is optimal; the high and middle actions give the agent equal utility $1$, and principal-favorable tie breaking selects the high action with principal payoff $6$.

Status and first remaining gap

The line hypothesis turns all incentives into constraints on one scalar and makes minimum payments explicit. General rows have several independent directions; neither the support bound nor fixed-$n$ enumeration yields an operation count polynomial jointly in $n,m$. No reduction proving equivalence to general strongly polynomial linear programming is asserted. The first gap is a uniform method for those multidimensional incentive systems.
Finite implementation checks.
As a finite algebraic check, the affine-line algorithm was compared with complete vertex enumeration of every action's payment LP on 100 rational four-action, three-outcome instances, using exact fraction arithmetic and random seed $20261009$. Costs included a zero-cost action and rewards were nonnegative integers. Every optimum and incentive-feasibility check agreed. This test supports the implementation but does not replace the proof.

References

  • [survey] P. Dütting, M. Feldman, and I. Talgam-Cohen, Algorithmic Contract Theory: A Survey, arXiv:2412.16384v1 (2024), Section 3.1, Observations 3.3--3.4 and the intervening computational discussion; Section 3.3 discusses simpler action and outcome domains. https://arxiv.org/html/2412.16384v1.

Completion Estimate

20%

Go to contribution →