Value-based Resource Matching with Fairness Criteria: Application to Agricultural Water Trading (aamas24-00008)

Given finite seller and buyer clone-type sets \(\Theta_S\) and \(\Theta_B\), rational masses \(\mu_\theta\), explicitly listed ordered unit positions with values \(s_{\theta,i}\) and \(b_{\phi,j}\), and type-level compatibility \(E\), where seller values are nondecreasing and buyer values are nonincreasing, choose nonnegative mass flows \(x_{\theta i,\phi j}\). Permit flow only when \((\theta,\phi)\in E\) and \(b_{\phi,j}\ge s_{\theta,i}\); impose \(\sum_{\phi,j}x_{\theta i,\phi j}\le\mu_\theta\), \(\sum_{\theta,i}x_{\theta i,\phi j}\le\mu_\phi\), and prefix constraints \(u_{\theta,i}\le u_{\theta,i-1}\) and \(v_{\phi,j}\le v_{\phi,j-1}\) for later positions, where \(u_{\theta,i}=\sum_{\phi,j}x_{\theta i,\phi j}\) and \(v_{\phi,j}=\sum_{\theta,i}x_{\theta i,\phi j}\). Output a feasible flow maximizing \(\sum_{\theta,\phi,i,j}(b_{\phi,j}-s_{\theta,i})x_{\theta i,\phi j}\), or report infeasibility.

A society is given by its support: disjoint finite seller and buyer type sets \(\Theta_S,\Theta_B\), listing each type \(a\) with positive binary-rational mass \(\mu_a\), with \(\sum_a\mu_a=1\). The support size is \(\tau=|\Theta_S|+|\Theta_B|\), not the number of possible types.
Each type \(a\) has an explicitly listed ordered sequence of \(\gamma_a\) unit positions. Let \(m=\sum_a\gamma_a\) and let \(L\) be the total binary input length. Seller values \(s_{\theta,i}\) are nonnegative binary rationals, nondecreasing in \(i\); buyer values \(b_{\phi,j}\) are nonnegative binary rationals, nonincreasing in \(j\). Equal values are allowed; the listed order remains binding.
Compatibility is an explicitly listed relation \(E\subseteq\Theta_S\times\Theta_B\). A flow consists of divisible real masses \(x_{\theta i,\phi j}\ge0\), with \(x_{\theta i,\phi j}=0\) unless \((\theta,\phi)\in E\) and \(b_{\phi,j}\ge s_{\theta,i}\).
Define \(u_{\theta,i}=\sum_{\phi,j}x_{\theta i,\phi j}\) and \(v_{\phi,j}=\sum_{\theta,i}x_{\theta i,\phi j}\). Require \(u_{\theta,i}\le\mu_\theta\), \(v_{\phi,j}\le\mu_\phi\), and \(u_{\theta,i}\le u_{\theta,i-1}\), \(v_{\phi,j}\le v_{\phi,j-1}\) whenever the preceding position exists. Unused capacity is permitted, with no minimum-trade constraints.
The optimization problem is to output a feasible flow maximizing \(\sum_{\theta,\phi,i,j}(b_{\phi,j}-s_{\theta,i})x_{\theta i,\phi j}\), or report infeasibility; any optimum is acceptable.

Is exact welfare maximization for this continuous problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

