we-solve (beta)

Econ-99 · economics · Economics

Subquadratic subsidies with arbitrary mixed-sign valuations

LLM status Open unverified

Statement

ECON-005 | U | Source passage unverified; not certified as a published open question

Definitions and formal target

For each agent, $v_i:2^M\to\mathbb R$ satisfies $v_i(\varnothing)=0$ and $|v_i(S\cup\{g\})-v_i(S)|\leq1$. No monotonicity or common sign is imposed. Define $s(v)$ as the infimum nonnegative total subsidy over complete envy-free bundle-payment allocations. Explicitly, $s(v)=\inf_{A,p\geq0}\{\sum_i p_i:v_i(A_i)+p_i\geq v_i(A_j)+p_j\ \forall i,j\}$, where $A$ partitions $M$.

\[ F(n)=\sup_{M\text{ finite}}\ \sup_{v\text{ satisfying the marginal bound}}s(v). \] Determine whether \[ \lim_{n\to\infty}\frac{F(n)}{n^2}=0. \] The limit runs over every positive integer $n$, not only a special arithmetic subsequence.

Clarifications and required assumptions

The absolute marginal bound is required for all bundles, so $|v_i(S)|\leq|S|$ follows from normalization; a bound only on $|v_i(\{g\})|$ would not control a nonadditive valuation. Use infima in $s(v)$ and allow extended-real values in $F(n)$. The little-$o$ target means: for every $\varepsilon>0$ there exists $n_0$ such that $F(n)\leq\varepsilon n^2$ for all integers $n\geq n_0$. The supremum over arbitrarily large $M$ makes uniformity in the number of items part of the question.

Variants and changes of scope

Additive mixed items. $v_i(S)=\sum_{g\in S}v_{ig}$ with $|v_{ig}|\leq1$ is a substantially smaller domain. Doubly monotone. Each item has a fixed sign of marginal contribution for each agent; arbitrary mixed-sign set functions need not satisfy this. Restricted arithmetic sequence. A result for only selected values of $n$ would not prove the all-integers little-$o$ statement. No claimed prime-power result from the inaccessible source is used as an established fact here.

Audit conclusion and source relationship

Verification incomplete. The paper's title, authors, arXiv identifier, and broad subsidy topic were corroborated, but its full text was unavailable in this audit. The earlier precise Section 6 attribution has been removed. This entry is a rigorously specified candidate target; its exact attribution and current open status are not certified. It must not be counted as a verified published open problem.

References and exact source roles

[S1] Max Dupré la Tour and Mashbat Suzuki (2026). Subquadratic Subsidies for Nonnegative or Nonpositive Valuations. arXiv:2609.08272v1, 8 September 2026.

Verified locator / source role: Bibliographic identity and broad abstract topic corroborated by the indexed arXiv record. Full text could not be retrieved. The draft's claimed Section 6 locators are NOT verified and have been withdrawn.

https://arxiv.org/abs/2609.08272

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-99-A2 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-99

Subquadratic subsidies with arbitrary mixed-sign valuations: The exact two-agent bound and a balanced-bundle reduction

Valuations are normalized arbitrary set functions with absolute single-item marginals at most one. Neither monotonicity nor a fixed marginal sign is imposed. The uniform asymptotic target is \[ F(n)=\sup_{M,v}\min_{A,p\geq0} \left\{\sum_i p_i:v_i(A_i)+p_i\geq v_i(A_j)+p_j\ \forall i,j\right\}, \qquad F(n)=o(n^2). \] Two-agent balancing can be proved directly even in this domain. The proof also identifies a difficulty in extending sign-removal transformations to arbitrary populations.

Theorem (Two arbitrary bounded-marginal agents): For $n=2$, every such instance has a complete envy-free allocation with total subsidy at most one. This is tight, so $F(2)=1$.
Proof: Order the items $g_1,\ldots,g_m$. Let $S_t=\{g_1,\ldots,g_t\}$ and define $d_t=v_1(S_t)-v_1(M\setminus S_t)$. The endpoints are $d_0=-v_1(M)$ and $d_m=v_1(M)$. Moving one item changes each of the two values by at most one, hence $|d_{t+1}-d_t|\leq2$. Either an endpoint is zero or a sign crossing occurs, so some $t$ satisfies $|d_t|\leq1$: at a crossing with both endpoint magnitudes greater than one the step would exceed two. Put $B=S_t$, $C=M\setminus S_t$.

