we-solve (beta)

Econ-135 · economics · computer science · Computational economics

Approximation frontier for randomized inspection contracts

LLM status Open unverified

Statement

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

Definitions and formal target

Let $A$ be $n$ actions with known costs $c_a\geq0$ and success probabilities $f_a\in[0,1]$, including a null action of cost zero. Success pays the principal one. A committed contract recommends $a$, pays $\alpha\in[0,1]$ upon success if no deviation is detected, and independently draws an undisclosed inspection set $S\subseteq A$ with law $p$. A deviation to $b\ne a$ is detected when $a\in S$ or $b\in S$.

The normalized monotone inspection cost $h:2^A\to\mathbb R_{\geq0}$ has $h(\varnothing)=0$. XOS means $h(S)=\max_{\ell\in K}\sum_{a\in S}w_{\ell a}$ for a finite family with $w_{\ell a}\geq0$; the family is not assumed given explicitly. Subadditive means $h(S\cup T)\leq h(S)+h(T)$. Submodular means $h(S)+h(T)\geq h(S\cup T)+h(S\cap T)$.

Agent utilities and the compliant principal payoff are \[ U_a=\alpha f_a-c_a,\quad U_b=\alpha f_b\Pr_{S\sim p}(S\cap\{a,b\}=\varnothing)-c_b,\quad \Pi=(1-\alpha)f_a-\mathbb E_p h(S). \] Require $U_a\geq U_b$ for every $b$, with ties selecting $a$; let $\Pi^\star$ be the maximum over such contracts. Under the source's exact value/demand oracle and arithmetic conventions, does XOS admit a PTAS, $\Pi\geq(1-\varepsilon)\Pi^\star$, for every fixed $\varepsilon\in(0,1)$? Does the subadditive class admit a constant $C\geq1$ with $\Pi\geq\Pi^\star/C$?

Clarifications and required assumptions

A cost-zero action with zero payment and no inspection provides nonnegative principal payoff, so $\Pi^\star\geq0$; its success probability need not be zero. Inspection is independent of success and the agent acts before observing the draw. The finite distribution over $2^A$ defines the mathematical feasible set; a polynomial algorithm must output an implementable distribution, with a declared support/sampling representation. A value query returns $h(S)$; a demand query at nonnegative prices $q$ maximizes $h(S)-\sum_{a\in S}q_a$. The source treats numeric descriptions as $O(1)$. A rational-input polynomial-bit guarantee is a separately specified extension, not silently supplied by that convention.

Variants and changes of scope

XOS PTAS. For each fixed $\varepsilon\in(0,1)$, require polynomial time in the number of actions under the declared arithmetic/oracle model, with $\Pi\geq(1-\varepsilon)\Pi^\star$. Subadditive approximation. Require $\Pi\geq\Pi^\star/C$ for an absolute $C\geq1$, rather than assuming a PTAS. Oracle strength. The source permits value and demand access; a demand query maximizes $h(S)-\sum_{g\in S}q_g$. Value-only access is a stronger algorithmic request and does not automatically inherit the same open status. Observation. Fully observable inspection, partial observation, and deterministic inspection are different problems.

Audit conclusion and source relationship

The inspection payoff formula matches Section 2. Section 8 explicitly discusses the XOS PTAS and subadditive constant-factor questions. The draft had silently weakened oracle access to value-only; the main question now uses the source's value/demand access model. The payoff guarantee is multiplicative, not an additive approximation.

References and exact source roles

[S1] Tomer Ezra, Stefano Leonardi, and Matteo Russo (2026). Contract Design Beyond Hidden-Actions. SODA 2026, 2113--2133; DOI: 10.1137/1.9781611978971.77. Checked author version: arXiv:2402.16553v2, 26 November 2025.

Verified locator / source role: Section 2 (model and value/demand oracles); Section 8, Discussion (approximation questions). The draft incorrectly called Section 8 a conclusion.

https://arxiv.org/html/2402.16553v2

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 1

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

GPT 6 Astra Ultra attempt on Econ-135

Problem ID: D86-132 Model: GPT 6 Astra Ultra Version: 1

Approximation frontier for randomized inspection contracts

