Answer: Yes. Mass-weighted UNB has an exact rational implementation polynomial in \(m,\tau,L\) for \(m=2\), returns an SI, EF, PO allocation, and has tight fair-ratios \(1+\alpha\) for social welfare and \(1/(1-\alpha)\) for utilization for every rational \(\alpha\in(0,\tfrac12]\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWith 2 resources, mechanism UNB can be implemented in polynomial time, sat- isfies SI, EF, PO, and SP, and has FRSW(UNB) = 1 + α and FRUtil(UNB) = 1 1 −α.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) of rational normalized two-resource demand types \(d_t\in(0,1]^2\), with \(\max_r d_{tr}=1\), and positive rational masses \(\mu_t\) summing to \(1\), find a per-member bundle \(a_t=y_td_t\) for each type, subject to \(\sum_t\mu_ta_{tr}\le1\). Let \(u_t(a)=\min_r a_r/d_{tr}\); require continuous SI \(y_t\ge1\), type-level EF \(u_t(a_t)\ge u_t(a_s)\) for all \(t,s\), and PO. Start with \(a_t=d_t\), then apply mass-weighted UNB: raise the resource-1 allocations of supported types in \(G_2=\{t:d_{t1}<1\}\) with the least current \(a_{t1}\), advancing tied types together and weighting resource use by \(\mu_t\). After renaming resources so \(\alpha=\sum_{t\in G_2}\mu_t\le\tfrac12\), is there an exact rational implementation polynomial in support size \(\tau=|T|\) and bit length \(L\), with worst-case fair-ratios against optimal feasible SI-and-EF allocations \(\mathrm{FRSW}=1+\alpha\) and \(\mathrm{FRUtil}=1/(1-\alpha)\)?
A society is given by its support: a list of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length and \(m=2\).
Each type has rational demand \(d_t\in(0,1]^2\) with \(\max_r d_{tr}=1\). Each resource has capacity \(1\); allocations give every member of type \(t\) the same non-wasteful bundle \(a_t=y_td_t\), with \(y_t\ge0\) and \(\sum_t\mu_ta_{tr}\le1\).
Utilities are \(u_t(a)=\min_r a_r/d_{tr}\). SI requires \(y_t\ge1\), EF requires \(y_t\ge u_t(a_s)\) for all \(t,s\), and PO means Pareto optimality among feasible allocations on this support, without imposing SI or EF on improvements.
Use resource labels satisfying \(G_1=\{t:d_{t1}=1\}\), \(G_2=\{t:d_{t1}<1\}\), and \(\alpha=\sum_{t\in G_2}\mu_t\in(0,\tfrac12]\); thus \((1,1)\) belongs to \(G_1\).
Mass-weighted UNB starts at \(a_t=d_t\). While both resources have slack, let \(P\) be the types in \(G_2\) with least current \(a_{t1}\), and increase their bundles by \((\delta,\delta/d_{t1})\) together until another type in \(G_2\) joins the minimum or a resource is exhausted; consumption is weighted by \(\mu_t\). If no further type exists, only exhaustion limits the step. Types in \(G_1\) remain fixed.
Define \(\mathrm{SW}(A)=\sum_t\mu_ty_t\) and \(\mathrm{U}(A)=\min_r\sum_t\mu_ta_{tr}\). For \(Q\in\{\mathrm{SW},\mathrm{U}\}\), define \(\mathrm{FR}_Q(\mathrm{UNB};\alpha)=\sup_{I:\alpha(I)=\alpha}\frac{\max_{A\text{ feasible, SI, EF}}Q(A)}{Q(\mathrm{UNB}(I))}\), with the supremum over all finite rational supports and benchmarks using the same type-level bundles.
Does mass-weighted UNB admit an exact rational implementation in time polynomial in \(m,\tau,L\), returning an SI, EF, PO allocation, with tight fair-ratios \(\mathrm{FR}_{\mathrm{SW}}(\mathrm{UNB};\alpha)=1+\alpha\) and \(\mathrm{FR}_{\mathrm{U}}(\mathrm{UNB};\alpha)=1/(1-\alpha)\) for every rational \(\alpha\in(0,\tfrac12]\)?
For finite equal-weight agents, UNB is polynomial-time, satisfies SI, EF, PO and strategyproofness, and has these tight fair-ratios. [Discrete result](https://arxiv.org/pdf/2210.05237).
No result settling this precise mass-weighted implementation and approximation question was located.
Yes. Mass-weighted UNB has an exact rational implementation polynomial in the support size and input bit length. It returns an SI, EF, PO allocation, and both stated fair-ratios hold.
Throughout, “binary-rational” means a rational number whose numerator and denominator are encoded in binary. This is the interpretation compatible with allowing every rational \(\alpha\).
Write the demands as
\[
\text{not used}
\]
For \(t\in G_1\), put \(c_t=d_{t2}\), so \(d_t=(1,c_t)\). For \(t\in G_2\), put \(b_t=d_{t1}\), so \(d_t=(b_t,1)\), where \(0<b_t<1\).
For a water level \(\lambda\ge0\), define
\(y_t(\lambda)=1\) for \(t\in G_1\), and
\(y_t(\lambda)=\max\{1,\lambda/b_t\}\) for \(t\in G_2\).
Thus a type in \(G_2\) receives first-resource amount
\(a_{t1}(\lambda)=\max\{b_t,\lambda\}\).
The aggregate resource consumptions are
\[
\text{not used}
\]
\(C_1(\lambda)=1-\alpha+\sum_{t\in G_2}\mu_t\max\{b_t,\lambda\}\),
\(C_2(\lambda)=\sum_{t\in G_1}\mu_tc_t+\sum_{t\in G_2}\mu_t\max\{1,\lambda/b_t\}\).
Let \(\beta=\min_{t\in G_2}b_t\). At \(\lambda=\beta\), this is exactly the initial allocation \(a_t=d_t\). Increasing \(\lambda\) raises precisely the types currently having the least first-resource amount, with the increments prescribed in the question. Therefore this parametrization describes the specified UNB process exactly.
Initially both consumptions are at most \(1\), and
\(C_1(\beta)=1-\alpha+\sum_{t\in G_2}\mu_tb_t<1\).
If \(C_2(\beta)=1\), UNB stops immediately. Otherwise both consumptions are continuous and strictly increasing on \([\beta,\infty)\): the types attaining \(\beta\) contribute positive slopes to both resources. Moreover,
\(C_1(1)=1-\alpha+\sum_{t\in G_2}\mu_t=1\).
Consequently there is a first exhaustion level \(\lambda_*\in[\beta,1]\). UNB returns \(a_t=y_t(\lambda_*)d_t\).
Sort the distinct numbers \(b_t\), and append \(1\). These are the only water-level breakpoints.
On an interval between consecutive breakpoints, let
\(H=\{t\in G_2:b_t\le\lambda\}\) be the active types. Throughout that interval,
\(C_r(\lambda)=A_r+B_r\lambda\),
where
\(A_1=1-\alpha+\sum_{t\in G_2\setminus H}\mu_tb_t,\qquad B_1=\sum_{t\in H}\mu_t\),
\(A_2=\sum_{t\in G_1}\mu_tc_t+\sum_{t\in G_2\setminus H}\mu_t,\qquad B_2=\sum_{t\in H}\mu_t/b_t\).
Both slopes are positive. The candidate exhaustion levels are therefore the exact rationals
\(\lambda_r=(1-A_r)/B_r,\qquad r\in\{1,2\}\).
Starting at \(\beta\), inspect the intervals in increasing order. If the smaller candidate lies within the current interval, return that level. Otherwise proceed to the next breakpoint. Exhaustion at an endpoint terminates the algorithm. Since \(C_1(1)=1\), termination is guaranteed.
There are at most \(\tau\) intervals. Recomputing the four coefficients from their displayed formulas on each interval uses \(O(\tau^2)\) rational arithmetic operations, in addition to sorting.
This is also polynomial in bit complexity. Each coefficient is a sum of input rationals, products of two input rationals, or quotients of two input rationals. A common denominator can be formed using products of their denominators, and, for the quotients, the relevant input numerators. The combined bit lengths of these factors are \(O(L)\). Summing at most \(\tau\) terms adds at most \(O(\log\tau)\) bits. Forming \(\lambda_r\), comparing candidates, and producing \(\lambda_*/b_t\) consequently uses rationals of polynomially bounded bit length.
Thus the algorithm returns an exact rational allocation in time polynomial in \(\tau,L\), hence polynomial in \(m,\tau,L\) for the stipulated \(m=2\).
Every returned multiplier satisfies \(y_t\ge1\), directly from its definition.
We check all ordered pairs of groups.
For \(t,s\in G_1\), both have utility \(1\), and the first coordinate gives
\(u_t(a_s)\le a_{s1}/d_{t1}=1=y_t\).
For \(t\in G_1\), \(s\in G_2\), the bound \(\lambda_*\le1\) gives
\(a_{s1}=\max\{b_s,\lambda_*\}\le1\). Hence
\(u_t(a_s)\le a_{s1}/d_{t1}\le1=y_t\).
For \(t\in G_2\), \(s\in G_1\), the second coordinate gives
\(u_t(a_s)\le a_{s2}/d_{t2}=c_s\le1\le y_t\).
Finally, suppose \(t,s\in G_2\). If \(b_t\le b_s\), then
\(y_t=\max\{1,\lambda_*/b_t\}\ge\max\{1,\lambda_*/b_s\}=y_s\).
Using the second coordinate, \(u_t(a_s)\le y_s\le y_t\).
If \(b_t>b_s\), then
\(a_{t1}=\max\{b_t,\lambda_*\}\ge\max\{b_s,\lambda_*\}=a_{s1}\).
Using the first coordinate,
\(u_t(a_s)\le a_{s1}/b_t\le a_{t1}/b_t=y_t\).
These cases establish EF.
At termination, some resource \(r_*\) has consumption exactly \(1\).
Consider any alternative allocation with utility at least \(y_t\) for every type. Even allowing wasteful alternative bundles, its bundle for type \(t\) must have coordinate \(r_*\) at least \(y_td_{tr_*}\). If some type \(s\) obtains strictly greater utility, its coordinate \(r_*\) must be strictly greater than \(y_sd_{sr_*}\).
Because \(\mu_s>0\) and \(d_{sr_*}>0\), aggregate consumption of resource \(r_*\) would then exceed \(1\). This contradicts feasibility. Hence the allocation is PO without imposing SI or EF on improvements.
The following correspondence transfers approximation guarantees; it is not used to implement the algorithm.
Choose an integer \(N\) such that \(n_t=N\mu_t\) is a positive integer for every type. Replace type \(t\) by \(n_t\) identical equal-weight agents with demand \(d_t\). There are \(N\) agents altogether.
Given a type allocation \(a_t=y_td_t\), give each corresponding agent the bundle
\(\widetilde a_i=a_t/N,\qquad \widetilde y_i=y_t/N\).
Feasibility is preserved exactly, since
\(\sum_i\widetilde a_{ir}=\sum_t n_ta_{tr}/N=\sum_t\mu_ta_{tr}\).
The equal-weight SI condition is \(\widetilde y_i\ge1/N\), equivalent to \(y_t\ge1\). Homogeneity of Leontief utility shows that all EF inequalities are preserved.
Conversely, in any non-wasteful EF allocation of the replicated instance, agents with identical demands have identical multipliers. Indeed, for two such agents \(i,j\), their mutual EF inequalities give
\(\widetilde y_i\ge\widetilde y_j\) and
\(\widetilde y_j\ge\widetilde y_i\).
Their common bundle can therefore be multiplied by \(N\) to recover a type allocation.
Thus there is a bijection between the two feasible SI, EF benchmark sets.
Both objectives are preserved:
\(\sum_i\widetilde y_i=\sum_t n_ty_t/N=\sum_t\mu_ty_t\),
and
\(\min_r\sum_i\widetilde a_{ir}=\min_r\sum_t\mu_ta_{tr}\).
The maxima in these benchmark sets exist. In the type formulation, feasibility bounds \(y_t\le1/\mu_t\), using a dominant coordinate of type \(t\). SI and EF are closed linear inequalities, and the initial allocation is feasible and satisfies both. The benchmark set is therefore nonempty and compact, and both objectives are continuous.
Equal-weight UNB starts each replicated agent at \(d_t/N\), exactly the scaled weighted initial allocation.
If the weighted active set is \(P\), its replicated active set consists of all \(n_t\) agents for \(t\in P\). A weighted increment \((\delta,\delta/b_t)\) corresponds to per-agent increment
\((\delta/N,\delta/(Nb_t))\).
The total replicated consumption increments are
\(\sum_{t\in P}n_t\delta/N=\delta\sum_{t\in P}\mu_t\),
\(\sum_{t\in P}n_t\delta/(Nb_t)=\delta\sum_{t\in P}\mu_t/b_t\).
These equal the weighted consumption increments. Meeting levels scale by \(1/N\), so meeting and exhaustion events correspond exactly. Induction over the successive events proves that the two UNB outputs correspond.
Finally, the minority proportion is unchanged:
\(|\widetilde G_2|/N=\sum_{t\in G_2}n_t/N=\alpha\).
The prescribed treatment of \((1,1)\) is also unchanged.
We use the established equal-weight theorem in its fixed-\(\alpha\) form: for two resources, positive normalized demands, and the prescribed grouping, the supremal fair-ratios of UNB are \(1+\alpha\) for social welfare and \(1/(1-\alpha)\) for utilization. The theorem’s lower-bound constructions use rational demands; for rational \(\alpha=p/q\), their population sizes can tend to infinity through multiples of \(q\). These statements are proved in Theorem 1 and Lemmas 3–4 of the [cited paper](https://arxiv.org/pdf/2210.05237).
All its hypotheses hold for the replicated instance. The correspondence above preserves the benchmark optimum, the mechanism’s objective value, and \(\alpha\). Hence every rational mass-weighted instance satisfies
\(\displaystyle \frac{\max_{A\text{ feasible, SI, EF}}\mathrm{SW}(A)}{\mathrm{SW}(\mathrm{UNB}(I))}\le1+\alpha\),
\(\displaystyle \frac{\max_{A\text{ feasible, SI, EF}}\mathrm{U}(A)}{\mathrm{U}(\mathrm{UNB}(I))}\le\frac1{1-\alpha}\).
For the reverse inequalities, take the rational equal-weight instances approaching the two bounds at the chosen fixed rational \(\alpha\). Merge identical demands into distinct support types, assigning each type its multiplicity divided by the population size. The resulting masses are positive binary-encoded rationals.
The same correspondence, read in reverse, preserves both benchmark optima and both UNB objective values. Consequently these finite rational supports approach the respective bounds. This establishes tightness as a supremum, without requiring a finite instance to attain it.
Therefore
\(\displaystyle \mathrm{FR}_{\mathrm{SW}}(\mathrm{UNB};\alpha)=1+\alpha,\qquad \mathrm{FR}_{\mathrm{U}}(\mathrm{UNB};\alpha)=\frac1{1-\alpha}\)
for every rational \(\alpha\in(0,\tfrac12]\).
The potentially large replicated population affects only the proof of correspondence. The exact implementation operates directly on the support.
⟨structured verdict parsed — rendered above⟩
Assessment: proved with a minor presentation defect. The argument establishes the requested exact polynomial-time implementation, SI, EF, unrestricted PO, and both tight fair-ratios. The replication argument correctly transfers the discrete guarantees without using the potentially large replicated population in the implementation.
No major mathematical issue was found.
The proof addresses the stipulated case \(m=2\). It does not claim an implementation or the same guarantees for arbitrary numbers of resources.
The opening interpretation of “binary-rational” as a rational encoded by binary numerator and denominator is explicit and consistent with the task’s quantification over every rational \(\alpha\). Under that intended interpretation, there is no domain mismatch.
The grouping is correct: normalization forces \(d_t=(1,c_t)\) in \(G_1\) and \(d_t=(b_t,1)\), with \(0<b_t<1\), in \(G_2\). The type \((1,1)\) remains in \(G_1\).
The displayed multipliers and consumptions correctly describe the prescribed process.
The assertions about exhaustion are valid. Positivity of the masses and \(b_t<1\) give \(C_1(\beta)<1\). Initial feasibility gives \(C_2(\beta)\le1\). The types attaining \(\beta\) ensure strictly positive slopes on every subsequent interval, and \(C_1(1)=1\).
Thus the first exhaustion level exists in \([\beta,1]\). Immediate exhaustion of resource \(2\) is explicitly covered.
Minor presentation issue: Section 1 contains two display blocks consisting only of \text{not used}. They supply no mathematical content and should be deleted. The surrounding definitions are complete, so these placeholders do not create a mathematical gap.
The interval coefficients \(A_1,B_1,A_2,B_2\) are correct. Both slopes are positive because the active set contains a type of positive mass.
The exhaustion candidates \(\lambda_r=(1-A_r)/B_r\) are therefore well-defined rational numbers. The interval scan correctly handles:
An already passed exhaustion candidate cannot occur during the scan: reaching an interval without termination means neither resource has exhausted at its left endpoint.
There are at most \(\tau\) intervals, and the stated \(O(\tau^2)\) rational-operation count is valid.
The bit-complexity argument also stands. The coefficient formulas involve sums of input rationals and products or quotients of pairs of input rationals. The stated denominator construction has polynomial bit length; summing the terms adds only logarithmic overhead beyond those denominator and numerator bounds. Candidate formation, exact comparisons, and output formation preserve polynomial bit length.
Consequently, the proof establishes polynomial running time in \(\tau,L\), and hence in \(m,\tau,L\) for fixed \(m=2\).
Every multiplier is at least \(1\) by construction. This directly verifies SI.
All ordered pairs are covered.
The divisions are legitimate because all demand coordinates are positive. Equality cases are included. No EF gap is present.
The proof uses a resource exhausted at termination. Any weak utility improvement must preserve at least the original amount of that resource for every type; any strict utility improvement must strictly increase it for the improved type.
Positive mass makes that strict increase contribute strictly to aggregate consumption. Feasibility then fails. This proves PO even against wasteful alternatives, without imposing SI or EF on improvements.
A common denominator supplies an integer \(N\) with positive integer multiplicities \(n_t=N\mu_t\). Its size is irrelevant to the implementation because replication is used only in the proof.
The scaling \(a_t/N\) correctly preserves:
The converse is valid for the required non-wasteful benchmark allocations. Identical-demand agents must have equal multipliers by mutual EF, so their bundles recover a single type-level bundle after multiplication by \(N\). Hence the claimed benchmark bijection is justified.
The compactness argument is also correct: a dominant coordinate bounds each multiplier by \(1/\mu_t\), and the constraints form a closed, nonempty set. Both objective maxima exist.
For the mechanisms, all replicas of an active type receive the same scaled increment. The displayed aggregate increments are correct, and both meeting and exhaustion events correspond. The minority proportion and treatment of \((1,1)\) are preserved.
The citation supports the precise result being used. The paper’s Theorem 1 states the two UNB ratios; Lemma 3 supplies the upper bounds and Lemma 4 supplies the asymptotic lower bounds. Its model uses positive normalized demands, non-wasteful allocations, the same grouping convention, and SI–EF benchmarks. These hypotheses hold for the replicated instances. [Cited paper, Sections 2–3](https://arxiv.org/pdf/2210.05237).
The rationality and fixed-\(\alpha\) claims also check out: Lemma 4 uses demands parameterized by \(1/n\), with group sizes \(n(1-\alpha)\) and \(n\alpha\). For rational \(\alpha=p/q\), arbitrarily large multiples of \(q\) satisfy the integrality requirements and the construction’s population-size restrictions. [Cited paper, Lemma 4](https://arxiv.org/pdf/2210.05237).
Thus the upper-bound transfer is justified. Merging identical demands in the lower-bound instances produces admissible finite rational supports, and the established correspondence preserves their objective ratios exactly. The conclusion correctly concerns a supremum rather than finite attainment.
Delete the two unused display placeholders in Section 1. No additional lemma, construction, or mathematical clarification is required.
⟨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.