The vigilant eating rule: A general approach for probabilistic economic design with constraints (d4-journals-geb-2022-0067)

Given finite object types \(O\), applicant types \(\Theta\), rational applicant mass \( \mu \), per-capita object supplies \(q\), and type data specifying preferences and priorities, compute a feasible mass allocation \(x_{\theta,o}\) with \( \sum_o x_{\theta,o}=\mu_\theta \), \( \sum_\theta x_{\theta,o}=q_o \), and \(p_{\theta,o}=x_{\theta,o}/\mu_\theta\) satisfying \( \sum_{o'\succeq_\theta o,\;o'\ne o}p_{\theta,o'}+\frac{1}{q_o}\sum_{\theta':\,\theta'\succeq_o\theta}x_{\theta',o}\ge 1 \); return the resulting \( \mathrm{FS\text{-}VER} \), equivalently the constrained ordinally egalitarian allocation.

Let \(O\) be a finite set of object types and \(\Theta\) a finite set of applicant types. Each type has a weak preference over \(O\) and a positive rational mass \(\mu_\theta\); each object has a weak priority over \(\Theta\) and a positive rational supply \(q_o\), with \(\sum_\theta\mu_\theta=\sum_o q_o\).
An allocation has \(x_{\theta,o}\geq0\), \(\sum_o x_{\theta,o}=\mu_\theta\), and \(\sum_\theta x_{\theta,o}=q_o\). Write \(p_{\theta,o}=x_{\theta,o}/\mu_\theta\). It is fractionally stable when, for every \(\theta,o\), \(\sum_{o'\succeq_\theta o,\,o'\neq o}p_{\theta,o'}+\frac{1}{q_o}\sum_{\theta':\,\theta'\succeq_o\theta}x_{\theta',o}\geq1\).
For each type \(\theta\) and each initial segment of its preference indifference classes, record the total \(p_{\theta,o}\) in that segment. A constrained ordinally egalitarian allocation lexicographically maximizes the nondecreasing sort of all these recorded values over fractionally stable allocations; call any such allocation \(\mathrm{FS\text{-}VER}\).

Is computing \(\mathrm{FS\text{-}VER}\) for these finite-type mass instances in P, or is it NP-hard?

For finite-agent probabilistic allocation, \(\mathrm{FS\text{-}VER}\) is computable in polynomial time, including with weak preferences and priorities.

Result

The problem is polynomial-time solvable whenever a fractionally stable allocation exists. More generally, a polynomial-time algorithm can either compute an \(\mathrm{FS\text{-}VER}\) allocation or report that no fractionally stable allocation exists.

The existence qualification is necessary: the stated assumptions do not guarantee feasibility.

1. Fractional stability defines a polynomial-size rational polytope

Let \(n=|\Theta|\) and \(m=|O|\). Write \(P\) for the set of allocations satisfying the mass constraints, supply constraints, nonnegativity, and the stated fractional-stability inequalities.

Substituting \(p_{\theta,o}=x_{\theta,o}/\mu_\theta\), each stability inequality becomes