Status. Unresolved for the XOS PTAS and subadditive constant approximation. We solve the additive-cost restriction explicitly, including optimized payment, and identify the cost-minimization oracle that a generalization would require.

Short problem and maintained contract model

There are finitely many actions $A$, $|A|=n$, with success probabilities $f_b\in[0,1]$ and costs $c_b\geq0$, including an action of zero cost. A recommendation $a$, payment $\alpha\in[0,1]$ on success, and hidden independent inspection set $S$ give utilities \[ U_a=\alpha f_a-c_a,\qquad U_b=\alpha f_b{\mathbb{P}}(S\cap\{a,b\}=\varnothing)-c_b\quad(b\ne a). \] Recommendation-favoring ties are allowed. Principal payoff is $(1-\alpha)f_a-{\mathbb{E}} h(S)$. Our restriction is additive inspection cost $h(S)=\sum_{b\in S}w_b$, with known $w_b\geq0$. The $w_b$ denote inspection costs, distinct from action costs $c_b$.

A necessary condition for implementation is $U_a\geq0$, since deviation to a zero-cost action has nonnegative utility. It is also sufficient with unrestricted inspection: inspecting $a$ always gives all deviations utility at most zero. For $\alpha>0$ and $U_a\geq0$, define \[ r_b=\begin{cases} \max\{0,1-(U_a+c_b)/(\alpha f_b)\},&f_b>0,\\ 0,&f_b=0, \end{cases}\qquad b\ne a. \] Each $r_b\in[0,1]$. Incentive compatibility is equivalent to ${\mathbb{P}}(a\in S\text{ or }b\in S)\geq r_b$ for all $b\ne a$.

Theorem (Exact cost for a fixed recommendation and payment): For $\alpha>0$ and $U_a\geq0$, the minimum additive inspection cost is \[ C(a,\alpha)=\min_{0\leq z\leq1} \left\{w_az+\sum_{b\ne a}w_b(r_b-z)_+\right\}. \tag{1} \] A minimum is attained at $z=0$ or at one of the $r_b$. An optimal inspection distribution can be represented with at most $n+1$ sets and found by sorting these requirements.
Proof: Let $z={\mathbb{P}}(a\in S)$. By the union bound, $r_b\leq z+{\mathbb{P}}(b\in S,a\notin S)$, so ${\mathbb{P}}(b\in S)\geq(r_b-z)_+$. Additive expected cost is therefore at least the objective in (1). Conversely, fix $z\in[0,1]$ and draw $U$ uniformly from $[0,1]$. If $U<z$, inspect only $a$. Otherwise inspect precisely those $b\ne a$ with $U<r_b$. Then ${\mathbb{P}}(b\in S)=(r_b-z)_+$ and ${\mathbb{P}}(a\in S\text{ or }b\in S)=\max(z,r_b)\geq r_b$. The construction attains the lower bound. Thresholds at $z$ and the distinct $r_b$ give at most $n+1$ constant-set intervals, an explicit finite distribution. The objective is continuous piecewise linear in $z$ with breakpoints at the $r_b$; above $\max_b r_b$ it is $w_az$, which is nondecreasing. Hence a minimum occurs at zero or a listed breakpoint. ∎
Corollary (A transparent decision rule): If all $r_b$ are positive and $w_a\geq\sum_{b\ne a}w_b$, choosing $z=0$ is optimal. More generally the one-sided slopes of the objective in (1) are obtained from $w_a-\sum_{b:r_b>z}w_b$, with the appropriate equality terms at breakpoints. Thus inspecting the recommended action is worthwhile exactly when it replaces sufficiently costly marginal inspections.
Proof: On every open interval between consecutive requirements, differentiating (1) gives the stated slope. The slope is nondecreasing as $z$ rises. Under the first condition every slope is nonnegative, so zero minimizes the function. The one-sided slope test characterizes minima of this convex piecewise-linear function. ∎
Theorem (Global additive-cost optimization): For rational $f_b,c_b,w_b$, an optimal additive-cost contract can be obtained by a polynomial number of rational arithmetic operations, comparisons, and square-root operations. It has an explicit polynomial-size inspection support and algebraic probabilities of degree at most two. This is an exact algebraic-output result; it does not assert that every optimal payment is rational.
Proof: For a recommendation with $c_a=0$, payment zero and no inspections implement $a$ and give payoff $f_a$, which is an upper bound for any contract recommending $a$. For $c_a>0$, recommendations with $f_a<c_a$ are impossible; otherwise restrict $\alpha$ to $[c_a/f_a,1]$, a compact interval bounded away from zero. For each $b$ with $f_b>0$, the unclipped requirement has form \[ \widetilde r_b(\alpha)=1-f_a/f_b+(c_a-c_b)/(\alpha f_b). \] Collect all points in the payment interval where an unclipped requirement is zero or two unclipped requirements are equal, as well as the endpoints. Every equality is affine in $1/\alpha$, hence has at most one solution unless it holds identically. There are $O(n^2)$ nontrivial partition points, all rational. Inside each resulting interval, signs and ordering of all clipped requirements are constant. By (1), the optimal $z$ is selected from $0$ and the $r_j$. For any such candidate, on a fixed payment interval the inspection cost is $A+B/\alpha$ for explicitly computed rational constants $A,B$. Its principal payoff is \[ F(\alpha)=f_a(1-\alpha)-A-B/\alpha. \] Its derivative is $-f_a+B/\alpha^2$. Thus its maximum on the closed interval is attained at an endpoint, or at $\sqrt{B/f_a}$ if $B>0$ and this point lies inside. Endpoint values use the original continuous clipped formulas, so ties and coincident breakpoints cause no difficulty. The principal maximizes over $z$ candidates as well as $\alpha$, so it suffices to maximize each candidate function separately and compare all resulting values. Repeating for at most $n$ recommendations is polynomial. Formula (1)'s threshold construction then gives a distribution whose endpoints are rational expressions in a rational or quadratic optimal payment; its support is polynomial and its probabilities lie in the same quadratic field. Standard comparison of rational quadratic numbers, for example by sign checks before squaring, is exact and uses polynomial bit complexity for these expressions. An action of zero cost ensures at least one feasible contract and a nonnegative optimum. ∎