If the agents weakly prefer different bundles, give each a preferred bundle and pay zero. Otherwise label the common preferred bundle $B$, and put $d_i=v_i(B)-v_i(C)\geq0$; the construction ensures $d_1\leq1$. If $d_1\leq d_2$, give $B$ to agent 2, $C$ to agent 1, and pay agent 1 exactly $d_1$. Agent 1 is indifferent, and agent 2 does not envy because $d_2\geq d_1$. If $d_2<d_1$, reverse the assignment and pay agent 2 exactly $d_2$. The total is at most one in either case. Ties may be assigned to the first case and cause no problem. Empty markets give both empty bundles and zero payments.

For the lower bound use one good valued at one by both agents. Its nonrecipient requires a subsidy at least one more than the recipient's, so the total is at least one. ∎

Proposition (A sign-removal reduction with explicit imbalance cost): For arbitrary $n$, define the normalized monotone valuations \[ w_i(S)=\frac{v_i(S)+|S|}{2}. \] Their single-item marginals lie in $[0,1]$. If an allocation $A$ is envy-free for $w$ with nonnegative subsidies $q$, then it is envy-free for $v$ with nonnegative subsidies of total at most \[ 2\sum_i q_i+\sum_i\left(|A_i|-\min_j|A_j|\right). \] In particular, equal-cardinality allocations incur no imbalance cost.
Proof: The absolute marginal bound gives $0\leq w_i(S\cup\{g\})-w_i(S)\leq1$, and normalization is immediate. Multiply each envy inequality for $w$ by two to obtain \[ v_i(A_i)+|A_i|+2q_i\geq v_i(A_j)+|A_j|+2q_j. \] Set $c=\min_j(|A_j|+2q_j)$ and $p_i=|A_i|+2q_i-c$. These payments are nonnegative, preserve the inequalities, and have sum $2\sum_iq_i+\sum_i|A_i|-nc$. Since $c\geq\min_j|A_j|$, this is at most the asserted bound. ∎
Proposition (Finite markets always have a finite subsidy witness): For $n\geq2$ and $m=|M|$, total subsidy at most $(n-1)m$ always suffices in the arbitrary-sign domain.
Proof: Choose $r$ maximizing $H=v_r(M)$. Give $M$ to $r$ and empty bundles to everyone else. If $H\geq0$, pay every other agent $H$ and pay $r$ zero. The inequality $v_i(M)\leq H$ verifies all envy comparisons. If $H<0$, pay $r$ exactly $-H$ and pay all other agents zero. The recipient's utility is zero; any other agent values that bundle-payment pair at $v_i(M)-H\leq0$. Finally, normalization and bounded marginals give $|H|\leq m$. The first total is at most $(n-1)m$, and the second at most $m\leq(n-1)m$. ∎
Source relationship and remaining gap.
Dupré la Tour and Suzuki [source], Section 6, discuss extending the all-integer result beyond uniform bundle signs. The two-agent result and imbalance calculation here are self-contained restricted deductions. A monotone subsidy theorem does not control the cardinality imbalance of its allocation; the displayed reduction can therefore introduce an arbitrarily large cost as $m$ increases. The two-agent theorem and finite-market bound do not imply the required all-integers asymptotic statement, whose supremum ranges over unbounded $m$.

References

Completion Estimate

10%

Go to contribution →

Econ-99-A1 · Exploration · LLM-generated · gpt 6 astra pro ·

GPT 6 Astra Pro attempt on Econ-99

{Subquadratic subsidies for arbitrary mixed-sign valuations}

D63-97.tex

Research attempt and adversarial audit --- 9 October 2026

Tools. Web browsing: YES. Computation: YES (Python, exact integer/rational checks, and explicitly identified numerical diagnostics). Status convention. A full proof of a restricted theorem does not resolve the full input. Literature results are marked as imported; no novelty or exhaustive current-literature certification is claimed. Computational searches certify only their stated finite domains.

FORMAL RESTATEMENT

