Answer: Both unit-sum and unit-range valuations have tight uniform worst-case ratio \(\Theta(\tau)\) under the stated unrestricted priority vectors. A polynomial-time algorithm guarantees \(\tau\), and every deterministic one-query-per-pair algorithm has ratio at least \(\tau-1\) on suitable inputs.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet X denote one of the properties in the set {Pareto-optimal, rank-maximal, max-cardinality rank- maximal, and fair}. Let A be a non-adaptive determinis- tic algorithm that always produces a matching that satisfies property X and asks at most one query per (agent, object) pair. If there are n agents with unit-sum valuation functions or unit-range valuations, then L(A) ∈Ω(√n).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_\theta\), ordinal preferences and acceptability data, object capacities \(q_j\), a priority vector \(p\), and hidden type-level valuations \(v_\theta\) consistent with the unit-sum or unit-range model, choose one threshold \(t_{\theta j}\) non-adaptively for every type-category pair, observe the bits \(Q(\theta,j,t_{\theta j})\), and output a feasible priority-\(p\) mass assignment \(y\) minimizing the worst-case ratio \(\max_{z\in S_p} SW(z\mid v)/SW(y\mid v)\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Normalize \(\sum_\theta\mu_\theta=1\). There are \(m\ge2\) object categories with positive binary-rational capacities \(q_j\), normalized by \(\sum_jq_j=1\).
Each type has a nonempty acceptable set \(A_\theta\) and a weak preference order on it; define \(r_{\theta j}=1+|\{k\in A_\theta:k\succ_\theta j\}|\). Hidden valuations are common to all mass of a type, satisfy \(v_{\theta j}\in[0,1]\), vanish outside \(A_\theta\), and satisfy \(j\succeq_\theta k\iff v_{\theta j}\ge v_{\theta k}\) within \(A_\theta\).
Treat separately unit-sum valuations, \(\sum_jv_{\theta j}=1\), and unit-range valuations, \(\max_{j\in A_\theta}v_{\theta j}=1\), \(\min_{j\in A_\theta}v_{\theta j}=0\); the latter requires at least two preference indifference classes per type.
A feasible mass assignment satisfies \(y_{\theta j}\ge0\), \(y_{\theta j}=0\) outside acceptability, \(\sum_jy_{\theta j}\le\mu_\theta\), and \(\sum_\theta y_{\theta j}\le q_j\); unmatched mass has zero welfare. Given a nonconstant \(p\in\mathbb Z_{\ge0}^{m}\), let \(S_p\) be the feasible assignments maximizing \(\sum_{\theta,j\in A_\theta}p_{r_{\theta j}}y_{\theta j}\).
A deterministic algorithm chooses one binary-rational threshold \(t_{\theta j}\in[0,1]\) for each type-category pair using only the public input, receives \(Q(\theta,j,t_{\theta j})=\mathbf1\{v_{\theta j}\ge t_{\theta j}\}\), and outputs a rational assignment \(y_A(I,Q(v))\in S_p\). It may split a type's mass among categories.
Define \(SW(y\mid v)=\sum_{\theta,j}y_{\theta j}v_{\theta j}\) and \(D(A,I)=\sup_{v\text{ consistent with }I}\frac{\max_{z\in S_p}SW(z\mid v)}{SW(y_A(I,Q(v))\mid v)}\), with \(0/0=1\) and a positive numerator divided by zero equal to \(+\infty\). Let \(L\) be the public input's total bit length, including masses, capacities, and priorities; state running times in \(m,\tau,L\) and any additional parameters.
What asymptotically tight worst-case welfare approximation ratio can deterministic algorithms running in polynomial time in \(m,\tau,L\) guarantee in this model, separately for unit-sum and unit-range valuations, allowing dependence on \(\mu,q,p\)?
For discrete societies with \(n\) agents and \(n\) objects, one non-adaptive threshold query per pair entails an \(\Omega(\sqrt n)\) welfare-ratio lower bound for rank-maximal, maximum-cardinality rank-maximal, and fair matchings; upper bounds are \(O(n^{2/3})\) for unit-sum and \(O(\sqrt n)\) for unit-range valuations. [Ma–Menon–Larson](https://arxiv.org/pdf/2011.13977)
No result settling this exact mass-assignment query model was located in the literature search.
For the model as stated, the tight uniform worst-case ratio is \(\Theta(\tau)\), for both unit-sum and unit-range valuations.
More precisely:
The upper bound needs no valuation information. Section 5 gives a polynomial-time computable, public-input-dependent refinement \(K(I)\le\tau\).
The scope matters: the question permits arbitrary nonconstant nonnegative priority vectors. The lower bound uses \(p_2=1\) and all other priorities zero. Consequently, it does not establish a matching bound for the narrower rank-maximal or fair subclasses studied by [Ma–Menon–Larson](https://arxiv.org/pdf/2011.13977).
The upper bound rests on a property of transportation polytopes. We prove it explicitly because maximizing different preference prefixes separately would otherwise require an additional factor depending on \(m\).
Lemma. Let \(\mathcal T\) be a nonempty transportation polytope with prescribed positive row masses \(b_i\), prescribed positive column masses \(c_j\), and an allowed bipartite edge set. Fix a row \(h\) and an ordering of the columns. There is a matrix in \(\mathcal T\) whose row \(h\) simultaneously maximizes its allocation to every prefix of that ordering.
Proof. Write \(J\) for the column set and \(N_i\subseteq J\) for the allowed neighbors of row \(i\). The total row and column masses agree.
For \(C\subseteq J\), define
\(\displaystyle H(C)=\sum_{\substack{i\ne h\\N_i\subseteq C}}b_i,\qquad f(C)=\sum_{j\in C}c_j-H(C).\)
We first characterize the possible row-\(h\) vectors. A vector \(x\) is such a row vector precisely when
\(\displaystyle x\ge0,\qquad x_j=0\text{ for }j\notin N_h,\qquad x(J)=b_h,\qquad x(C)\le f(C)\text{ for every }C\subseteq J,\)
where \(x(C)=\sum_{j\in C}x_j\).
Necessity follows because all other rows whose neighbors lie inside \(C\) must receive their entire mass from the residual column capacities in \(C\).
For sufficiency, the singleton inequalities ensure \(c_j-x_j\ge0\). For any subset \(R\) of the other rows, let \(N(R)=\bigcup_{i\in R}N_i\). Then
\(\displaystyle \sum_{i\in R}b_i\le H(N(R))\le\sum_{j\in N(R)}(c_j-x_j).\)
These are the capacitated Hall inequalities. By the max-flow min-cut theorem, they suffice to allocate all other row masses to the residual capacities: a finite cut associated with \(R\) has capacity equal to the mass of rows outside \(R\), plus the residual capacity of \(N(R)\). The displayed inequality makes every such cut at least the required total flow. Residual total capacity equals the total mass of the other rows, so all row and column equalities are satisfied.
We next put this row-vector characterization into a form where a greedy construction applies.
For each fixed nonempty set \(N_i\), the function \(\mathbf1\{N_i\subseteq C\}\) is supermodular. Indeed, for any \(C,D\subseteq J\),
\(\displaystyle \mathbf1\{N_i\subseteq C\}+\mathbf1\{N_i\subseteq D\}\le\mathbf1\{N_i\subseteq C\cup D\}+\mathbf1\{N_i\subseteq C\cap D\}.\)
Thus \(H\) is supermodular and \(f\) is submodular. Feasibility of \(\mathcal T\) implies \(f(C)\ge0\) for every \(C\). Moreover, \(f(\varnothing)=0\) and \(f(J)=b_h\).
Although \(f\) need not be monotone, its monotone closure
\(\displaystyle g(C)=\min_{D\supseteq C}f(D)\)
is nonnegative, monotone, and submodular. To verify submodularity, choose minimizing supersets \(D\supseteq C\) and \(E\supseteq C'\). Then
\(\displaystyle g(C)+g(C')=f(D)+f(E)\ge f(D\cup E)+f(D\cap E)\ge g(C\cup C')+g(C\cap C').\)
For nonnegative \(x\), the inequalities \(x(C)\le f(C)\) for all \(C\) are equivalent to \(x(C)\le g(C)\): if \(D\supseteq C\), then \(x(C)\le x(D)\le f(D)\).
Define
\(\displaystyle r(C)=g(C\cap N_h).\)
An existing feasible row vector, supported on \(N_h\), shows \(g(N_h)\ge b_h\); monotonicity and \(g(J)=b_h\) give equality. Therefore \(r\) is normalized, monotone, submodular, and satisfies \(r(J)=b_h\). The possible row vectors are exactly
\(\displaystyle \{x\ge0:x(J)=b_h,\ x(C)\le r(C)\text{ for every }C\subseteq J\}.\)
To check this last equivalence, a supported vector satisfying the \(g\)-inequalities has \(x(C)=x(C\cap N_h)\le r(C)\). Conversely, the \(r\)-inequalities imply \(x(J\setminus N_h)=0\) and imply the \(g\)-inequalities because \(r(C)\le g(C)\).
Now order the columns as \(j_1,\ldots,j_M\), and let \(C_\ell=\{j_1,\ldots,j_\ell\}\). Set
\(\displaystyle x_{j_\ell}=r(C_\ell)-r(C_{\ell-1}).\)
These entries are nonnegative and sum to \(b_h\). They satisfy every subset inequality. Specifically, for a subset \(C\), submodularity says that the marginal contribution of each element of \(C\), when added after all preceding columns, is no greater than its marginal contribution when added after only the preceding elements of \(C\). Summing gives \(x(C)\le r(C)\).
Hence this vector extends to a matrix in \(\mathcal T\). It satisfies \(x(C_\ell)=r(C_\ell)\), while every feasible row vector satisfies \(x(C_\ell)\le r(C_\ell)\). It therefore maximizes every prefix simultaneously. \(\square\)
Let \(P\) be the feasible assignment polytope. It is nonempty and compact: the zero assignment is feasible, and each coordinate is bounded by its type mass. Write
\(\displaystyle W^*=\max_{y\in P}\sum_{\theta,j\in A_\theta}p_{r_{\theta j}}y_{\theta j}.\)
Thus \(S_p\) is a nonempty compact rational face of \(P\).
Add an artificial row \(\star\), of mass \(1\), and an artificial column \(\bot\), of capacity \(1\). Lift an assignment \(y\in P\) by setting
\(\displaystyle \widetilde y_{\theta j}=y_{\theta j},\qquad \widetilde y_{\theta\bot}=\mu_\theta-\sum_jy_{\theta j},\)
\(\displaystyle \widetilde y_{\star j}=q_j-\sum_\theta y_{\theta j},\qquad \widetilde y_{\star\bot}=\sum_{\theta,j}y_{\theta j}.\)
The normalizations make every augmented row and column equality hold. Conversely, every feasible augmented transportation matrix determines exactly this lift of its restriction to the original coordinates. Hence the lifting is a bijection.
Give original edges their priority weights and artificial edges weight zero. By linear-programming duality, an optimal dual solution has row and column potentials \(a_i,b_j\) satisfying
\(\displaystyle a_i+b_j\ge w_{ij}\)
on every allowed edge. For a feasible transportation matrix, the difference between the dual objective and its objective is
\(\displaystyle \sum_{i,j}(a_i+b_j-w_{ij})\widetilde y_{ij}.\)
Every summand is nonnegative. Therefore a matrix is optimal exactly when it uses only tight edges, those satisfying \(a_i+b_j=w_{ij}\).
Consequently, the lift of \(S_p\) is a nonempty transportation polytope with prescribed row and column masses and a restricted allowed edge set. The lemma applies.
For type \(\theta\), let its indifference classes, best first, be
\(\displaystyle C_{\theta,1},\ldots,C_{\theta,d_\theta},\)
and define the preferred prefixes
\(\displaystyle P_{\theta,\ell}=\bigcup_{a=1}^{\ell}C_{\theta,a}.\)
Order the augmented columns by these classes, placing the remaining columns afterward. The lemma gives an assignment \(y^{(\theta)}\in S_p\) simultaneously maximizing
\(\displaystyle \sum_{j\in P_{\theta,\ell}}y_{\theta j}\)
for every \(\ell\).
This assignment can be found with one LP, rather than by constructing the set functions in the lemma. Maximize over \(S_p\) the public objective
\(\displaystyle \sum_{\ell=1}^{d_\theta}(d_\theta-\ell+1)\sum_{j\in C_{\theta,\ell}}y_{\theta j}=\sum_{\ell=1}^{d_\theta}\sum_{j\in P_{\theta,\ell}}y_{\theta j}.\)
Each summand is bounded by its individual maximum, and the lemma shows that all these maxima are simultaneously attainable. Every optimizer therefore attains every prefix maximum.
For any consistent valuation, let \(u_{\theta,\ell}\) be the common value of class \(C_{\theta,\ell}\), and put \(u_{\theta,d_\theta+1}=0\). Then
\(\displaystyle \sum_jy_{\theta j}v_{\theta j}=\sum_{\ell=1}^{d_\theta}(u_{\theta,\ell}-u_{\theta,\ell+1})\sum_{j\in P_{\theta,\ell}}y_{\theta j}.\)
All coefficients are nonnegative. Thus, for every \(z\in S_p\),
\(\displaystyle \sum_jy^{(\theta)}_{\theta j}v_{\theta j}\ge\sum_jz_{\theta j}v_{\theta j}.\)
This holds for both normalizations, and in fact for every nonnegative valuation respecting the weak order.
Output
\(\displaystyle \overline y=\frac1\tau\sum_\theta y^{(\theta)}.\)
Convexity gives \(\overline y\in S_p\). Nonnegativity of utilities and the preceding dominance property imply, for every \(z\in S_p\),
\(\displaystyle SW(\overline y\mid v)=\frac1\tau\sum_\theta SW(y^{(\theta)}\mid v)\ge\frac1\tau\sum_\theta\sum_jy^{(\theta)}_{\theta j}v_{\theta j}\ge\frac1\tau SW(z\mid v).\)
Taking a welfare-maximizing \(z\) proves \(D(A,I)\le\tau\). If the output welfare is zero, the inequality forces the numerator to be zero, so the specified ratio convention is respected.
To meet the query requirement, choose \(t_{\theta j}=0\) for every pair and ignore the answers.
First solve the priority LP to obtain \(W^*\). Then solve the \(\tau\) type-specific LPs over the feasible constraints together with the equality defining \(S_p\).
There are at most \(m\tau\) variables and \(O(m+\tau)\) constraints apart from nonnegativity. The new ordinal coefficients are integers at most \(m\). Standard exact rational LP algorithms return rational optima of polynomial encoding length in polynomial bit complexity; their hypotheses hold here because the polytopes are nonempty, rational, and bounded.
Thus the algorithm uses \(\tau+1\) LP solves and runs in \(\operatorname{poly}(m,\tau,L)\) time. Averaging preserves polynomial encoding length. No running-time dependence on reciprocal masses or capacities is required.
Fix \(k\ge2\), and define
\(\displaystyle s=\lceil\log_2 k\rceil,\qquad \beta=2^{-(s+1)},\qquad R=\frac12-\beta.\)
There are categories \(a,b,z,c_1,\ldots,c_s\), so \(m=s+3\). Set
\(\displaystyle q_a=\frac12,\qquad q_b=\beta,\qquad q_{c_\ell}=R\,2^{-\ell}\quad(1\le\ell\le s),\qquad q_z=R\,2^{-s}.\)
These capacities are positive dyadic rationals and sum to \(1\).
There are candidate types \(1,\ldots,k\), with masses
\(\displaystyle \mu_i=\beta\quad(1\le i<k),\qquad \mu_k=\frac12-(k-1)\beta,\)
and one additional type \(d\), with \(\mu_d=1/2\). Every candidate mass is at least \(\beta\), and the masses sum to \(1\).
Choose distinct subsets \(T_1,\ldots,T_k\subseteq\{1,\ldots,s\}\). Candidate \(i\) has preference classes
\(\displaystyle \{a\}\succ_i\{b\}\succ_i\bigl(\{z\}\cup\{c_\ell:\ell\in T_i\}\bigr),\)
with all other categories unacceptable. Thus the candidate types are distinct even if a type is identified solely by its public ordinal data.
Type \(d\) has \(\{b\}\succ_d\{a\}\succ_d\{z\}\).
Take \(p_2=1\) and \(p_r=0\) for every \(r\ne2\). This is a permitted nonconstant priority vector.
The priority objective is
\(\displaystyle y_{da}+\sum_{i=1}^k y_{ib}.\)
Its maximum is \(q_a+q_b\): assign all mass of type \(d\) to \(a\), and assign mass \(\beta\) of any candidate to \(b\). Therefore every \(y\in S_p\) satisfies
\(\displaystyle y_{da}=\frac12,\qquad \sum_i y_{ib}=\beta.\)
In particular, category \(a\) is saturated by type \(d\), and type \(d\)'s mass is exhausted. Every top-choice allocation is zero throughout \(S_p\).
Choose parameters \(0<\epsilon_i,\epsilon_d<1/4\). All bottom-class and unacceptable values are zero.
For unit-sum valuations, use
\(\displaystyle v_{ia}=1-\epsilon_i,\qquad v_{ib}=\epsilon_i,\qquad v_{db}=1-\epsilon_d,\qquad v_{da}=\epsilon_d.\)
For unit-range valuations, use
\(\displaystyle v_{ia}=1,\qquad v_{ib}=\epsilon_i,\qquad v_{db}=1,\qquad v_{da}=\epsilon_d.\)
Each family satisfies its normalization and exactly represents the stated three-class orders. Consequently, for either normalization and every \(y\in S_p\),
\(\displaystyle SW(y\mid v)=\frac12\epsilon_d+\sum_i y_{ib}\epsilon_i.\)
Fix any deterministic algorithm and its publicly chosen thresholds.
For unit-range valuations, top, bottom, and unacceptable values are fixed. For a second-choice query, every sufficiently small positive parameter answers yes when its threshold is zero and no when its threshold is positive.
For unit-sum valuations, second-choice queries behave identically. A top-choice query with threshold \(1\) always answers no; a top-choice query with threshold below \(1\) answers yes whenever \(\epsilon_i<1-t\).
There are finitely many thresholds. Hence, separately for either normalization, there is an \(\eta\in(0,1/4]\) such that all parameter vectors in \((0,\eta)^{k+1}\) produce the same transcript. This includes thresholds at both endpoints.
The algorithm therefore returns one fixed assignment on this family. Put \(x_i=y_{ib}\). Since \(\sum_i x_i=\beta\), some candidate \(h\) satisfies \(x_h\le\beta/k\).
For \(0<\epsilon<\eta\), now set
\(\displaystyle \epsilon_h=\epsilon,\qquad \epsilon_i=\epsilon^2\ (i\ne h),\qquad \epsilon_d=\epsilon^2.\)
All these valuations retain the same transcript.
Assigning the entire capacity of \(b\) to \(h\) is feasible because \(\mu_h\ge\beta\). It maximizes welfare, since all other candidates have smaller second-choice values. Thus
\(\displaystyle \max_{z\in S_p}SW(z\mid v)=\beta\epsilon+\frac12\epsilon^2,\)
whereas the algorithm obtains
\(\displaystyle SW(y_A\mid v)=x_h\epsilon+\left(\frac12+\beta-x_h\right)\epsilon^2.\)
If \(x_h>0\), their ratio tends, as \(\epsilon\) decreases to zero, to \(\beta/x_h\ge k\). If \(x_h=0\), the ratio tends to infinity. Taking the supremum proves
\(\displaystyle D(A,I_k)\ge k=\tau-1.\)
The proof permits fractional \(x_i\); it makes no integrality assumption. It also imposes no computational restriction on the algorithm beyond the stated finite non-adaptive queries.
The upper bound can retain dependence on \(\mu,q,p\) through the geometry of \(S_p\).
Define
\(\displaystyle U_{\theta,\ell}=\max_{z\in S_p}\sum_{j\in P_{\theta,\ell}}z_{\theta j}.\)
The type-specific assignment \(y^{(\theta)}\) from Section 3 gives all these values simultaneously.
Solve the following additional LP:
\(\displaystyle \alpha^*=\max\left\{\alpha:0\le\alpha\le1,\ y\in S_p,\ \sum_{j\in P_{\theta,\ell}}y_{\theta j}\ge\alpha U_{\theta,\ell}\text{ for every }\theta,\ell\right\}.\)
The averaged assignment shows \(\alpha^*\ge1/\tau\). Define \(K(I)=1/\alpha^*\), so \(1\le K(I)\le\tau\).
For its optimal assignment \(y\), every \(z\in S_p\) satisfies
\(\displaystyle \sum_{j\in P_{\theta,\ell}}y_{\theta j}\ge\alpha^*\sum_{j\in P_{\theta,\ell}}z_{\theta j}.\)
Applying the nonnegative prefix decomposition of welfare from Section 3 yields
\(\displaystyle SW(y\mid v)\ge\alpha^*SW(z\mid v).\)
Thus this assignment guarantees \(D(A,I)\le K(I)\) under both normalizations. Computing it requires \(\tau+2\) LP solves in total and still takes \(\operatorname{poly}(m,\tau,L)\) time.
For the lower-bound inputs, \(K(I_k)=k\). Indeed, each candidate's prefix through \(b\) has maximum \(\beta\), so summing the corresponding constraints forces \(\alpha\le1/k\). Conversely, averaging the \(k\) candidate-specific prefix-maximizing assignments gives \(\alpha=1/k\); type \(d\)'s prefix allocations are fixed throughout \(S_p\). Therefore the public-input-dependent guarantee is exactly optimal on these inputs.
This does not claim that \(K(I)\) is optimal on every individual input. For example, unit-range valuations with exactly two indifference classes per type are publicly determined, so welfare can then be optimized exactly. The proved \(\Theta(\tau)\) characterization concerns the unrestricted worst case asked for here.
⟨structured verdict parsed — rendered above⟩
The claimed uniform worst-case bound of \(\Theta(\tau)\) is proved for both normalizations, under the unrestricted priority vectors in the task. The upper bound accommodates fractional assignments, and the lower bound applies even to computationally unrestricted deterministic algorithms with the prescribed queries. I found no major or minor mathematical issues.
The set function \(H\) is supermodular, so \(f\) is submodular. Feasibility implies \(f(C)\ge0\); positive row masses and feasibility also ensure that no row has an empty neighborhood. Thus \(f(\varnothing)=0\) and \(f(J)=b_h\).
The monotone closure \(g\) has the claimed properties. Its submodularity proof uses minimizing supersets correctly, and its inequalities are equivalent to those for \(f\) when \(x\ge0\). The restriction \(r(C)=g(C\cap N_h)\) correctly enforces support on \(N_h\). The existing feasible row vector establishes \(g(N_h)=b_h\).
Finally, the greedy marginal construction satisfies every subset inequality by the diminishing-marginal consequence of submodularity. It attains each prefix bound simultaneously. This establishes the lemma without an omitted structural theorem.
The transportation dual is stated correctly. For a fixed optimal dual solution, the objective gap is a sum of nonnegative slack-times-flow terms. Therefore optimal matrices are exactly the feasible matrices supported on tight edges. This supplies the restricted transportation polytope required by the lemma.
The welfare decomposition is correct, including when the lowest acceptable value is positive: setting the additional value to zero accounts for the full acceptable-set allocation. Every coefficient is nonnegative. Consequently, the resulting assignment maximizes the chosen type’s welfare over \(S_p\) for every consistent valuation. Neither normalization adds an unmet hypothesis.
When the averaged assignment has zero welfare, the inequality forces every comparator’s welfare to be zero. The convention \(0/0=1\) therefore causes no exception. Threshold zero is permitted for every pair, so ignoring the answers complies with the query model.
Computing \(W^*\), imposing its equality, solving the type-specific LPs, and averaging their rational outputs all preserve polynomial bit complexity. The claimed dependence \(\operatorname{poly}(m,\tau,L)\) does not conceal dependence on reciprocal masses or capacities.
\(k\beta\le1/2\), so \(\mu_k\ge\beta\), and all masses are positive and sum to \(1\).
There are enough distinct subsets to define the \(k\) distinct candidate types. Their middle category has rank \(2\), regardless of the size of the bottom tie. Thus the priority objective is exactly the expression given.
The objective is bounded above by \(q_a+q_b\), and the displayed feasible assignment attains this bound. Equality forces both stated saturation conditions. Those conditions exhaust type \(d\)’s mass and category \(a\)’s capacity, proving that every top-choice allocation is zero on \(S_p\).
For any fixed finite threshold collection, sufficiently small positive parameters produce the same answers. The argument handles thresholds at \(0\) and \(1\), including the varying top values in the unit-sum case. A common positive \(\eta\) therefore exists.
Determinism makes the output fixed on that transcript. Since the candidate allocations to \(b\) sum to \(\beta\), some candidate receives at most \(\beta/k\). The subsequent choice of parameters remains inside the common-transcript family.
Their ratio tends to at least \(k\) when \(x_h>0\), and diverges when \(x_h=0\). A limiting ratio suffices because distortion is defined as a supremum; attainment is unnecessary. This proves the lower bound for fractional outputs under both normalizations.
On the lower-bound inputs, summing the candidate constraints gives \(\alpha\le1/k\). Averaging their prefix-maximizing assignments supplies the reverse bound, while type \(d\)’s prefixes are fixed. Thus \(K(I_k)=k\).
The output correctly limits its conclusion to the unrestricted uniform worst case. It does not claim pointwise optimality of \(K(I)\), or matching lower bounds for the narrower priority subclasses mentioned in the task.
No additional clarification is needed to verify the claimed result.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.