Fair and Efficient Online Allocations with Normalized Valuations (d4-conf-aaai-2021-1458)

Given \(T\), two valuation-stream types \(A,B\) with masses \(\mu_A=\mu_B=1/2\), normalized streams \(v_{\theta t}\ge0\) satisfying \(\sum_t v_{\theta t}=1\), and only prefix revelation, determine the best online policy choosing irrevocable \(x_{At},x_{Bt}\ge0\) with \(x_{At}+x_{Bt}\le1\), subject to \(u_\theta=\sum_t v_{\theta t}x_{\theta t}\ge1/2\), maximizing the worst-case ratio \(\frac{u_A+u_B}{\sum_t\max\{v_{At},v_{Bt}\}}\); in particular, determine whether guarded \(p=2.7\) achieves \(0.916\) and whether any fair-share policy can exceed \(0.933\).

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) denotes support size, not the number of possible types. Here \(\tau=2\), with types \(A,B\) and \(\mu_A=\mu_B=1/2\).
There are \(m=T\ge1\) unit divisible items. Each type has an additive valuation stream of nonnegative binary rationals satisfying \(\sum_{t=1}^T v_{\theta t}=1\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\) and any additional parameters.
The policy knows the support labels, masses, normalization, and horizon, but learns stream entries only when their item arrives. It is deterministic and chooses irrevocable real allocations \(x_{At},x_{Bt}\ge0\) with \(x_{At}+x_{Bt}\le1\), using only the revealed prefix.
Here \(x_{\theta t}\) is the total item fraction allocated to type \(\theta\), and \(u_\theta=\sum_t v_{\theta t}x_{\theta t}\) is its aggregate utility. Fair-share requires \(u_\theta\ge\mu_\theta=1/2\) on every admissible stream. The benchmark is unrestricted offline welfare \(\sum_t\max\{v_{At},v_{Bt}\}\).
Guarded poly-proportional allocation with \(p=2.7\) allocates each infinitesimal item fraction in proportions \(v_{At}^p:v_{Bt}^p\) until a type's accumulated utility plus its remaining normalized value reaches \(1/2\); it then gives that type the rest of the current item and every subsequent item. Split zero-valued items equally; resolve simultaneous triggers in favor of \(A\).

What is the optimal uniform worst-case approximation ratio \(\rho^*=\sup_{\mathcal A}\inf_{T,\mathbf v}\frac{u_A^{\mathcal A}(\mathbf v)+u_B^{\mathcal A}(\mathbf v)}{\sum_{t=1}^T\max\{v_{At},v_{Bt}\}}\), where \(\mathcal A\) ranges over fair-share online policies allowed to know \(T\)?

