d4-conf-wine-2019-0024 (d4-conf-wine-2019-0024)

Given \(m\) goods, per-capita supplies \(s_j\), finitely many route types \(t\in T\) with positive rational masses \(\mu_t\) summing to \(1\), and a per-person bundle \(x_t\) for each type satisfying route proportions and \(\sum_t \mu_t x_{tj}\le s_j\), decide whether common continuous strictly increasing curves \(f_j\), with \(f_j(0)=0\), make each type’s bundle affordable at unit budget and utility-maximizing for \(u_t(z)=\min_{j\in R_t}z_j\). If so, compute the curve values at the allocated-quantity breakpoints.

Let \(m\ge 1\) divisible goods have nonnegative binary-rational per-capita supplies \(s_j\). A society is given by its support: a list \(T\) of \(\tau\ge 1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has a nonempty route \(R_t\subseteq\{1,\ldots,m\}\) and a prescribed bundle satisfying \(x_{tj}=a_t\) for \(j\in R_t\) and \(x_{tj}=0\) otherwise, where \(a_t\ge 0\) is a binary rational. At least one \(a_t\) is positive, and \(\sum_t\mu_t x_{tj}\le s_j\) for every good.
A common price curve for good \(j\) is a continuous strictly increasing function \(f_j:\mathbb R_{\ge 0}\to\mathbb R_{\ge 0}\) with \(f_j(0)=0\). A person's bundle \(z\) costs \(C_f(z)=\sum_j f_j(z_j)\), and every person has budget \(1\).
The curves support the prescribed allocation when, for every type \(t\), \(C_f(x_t)\le 1\) and \(x_t\) maximizes \(u_t(z)=\min_{j\in R_t}z_j\) over all \(z\in\mathbb R_{\ge 0}^m\) with \(C_f(z)\le 1\). Individual alternatives are not capped by supplies; aggregate feasibility requires only the inequalities above, without supply exhaustion.
On a yes-instance, the computational problem also asks for exact rational values \(f_j(q)\) at every distinct positive allocated quantity \(q\in\{x_{tj}:t\in T\}\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).

Is deciding whether such supporting curves exist in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? If it is in \(\mathrm P\), can the requested breakpoint values also be computed in polynomial time in \(m,\tau,L\)?

For finitely many individually listed agents with Leontief utilities and equal budgets, Goel, Hulett, and Plaut establish polynomial-time recognition and construction of supporting strictly increasing price curves. Their result applies in particular to nonempty unweighted routes.

Result. Recognition is in \(\mathrm{P}\), and exact rational breakpoint values can also be computed in polynomial time. Both tasks require \((L+m\tau)^{O(1)}\) bit operations.

1. Individual optimality is equivalent to spending the whole budget

For a type \(t\), define the cost of obtaining utility \(b\) using only its route by
\[ B_t(b)=\sum_{j\in R_t}f_j(b). \]
Because \(R_t\) is nonempty, \(B_t\) is continuous and strictly increasing.

We claim that the prescribed bundle is affordable and utility-maximizing exactly when \(B_t(a_t)=1\).

Indeed, affordability gives \(B_t(a_t)\le 1\). If this inequality is strict, continuity gives some \(\delta>0\) with \(B_t(a_t+\delta)<1\). Purchasing quantity \(a_t+\delta\) of every route good then strictly improves utility within budget. Conversely, if \(B_t(a_t)=1\), every bundle \(z\) with \(u_t(z)>a_t\) satisfies \(z_j>a_t\) for every \(j\in R_t\). Thus strict increase and nonnegativity imply
\[ C_f(z)\ge\sum_{j\in R_t}f_j(z_j)> \sum_{j\in R_t}f_j(a_t)=1. \]
Consequently, such a bundle is unaffordable.

In particular, any type with \(a_t=0\) makes the instance a no-instance, since \(B_t(0)=0\). Henceforth assume every \(a_t>0\).

2. An equivalent finite system

List the distinct allocated quantities in increasing order as \(0=q_0<q_1<\cdots<q_K\), where \(K\le\tau\). Let \(\ell(t)\) denote the index satisfying \(a_t=q_{\ell(t)}\).

Introduce one increment variable \(d_{jk}\) for each good \(j\) and index \(k\). Supporting curves necessarily give
\[ d_{jk}=f_j(q_k)-f_j(q_{k-1})>0, \]
and the preceding optimality condition becomes
\[ \sum_{j\in R_t}\sum_{k=1}^{\ell(t)}d_{jk}=1 \qquad(t\in T). \]

These conditions are also sufficient. Given strictly positive increments satisfying the equations, set \(y_{j0}=0\) and \(y_{jk}=\sum_{h=1}^{k}d_{jh}\). Define, for \(q_{k-1}\le b\le q_k\),
\[ f_j(b)=y_{j,k-1}+ \frac{d_{jk}}{q_k-q_{k-1}}(b-q_{k-1}), \]
and, for \(b\ge q_K\), define \(f_j(b)=y_{jK}+b-q_K\).

The formulas agree at their endpoints. Every segment has positive slope, including the final ray, so each curve is continuous, strictly increasing, nonnegative, and zero at zero. The equations ensure that every prescribed bundle costs exactly \(1\); Section 1 proves individual optimality.

Thus supporting curves exist exactly when the finite equations admit strictly positive increments.

3. Handling strict positivity by a bounded linear program

First, we may impose \(d_{jk}\le1\) without changing strict feasibility. If an increment appears in a budget equation, it is a positive summand in a sum equal to \(1\), so it is already at most \(1\). Any increment appearing in no budget equation may be replaced by \(1\).

Now maximize a variable \(\varepsilon\), subject to:

• \(\sum_{j\in R_t}\sum_{k=1}^{\ell(t)}d_{jk}=1\) for every \(t\in T\);
• \(0\le\varepsilon\le1\);
• \(\varepsilon\le d_{jk}\le1\) for every \(j,k\).

If strictly positive increments exist, normalize them as above and take \(\varepsilon=\min_{j,k}d_{jk}>0\). This gives a feasible solution with positive objective value. Conversely, any feasible solution with \(\varepsilon>0\) gives strictly positive increments.

The feasible region is closed and contained in \([0,1]^{mK+1}\), so, when nonempty, an optimum exists. Therefore the decision rule is:

• Return no if the linear program is infeasible.
• Otherwise, return yes exactly when its exact optimum \(\varepsilon^\star\) is positive.

This requires exact rational optimization, rather than a numerical tolerance. The standard polynomial-time theorem for rational linear programming provides infeasibility detection and exact rational optimal solutions of polynomial encoding length; see [Gleixner and Steffy, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).

4. Complexity and exact construction

The linear program has \(n=mK+1\) variables, \(\tau\) equality constraints, and \(2mK+2\) inequality constraints. Every coefficient lies in \(\{-1,0,1\}\), and every right-hand side lies in \(\{0,1\}\). Its dense binary encoding has length
\[ O\bigl((mK+\tau+1)(mK+1)\bigr)=O\bigl((m\tau+1)^2\bigr). \]
Sorting the input rational quantities and finding their indices takes polynomial time in \(L\). Exact rational linear programming therefore gives recognition in \((L+m\tau)^{O(1)}\) bit operations.

On a yes-instance, obtain an exact rational optimal solution. Output
\[ f_j(q_k)=\sum_{h=1}^{k}d_{jh} \qquad(1\le j\le m,\;1\le k\le K). \]
These are all the requested values, including quantities never allocated on a particular good. Polynomially many additions of polynomial-length rationals take polynomial time and produce polynomial-length outputs. The interpolation in Section 2 also constructs supporting curves with an exact rational description.

For an explicit existence bound on output length, an optimal vertex can be chosen because the feasible region is a nonempty compact polytope. At a vertex, \(n\) linearly independent active constraints determine the coordinates. Their coefficient matrix and right-hand side have entries of absolute value at most \(1\). Cramer’s rule and Hadamard’s inequality bound the absolute values of the relevant determinants by \(n^{n/2}\). All coordinates therefore have a common denominator of absolute value at most \(n^{n/2}\); cumulative breakpoint values require only \(O(n\log n+\log K)\) bits each.

Finally, the masses \(\mu_t\) and supplies \(s_j\) enter only the aggregate feasibility condition, which is already assumed. The construction supports the given allocation and hence preserves those inequalities. Since every person of a type faces the same demand problem, one budget equation per listed type suffices. No expansion by mass denominators, or enumeration of types outside the support, is needed.

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly. Recognition and computation of exact rational breakpoint values both follow from the stated linear program, with polynomial bit complexity. No major or minor mathematical issues were found.

• Individual optimality and budget exhaustion

The function \(B_t(b)\) is continuous and strictly increasing because it is a finite sum of continuous strictly increasing functions over a nonempty route.

If \(B_t(a_t)<1\), continuity at \(a_t\) provides a positive increase in quantity that remains affordable. The corresponding route bundle strictly improves utility. This argument also applies when \(a_t=0\).

Conversely, if \(B_t(a_t)=1\), every bundle with utility greater than \(a_t\) has strictly greater quantities on every route good. Strict increase makes its route cost exceed \(1\), and nonnegative costs outside the route cannot reduce its total cost. Thus the prescribed bundle is affordable and maximizing.

The rejection of every instance containing a type with \(a_t=0\) is therefore justified. After that rejection, \(K\ge1\).

• Equivalence with the finite increment system

Necessity is correct: strict increase gives \(d_{jk}>0\), and telescoping converts each budget condition into the stated equality.

Sufficiency is also correct. The interpolation denominators are positive because the quantities are distinct and sorted. Adjacent formulas agree at every breakpoint, including the junction with the final ray. Positive slopes give strict increase throughout the domain; the curves start at zero and remain nonnegative.

The budget equations then imply individual optimality by Section 1. Introducing increments for every good at every global quantity is legitimate, including quantities never allocated on that good.

• Upper bounds and strict positivity

The normalization \(d_{jk}\le1\) preserves strict feasibility. Each increment occurring in an equation has coefficient \(1\) and is one of finitely many positive summands totaling \(1\), so it is already at most \(1\). An increment occurring in no equation may be changed independently to \(1\).

There are finitely many increments, so a strictly positive normalized solution has a strictly positive minimum. Taking this minimum as \(\varepsilon\) satisfies the linear program. Conversely, a feasible solution with \(\varepsilon>0\) makes every increment strictly positive.

The feasible region is closed and bounded. Consequently, whenever it is nonempty, its objective attains a maximum. The stated decision rule correctly distinguishes infeasibility, optimum zero, and positive optimum.

• Exact linear programming

The invoked theorem is applicable: a linear program with explicitly encoded rational coefficients can be checked for feasibility and, when feasible with bounded objective, optimized exactly in polynomial bit time, with a rational optimal solution of polynomial encoding length.

Here all coefficients, right-hand sides, and objective coefficients are rational; the feasible region is bounded by the explicit box constraints. No nondegeneracy or full-dimensionality assumption is needed. The cited [Gleixner–Steffy discussion, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf) confirms the availability of exact polynomial-time algorithms for rational linear programming.

Using exact optimization, rather than a numerical positivity tolerance, correctly handles potentially small positive optima.

• Size and running-time calculations

The counts \(mK+1\) variables, \(\tau\) equalities, and \(2mK+2\) inequalities are correct. The dense encoding bound follows from those counts and the constant-size coefficients. Since \(K\le\tau\) and \(m\ge1\), the stated bound \(O((m\tau+1)^2)\) is valid.

Sorting and comparing binary-encoded rational quantities takes polynomial time in the input length. Constructing and solving the linear program therefore takes \((L+m\tau)^{O(1)}\) bit operations.

• Exact output and determinant bound

The cumulative sums give precisely the breakpoint values of the constructed curves. There are at most \(m\tau\) requested values, and polynomially many additions of polynomial-length rationals preserve polynomial total bit complexity.

The additional vertex bound is correct. A nonempty compact polytope has an optimal vertex, and at a vertex one can select \(n\) linearly independent active constraints. Their integer coefficient matrix is nonsingular. Cramer’s rule gives a common denominator equal, up to sign, to its determinant; Hadamard’s inequality bounds both that determinant and the numerator determinants by \(n^{n/2}\).

Summing at most \(K\) coordinates over this common denominator gives the stated \(O(n\log n+\log K)\) encoding bound per breakpoint value. This paragraph establishes an existence bound for a vertex output; the preceding general polynomial output bound already suffices for the algorithm.

• Support representation and aggregate feasibility

The masses and supplies affect only the aggregate feasibility inequalities, which the task assumes. The constructed curves leave the prescribed allocation unchanged.

Every person of a given type has the same individual optimization problem, so one equation per listed type suffices. Neither expansion by mass denominators nor enumeration of unlisted types is required. Thus the argument addresses the support-encoded problem directly.

No repair or additional clarification is necessary.

⟨structured verdict parsed — rendered above⟩