For every integer $n\ge1$ and finite $M$, let $v_i:2^M\to{\mathbb{R}}$ satisfy $v_i(\varnothing)=0$ and \[ |v_i(S\cup\{g\})-v_i(S)|\le1\quad\text{for every }S\subseteq M,\ g\notin S. \] There is no monotonicity, common-sign, additivity or fixed item-sign assumption. Let $s(v)$ be the least total nonnegative subsidy over complete envy-free allocations, initially interpreted as an infimum, and \[ F(n)=\sup_{M\text{ finite}}\sup_v s(v)\in[0,+\infty]. \] The literal question is whether \[ \forall\varepsilon>0\ \exists n_0\ \forall\text{ integers }n\ge n_0: F(n)\le\varepsilon n^2. \] The all-integers quantifier and independence from $m$ are essential. A bound only on singleton values is insufficient; the displayed bound applies to every marginal. Additive signed values and doubly monotone valuations are proper subdomains. A prime-power subsequence is not the asserted limit.

QUICK LITERATURE/CONTEXT CHECK

The now-accessible 2026 source explicitly separates the arbitrary-sign all-integers question from its same-sign theorem [subq]. Dupré la Tour and Fujii obtain the corresponding subquadratic scale for prime-power numbers of agents [prime]. Lu, Mackenzie and Suzuki's July 2026 theorem gives subsidies at most one per agent for additive mixed values in $[-1,1]$ [mixed]; subtracting the minimum payment gives total at most $n-1$. Thus the additive variant is settled by that imported result, not by an extension to arbitrary set functions.

ATTACK PLAN

The proof track establishes exact finite feasibility and sharp $n=1,2$ values, then tests whether a prime-power bound can be extended by padding. The disproof track tests sign-dependent dummy agents and context-dependent marginal functions. A second reduction adds a cardinality function to force monotonicity, while explicitly accounting for its payment cost.
ToolRole
Difference constraintsCharacterize exactly which partitions admit subsidies.
Longest-path potentialsGive minimal nonnegative payments and a certificate.
Finite welfare-maximizing assignmentEnsures feasibility for at least one bundle assignment.
Prefix crossingProduces the sharp two-agent bound.
Greedy load balancingSolves identical monotone valuations.
Oracle/bit-complexity accountingSeparates evaluation of a certificate from finding it.
Small Lipschitz set-function searchTests nonadditive and mixed-sign boundary cases.
Topological/discrepancy methodsPossible route to global bounds, but not a polynomial algorithm by themselves.

WORK

A complete payment certificate for a fixed partition

Lemma (Difference constraints, exact feasibility and attainment): For a complete allocation $A$, put $w_{ij}=v_i(A_j)-v_i(A_i)$. There exist nonnegative subsidies making $A$ envy-free if and only if every directed cycle of this complete weighted graph has nonpositive total weight. In that case the coordinatewise smallest nonnegative feasible vector is \[ p_i^*=\max\left\{0,\ \text{total weights of directed paths starting at }i\right\}, \] where the maximum may be restricted to simple paths. In particular $\min_i p_i^*=0$. For every finite valuation instance there is at least one envy-freeable complete allocation, and the infimum defining $s(v)$ is attained.
Proof: The envy inequalities are $p_i\ge w_{ij}+p_j$. Summing around a cycle gives zero on the payment side, so positive cycles are impossible. Conversely, when no cycle is positive, deleting a repeated-vertex segment from a walk does not decrease its weight. The largest walk weight is therefore attained by a simple path of length at most $n-1$, including the empty path of weight zero. Prepending edge $i\to j$ to a maximizing path from $j$ and deleting any resulting nonpositive cycles proves $p_i^*\ge w_{ij}+p_j^*$. Thus $p^*$ is feasible and nonnegative.

Any nonnegative feasible $p$ dominates every path weight starting at $i$: sum the edge inequalities along that path and use nonnegativity of its final payment. Hence $p_i\ge p_i^*$ for every $i$. If the minimum coordinate of $p^*$ were positive, subtracting it from all coordinates would give a strictly smaller nonnegative feasible vector, a contradiction.

To obtain some envy-freeable allocation, begin with any $n$ bundle occurrences, including empty occurrences, forming a partition. Choose an assignment of those bundles to the agents that maximizes total value over the finite set of $n!$ assignments. A positive cycle in its envy graph would reassign the bundles cyclically and strictly increase that total, an impossibility. Finally there are finitely many complete allocations. Each feasible one has the attained minimum total $\sum_i p_i^*$, and at least one is feasible; taking the smallest of finitely many such totals proves attainment of $s(v)$. ∎