Where the XOS and subadditive difficulty enters

For any monotone cost, when a realized set contains $a$, deleting its other elements cannot hurt detection and cannot raise cost. Thus such sets can always be replaced by $\{a\}$. The remaining optimization for fixed $a,\alpha$ is the finite linear program \[ \min_{(p_S)}\sum_Sh(S)p_S,\quad \sum_Sp_S=1,\quad \sum_{S:S\cap\{a,b\}\ne\varnothing}p_S\geq r_b,\quad p_S\geq0. \] A basic optimal solution has at most $n$ positive probabilities: there are the normalization equality and at most $n-1$ independent active detection constraints. This small-support existence fact does not identify those sets efficiently.

For dual weights $\lambda_b\geq0$, testing dual feasibility requires minimizing \[ h(S)-\sum_{b\ne a}\lambda_b{\mathbf 1}\{S\cap\{a,b\}\ne\varnothing\}. \] Among sets avoiding $a$, this becomes minimization of $h(S)-\sum_{b\in S}\lambda_b$. The source's demand query instead maximizes $h(S)-\sum_{b\in S}q_b$. These are different optimization tasks; an arbitrary demand oracle does not automatically supply this minimum. Additivity collapses the coupling and yields (1). XOS and subadditive functions need not admit the same collapse, and a cost approximation alone need not give a multiplicative approximation to principal profit when revenue and inspection cost nearly cancel.

Reference

Tomer Ezra, Stefano Leonardi and Matteo Russo, Contract Design Beyond Hidden-Actions, SODA 2026, 2113--2133; author version arXiv:2402.16553v2 (26 November 2025), Sections 2 and 8. https://arxiv.org/html/2402.16553v2; https://doi.org/10.1137/1.9781611978971.77. The model and oracle scope were checked in the primary text. The additive case belongs to the tractable side of the broader inspection literature; the explicit derivation here does not claim to solve its XOS or subadditive approximation questions.

Completion Estimate

20%

Go to contribution →