d4-journals-jair-2024-0044 (d4-journals-jair-2024-0044)

Given finite driver and request type sets \(U,V\), feasible edges \(E\), positive rational driver masses \(b_u\) with \(\sum_u b_u=1\), request arrival rates \(r_v\) over a unit horizon, patience limits \(\Delta_v\), and edge acceptance probabilities \(p_{uv}\) and rewards \(w_{uv}\), characterize the ratio pairs \((\rho_P,\rho_F)\) attainable by a causal fluid policy uniformly over instances. The policy routes arriving request mass among ordered sequences of at most \(\Delta_v\) probes; a fraction \(p_{uv}\) succeeds at edge \((u,v)\), consuming driver mass and earning reward. Compare its total profit and minimum matched fraction across driver types with the fluid LP benchmarks: maximize \(\sum_{(u,v)\in E}w_{uv}p_{uv}z_{uv}\) for profit and \(\min_u \sum_v p_{uv}z_{uv}/b_u\) for fairness, subject to \(\sum_v p_{uv}z_{uv}\le b_u\), \(\sum_u z_{uv}\le\Delta_v r_v\), and \(\sum_u p_{uv}z_{uv}\le r_v\).

Let \(U,V\) be nonempty finite sets of driver and request types, with feasible edges \(E\subseteq U\times V\). A society is given by its support: the list of its \(\tau=|U|\) positive-mass types, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Let \(m=|V|\), \(L\) be the total input bit length, and \(\Delta_{\max}=\max_v\Delta_v\); express running times in these parameters.
Driver masses satisfy \(b_u>0\) and \(\sum_u b_u=1\). During \(t\in[0,1]\), request mass of type \(v\) arrives continuously at the known constant rate \(r_v>0\); total request mass is unrestricted. Patience limits \(\Delta_v\) are positive integers, acceptance fractions satisfy \(p_{uv}\in(0,1]\), and rewards satisfy \(w_{uv}\ge0\); all numerical data are binary rationals except the integer patience limits.
A causal fluid policy may split or reject arriving request mass and route it through ordered sequences of at most \(\Delta_v\) feasible probes, completing processing immediately without waiting. Driver types may repeat in a sequence, representing probes to distinct driver individuals of that type.
Probing request mass \(a\) at \((u,v)\) immediately matches \(p_{uv}a\), consumes that much currently unmatched driver mass, and earns \(w_{uv}p_{uv}a\); only the remaining \((1-p_{uv})a\) may continue. Failed probes consume no driver mass. Successful mass must leave the probing process, each driver individual can be matched only once, and driver stocks must remain nonnegative at every time.
Let \(M_{uv}\) be total matched mass on an edge. Policy profit and fairness are \(P=\sum_{(u,v)\in E}w_{uv}M_{uv}\) and \(F=\min_{u\in U}\sum_v M_{uv}/b_u\), respectively.
Define \(\mathcal Z\) by \(z_{uv}\ge0\), \(\sum_v p_{uv}z_{uv}\le b_u\), \(\sum_u z_{uv}\le\Delta_v r_v\), and \(\sum_u p_{uv}z_{uv}\le r_v\). The separate benchmarks are \(P^*=\max_{z\in\mathcal Z}\sum_{(u,v)\in E}w_{uv}p_{uv}z_{uv}\) and \(F^*=\max_{z\in\mathcal Z}\min_u\sum_v p_{uv}z_{uv}/b_u\).
A pair \((\rho_P,\rho_F)\in[0,1]^2\) is uniformly attainable if one causal policy, given the instance data, guarantees \(P\ge\rho_P P^*\) and \(F\ge\rho_F F^*\) simultaneously on every instance; these inequalities also define the guarantee when a benchmark is zero.

Which ratio pairs \((\rho_P,\rho_F)\in[0,1]^2\) are uniformly attainable by causal fluid policies against these two benchmarks?

