Answer: A deterministic online policy running in time polynomial in \(m,\tau,L\) exists and guarantees \(\mathrm{ALG}\ge\tfrac12\mathrm{OPT}\) for every admissible arrival sequence.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateOur design is a 2-competitive online auction mechanism with time discounting values.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite horizon \(T\), a finite support \(\Theta\) of types \(\theta=(a_\theta,d_\theta,v_\theta)\) with rational masses \(\mu_\theta\), and shared discount functions \(F,D\), each arriving type mass is revealed at its arrival slot while future arrivals remain unknown. With per-capita capacity \(q\) per slot, does there exist an online allocation policy assigning mass \(x_{\theta,t}\) only for \(a_\theta\le t\le d_\theta\), with \(\sum_t x_{\theta,t}\le\mu_\theta\) and \(\sum_\theta x_{\theta,t}\le q\), whose welfare \(\sum_{\theta,t}x_{\theta,t}\max\{v_\theta F(t)+D(t),0\}\) is at least half the offline optimum for every arrival sequence?
A society is given by its support: a list of \(\tau\) types \(\theta=(a_\theta,d_\theta,v_\theta)\) with positive binary-rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(T\ge1\) slots (write \(m=T\)); \(1\le a_\theta\le d_\theta\le T\) are integers and \(v_\theta\ge0\) is rational. Each unit of society mass demands at most one unit of service.
Shared discount functions are given as binary-rational tables: \(0<F(t)\le1\) and \(D(t)\le0\), both nonincreasing. Service at slot \(t\) has per-unit value \(w_\theta(t)=\max\{v_\theta F(t)+D(t),0\}\).
The horizon, discount tables, and rational per-slot capacity \(q>0\) are known initially. Each type and its entire mass are revealed at the beginning of slot \(a_\theta\); future support entries are unknown.
A deterministic online policy irrevocably assigns nonnegative rational mass \(x_{\theta,t}\) using only information revealed through slot \(t\), with \(x_{\theta,t}=0\) outside \([a_\theta,d_\theta]\), \(\sum_t x_{\theta,t}\le\mu_\theta\), and \(\sum_\theta x_{\theta,t}\le q\).
Its welfare is \(\mathrm{ALG}=\sum_{\theta,t}x_{\theta,t}w_\theta(t)\); \(\mathrm{OPT}\) is the maximum welfare under the same constraints with the entire sequence known. Let \(L\) be the total binary input length; measure running times in \(m=T\), \(\tau\), and \(L\).
Does there exist a single online policy running in time polynomial in \(m,\tau,L\) that guarantees \(\mathrm{ALG}\ge\tfrac12\mathrm{OPT}\) for every admissible arrival sequence, or is such a guarantee impossible?
For indivisible unit-demand agents with time-discounting values and a fixed integer supply per slot, a polynomial-time online allocation rule is known to guarantee \(\mathrm{ALG}\ge\tfrac12\mathrm{OPT}\). [Source](https://ojs.aaai.org/index.php/AAAI/article/download/8801/8660)
No result settling this precise rational-mass online formulation was identified in the search.
Proven result. Yes. A deterministic policy that greedily serves the available mass with the highest current per-unit value guarantees \(\mathrm{ALG}\ge \tfrac12\mathrm{OPT}\) and runs in time polynomial in \(m,\tau,L\).
This extends the highest-current-value allocation rule in the [cited paper](https://ojs.aaai.org/index.php/AAAI/article/download/8801/8660). The proof below works directly with rational masses.
1. Policy and feasibility. Let \(g_{\theta,t}\) denote the policy’s allocation. At the beginning of slot \(t\), define the remaining mass of each revealed type by
\(\displaystyle r_{\theta,t}=\mu_\theta-\sum_{s<t}g_{\theta,s}.\)
Consider the types satisfying \(a_\theta\le t\le d_\theta\), \(r_{\theta,t}>0\), and \(w_\theta(t)>0\). Sort them by nonincreasing \(w_\theta(t)\), breaking ties deterministically. Start with remaining capacity \(c=q\). For each type in this order, assign
\(\displaystyle g_{\theta,t}=\min\{r_{\theta,t},c\},\)
and subtract this allocation from \(c\). All other allocations are zero.
Every assignment respects both the remaining type mass and the remaining slot capacity. The policy uses only revealed types and the initially known discount tables, so it is deterministic and online.
For each type, its value is nonincreasing in time. Indeed, if \(s\le t\), then \(v_\theta\ge0\) and the assumed monotonicity give
\(\displaystyle v_\theta F(s)+D(s)\ge v_\theta F(t)+D(t).\)
Taking the maximum with zero preserves this inequality, hence \(w_\theta(s)\ge w_\theta(t)\).
2. A single-slot optimality lemma. At slot \(t\), the greedy allocation maximizes \(\sum_\theta u_\theta w_\theta(t)\) over all allocations to currently available types satisfying
\(\displaystyle 0\le u_\theta\le r_{\theta,t},\qquad \sum_\theta u_\theta\le q.\)
Here is a direct proof. If the total available positive-value mass is at most \(q\), greedy takes all of it, which maximizes the objective.
Otherwise, greedy fills capacity \(q\). Let \(\lambda>0\) be the value of the last type receiving positive allocation. Greedy takes all available mass with value greater than \(\lambda\), takes no mass with value less than \(\lambda\), and possibly takes some mass with value equal to \(\lambda\). Thus, for every feasible \(u\),
\(\displaystyle \sum_\theta w_\theta(t)(g_{\theta,t}-u_\theta) = \sum_\theta (w_\theta(t)-\lambda)(g_{\theta,t}-u_\theta) +\lambda\left(q-\sum_\theta u_\theta\right) \ge0. \)
Each summand in the first sum is nonnegative: above \(\lambda\), \(g_{\theta,t}=r_{\theta,t}\ge u_\theta\); below \(\lambda\), \(g_{\theta,t}=0\le u_\theta\); and at \(\lambda\), the coefficient vanishes. The final term is nonnegative by feasibility. This proves the lemma.
3. Charging an offline optimum. Fix an optimal offline allocation \(o_{\theta,t}\). Such an optimum exists because its feasible set is a nonempty compact polytope and welfare is continuous.
Define cumulative allocations, with \(O_{\theta,0}=G_{\theta,0}=0\), by
\(\displaystyle O_{\theta,t}=\sum_{s\le t}o_{\theta,s},\qquad G_{\theta,t}=\sum_{s\le t}g_{\theta,s}.\)
For the proof, label each type’s mass by the interval \([0,\mu_\theta)\). Represent the offline and greedy allocations at slot \(t\) by the respective intervals
\(\displaystyle I_{\theta,t}=[O_{\theta,t-1},O_{\theta,t}),\qquad J_{\theta,t}=[G_{\theta,t-1},G_{\theta,t}). \)
Their lengths are \(o_{\theta,t}\) and \(g_{\theta,t}\). This labeling is legitimate because mass within a type has identical availability and per-unit values.
Partition each offline interval into two parts. Let
\(\displaystyle z_{\theta,t} =\left|I_{\theta,t}\cap[0,G_{\theta,t-1})\right|, \qquad y_{\theta,t}=o_{\theta,t}-z_{\theta,t}, \)
where \(|\cdot|\) denotes interval length. Thus \(z_{\theta,t}\) is offline mass whose labels greedy served strictly before \(t\), while \(y_{\theta,t}\) consists of the remaining labels.
We bound these two contributions separately.
The remaining contribution. The labels counted by \(y_{\theta,t}\) lie inside \([G_{\theta,t-1},\mu_\theta)\). Consequently,
\(\displaystyle 0\le y_{\theta,t}\le\mu_\theta-G_{\theta,t-1}=r_{\theta,t}.\)
Also, \(y_{\theta,t}\le o_{\theta,t}\), so
\(\displaystyle \sum_\theta y_{\theta,t}\le q.\)
Whenever \(y_{\theta,t}>0\), offline feasibility implies \(a_\theta\le t\le d_\theta\); hence this type has already been revealed and is currently available. Therefore \(y_{\theta,t}\) forms a feasible comparison allocation for the single-slot lemma, including any zero-value components. It follows that
\(\displaystyle \sum_\theta y_{\theta,t}w_\theta(t) \le \sum_\theta g_{\theta,t}w_\theta(t). \)
Summing over slots gives
\(\displaystyle \sum_{\theta,t}y_{\theta,t}w_\theta(t)\le\mathrm{ALG}.\)
The previously served contribution. For \(s<t\), define
\(\displaystyle c_{\theta,s,t}=|J_{\theta,s}\cap I_{\theta,t}|.\)
The greedy intervals with \(s<t\) partition \([0,G_{\theta,t-1})\), so
\(\displaystyle z_{\theta,t}=\sum_{s<t}c_{\theta,s,t}.\)
For fixed \(\theta,s\), the offline intervals are disjoint. Their intersections with \(J_{\theta,s}\) therefore have total length at most \(g_{\theta,s}\):
\(\displaystyle \sum_{t>s}c_{\theta,s,t}\le g_{\theta,s}.\)
Using the proved monotonicity \(w_\theta(t)\le w_\theta(s)\) whenever \(s<t\), we obtain
\(\displaystyle \sum_{\theta,t}z_{\theta,t}w_\theta(t) = \sum_{\theta,s}\sum_{t>s}c_{\theta,s,t}w_\theta(t) \le \sum_{\theta,s}w_\theta(s)\sum_{t>s}c_{\theta,s,t} \le \sum_{\theta,s}g_{\theta,s}w_\theta(s) = \mathrm{ALG}. \)
Because \(o_{\theta,t}=y_{\theta,t}+z_{\theta,t}\), the two bounds yield
\(\displaystyle \mathrm{OPT} =\sum_{\theta,t}o_{\theta,t}w_\theta(t) \le2\mathrm{ALG}. \)
Thus the policy guarantees \(\mathrm{ALG}\ge\tfrac12\mathrm{OPT}\) on every admissible sequence.
4. Exact rational running time. At each slot, the policy evaluates and sorts at most \(\tau\) values and performs at most \(\tau\) allocation updates. Across all slots, this requires \(O(m\tau\log(\tau+1))\) comparisons and \(O(m\tau)\) additional arithmetic operations.
To check bit complexity, let \(Q\) be the product of the denominators of all masses and of \(q\). This is only an analysis device; the online policy need not know future denominators. Its binary length is \(O(L)\). Every remaining mass, remaining capacity, and allocation is an integer multiple of \(1/Q\), because the policy uses only subtraction and minimum on these quantities. Remaining masses are at most \(1\), and remaining capacities are at most \(q\); consequently their numerators and denominators have \(O(L)\) bits.
Each current value \(\max\{v_\theta F(t)+D(t),0\}\) also has \(O(L)\) bits, since its calculation involves a constant number of operations on input rationals. Exact comparisons and allocation updates therefore take polynomial time in \(L\). The overall running time is polynomial in \(m,\tau,L\), as required.
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested deterministic online guarantee and polynomial running time. The charging proof is sound. There is one minor clarification concerning the existence of an optimum when allocations are required to be rational.
The policy considers only revealed types whose availability intervals contain the current slot. Each allocation is bounded by both the remaining type mass and remaining slot capacity. Subtracting the allocation preserves nonnegativity of both quantities. Thus all mass, capacity, and availability constraints hold.
The policy uses no future support information. Deterministic tie-breaking suffices; the proof does not require any particular ordering among equal-value types. Minimum and subtraction preserve rationality.
For every type and every pair of slots \(s\le t\), the assumptions \(v_\theta\ge0\), \(F(s)\ge F(t)\), and \(D(s)\ge D(t)\) imply
\[
v_\theta F(s)+D(s)\ge v_\theta F(t)+D(t).
\]
Taking the maximum with zero preserves the inequality. Consequently, the monotonicity used later in the charging argument holds throughout the stated domain.
Both cases are valid.
If the available positive-value mass is at most \(q\), serving all of it maximizes welfare, because every comparison allocation is bounded componentwise by the available mass and zero-value allocations contribute nothing.
Otherwise, greedy fills capacity and the last positively allocated type has a value \(\lambda>0\). The displayed identity correctly uses \(\sum_\theta g_{\theta,t}=q\). Every term has the claimed sign: types above the threshold are fully served, types below it receive zero, and threshold types have zero coefficient. The remaining capacity term is nonnegative.
The sums must be understood over currently available types, as specified in the lemma. Zero-value types cause no difficulty.
Minor issue: The compactness argument establishes attainment over the real feasible polytope. The task requires rational allocations, whose feasible set is generally not compact. The write-up omits the routine justification that an optimal allocation can be chosen rational.
Minimum clarification: explicitly invoke the standard fact that a linear objective with rational coefficients on a nonempty bounded polytope defined by rational constraints has a rational optimal solution, and identify those hypotheses here.
Apart from that clarification, the labeling is legitimate. Cumulative allocations remain within each type’s mass interval. The intervals for each schedule are disjoint, and assigning labels in service order imposes no additional restriction because all mass of a type has identical availability and values.
The portion counted by \(y_{\theta,t}\) lies in the mass not served by greedy before slot \(t\). Hence its length is at most \(r_{\theta,t}\). Its total over types is at most the offline slot allocation, and therefore at most \(q\).
Any positive component corresponds to a type available at slot \(t\), so that type has already been revealed. Thus this comparison allocation satisfies every hypothesis of the single-slot lemma. Including zero-value components is valid. Summation over slots gives the claimed bound by \(\mathrm{ALG}\).
For each type, greedy intervals before slot \(t\) partition exactly the prefix used to define \(z_{\theta,t}\). Therefore the identity expressing \(z_{\theta,t}\) as a sum of intersection lengths is correct.
For fixed \(\theta,s\), disjointness of the offline intervals prevents their intersections from charging more than the length of \(J_{\theta,s}\). Monotonicity bounds every later offline per-unit value by the corresponding earlier greedy value. Nonnegativity justifies multiplying the intersection-length bound by that earlier value.
All sums are finite, so their rearrangement is valid. The previously served contribution is consequently at most \(\mathrm{ALG}\). The two contributions partition every offline allocation, yielding \(\mathrm{OPT}\le2\mathrm{ALG}\).
The stated operation counts are valid for scanning, evaluating, sorting, and allocating among at most \(\tau\) types per slot.
The denominator-product argument correctly bounds the size of allocation quantities in reduced rational representation. The binary length of \(Q\) is bounded by the total input denominator length. Quantities bounded by \(1\) or \(q\) consequently have numerators of \(O(L)\) bits as well. Using future denominators solely for this analysis does not violate online information restrictions.
Value calculations involve only a constant number of rational operations on input entries, so their bit lengths are also \(O(L)\). Exact comparisons and normalized rational arithmetic take polynomial time. No enumeration of individual mass units is required.
Section 4.1 of the [cited paper](https://ojs.aaai.org/index.php/AAAI/article/download/8801/8660) does use the highest-current-value allocation rule for indivisible agents. Its tie-breaking is random, whereas this output specifies deterministic ties; the submitted proof independently justifies its own rule.
The argument covers \(T=1\), zero values, insufficient available mass, exhausted capacity, arbitrary positive rational \(q\), equal values, and \(\mathrm{OPT}=0\). No division by welfare or positive optimum is used.
The only requested repair is the rational-optimum clarification. No additional charging lemma or algorithmic argument is needed.
⟨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.