Corollary (An item-dependent bound, not a uniform theorem): If $v_i(\varnothing)=0$ and every absolute one-item marginal is at most one, then some envy-free allocation has total subsidy at most $(n-1)^2m$, where $m=|M|$.
Proof: Adding the items of a bundle one at a time gives $|v_i(S)|\le |S|$. Distinct allocated bundles are disjoint, so $|w_{ij}|\le|A_i|+|A_j|\le m$. On an envy-freeable allocation, every simple path has at most $n-1$ edges, whence $p_i^*\le(n-1)m$. At least one coordinate is zero, giving the bound. It is zero when $n=1$ or $m=0$. ∎
The supremum over all finite $M$ makes this estimate insufficient for any proposed bound depending only on $n$.
Lemma (Exact evaluation with polynomial-size payments): For a specified allocation with rational oracle values of bit length at most $L$, envy-freeability and the minimum payments can be computed with $n^2$ value queries and $O(n^3)$ rational arithmetic operations. The output bit length is polynomial in $n,m,L$.
Proof: Set $p^{(0)}=0$ and iterate \[ p_i^{(k+1)}=\max\{p_i^{(k)},\max_j(w_{ij}+p_j^{(k)})\}. \] An induction on $k$ identifies $p_i^{(k)}$ as the greatest weight of a walk starting at $i$ of length at most $k$, also allowing zero. If $p^{(n)}=p^{(n-1)}$, this vector satisfies all constraints and equals the minimum vector. If an entry increases, some length-$n$ walk improves on all shorter walks; it must contain a positive cycle, since deleting only nonpositive cycles could not lower its weight. Thus the allocation is infeasible. The recurrence has $n$ rounds of $n^2$ comparisons/additions. A path sums at most $n$ differences of input rationals. Forming common denominators by multiplication bounds its encoding length by $O(nL+\log n)$; each maximum selects one such rational. Query arguments are $m$-bit masks. These facts give polynomial bit complexity, not just a real-arithmetic claim. ∎

A sharp theorem for two agents, even without monotonicity

Theorem: For $n=2$, any normalized valuations with absolute one-item marginals at most one have an envy-free allocation with total subsidy at most one. This can be found with $O(m)$ value queries. The worst-case constant one is sharp.
Proof: Order the items arbitrarily and let $S_k$ be the first $k$, $0\le k\le m$. Write $d_i(S)=v_i(S)-v_i(M\setminus S)$. Consecutive $d_1(S_k)$ differ in absolute value by at most two, because an item is added on one side and removed on the other. The first and last are $-v_1(M)$ and $v_1(M)$. Hence some $k$ has $|d_1(S_k)|\le1$: otherwise the sequence must cross from a number below $-1$ to a number above $1$, or in the reverse direction, in one step of absolute size greater than two. This also covers $v_1(M)=0$ and $m=0$ by choosing $k=0$.

Fix this bipartition $S,T$. Write $d_i=v_i(S)-v_i(T)$. If $d_1\ge d_2$, assign $S$ to agent 1 and $T$ to agent 2. The constraints on the payment difference are \[ d_2\le p_2-p_1\le d_1. \] Choose the element of this closed interval nearest zero; its absolute value is the minimum possible total nonnegative subsidy, by placing that amount on the appropriate agent and zero on the other. If $d_1<d_2$, reverse the bundles and apply the same argument to $-d_1,-d_2$. The resulting minimum total is zero if $d_1,d_2$ straddle zero, and otherwise $\min\{|d_1|,|d_2|\}$. It is therefore at most one. Scanning the prefixes requires $O(m)$ queries and the final pair of values for agent 2; all arithmetic is exact for rational inputs.

For sharpness, use one good valued at one by both agents. Whichever receives it, the other needs a subsidy exactly one larger than the recipient's. Nonnegative payments therefore have total at least one, achieved by paying the nonrecipient one and the recipient zero. ∎

For monotone goods the sequence $d_1(S_k)$ is nondecreasing, so the sign crossing can instead be located by binary search with $O(\log(m+1))$ queries. This improvement is not asserted for arbitrary nonmonotone functions.