\( \displaystyle \frac{1}{\mu_\theta} \sum_{\substack{o'\succeq_\theta o\\o'\neq o}}x_{\theta,o'} + \frac{1}{q_o} \sum_{\theta'\succeq_o\theta}x_{\theta',o} \geq 1. \)

The masses and supplies are given positive rational constants. Consequently, these are linear inequalities with rational coefficients of polynomial encoding length. There are \(nm\) variables, \(nm\) stability inequalities, and polynomially many allocation constraints.

Moreover, nonnegativity and the row sums imply \(0\leq x_{\theta,o}\leq\mu_\theta\). Thus \(P\) is a bounded rational polytope, possibly empty.

We use the standard theorem that rational linear programming admits exact feasibility testing and optimization in time polynomial in its binary encoding length. See [MIT’s notes on polynomial-time linear programming](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).

Hence emptiness of \(P\) can be decided in polynomial time. Assume henceforth that \(P\neq\varnothing\).

2. Replace the sorted objective by cumulative sums

Index all recorded preference-prefix values by \(i\in\{1,\ldots,K\}\). Each is a rational linear function

\( \displaystyle f_i(x)=\frac{1}{\mu_{\theta(i)}}\sum_{o\in A_i}x_{\theta(i),o}, \)

where \(A_i\) is the corresponding initial segment. There are at most \(K\leq nm\) such values, and each belongs to \([0,1]\).

Let their nondecreasing ordering be

\( f_{(1)}(x)\leq\cdots\leq f_{(K)}(x), \)

and define

\( \displaystyle S_k(x)=\sum_{j=1}^{k}f_{(j)}(x) \quad\text{for }k\in\{1,\ldots,K\}. \)

Lexicographically maximizing the sorted vector is equivalent to lexicographically maximizing \((S_1(x),\ldots,S_K(x))\). Indeed, if two sorted vectors first differ at coordinate \(r\), their cumulative sums agree before \(r\), and their cumulative sums at \(r\) differ by exactly the difference of their \(r\)-th coordinates.

We next represent upper bounds on these cumulative sums using linear constraints.

3. A polynomial-size extended formulation

For any \(v_1,\ldots,v_K\in[0,1]\), with nondecreasing ordering \(v_{(1)},\ldots,v_{(K)}\), we have

\( \displaystyle \sum_{j=1}^{k}v_{(j)} = \max_{0\leq t\leq1} \left(kt-\sum_{i=1}^{K}\max\{t-v_i,0\}\right). \)

To verify the identity, for every \(t\),

\( \displaystyle kt-\sum_{i=1}^{K}\max\{t-v_i,0\} \leq kt-\sum_{j=1}^{k}(t-v_{(j)}) = \sum_{j=1}^{k}v_{(j)}. \)

Here the inequality follows because the sum of positive parts over all indices is at least the sum of \(t-v_{(j)}\) over the first \(k\) indices. Equality holds at \(t=v_{(k)}\): terms after the first \(k\) contribute zero, while terms among the first \(k\) equal \(t-v_{(j)}\). This also covers ties.

Construct a polytope \(Q\) with variables \(x\), \(y_k\), \(t_k\), and \(u_{ki}\), subject to \(x\in P\) and, for every \(k,i\),

\( 0\leq t_k\leq1,\qquad 0\leq u_{ki}\leq1,\qquad u_{ki}\geq t_k-f_i(x), \)

together with, for every \(k\),

\( \displaystyle 0\leq y_k\leq k,\qquad y_k\leq kt_k-\sum_{i=1}^{K}u_{ki}. \)

The identity above proves both of the following:

• Every point of \(Q\) satisfies \(y_k\leq S_k(x)\) for every \(k\).
• Every \(x\in P\) extends to a point of \(Q\) satisfying \(y_k=S_k(x)\) simultaneously for every \(k\). Choose \(t_k=f_{(k)}(x)\) and \(u_{ki}=\max\{t_k-f_i(x),0\}\).

The polytope \(Q\) is nonempty and bounded. Its numbers of variables and constraints are \(O(nm+K^2)\), and its rational encoding length is polynomial in the original input length.

4. Exact lexicographic optimization takes polynomial time

Set \(Q_0=Q\). For \(k=1,\ldots,K\), solve the linear program

\( \displaystyle \alpha_k=\max\{y_k:z\in Q_{k-1}\}, \)

where \(z\) denotes all variables, and then set

\( Q_k=\{z\in Q_{k-1}:y_k=\alpha_k\}. \)

Each set \(Q_k\) is a nonempty face of \(Q_{k-1}\), because it is the set of maximizers of a linear functional on a nonempty compact polytope. Inductively, it is a face of \(Q\). Any point of \(Q_K\) therefore lexicographically maximizes \((y_1,\ldots,y_K)\) over \(Q\).

For completeness, the encoding lengths remain polynomial throughout this procedure. Every vertex of a face of \(Q\) is a vertex of \(Q\), so each \(\alpha_k\) is a coordinate of some vertex of the original polytope \(Q\). Vertex coordinates have polynomial bit length: after clearing denominators, a vertex solves a nonsingular subsystem of tight constraints, and Cramer’s rule bounds its numerator and denominator by determinants of polynomial-size integer matrices. Thus every added equality has polynomial encoding length. The algorithm uses \(K\) polynomial-size rational linear programs.

Let \(z^*\in Q_K\), with allocation component \(x^*\) and coordinates \(y^*\). Necessarily,

\( y_k^*=S_k(x^*)\quad\text{for every }k. \)

Otherwise, extending \(x^*\) with all coordinates equal to \(S_k(x^*)\), as permitted by Section 3, would weakly increase every coordinate and strictly increase at least one. That would contradict lexicographic optimality of \(y^*\).

If another allocation \(x'\in P\) had a lexicographically larger cumulative-sum vector, its extension to \(Q\) would likewise contradict optimality of \(y^*\). Therefore \(x^*\) lexicographically maximizes the cumulative sums and, by Section 2, the nondecreasing sorted recorded values. It is an \(\mathrm{FS\text{-}VER}\) allocation.

5. Feasibility is not guaranteed

Take one object type \(o\) with supply \(q_o=2\), and two applicant types \(a,b\), each of mass \(1\). Both have only \(o\) in their preferences, and the object ranks \(a\) strictly above \(b\).

The allocation constraints force \(x_{a,o}=x_{b,o}=1\). For the pair \((a,o)\), the preference sum is empty and only \(a\) has priority weakly above \(a\). Its stability inequality therefore requires

\( \displaystyle 0+\frac{x_{a,o}}{q_o}=\frac12\geq1, \)

which is false.

Thus the literal task of returning an allocation on every stated input is not well-defined. With the necessary convention that infeasibility may be reported—or under a feasibility promise—the exact computation is in \(\mathrm{P}\), including weak preferences and priorities.

⟨structured verdict parsed — rendered above⟩

The argument establishes polynomial-time exact computation whenever a fractionally stable allocation exists, together with polynomial-time detection of infeasibility. Its central steps are correct. I found one minor terminology error and no mathematical gap.

• The feasible region is correctly formulated.

Substituting the definition of \(p_{\theta,o}\) gives precisely the displayed linear stability inequalities. Positivity of every \(\mu_\theta\) and \(q_o\) justifies the divisions. Taking reciprocals of positive binary-encoded rationals preserves polynomial encoding length.

There are \(nm\) allocation variables and \(nm\) stability inequalities. Each inequality has polynomially many coefficients, so the entire explicit system has polynomial encoding length. Nonnegativity and the row constraints give \(0\leq x_{\theta,o}\leq\mu_\theta\), establishing boundedness.

The invoked theorem—exact feasibility testing and optimization for rational linear programs in time polynomial in binary input length—is applicable. It does not require a full-dimensional feasible region, which matters because allocation equalities are present. The cited [MIT notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial-time rational LP algorithms and the requisite encoding bounds.

• The recorded objectives and cumulative-sum transformation are valid.

Each nonempty preference prefix defines the stated rational linear function. Each type has at most \(m\) indifference classes, yielding \(K\leq nm\). The allocation constraints imply \(f_i(x)\in[0,1]\).

If empty prefixes are included in the task’s terminology, they add only constant-zero entries; this convention does not affect the optimization.

The proof of lexicographic equivalence is correct: at the first differing sorted coordinate, all preceding cumulative sums agree, and the current cumulative sums differ by precisely the same amount. Thus the transformation preserves both the first differing position and its comparison direction.

• The order-statistic identity is correct, including its boundary cases.

For every admissible \(t\), the sum of all positive parts dominates the sum of \(t-v_{(j)}\) over the first \(k\) indices. This justifies the displayed upper bound on the maximized expression.

At \(t=v_{(k)}\), the first \(k\) differences are nonnegative and every subsequent positive part vanishes. Equality therefore holds. This reasoning covers ties, values equal to zero or one, and both \(k=1\) and \(k=K\).

• The extended formulation has exactly the properties needed.

Its constraints imply
\(u_{ki}\geq\max\{t_k-f_i(x),0\}\), and hence \(y_k\leq S_k(x)\).

Conversely, the proposed choices of \(t_k\) and \(u_{ki}\) attain equality. All their bounds are satisfied because the recorded values lie in \([0,1]\). Also, \(0\leq S_k(x)\leq k\), so the bounds on \(y_k\) introduce no obstruction.

Different values of \(k\) have separate auxiliary variables, so these equality-attaining extensions can indeed be chosen simultaneously. Consequently, nonemptiness of \(P\) implies nonemptiness of \(Q\).

The variable and constraint counts are correct. Although explicitly expanding the functions \(f_i\) increases the number of coefficient entries, that increase remains polynomial. Every variable is bounded.

Minor issue: Section 2 says the formulation represents “upper bounds on these cumulative sums.” The actual relation is \(y_k\leq S_k(x)\): the cumulative sum bounds the auxiliary variable from above. The inequalities and all subsequent uses have the correct direction.

Minimum clarification: Replace that phrase with “auxiliary variables bounded above by these cumulative sums.”

• Sequential optimization is exact and polynomial-time.

Each optimization occurs over a nonempty compact polytope, so its maximum is attained. Restricting to the maximizers produces a nonempty face. The induction that every resulting set is a face of the original \(Q\) is valid.

Sequentially maximizing coordinates while fixing previous optimal values gives lexicographic maximization of the auxiliary vector.

The bit-length argument correctly avoids a possible accumulation problem: every optimal coordinate value is attained at a vertex of the original \(Q\). Rational vertex coordinates have polynomial bit length by the stated tight-constraint and determinant argument. Clearing denominators preserves polynomial bit length, and the determinant bounds therefore apply.

Thus all added equalities have polynomial encoding length, and the polynomial number of LP calls has polynomial total running time. A final optimizing LP also supplies a rational point in the final face.

• The transfer back to the allocation objective is sound.

Every feasible auxiliary vector is coordinatewise bounded above by the cumulative-sum vector of its allocation. If any inequality were strict at a lexicographic optimum, the simultaneous equality-attaining extension would lexicographically improve it. This is a valid contradiction.

Likewise, any allocation with a lexicographically larger cumulative-sum vector would yield a better feasible auxiliary vector. Together with Section 2, this proves the required ordinal egalitarian optimality.

• The infeasibility example is valid and appropriately limits the conclusion.

The example satisfies positive rational masses and supply, balanced totals, and valid preference and priority orders. Allocation feasibility forces both entries to equal one.

For the top-priority type, the preference contribution is zero and the priority contribution is \(1/2\). The required inequality fails. Therefore, the task’s assumptions genuinely do not ensure the existence of a fractionally stable allocation.

Reporting infeasibility is consequently a necessary qualification to an algorithm defined on every stated input. The prover explicitly provides that qualification and establishes the promised polynomial-time result.

No new lemma, alternative argument, or substantive repair is needed.

⟨structured verdict parsed — rendered above⟩