The discrete counterpart, with individually listed agents and indivisible unit positions, is solvable in polynomial time in the total number of positions under these monotonicity assumptions ([discrete result](https://arxiv.org/pdf/2402.06576)).
No prior result settling exactly the support-encoded continuous problem above was located.

Result

Exact welfare maximization is solvable in time polynomial in \(m,\tau,L\). The stated continuous problem is a rational linear program of polynomial encoding length. This directly solves the support-encoded problem without expanding type masses into individual agents.

Every valid instance is feasible because the zero flow satisfies all constraints. The substantive task is to compute an exact optimum.

1. An exact linear-programming formulation

Define the seller and buyer position sets by

\(P_S=\{(\theta,i):\theta\in\Theta_S,\ 1\le i\le\gamma_\theta\}\),

\(P_B=\{(\phi,j):\phi\in\Theta_B,\ 1\le j\le\gamma_\phi\}\).

Let the set of permitted position pairs be

\(F=\{((\theta,i),(\phi,j))\in P_S\times P_B:(\theta,\phi)\in E,\ b_{\phi,j}\ge s_{\theta,i}\}\).

Introduce one real variable \(x_{\theta i,\phi j}\) for each pair in \(F\). All other flow coordinates are defined to be zero. Write the following linear forms:

\(U_{\theta,i}(x)=\sum_{(\phi,j):((\theta,i),(\phi,j))\in F}x_{\theta i,\phi j}\),

\(V_{\phi,j}(x)=\sum_{(\theta,i):((\theta,i),(\phi,j))\in F}x_{\theta i,\phi j}\).

An empty sum is zero. Consider the linear program maximizing

\(\displaystyle \sum_{((\theta,i),(\phi,j))\in F}(b_{\phi,j}-s_{\theta,i})x_{\theta i,\phi j}\)

subject to:

• \(x_{\theta i,\phi j}\ge0\) for every pair in \(F\);
• \(U_{\theta,i}(x)\le\mu_\theta\) for every seller position;
• \(V_{\phi,j}(x)\le\mu_\phi\) for every buyer position;
• \(U_{\theta,i}(x)-U_{\theta,i-1}(x)\le0\) for every seller position with \(i\ge2\);
• \(V_{\phi,j}(x)-V_{\phi,j-1}(x)\le0\) for every buyer position with \(j\ge2\).

Equivalence. Restricting any feasible flow from the question to \(F\) gives a feasible point of this program: forbidden coordinates are already zero, and each displayed inequality is precisely a required capacity or ordering inequality.

Conversely, extending a feasible point of this program by zero outside \(F\) gives a feasible flow from the question. The definition of \(F\) enforces compatibility and the value restriction; the remaining constraints enforce all capacity and ordering requirements.

The objectives agree under these two operations. Thus the correspondence preserves both feasibility and welfare exactly.

2. Polynomial encoding length

Let \(m_S=|P_S|\), \(m_B=|P_B|\), and \(q=|F|\). Then

\(q\le m_Sm_B\le m^2/4\).

There are \(q\) nonnegativity inequalities, \(m\) capacity inequalities, and at most \(m\) ordering inequalities. Therefore the program has at most \(q+2m\) inequalities.

Every constraint-matrix entry belongs to \(\{-1,0,1\}\). Its right-hand sides are input masses or zero. Every objective coefficient is the difference of two input rationals.

To check the numerical encoding explicitly, if the two values are \(p/r\) and \(t/u\), their difference is

\(\displaystyle \frac{p}{r}-\frac{t}{u}=\frac{pu-tr}{ru}\).

Multiplication and subtraction increase binary length by at most a constant multiple of the combined operand lengths. Hence each objective coefficient has binary length \(O(L+1)\) and can be computed in polynomial time.

The set \(F\) can likewise be constructed in polynomial time by checking the explicitly listed compatibility relation and comparing rational values for each of at most \(m^2\) position pairs. Even a dense encoding of the resulting constraint matrix has polynomial size in \(m,\tau,L\).

No step creates copies proportional to a mass denominator.

3. Existence and encoding of an exact optimum

The zero vector is feasible. For any permitted coordinate, nonnegativity and its seller capacity constraint imply

\(0\le x_{\theta i,\phi j}\le U_{\theta,i}(x)\le\mu_\theta\le1\).

Thus the feasible region is a nonempty, closed, bounded polytope. The linear objective attains its maximum. If \(q=0\), the zero flow is the only flow and is optimal.

For \(q\ge1\), the standard vertex theorem for linear programming ensures that an optimum exists at a vertex of this polytope. Its coordinates have polynomial binary length, as the following calculation shows.

Write the constraints as \(Ax\le d\). Let \(D\) be the product of the denominators of all input masses. Then \(Dd\) is integral, and \(\log_2 D=O(L)\). Moreover, every entry of \(Dd\) has absolute value at most \(D\).

At a vertex, select \(q\) linearly independent tight inequalities. They give

\(Bx=d'\),

where \(B\) is a nonsingular integer matrix with entries in \(\{-1,0,1\}\). By Cramer’s rule,

\(\displaystyle x_k=\frac{\det B_k}{D\det B}\),

where \(B_k\) replaces column \(k\) of \(B\) by \(Dd'\). The determinant expansion contains \(q!\) terms. Each term for \(B\) has absolute value at most one; each term for \(B_k\) has absolute value at most \(D\). Consequently,

\(1\le|\det B|\le q!\), and \(|\det B_k|\le q!D\).

Both numerator and denominator therefore have binary length \(O(L+q\log(q+1))\). An exact rational optimum has polynomial output length.

4. Polynomial-time algorithm

Apply the standard exact rational linear-programming theorem: an explicitly encoded rational linear program can be solved in time polynomial in its total binary encoding length, returning an exact rational optimum when the feasible region is nonempty and bounded. This is the polynomial-time LP theorem established by [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239).

All its hypotheses have been checked here: rational data, an explicit polynomial-size formulation, nonemptiness, and boundedness. Solve the program above and extend its output by zero outside \(F\). By the equivalence in Section 1, the result is an exact welfare-maximizing feasible flow.

This proof does not require the discrete theorem. In fact, the same linear-programming argument works with arbitrary explicitly listed rational values: the ordering inequalities remain linear even without value monotonicity. Equal values and the binding listed order are already handled by the formulation.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The formulation matches the stated continuous problem exactly, has polynomial binary encoding length, and satisfies the hypotheses of exact polynomial-time rational linear programming. No major or minor mathematical issues were found.

• Variables and admissibility. The set \(F\) contains exactly the compatible position pairs satisfying \(b_{\phi,j}\ge s_{\theta,i}\). Defining all coordinates outside \(F\) to be zero enforces precisely the required restrictions. Equality of values is correctly permitted.

• Constraints and equivalence. The forms \(U_{\theta,i}\) and \(V_{\phi,j}\) are exactly the seller and buyer marginal flows. Their capacity inequalities and adjacent-position inequalities reproduce every constraint in the task. Restriction to \(F\) and extension by zero are inverse operations on feasible flows and preserve the objective. No integrality or additional trade requirement is introduced.

• Feasibility and edge cases. Zero flow satisfies nonnegativity, capacities, and every ordering inequality. Thus every valid input is feasible. Empty sums are explicitly defined, so positions without permitted partners cause no ambiguity. The case \(q=0\), including empty position sets, is correctly handled by returning zero flow.

• Formulation size. With \(m=m_S+m_B\), the bound

\[ q\le m_Sm_B\le m^2/4 \]
is correct. There are exactly \(q\) nonnegativity inequalities, \(m\) capacity inequalities, and at most \(m\) ordering inequalities. Every matrix entry is in \(\{-1,0,1\}\): adjacent positions have disjoint sets of incident variable coordinates, so subtracting their marginal forms cannot create coefficients of larger magnitude.

Constructing \(F\) requires only polynomially many compatibility checks and exact rational comparisons. A dense matrix encoding consequently remains polynomial in \(m,\tau,L\).

• Numerical encoding. The displayed rational subtraction formula is correct. Products, differences, and comparisons of input rationals have polynomial bit complexity. Each objective coefficient has binary length \(O(L+1)\); repeated masses on the right-hand side also contribute only polynomial total length. No denominator-sized population expansion occurs.

• Existence of an optimum. Nonnegativity and seller capacity give

\[ 0\le x_{\theta i,\phi j}\le\mu_\theta\le1. \]
Therefore the feasible set is closed, bounded, and nonempty. The objective is linear and hence continuous, so its maximum is attained. The invoked vertex theorem applies to a nonempty bounded polyhedron, including one of lower affine dimension.

• Exact output length. The denominator product \(D\) satisfies \(\log_2D=O(L)\), because the masses’ denominator encodings are part of the input. Every entry of \(Dd\) is an integer of absolute value at most \(D\).

At a vertex, selecting \(q\) independent tight constraints is valid. The Cramer’s-rule expression
\[ x_k=\frac{\det B_k}{D\det B} \]
correctly accounts for replacing the column by \(Dd'\). Each determinant term for \(B_k\) contains exactly one entry from that replacement column, so the bounds \(|\det B_k|\le q!D\) and \(1\le|\det B|\le q!\) are correct. The resulting coordinate bit-length bound is polynomial.

• Algorithm and complexity conclusion. The prover states the needed standard theorem precisely enough: explicit rational linear programs admit polynomial-time exact optimization, returning a rational optimum for nonempty bounded feasible regions. This is the standard rational LP result associated with [Khachiyan’s cited publication](https://www.mathnet.ru/eng/zvmmf5239). All relevant hypotheses are verified in the write-up. Extending the returned solution by zero requires at most polynomially many output coordinates and preserves optimality.

The observation that value monotonicity is unnecessary for this LP argument is also correct: listed-order constraints remain linear, and admissibility is explicitly encoded in \(F\).

Required clarification or repair: none.

⟨structured verdict parsed — rendered above⟩