Corollary: $F(1)=0$, $F(2)=1$, and $F(n)\ge n-1$ for every $n\ge1$.
Proof: With one agent all items can be assigned to it and no pairwise envy is possible, so no subsidy is needed. The two-agent upper bound and its single-good lower witness are Theorem Theorem. For general $n$ the same one-good instance forces each nonrecipient's payment to equal the recipient's payment plus one, giving the exact minimum $n-1$. ∎
Theorem (Identical doubly monotone valuations): Suppose every agent has the same normalized valuation $v$, with a common partition $M=G\sqcup B$ such that every marginal of $g\in G$ lies in $[0,1]$ and every marginal of $g\in B$ lies in $[-1,0]$. Then an envy-free allocation exists with total subsidy at most $n-1$.
Proof: Maintain the current bundle values. Assign each good to a currently minimum-value bundle and each chore to a currently maximum-value bundle, in any fixed processing order. If the current range lies in $[a,a+1]$, adding a good to a minimum bundle keeps its new value in that range. If the current maximum is $b$ and the range lies in $[b-1,b]$, adding a chore to a maximum bundle also keeps its new value in that range. All other bundles remain unchanged. Starting from zeros, the spread never exceeds one. At the end pay $p_i=\max_jv(A_j)-v(A_i)$. All agents evaluate every bundle-payment pair at the same number, and at least one payment is zero while none exceeds one. This proves the bound. Additivity is not used; the fixed marginal signs are used at every assignment. ∎

A failed extension from prime powers

Proposition (Zero-valued dummy agents do not preserve the required budget): Appending zero-valued agents and then deleting them is not, by itself, a valid reduction preserving the minimum nonnegative subsidy.
Proof: Let $r\ge2$ original agents all value one chore $g$ at $-1$. If $h$ receives it, envy-freeness imposes $p_h\ge1+p_i$ for every other original agent and the reverse comparison imposes $p_h\le1+p_i$. The minimum total is therefore one, attained by $p_h=1$ and all other payments zero.

Append one dummy whose valuation is identically zero. Give the chore to the dummy and pay everyone zero. An original agent values its own empty bundle at zero and the dummy's chore at $-1$, so it does not envy. It is indifferent to other empty bundles. The dummy values every bundle at zero. Thus the augmented instance is envy-free with zero subsidy. Deleting the dummy leaves an unallocated original chore; no reassignment to the original agents preserves the zero budget. Consequently an arbitrary low-subsidy padded solution does not give a same-budget original solution. ∎

The proposition does not prove that $F(n)$ is nonmonotone and does not disprove the main asymptotic statement. It isolates a concrete missing step in a padding argument.

Proposition (Monotonizing by cardinality changes the subsidy scale): The transformation $u_i(S)=(v_i(S)+|S|)/2$ gives normalized monotone functions with marginals in $[0,1]$. But transforming their subsidies back can add a term of order $m$ to the total payment bound.
Proof: A marginal of $u_i$ is $(\Delta v_i+1)/2\in[0,1]$. If $A,p$ is envy-free for $u$, multiply its inequalities by two to obtain \[ v_i(A_i)+|A_i|+2p_i\ge v_i(A_j)+|A_j|+2p_j. \] Thus $t_i=|A_i|+2p_i$ gives feasible nonnegative payments for $v$. Subtracting their minimum preserves envy-freeness, but the resulting total is \[ m+2\sum_i p_i-n\min_i\{|A_i|+2p_i\}. \] There is no uniform cancellation of the $m$ term in this formula. This is a failure of the reduction's bound, not a lower bound on optimal original subsidies. ∎

Precisely what the imported partial theorems cover

For additive valuations $v_i(S)=\sum_{g\in S}a_{ig}$ with $a_{ig}\in[-1,1]$, the imported theorem in [mixed] supplies an envy-free allocation with every payment in $[0,1]$. Common subtraction gives the exact worst-case total $n-1$, using Corollary Corollary for tightness. For arbitrary functions at prime-power $n$, [prime] supplies an $O(n^{3/2}\sqrt{\log n})$ total bound. Neither theorem asserts the all-integers, arbitrary-function conclusion. The item-dependent Corollary Corollary (An item-dependent bound, not a uniform theorem) proves finiteness of $s(v)$ for each instance, not finiteness of the supremum $F(n)$ uniformly over item counts.

VERIFICATION