For two discrete agents and divisible items, guarded \(p=2.7\) guarantees \(0.916\), while no fair-share online algorithm guarantees more than \(0.933\), even knowing the horizon. [Verified results](https://ojs.aaai.org/index.php/AAAI/article/download/16685/16492).
Under the aggregate allocation and utility conventions above, these bounds also apply to this two-type model; this is an identification of the stated models, rather than a separate literature result. Search found no result determining the optimal ratio.

Partial result: a stronger three-item upper bound

The exact optimal ratio is not determined here. I establish
$$ \boxed{ 0.916\le \rho^* \le \frac{3874814720}{4154778441} \approx 0.932616450. } $$
The upper bound strictly improves the verified bound $347/372$. Its proof uses two explicit admissible streams and applies to policies that know the horizon.

I also prove an exact criterion for whether a revealed prefix permits a fair continuation, and give a direct fairness proof and computational bounds for the guarded policy.

1. The three-item adversary

Fix any deterministic fair-share online policy and announce $T=m=3$. Consider the following two streams:

| Item | Stream I: $v_{At}$ | Stream I: $v_{Bt}$ | Stream II: $v_{At}$ | Stream II: $v_{Bt}$ |
|---|---:|---:|---:|---:|
| $1$ | $214/512$ | $285/512$ | $214/512$ | $285/512$ |
| $2$ | $137/512$ | $0$ | $298/512$ | $227/512$ |
| $3$ | $161/512$ | $227/512$ | $0$ | $0$ |

All entries are nonnegative dyadic rationals. Normalization follows from
$$ 214+137+161=214+298=512, \qquad 285+227=512. $$

The first item and the announced horizon are identical. Consequently, determinism forces the same first-item fraction allocated to $A$ on both streams. Denote it by $x\in[0,1]$.

The following inequalities allow fractions to remain unallocated: whenever $A$ receives fraction $w$, feasibility implies that $B$ receives at most $1-w$.

Stream I

Let $y,z\in[0,1]$ be the fractions of items $2,3$ allocated to $A$. Fairness for $A$ requires
$$ 214x+137y+161z\ge256. $$
Since $y\le1$,
$$ z\ge\frac{119-214x}{161}. $$

Bounding $B$’s allocation by the complementary fractions gives the welfare bound
$$ W_{\mathrm I} \le 1-\frac{71}{512}x +\frac{137}{512}y -\frac{66}{512}z. $$
The coefficient of $y$ is positive and that of $z$ is negative. Hence
$$ \begin{aligned} W_{\mathrm I} &\le 1-\frac{71}{512}x+\frac{137}{512} -\frac{66}{512}\frac{119-214x}{161}\\ &=\frac{96635+2693x}{82432}. \end{aligned} $$
This remains valid when the displayed lower bound on $z$ is negative: multiplying that lower bound by a negative coefficient still produces an upper bound.

The unrestricted offline benchmark is
$$ \operatorname{OPT}_{\mathrm I} =\frac{285+137+227}{512} =\frac{649}{512}. $$
Therefore
$$ \frac{W_{\mathrm I}}{\operatorname{OPT}_{\mathrm I}} \le \frac{96635+2693x}{104489}. $$

Stream II

Let $y\in[0,1]$ be the fraction of item $2$ allocated to $A$. Fairness for $B$, together with feasibility, implies
$$ \frac12 \le u_B \le \frac{285}{512}(1-x)+\frac{227}{512}(1-y). $$
Thus
$$ 285x+227y\le256, \qquad y\le\frac{256-285x}{227}. $$

The welfare satisfies
$$ \begin{aligned} W_{\mathrm {II}} &\le1-\frac{71}{512}x+\frac{71}{512}y\\ &\le1-\frac{71}{512}x +\frac{71}{512}\frac{256-285x}{227}\\ &=\frac{525}{454}-\frac{71}{227}x. \end{aligned} $$
Here
$$ \operatorname{OPT}_{\mathrm {II}} =\frac{285+298}{512} =\frac{583}{512}, $$
so
$$ \frac{W_{\mathrm {II}}}{\operatorname{OPT}_{\mathrm {II}}} \le \frac{134400-36352x}{132341}. $$

Eliminating the first allocation

Let $r$ be the smaller of the policy’s actual ratios on these two streams. Both inequalities hold:
$$ 104489r\le96635+2693x, $$
$$ 132341r\le134400-36352x. $$
Multiply the first by $36352$ and the second by $2693$, then add. The terms involving $x$ cancel:
$$ \begin{aligned} &(36352\cdot104489+2693\cdot132341)r\\ &\qquad\le36352\cdot96635+2693\cdot134400. \end{aligned} $$
The two integer expressions are respectively $4154778441$ and $3874814720$. Therefore
$$ r\le\frac{3874814720}{4154778441}. $$

For every deterministic fair-share policy, at least one of the two admissible streams has ratio at most this constant. Taking the supremum over policies proves the claimed uniform upper bound.

The improvement over the previous bound is strict:
$$ \frac{347}{372} -\frac{3874814720}{4154778441} = \frac{2978959}{16619113764}>0. $$

This construction has $m=3$, $\tau=2$, and constant input bit length $L$. Constructing it requires constant time.

2. An exact criterion for fair continuation

Consider a revealed prefix with at least one item remaining. Write
$$ U_\theta=\text{utility already allocated to type }\theta, $$
$$ R_\theta=1-\sum_{\text{revealed }t}v_{\theta t}, \qquad d_\theta=\max\left\{0,\frac12-U_\theta\right\}. $$
Thus $R_\theta$ is the total value still to arrive, and $d_\theta$ is the remaining utility deficit.

Proposition. There exists an online continuation that satisfies fairness for every admissible suffix if and only if:

• $R_\theta=0$ implies $d_\theta=0$;
• defining $q_\theta=d_\theta/R_\theta$ when $R_\theta>0$, and $q_\theta=0$ otherwise,

$$ q_A+q_B\le1. $$

Necessity. If $R_\theta=0$ and $d_\theta>0$, no future allocation can supply the missing utility.

Otherwise, an admissible suffix places all residual values $(R_A,R_B)$ in the next item and gives every subsequent item zero value. The residual values are binary rationals because the revealed prefix is rational. On this item, each type with positive residual value must receive fraction at least $d_\theta/R_\theta$. Item feasibility therefore requires $q_A+q_B\le1$.

Sufficiency. Allocate fraction $q_\theta$ of every remaining item to type $\theta$. This uses only information available at the prefix and is feasible because the fractions sum to at most $1$. The additional utility is exactly $q_\theta R_\theta=d_\theta$ when $R_\theta>0$. Types with zero residual value already have their fair share. Thus every type finishes with utility at least $1/2$. $\square$

At the terminal prefix, the condition is simply $d_A=d_B=0$.

Consequently, every fair-share policy must satisfy this criterion after each nonterminal reachable prefix. Checking it takes $O(\tau)$ exact real operations. If the state quantities are rational with total encoding length $B$, elementary rational arithmetic gives an $O(\tau B^2)$ bit-time bound.

3. Direct fairness proof for the guarded policy

The following argument applies to every fixed $p>0$, including $p=27/10$.

Before a trigger, an item with values $(a,b)$ is allocated in fractions
$$ q_A=\frac{a^p}{a^p+b^p}, \qquad q_B=\frac{b^p}{a^p+b^p}. $$
For $(a,b)=(0,0)$, use equal division as stipulated.

For a processed prefix, possibly ending partway through an item, let $H_\theta$ be the total value of all processed item fractions to type $\theta$. Let $U_\theta$ be its allocated utility and set
$$ \ell_\theta=H_\theta-U_\theta. $$
Since every processed fraction is completely allocated, $\ell_\theta$ is the value to $\theta$ of the fractions allocated to the other type. Normalization gives
$$ U_\theta+(1-H_\theta)=1-\ell_\theta. $$
Thus the trigger condition is precisely $\ell_\theta=1/2$.

A pointwise inequality

For all $a,b\ge0$,
$$ bq_B \ge \left(1+\frac2p\right)aq_B-\frac ap. $$
When either value is zero, the inequality follows directly from the allocation rule.

For $a,b>0$, put $r=b/a$. Multiplying the claimed inequality by $p(1+r^p)/a$ reduces it to
$$ h(r):=pr^{p+1}-(p+1)r^p+1\ge0. $$
Its derivative is
$$ h'(r)=p(p+1)r^{p-1}(r-1). $$
Therefore $h$ decreases on $(0,1)$ and increases on $(1,\infty)$. Since $h(1)=0$, the inequality holds.

Utility at a trigger

Suppose $A$ triggers first. Apply the pointwise inequality to every processed item fraction, multiplying by the processed fraction where necessary, and sum. Before the trigger,
$$ U_B\ge \left(1+\frac2p\right)\ell_A-\frac{H_A}{p}. $$
At the trigger, $\ell_A=1/2$, giving the stronger bound
$$ \boxed{ U_B\ge\frac12+\frac{1-H_A}{p}. } $$
In particular, $B$ already has its fair share.

Moreover,
$$ U_A+(1-H_A)=\frac12. $$
Giving $A$ the rest of the current item and every subsequent item therefore makes its final utility exactly $1/2$. The case where $B$ triggers first follows by exchanging the type labels.

If neither type triggers, neither loss can pass $1/2$: during each item the losses vary continuously, and crossing that threshold would cause a trigger. At the end $H_\theta=1$, so
$$ u_\theta=1-\ell_\theta\ge\frac12. $$

Finally, simultaneous triggers cause no problem. At an $A$ trigger, the displayed margin implies $U_B\ge1/2+(1-H_A)/p$. A simultaneous $B$ trigger requires $U_B+(1-H_B)=1/2$. Nonnegativity forces
$$ 1-H_A=1-H_B=0, \qquad U_B=\frac12. $$
Both types then already have their fair shares and all remaining values are zero. The stipulated tie rule is harmless.

This proves fairness without importing the paper’s fairness lemma.

4. The lower bound and computational model

The supplied welfare theorem states that guarded $p=2.7$ achieves ratio at least $0.916$. Its hypotheses match this problem: two normalized additive valuation rows, divisible items, irrevocable online allocations, and unrestricted offline welfare as benchmark. Here the aggregate utilities are exactly those two utilities, and the masses specify the thresholds $1/2$. The policy does not require knowledge of the horizon, so allowing that knowledge preserves its guarantee. Hence $\rho^*\ge0.916$. [Theorem 3 of Gkatzelis, Psomas, and Tan](https://ojs.aaai.org/index.php/AAAI/article/download/16685/16492).

The welfare guarantee is the imported result; the fairness argument above is independent.

Exact real arithmetic

Maintain $\ell_A,\ell_B$ until a trigger. For the current item, compute the proportional fractions and the candidate processed fractions
$$ f_\theta= \frac{1/2-\ell_\theta}{v_{\theta t}(1-q_\theta)} $$
when the denominator is positive; otherwise set $f_\theta=+\infty$. Process proportionally until the earliest candidate trigger, or until the item ends.

For $p=27/10$, each power can be computed with a fixed number of multiplications and a nonnegative tenth-root extraction. In a model where these operations and exact comparisons have unit cost, the policy uses $O(m\tau)$ operations and $O(\tau)$ working real registers, with $\tau=2$. Reading the binary input additionally requires $O(L)$ decoding work.

This is a real-arithmetic bound, not a polynomial bit-time claim.

Exact symbolic bit computation

An exact implementation can return symbolic algebraic representations of its real allocations.

For a positive-valued item $(a_i,b_i)$, its fraction $q_i$ allocated to $A$ is the unique solution in $(0,1)$ of
$$ b_i^{27}q_i^{10}=a_i^{27}(1-q_i)^{10}. $$
Uniqueness follows because $q_i/(1-q_i)$ is strictly increasing there. Items with a zero value have rational proportional fractions.

Before the first trigger,
$$ \ell_A=\sum_{i<t}a_i(1-q_i), \qquad \ell_B=\sum_{i<t}b_iq_i. $$
Testing whether a candidate trigger occurs within the current item uses linear polynomials in the $q_i$. Comparing the two candidate trigger fractions, after multiplying by positive denominators, uses polynomials of degree at most $2$.

Each exact comparison can therefore be decided by an existential real formula containing at most $m$ variables and $O(m)$ integer polynomials of degree at most $10$. Clearing rational denominators gives coefficient bit lengths $O(L+\log(m+1))$.

A standard single-block quantifier-elimination theorem uses $s^{k+1}d^{O(k)}$ integer arithmetic operations for $k$ variables, $s$ polynomials, and degree bound $d$, with intermediate integer bit lengths at most $Hd^{O(k)}$ when input coefficient lengths are at most $H$. [Theorem 2.27 in Basu’s survey](https://www.math.purdue.edu/~sbasu/raag_survey2011_final-sep4-2014.pdf).

Applying that theorem with $k\le m$, $s=O(m)$, and $d=10$, and using elementary integer arithmetic, gives the conservative total bit-time bound
$$ (L+\log(m+1))^2(m+1)^{O(m)} $$
for $\tau=2$. The allocation expressions themselves use the specified algebraic roots and rational arithmetic. This establishes exact implementability, while leaving polynomial bit-time implementation unproved.

5. What remains open

The upper-bound proof supplies a stricter impossibility bound, not an optimal policy. Neither its sharpness for horizon $3$ nor its sharpness over arbitrary horizons has been established.

The outstanding target is to determine the exact value within
$$ \left[ 0.916,\, \frac{3874814720}{4154778441} \right]. $$

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: partial, with a valid stronger upper bound. The output establishes
$$ 0.916\le \rho^*\le \frac{3874814720}{4154778441} \approx 0.932616449956206. $$
The adversarial construction, continuation criterion, and direct fairness proof are correct. The computational bounds are valid under the stated computational models. However, the exact optimal ratio requested by USER_TASK remains undetermined, as the prover explicitly acknowledges.

1. Three-item upper bound

Admissibility and indistinguishability

Both streams have nonnegative dyadic entries and normalized valuation rows. The displayed normalization identities are correct. The zero-valued final item in Stream II is admissible.

Both streams announce the same horizon and reveal identical first-item values. A deterministic policy therefore chooses the same first allocation to $A$, denoted by $x$, on both streams. Knowing the horizon does not distinguish them.

Allowing unallocated fractions causes no problem: replacing $B$’s allocation by its upper bound, the complementary fraction, only increases the welfare expressions because valuations are nonnegative.

Stream I

Fairness for $A$ gives
$$ 214x+137y+161z\ge256. $$
Using $y\le1$ correctly yields
$$ z\ge\frac{119-214x}{161}. $$

The welfare upper bound is correctly expanded:
$$ W_{\mathrm I} \le\frac{512-71x+137y-66z}{512}. $$
The subsequent substitutions preserve the inequality directions. In particular, a negative lower bound on $z$ remains usable because its coefficient in the welfare expression is negative.

Rechecking the arithmetic gives
$$ W_{\mathrm I}\le\frac{96635+2693x}{82432}. $$
The benchmark is correctly computed as
$$ \operatorname{OPT}_{\mathrm I}=\frac{649}{512}, $$
and hence
$$ \frac{W_{\mathrm I}}{\operatorname{OPT}_{\mathrm I}} \le\frac{96635+2693x}{104489}. $$

Not using fairness for $B$ merely weakens this upper bound; it does not invalidate it.

Stream II

Fairness for $B$ and feasibility correctly imply
$$ 285x+227y\le256. $$
The welfare expression and its substitution are correct:
$$ W_{\mathrm {II}} \le1-\frac{71}{512}x+\frac{71}{512}y \le\frac{525}{454}-\frac{71}{227}x. $$
The benchmark and normalized bound also check:
$$ \operatorname{OPT}_{\mathrm {II}}=\frac{583}{512}, \qquad \frac{W_{\mathrm {II}}}{\operatorname{OPT}_{\mathrm {II}}} \le\frac{134400-36352x}{132341}. $$

If the displayed upper bound on $y$ were negative, the policy could not satisfy fairness on this stream. Thus this possibility introduces no exception for a fair-share policy.

Elimination and uniform quantifiers

For the smaller actual ratio $r$, both displayed linear inequalities hold. The chosen positive multipliers cancel $x$, and the integer calculations are correct:
$$ 36352\cdot104489+2693\cdot132341=4154778441, $$
$$ 36352\cdot96635+2693\cdot134400=3874814720. $$
Consequently,
$$ r\le\frac{3874814720}{4154778441}. $$

The quantifier argument is valid: every deterministic fair-share policy fails to exceed this constant on at least one of these two fixed admissible streams. Taking the supremum over policies therefore preserves the upper bound.

The claimed numerical difference is also correct:
$$ \frac{347}{372}-\frac{3874814720}{4154778441} =\frac{2978959}{16619113764}>0. $$

Minor issue — provenance of the earlier exact constant. Neither USER_TASK nor the cited conference paper supplies the exact earlier bound $347/372$; the paper states $0.933$. The new bound does strictly improve the supplied $0.933$ bound, independently of this attribution. Minimum clarification: provide a precise source for the earlier exact constant and its applicable model. [Cited paper, Theorem 4](https://ojs.aaai.org/index.php/AAAI/article/download/16685/16492).

2. Fair-continuation criterion

The proposition is correct for an admissible revealed prefix after completed items.

• If a type has zero remaining value and positive deficit, fairness is impossible.
• Concentrating both residual values in the next item produces an admissible suffix with the announced horizon, using zero-valued items afterward. The residual values are binary rationals.
• Feasibility on that item requires the sum of the necessary fractions to be at most one.
• Conversely, allocating the fixed fractions defined at the prefix on every remaining item is online, feasible, and supplies each positive-residual type exactly its deficit.
• The separate terminal condition correctly handles the absence of further items.

Real-valued previously allocated utilities do not invalidate the argument: real continuation fractions are permitted.

The operation count $O(\tau)$ is valid when the state is already available. The conditional rational-state bound $O(\tau B^2)$ is a conservative elementary-arithmetic bound. It does not assert that every permitted policy has a rational state.

No substantive gap is present.

3. Direct fairness proof

Loss interpretation

Because the guarded policy fully allocates every processed fraction,
$$ \ell_\theta=H_\theta-U_\theta $$
has the stated interpretation. Normalization correctly identifies the trigger condition with
$$ \ell_\theta=\frac12. $$
This remains valid partway through an item because $H_\theta$ includes only the processed fraction.

Pointwise inequality

For positive $a,b$, the stated multiplication correctly reduces the inequality to
$$ h(r)=pr^{p+1}-(p+1)r^p+1\ge0. $$
Its derivative is correctly computed:
$$ h'(r)=p(p+1)r^{p-1}(r-1). $$
For every fixed $p>0$, this establishes the claimed minimum at $r=1$.

The cases with a zero value also satisfy the inequality under the stipulated allocation rule. The proof does not incorrectly extend its division by $p$ to $p=0$.

Trigger and terminal cases

Summing over processed fractions correctly gives
$$ U_B\ge\left(1+\frac2p\right)\ell_A-\frac{H_A}{p}. $$
At an $A$ trigger, this becomes
$$ U_B\ge\frac12+\frac{1-H_A}{p}. $$
Thus $B$ already satisfies fairness, while allocating all remaining fractions to $A$ supplies exactly its remaining deficit.

The no-trigger case is justified by continuity and stopping at the first threshold. The simultaneous-trigger argument correctly forces both remaining normalized values to be zero, so the tie rule cannot harm fairness.

No substantive gap is present.

4. Imported lower bound

The imported theorem is accurately stated and applicable. The cited paper uses two normalized additive agents, irrevocable allocations of divisible items, and unrestricted offline welfare. Its guarded rule allows a trigger within an item, matching the policy here. Theorem 3 states the $0.916$ guarantee for $p=2.7$. Restricting inputs to binary rationals preserves that guarantee. [Cited paper, model and Theorem 3](https://ojs.aaai.org/index.php/AAAI/article/download/16685/16492).

The identification with the two aggregate types follows from the utility and allocation conventions explicitly supplied in USER_TASK. No additional population-scaling assumption is needed.

5. Computational claims

The real-arithmetic implementation correctly computes candidate trigger locations from current losses and constant loss rates within an item. Its bounds,
$$ O(m\tau) $$
operations and $O(\tau)$ working real registers, are valid under the explicitly assumed unit-cost root extraction and exact comparison model. The additional input-decoding work is correctly separated.

For exact symbolic computation:

• For items with both values positive, the displayed degree-ten equation and interval restriction uniquely identify the proportional fraction.
• Items with a zero value have rational proportional fractions.
• Before the first trigger, accumulated losses are linear expressions in the selected roots.
• Finite trigger comparisons require polynomials of degree at most two after multiplication by positive denominators.
• The root constraints and comparison predicates therefore fit the stated variable, polynomial-count, degree, and coefficient-length bounds.

The specialization of Basu’s Theorem 2.27 to one existential block with no free variables supports both the arithmetic-operation and intermediate-bit-length bounds stated by the prover. [Basu’s survey, Theorem 2.27](https://www.math.purdue.edu/~sbasu/raag_survey2011_final-sep4-2014.pdf).

Polynomially many comparisons, formula construction, and symbolic expression output fit within the conservative total bound
$$ (L+\log(m+1))^2(m+1)^{O(m)} $$
for $\tau=2$. This establishes exact symbolic implementability, without establishing polynomial bit-time computation or a complexity classification of the optimal-ratio problem.

6. Outstanding target and required feedback

Major incompleteness relative to USER_TASK. The output provides unequal lower and upper bounds, without an attaining policy or a matching impossibility result. Therefore it does not determine the optimal uniform ratio.

This is an acknowledged limitation, not a false step in the upper-bound proof. Completing the assigned task requires additional mathematics; clarification alone cannot close the interval.

The direction is promising because the improved upper bound is rigorously established and remains valid with horizon knowledge.

⟨structured verdict parsed — rendered above⟩