d4-conf-aaai-2021-2045 (d4-conf-aaai-2021-2045)

Given finite types \(T\) with rational masses \(\mu_t\), rational per-capita capacities \(q_1,\ldots,q_k\) summing to \(1\), and rational costs ordered by type as \(c_{t1}\le\cdots\le c_{tk}\), compute a feasible mass assignment \(x_{tj}\) that lexicographically minimizes the descending multiset of assigned costs, and separately of regrets \(d_{tj}=c_{tj}-\min_\ell c_{t\ell}\). Prove or refute that filling interventions \(k,k-1,\ldots,1\) with the lowest-cost remaining mass, splitting at a cutoff when needed, returns these optima.

A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=k\ge1\) interventions with positive binary-rational capacities \(q_j\) satisfying \(\sum_jq_j=1\). Costs are binary rationals satisfying \(0\le c_{t1}\le\cdots\le c_{tk}\le1\); define regrets \(d_{tj}=c_{tj}-c_{t1}\).
Assume the entries of \(C\) are pairwise distinct and the entries \(d_{tj}\) with \(j\ge2\) are pairwise distinct; the unavoidable equalities \(d_{t1}=0\) are permitted.
A feasible assignment consists of divisible masses \(x_{tj}\ge0\) with \(\sum_jx_{tj}=\mu_t\) and \(\sum_tx_{tj}=q_j\). Each portion incurs its assigned cost or regret, rather than a type's average outcome.
For either array \(a=C\) or \(a=D\), list its distinct values as \(v_1>\cdots>v_s\). The descending mass profile is \(h_a(x)=(\sum_{t,j:a_{tj}=v_r}x_{tj})_{r=1}^s\); lexicographically minimize this vector, separately for costs and regrets.
The proposed greedy procedure visits \(j=k,k-1,\ldots,1\), filling capacity \(q_j\) from remaining types in increasing order of \(a_{tj}\), splitting a type's remaining mass at the cutoff; all mass left for intervention \(1\) is assigned there.

Is computing an optimal assignment for each objective polynomial-time solvable in \(m,\tau,L\), or NP-hard, where \(L\) is the total binary input length? Does the specified greedy procedure always return an optimum for each objective?