For discrete drivers with integer capacities \(B_u\), known i.i.d. request arrivals, and benchmarks additionally imposing \(x_{uv}\le B_u r_v\), no algorithm guarantees \(\rho_P+\rho_F>1\), \(\rho_P>0.51\), or \(\rho_F>0.51\); guarantees \((\alpha(e-1)/(e+1),\beta(e-1)/(e+1))\) are established asymptotically for \(\alpha,\beta>0\), \(\alpha+\beta\le1\). [Xu and Xu](https://www.jair.org/index.php/jair/article/download/15170/27012)
No characterization of this exact fluid model was located in the literature search.

Characterization

The uniformly attainable pairs are exactly
\[ \mathcal R=\left\{(\rho_P,\rho_F)\in[0,1]^2:\rho_P+\rho_F\le 1-e^{-1}\right\}. \]

More precisely, if all patience limits are bounded by a fixed positive integer \(D\), the exact region is
\[ \mathcal R_D=\left\{(\rho_P,\rho_F)\in[0,1]^2:\rho_P+\rho_F\le c_D\right\}, \qquad c_D=1-\left(1-\frac1D\right)^D. \]

The proof uses the stated fluid rule that failed probes consume no driver mass, and that repeated driver types are permitted.

1. The benchmarks are valid relaxations

For any policy, let \(z_{uv}\) be its total mass probed on edge \((u,v)\). The fluid matching rule gives \(M_{uv}=p_{uv}z_{uv}\).

Driver feasibility implies \(\sum_v p_{uv}z_{uv}\le b_u\). Since each request receives at most \(\Delta_v\) probes, \(\sum_u z_{uv}\le\Delta_v r_v\). Since successful mass leaves the process, \(\sum_u p_{uv}z_{uv}\le r_v\). Thus \(z\in\mathcal Z\).

Consequently, \(P^*\) and \(F^*\) are indeed upper bounds on the corresponding policy objectives.

The set \(\mathcal Z\) is nonempty, closed, and bounded: it contains zero, and each edge variable satisfies \(z_{uv}\le b_u/p_{uv}\). Both benchmarks therefore attain their maxima.

2. A realization lemma

Lemma. Let \(D=\Delta_{\max}\). For every \(z\in\mathcal Z\), there is a causal fluid policy whose matched masses satisfy
\[ M_{uv}=c_Dp_{uv}z_{uv} \]
on every edge.

Proof. Fix a request type \(v\), and write \(d=\Delta_v\). Define
\[ q_{uv}=\frac{z_{uv}}{d r_v}, \qquad q_{0v}=1-\sum_u q_{uv}, \qquad s_v=\frac{\sum_u p_{uv}z_{uv}}{r_v}. \]

The benchmark constraints imply \(q_{0v}\ge0\) and \(0\le s_v\le1\). Set
\[ h_v=\sum_u p_{uv}q_{uv}=\frac{s_v}{d}, \qquad f_v=\frac1d\sum_{j=0}^{d-1}(1-h_v)^j. \]

Because \(s_v\le1\), every summand is at least its value at \(s_v=1\). Hence
\[ f_v\ge \frac1d\sum_{j=0}^{d-1}\left(1-\frac1d\right)^j =1-\left(1-\frac1d\right)^d=c_d. \]

Furthermore, \(c_d\ge c_D\) when \(d\le D\). To verify this monotonicity, for real \(x>1\),
\[ \frac{d}{dx}\left[x\log\left(1-\frac1x\right)\right] =\frac1{x-1}-\log\left(1+\frac1{x-1}\right)>0, \]
using \(\log(1+y)<y\) for \(y>0\). Thus \((1-1/d)^d\) increases with \(d\), and \(c_d\) decreases; also \(c_1=1\).

It follows that the admission fraction \(a_v=c_D/f_v\) lies in \((0,1]\).

Process each arriving type-\(v\) fluid element as follows:

• Admit fraction \(a_v\), rejecting the remainder.
• Run \(d\) virtual stages immediately. At each stage, split surviving mass according to the fractions \(q_{uv}\) and \(q_{0v}\). The \(u\)-branch probes \((u,v)\); the zero branch skips that stage. Only failed probe mass and skipped mass continue.
• Reject all mass remaining after the final stage.

There are at most \(d\) actual probes on each route. Repeated types are allowed by the model.

At each stage, fraction \(h_v\) of its entering mass succeeds. Thus the entering rate at stage \(j+1\), for \(0\le j<d\), is \(r_va_v(1-h_v)^j\). Summing the matched rates on \((u,v)\) gives
\[ \begin{aligned} M_{uv} &=r_va_vp_{uv}q_{uv}\sum_{j=0}^{d-1}(1-h_v)^j\\ &=a_v f_v p_{uv}z_{uv}\\ &=c_Dp_{uv}z_{uv}. \end{aligned} \]

Apply these rules independently to every request type. The resulting constant consumption rate for driver type \(u\) is
\[ C_u=c_D\sum_v p_{uv}z_{uv}\le c_Db_u\le b_u. \]

Therefore its unmatched stock at time \(t\) is \(b_u-tC_u\), which is nonnegative throughout the horizon and positive for \(t<1\). The policy uses only arriving mass and current driver stocks, and completes every route immediately. It is causal and feasible. This proves the lemma. \(\square\)

3. Achievability

Choose benchmark optimizers \(z^P,z^F\in\mathcal Z\).

Let \(s=\rho_P+\rho_F\). If \(s=0\), rejecting everything suffices. Otherwise, suppose \(s\le c_D\), and define
\[ \alpha=\frac{\rho_P}{s}, \qquad \beta=\frac{\rho_F}{s}, \qquad z=\alpha z^P+\beta z^F. \]

Since \(\alpha,\beta\ge0\) and \(\alpha+\beta=1\), convexity gives \(z\in\mathcal Z\). Nonnegative rewards imply
\[ P(z)=\sum_{(u,v)\in E}w_{uv}p_{uv}z_{uv}\ge\alpha P^*. \]

For every driver type \(u\), the fairness optimizer satisfies \(\sum_v p_{uv}z^F_{uv}\ge b_uF^*\). Consequently,
\[ \sum_v p_{uv}z_{uv}\ge\beta b_uF^*, \qquad F(z)\ge\beta F^*. \]

The realization lemma now yields
\[ P\ge c_D\alpha P^*\ge\rho_PP^*, \qquad F\ge c_D\beta F^*\ge\rho_FF^*. \]

These deductions remain valid when either benchmark is zero.

Finally, \(c_D>1-e^{-1}\) for every finite \(D\): for \(D>1\), this follows from \(\log(1-1/D)<-1/D\), and the case \(D=1\) is immediate. Thus every pair with \(\rho_P+\rho_F\le1-e^{-1}\) is attainable on every instance.

4. Matching impossibility bound

Fix a positive integer \(D\) and a rational \(\varepsilon\in(0,1)\). Consider two driver types \(A,B\) and one request type \(v\), with
\[ b_A=\varepsilon,\qquad b_B=1-\varepsilon,\qquad r_v=r=\frac{\varepsilon}{2},\qquad \Delta_v=D. \]
Both edges are feasible, and
\[ p_{Av}=p_{Bv}=\frac1D,\qquad w_{Av}=1,\qquad w_{Bv}=0. \]

Benchmark values

The request-success constraint bounds total benchmark matched mass by \(r\), so \(P^*\le r\). Taking \(z_{Av}=Dr\) and \(z_{Bv}=0\) attains profit \(r\); its driver consumption is feasible because \(r\le b_A\). Therefore \(P^*=r\).

For any benchmark solution of fairness \(f\), summing the two driver requirements gives total matched mass at least
\[ f(b_A+b_B)=f. \]
Hence \(F^*\le r\). Equality is attained by
\[ z_{Av}=Drb_A,\qquad z_{Bv}=Drb_B. \]
This solution uses probe mass \(Dr\), matches mass \(r\), and consumes \(rb_u\le b_u\) from each driver type. Thus \(F^*=r\).

Every policy loses the same request fraction

Let \(N_j\) be the total request mass receiving a \(j\)-th actual probe. Regardless of routing, splitting, rejection, or capacity restrictions,
\[ N_1\le r,\qquad N_{j+1}\le\left(1-\frac1D\right)N_j. \]
The second inequality holds because only failed mass can continue, and both edges have acceptance fraction \(1/D\).

Therefore every policy satisfies
\[ M_{Av}+M_{Bv} =\frac1D\sum_{j=1}^{D}N_j \le r\left[1-\left(1-\frac1D\right)^D\right] =rc_D. \]

A policy meeting the requested guarantees would need
\[ M_{Av}=P\ge\rho_Pr, \qquad M_{Bv}\ge b_BF\ge(1-\varepsilon)\rho_Fr. \]
Combining these inequalities gives
\[ \rho_P+(1-\varepsilon)\rho_F\le c_D. \]

Uniform attainability requires this inequality for every rational \(\varepsilon\in(0,1)\). Letting \(\varepsilon\) tend to zero proves \(\rho_P+\rho_F\le c_D\). This establishes the exact bounded-patience region.

For unrestricted patience, the same inequality holds for every positive integer \(D\). Since \(c_D\) decreases to \(1-e^{-1}\), it proves the necessary condition
\[ \rho_P+\rho_F\le1-e^{-1}. \]

Together with Section 3, this completes the characterization.

5. Running time and representation

For fixed rational prescribed ratios, the construction has bit complexity polynomial in \(\tau,m,L,\Delta_{\max}\). If ratios are supplied as input, add their encoding length to \(L\).

The profit benchmark is a linear program with at most \(\tau m\) variables. The fairness benchmark adds one variable \(f\) and the linear constraints
\[ b_uf\le\sum_v p_{uv}z_{uv}. \]
Both have rational coefficients, polynomial encoding length, and attained optima, so polynomial-time rational linear programming applies.

The routing rule uses at most \(\sum_v\Delta_v\le m\Delta_{\max}\) stages, each with at most \(\tau\) probe branches. It therefore needs \(O(\tau m\Delta_{\max})\) stage-branch operations, without enumerating probe sequences. Its rational powers have bit lengths polynomial in \(\tau,m,L,\Delta_{\max}\).

This is a polynomial bound in the numerical value of \(\Delta_{\max}\), hence a pseudopolynomial bound when patience is binary encoded. The characterization itself includes real ratio pairs, with real split fractions allowed in the fluid policy.

⟨structured verdict parsed — rendered above⟩

The characterization is correct under the stated fluid rules. Both achievability and impossibility are established, including the boundary ratios, zero benchmarks, and patience limit \(1\). I found no substantive gaps or errors.

The computational claim is appropriately limited: the construction is polynomial in the numerical value of \(\Delta_{\max}\), hence pseudopolynomial when patience limits are binary encoded.

Step-by-step verification

1. Benchmark validity and attainment

The identity \(M_{uv}=p_{uv}z_{uv}\) follows directly from the fixed acceptance fraction for every probe on an edge. Repeated probes do not invalidate this identity: each probe contributes its own successful mass, and successful mass leaves the process.

All three benchmark constraints follow from the policy rules:

• Driver consumption cannot exceed \(b_u\).
• Total probe mass for request type \(v\) cannot exceed \(\Delta_v r_v\).
• Total successful mass for request type \(v\) cannot exceed its arriving mass \(r_v\).

Thus every feasible policy induces a point in \(\mathcal Z\), so both benchmarks are valid upper bounds.

The attainment argument is also correct. Positivity of \(p_{uv}\) gives the finite coordinate bound \(z_{uv}\le b_u/p_{uv}\). Consequently, \(\mathcal Z\) is nonempty and compact. Profit is continuous, and fairness is the minimum of finitely many continuous linear functions, since every \(b_u>0\). Both maxima therefore exist. This also covers an empty feasible-edge set.

2. Realization lemma

The definitions of \(q_{uv}\), \(q_{0v}\), and \(s_v\) have valid denominators because \(d\ge1\) and \(r_v>0\).

The benchmark constraints establish precisely the properties needed:

\[ \sum_u q_{uv}\le1,\qquad 0\le s_v\le1,\qquad h_v=s_v/d. \]

The estimate \(f_v\ge c_d\) is correct: each summand \((1-s_v/d)^j\) is at least \((1-1/d)^j\). The geometric-sum calculation gives the stated value of \(c_d\), including \(d=1\).

The monotonicity calculation is correct. For \(x>1\), the displayed derivative is positive by \(\log(1+y)<y\). Therefore \(c_d\) decreases with integer \(d\), with the endpoint \(c_1=1\) handled separately. Hence \(f_v\ge c_D>0\), and the admission fraction \(a_v=c_D/f_v\) belongs to \((0,1]\).

The routing construction respects the request-processing rules:

• Admission and routing are implemented by permitted fluid splitting.
• A skipped stage makes no probe.
• Only failed or skipped mass continues.
• Each route makes at most \(d\) actual probes.
• Repeated driver types are expressly permitted.

The survival calculation is correct. Each virtual stage removes fraction \(h_v\) of its entering mass, so stage \(j+1\) receives rate \(r_va_v(1-h_v)^j\). Summing edge successes gives exactly

\[ M_{uv}=a_vf_vp_{uv}z_{uv}=c_Dp_{uv}z_{uv}. \]

Although the display initially sums rates, these equal total masses because the horizon has length \(1\).

The stock-feasibility check is sufficient for the stated model. Consumption is constant, with

\[ C_u=c_D\sum_v p_{uv}z_{uv}\le b_u. \]

Thus stocks remain nonnegative throughout the horizon and positive before its endpoint. The construction requires no future arrivals and processes each arriving portion immediately. The lemma is established.

3. Simultaneous achievability

The convex combination of benchmark optimizers lies in \(\mathcal Z\). Both objective estimates are valid:

• Nonnegative rewards ensure that the fairness optimizer’s contribution cannot reduce profit.
• Nonnegative matched masses ensure that the profit optimizer’s contribution cannot reduce any driver’s fairness contribution.

Consequently,

\[ P(z)\ge\alpha P^*,\qquad F(z)\ge\beta F^*. \]

The realization lemma scales every matched coordinate by the same positive factor \(c_D\), so it scales both objectives by that factor. When \(s=\rho_P+\rho_F\le c_D\),

\[ c_D\alpha\ge\rho_P,\qquad c_D\beta\ge\rho_F. \]

No division by either benchmark occurs, so zero benchmarks cause no difficulty. The case \(s=0\) is separately and correctly handled.

The inequality \(c_D>1-e^{-1}\) holds for every finite positive integer \(D\). Therefore the construction attains every pair satisfying \(\rho_P+\rho_F\le1-e^{-1}\), including equality, on every finite instance.

4. Impossibility construction

Every instance in the proposed family satisfies the task’s assumptions:

• Both driver masses are positive and sum to \(1\).
• The request rate is positive.
• Acceptance fractions belong to \((0,1]\), including \(D=1\).
• Rewards are nonnegative.
• All required numerical data are rational.

The benchmark calculations are correct.

For profit, the request-success constraint gives \(P^*\le r\), and the proposed solution attains \(r\) while satisfying both probe and driver constraints.

For fairness, any feasible fairness value \(f\) requires total matched mass at least \(f\), since the driver masses sum to \(1\). Hence \(F^*\le r\). The proposed proportional solution is feasible and gives every driver matching fraction \(r\), establishing \(F^*=r\).

The actual-probe recurrence is valid under arbitrary splitting, rejection, routing, and stock restrictions:

\[ N_1\le r,\qquad N_{j+1}\le(1-1/D)N_j. \]

Every portion receiving another actual probe must survive its preceding probe, and both edges have the same failure fraction. Capacity restrictions can only reduce continuation.

Summing successful mass across probe positions therefore gives

\[ M_{Av}+M_{Bv}\le rc_D. \]

The guarantee inequalities imply

\[ M_{Av}\ge\rho_Pr,\qquad M_{Bv}\ge(1-\varepsilon)\rho_Fr. \]

Their combination yields the claimed necessary inequality. Uniformity over every rational \(\varepsilon\in(0,1)\) justifies taking the limit \(\varepsilon\to0\). This proves the bounded-patience necessity \(\rho_P+\rho_F\le c_D\).

For unrestricted patience, the same argument applies for every positive integer \(D\). The standard limit \(c_D\to1-e^{-1}\) gives exactly the claimed necessary condition. No finite instance attaining that limiting constant is required.

5. Running time and representation

The benchmark optimization claims are valid applications of polynomial-time rational linear programming. The programs have polynomially many variables and constraints, rational coefficients of polynomial encoding length, feasible regions, and finite attained optimal values.

The stage description avoids enumerating the potentially exponential collection of complete routes. Its number of stage-branch operations is bounded by \(O(\tau m\Delta_{\max})\).

The rational arithmetic claim is also sound: powers have exponent at most \(\Delta_{\max}\), so their bit lengths grow polynomially in that numerical value and the input encoding length. The prover explicitly distinguishes this bound from polynomial time in the binary encoding of patience.

The treatment of real ratio pairs is consistent with the task, which imposes no rationality restriction on policy split fractions. The computational encoding claim is separately restricted to rational prescribed ratios.

Issues and required feedback

No major or minor issues were identified. No additional clarification is needed to verify the characterization.

The result establishes the exact attainable region and a pseudopolynomial construction. It does not establish polynomial-time solvability in the full binary input length or a hardness classification.

⟨structured verdict parsed — rendered above⟩