The executable checks generated normalized integer set functions of the form \[ v(S)=\min_r\{c_r+|S\triangle K_r|\}-\min_r\{c_r+|K_r|\}. \] Each cone is 1-Lipschitz for the Hamming metric, and the pointwise minimum is also 1-Lipschitz: using a minimizing index at one endpoint gives one direction of the inequality, and interchanging endpoints gives the other. The program additionally checked every one-item marginal explicitly. With seed 20261009, it tested 200 two-agent/five-item instances and 200 three-agent/four-item instances. It enumerated every complete allocation, computed exact minimum payments by the recurrence, and found largest observed optima of one in both batches. These are nonuniform small samples, not worst-case asymptotic bounds; many generated valuations are not monotone. 

\begin{lstlisting} for each sampled valuation table v:     best = infinity     for each complete allocation A:         w[i,j] = v[i,A[j]] - v[i,A[i]]         p = longest-walk recurrence from zero         if p passes all envy constraints: best = min(best,sum(p))     retain exact best and a witnessing allocation \end{lstlisting}
The one-good lower example was verified algebraically for every $n$, not inferred from this sample. Boundary checks include $n=1$, no items, zero values, zero-weight cycles, and exact rational payment differences. No positive-cycle partition is declared feasible merely because one or more agents could be paid a large amount: a positive cycle makes every payment vector impossible.

The first integer greater than one that is not a prime power is six; however, settling a single six-agent bound would not establish an all-integers asymptotic. Padding to the next power of two is numerically convenient but mathematically blocked by Proposition Proposition (Zero-valued dummy agents do not preserve the required budget). The cardinality reduction explicitly retains its otherwise hidden $m$ dependence. The identical doubly monotone theorem covers context-dependent magnitudes but not context-dependent signs. No arbitrary nonmonotone function is silently treated as a fixed-sign good or chore.

FINAL

LABEL: UNRESOLVED. The all-integers little-$o(n^2)$ statement is not proved or disproved. Fully proved here are finite feasibility/attainment, $F(1)=0$, $F(2)=1$, the universal $n-1$ lower example, an identical doubly monotone linear theorem, and explicit failures of two proposed reductions. The additive variant is settled by the precisely stated imported 2026 theorem.

Exact first gap. No item-uniform subquadratic upper bound is obtained for arbitrary bounded-marginal functions along every unbounded sequence of non-prime-power agent counts. This report does not even independently establish a finite item-uniform bound for each such fixed count.

Three next moves. (1) Prove an agent-removal lemma with an $O(n)$ or smaller payment penalty that also reallocates the removed agents' items. (2) Find a sign-independent boundary condition for a partition-price equalization argument. (3) Search six-agent nonmonotone value tables with competing positive and negative marginals, then seek a scalable family that forces a large optimum over all allocations.

Minimal hard structure. A natural search domain is heterogeneous nonadditive preferences at non-prime-power agent counts. Context-dependent sign reversals are a useful additional stress test, not a proved necessary feature: even heterogeneous fixed-sign nonadditive preferences are not settled by the identical-valuation theorem. A purported asymptotic counterexample must lower-bound every complete allocation along unbounded agent counts and may need an item count growing with $n$.

Completion Estimate

18%

Sharp two-agent results, structured linear subcases, and reduction obstructions are proved; the unrestricted all-integers asymptotic remains unresolved. The known additive and prime-power variants are credited without being counted as a new general solution.

This is a subjective estimate of the fraction of the whole requested mathematical scope addressed by this report, including the named variants. It is not a probability of correctness, an objectively measured fraction of a proof, or an estimate that the remaining work takes the complementary fraction of the time. Only the eleven supplied files are assessed; no missing rank-1--200 statements are inferred.

References

  • [subq] M. Dupré la Tour and M. Suzuki. Subquadratic Subsidies for Nonnegative or Nonpositive Valuations. arXiv:2609.08272v1, 8 September 2026, Theorem 1 and Section 6. https://arxiv.org/html/2609.08272v1.
  • [prime] M. Dupré la Tour and K. Fujii. Discrepancy And Fair Division For Non-Additive Valuations. arXiv:2509.16802v1 (2025), Corollary 2. https://arxiv.org/html/2509.16802v1.
  • [mixed] X. Lu, S. Mackenzie and M. Suzuki. Optimal Subsidy Bounds for Goods and Chores: One Dollar Each Suffices. arXiv:2607.10089 (2026), Theorem 1.1. https://arxiv.org/html/2607.10089.

Go to contribution →