For finite unit-demand agents with row-sorted costs and the stated absence of relevant ties, lowest-cost-first filling from the last intervention backward computes both objectives in \(O(nk)\) arithmetic operations. [Nguyen, Das, and Garnett (2021)](https://cdn.aaai.org/ojs/16707/16707-13-20201-1-2-20210518.pdf)
No result settling this exact divisible-mass formulation was verified.

Result

Both objectives are polynomial-time solvable in \(m,\tau,L\). The specified greedy procedure always returns the unique optimal assignment for each objective. The two objectives may have different optimal assignments.

The proof below directly handles divisible masses. The corresponding unit-demand rule appears in Proposition 2 and Algorithm 1 of [Nguyen, Das, and Garnett (2021)](https://cdn.aaai.org/ojs/16707/16707-13-20201-1-2-20210518.pdf).

1. Properties of the two arrays

Fix either \(a=C\) or \(a=D\), and write \(h_a\) for its descending mass profile.

Row sorting and pairwise distinctness of the entries of \(C\) imply

\(c_{t1}<c_{t2}<\cdots<c_{tk}\).

Subtracting \(c_{t1}\) throughout row \(t\) therefore gives

\(0=d_{t1}<d_{t2}<\cdots<d_{tk}\).

Consequently, either chosen array satisfies:

• Every row is strictly increasing.
• Within each column \(j\ge2\), all entries are distinct.

The equal regrets in column \(1\) will not cause a problem.

An optimal assignment exists. Indeed, the feasible set

\(P=\{x\ge0:\ \sum_jx_{tj}=\mu_t,\ \sum_tx_{tj}=q_j\}\)

is nonempty because \(x_{tj}=\mu_tq_j\) is feasible. It is closed and bounded, since \(0\le x_{tj}\le\mu_t\), and hence compact.

Each coordinate of \(h_a\) is a continuous linear function. Minimize its first coordinate over \(P\), then its second over the minimizers of the first, and continue through all coordinates. At each step, the minimizer set is nonempty and compact. Any assignment in the final set is lexicographically optimal: a lexicographically smaller profile would contradict the minimum at its first differing coordinate.

2. The greedy cutoff property

Let \(g\) be the greedy assignment for \(a\). Before filling column \(j\), define the remaining mass of type \(t\) by

\(r_t=\mu_t-\sum_{\ell>j}g_{t\ell}\).

Its total is \(\sum_t r_t=\sum_{\ell\le j}q_\ell\), so enough mass remains to fill column \(j\). Thus the procedure produces a feasible assignment.

For \(j\ge2\), order the types with positive remaining mass by their distinct values \(a_{tj}\). Greedy filling assigns all remaining mass of every type preceding the cutoff, possibly part of the cutoff type, and no mass of any type following it.

It follows that, for distinct types \(t,u\),

\(g_{tj}>0\ \text{and}\ g_{uj}<r_u\quad\Longrightarrow\quad a_{tj}<a_{uj}.\)

To justify this implication, \(g_{tj}>0\) places \(t\) at or before the cutoff, while \(g_{uj}<r_u\) places \(u\) at or after it. Since the types are distinct, they cannot both be the cutoff type, so \(t\) precedes \(u\) strictly.

3. Every assignment differing from greedy can be improved

Let \(x\) be a feasible assignment with \(x\ne g\). Choose the largest column index \(j\) at which they differ. Hence

\(x_{t\ell}=g_{t\ell}\quad\text{for all }t\text{ and }\ell>j.\)

Necessarily \(j\ge2\): if every column above \(1\) agrees, the row-sum constraints force column \(1\) to agree as well.

Both assignments fill column \(j\) to the same capacity. Since their column vectors differ, there are distinct types \(t,u\) such that

\(x_{tj}<g_{tj},\qquad x_{uj}>g_{uj}.\)

Because the higher columns agree, both assignments have the same remaining masses \(r_t\) before column \(j\). In particular, \(x_{uj}\le r_u\). Therefore

\(g_{tj}>0,\qquad g_{uj}<r_u,\)

and the cutoff property gives \(a_{tj}<a_{uj}\).

Also, some mass of type \(t\) lies in a column \(i<j\), since

\(\sum_{i<j}x_{ti}=r_t-x_{tj}\ge g_{tj}-x_{tj}>0.\)

Choose such an \(i\), and set

\(\varepsilon=\min\{g_{tj}-x_{tj},\ x_{uj}-g_{uj},\ x_{ti}\}>0.\)

Define \(y\) by changing only four entries:

\[ \]
\(y_{tj}=x_{tj}+\varepsilon,\qquad y_{uj}=x_{uj}-\varepsilon,\)

\(y_{ti}=x_{ti}-\varepsilon,\qquad y_{ui}=x_{ui}+\varepsilon.\)

Both decreased entries remain nonnegative: \(\varepsilon\le x_{ti}\) and \(\varepsilon\le x_{uj}-g_{uj}\le x_{uj}\). Every affected row and column receives one increase and one decrease of the same size. Thus \(y\) is feasible.

Let \(v=a_{uj}\). Strict row sorting and the cutoff inequality give

\(a_{ti}<a_{tj}<v,\qquad a_{ui}<v.\)

Hence all profile coordinates corresponding to values greater than \(v\) are unchanged. At value \(v\), the total assigned mass decreases by exactly \(\varepsilon\): the only modified entry with value \(v\) is \((u,j)\). All other changes occur at smaller values. Consequently,

\(h_a(y)<_{\mathrm{lex}}h_a(x).\)

Thus every feasible assignment different from \(g\) fails to be optimal.

Since an optimal assignment exists, it must equal \(g\). This proves optimality and uniqueness for either choice of \(a\). For \(k=1\), the row constraints already force \(x_{t1}=\mu_t\), so the conclusion also holds.

4. Polynomial bit complexity

A simple implementation sorts the \(\tau\) types by \(a_{tj}\) separately for each column \(j\ge2\), then scans that order to fill the column. Column \(1\) receives the remaining masses. This requires

\(O\!\left(m\tau\log(\tau+1)\right)\)

rational comparisons and arithmetic operations. Computing \(D\) first requires \(O(m\tau)\) additional subtractions.

To bound the size of the mass arithmetic, let \(Q\) be the product of the denominators of all input masses and capacities. Its binary length is \(O(L)\), because the sum of the binary lengths of those denominators is at most \(L\).

Represent masses and capacities as integer multiples of \(1/Q\). Every greedy step uses only comparisons, minima, and subtraction. Therefore all residual masses, unfilled capacities, and output entries remain multiples of \(1/Q\). Their values lie between \(0\) and \(1\), so their integer numerators lie between \(0\) and \(Q\) and have \(O(L)\) bits.

The cost and regret entries also have \(O(L)\)-bit rational representations; taking a difference of two input rationals preserves this bound. Thus every required arithmetic operation has polynomial bit complexity, and the entire computation is polynomial in \(m,\tau,L\). No expansion into individual mass units is needed.

⟨structured verdict parsed — rendered above⟩

The output fully resolves the task. Both objectives are polynomial-time solvable, and the specified greedy procedure returns the unique optimal assignment under the stated assumptions. No mathematical gaps or false steps were found.

• Array properties. Pairwise distinctness of the cost entries, together with row sorting, implies \(c_{t1}<\cdots<c_{tk}\). Subtracting \(c_{t1}\) preserves strict inequalities within each row. The assumptions also guarantee distinct entries within every column \(j\ge2\) for both arrays. These are precisely the properties used in the exchange argument.

• Existence of an optimum. The proposed assignment \(x_{tj}=\mu_tq_j\) satisfies both sets of marginal constraints. The feasible set is closed and bounded in finite-dimensional space, hence compact. Successive minimization of the finitely many continuous profile coordinates produces nonempty compact minimizer sets and establishes existence of a lexicographic optimum.

• Greedy feasibility and cutoff property. The remaining-mass identity is correct and ensures that each column can be filled. For distinct types \(t,u\), the conditions \(g_{tj}>0\) and \(g_{uj}<r_u\) imply that both types have positive remaining mass. Their positions relative to the cutoff, together with column distinctness, correctly imply \(a_{tj}<a_{uj}\). A partially filled cutoff type causes no exception.

• Choice of an exchange. For any feasible \(x\ne g\), the largest differing column exists and must satisfy \(j\ge2\). Equal column totals supply distinct types with \(x_{tj}<g_{tj}\) and \(x_{uj}>g_{uj}\). Agreement in higher columns gives identical remaining masses, so the cutoff property applies. The displayed lower bound on \(\sum_{i<j}x_{ti}\) is valid and guarantees an entry \(x_{ti}>0\).

• Exchange feasibility. All three quantities defining \(\varepsilon\) are strictly positive. Its bounds ensure nonnegativity of the decreased entries, while the four modifications preserve every row and column total. Thus \(y\) is feasible.

• Strict profile improvement. With \(v=a_{uj}\), all three other modified entries have values strictly below \(v\). Consequently, every profile coordinate above \(v\) is unchanged, and the coordinate at \(v\) decreases by exactly \(\varepsilon\). Unmodified entries tied at \(v\) cannot affect this calculation. The equal zero regrets in column \(1\) therefore cause no difficulty. The claimed strict lexicographic improvement follows.

• Optimality, uniqueness, and edge cases. The argument excludes every feasible assignment other than \(g\) from optimality. Combined with existence, this establishes both optimality and uniqueness; no convergence or repeated-exchange argument is needed. The case \(k=1\) is explicitly and correctly handled. A support consisting of one type also creates no exception.

• Polynomial bit complexity. Sorting each relevant column and scanning its types gives the stated operation bound. The product \(Q\) has binary length \(O(L)\), and all mass calculations preserve integer multiples of \(1/Q\) with numerators between \(0\) and \(Q\). Cost differences and rational comparisons also involve only \(O(L)\)-bit operands. These bounds justify polynomial total bit complexity and polynomial output size without expanding masses into individual units.

• Citation and proof dependence. Proposition 2 and Algorithm 1 describe the corresponding backward greedy rule for the finite unit-demand setting. The attribution is accurate, and the divisible-mass proof does not depend on importing that result. [Nguyen, Das, and Garnett (2021)](https://cdn.aaai.org/ojs/16707/16707-13-20201-1-2-20210518.pdf)

No additional mathematical clarification or repair is required.

⟨structured verdict parsed — rendered above⟩