d4-conf-sagt-2022-0021 (d4-conf-sagt-2022-0021)

Given finitely many types \(t=(x_t,g_t)\), with rational destinations \(x_t>0\) and rational masses \(\mu_t\geq 0\) summing to \(1\), and a rational fleet rate \(\kappa\), does there exist a feasible continuous fleet? A taxi pattern is an integer vector \(c\in\mathbb{Z}_{\geq 0}^{T}\) with \(1\leq\sum_t c_t\leq 5\); assign each pattern a nonnegative rate \(z_c\), requiring \(\sum_c z_c c_t=\mu_t\) for every type and \(\sum_c z_c\leq\kappa\). Define \(\phi_c(x)=\int_0^x 1/n_c(r)\,dr\), where \(n_c(r)=\sum_{t:x_t\geq r}c_t\), and set \(\phi_c(x)=\infty\) if \(n_c(x)=0\). For every pair of taxi copies represented by positive-rate patterns \(c,d\), including two copies of the same pattern, and every \(t,u\) with \(c_t>0\), \(d_u>0\), and \(g_t=g_u\), require \(\phi_c(x_t)\leq\phi_{d-e_u+e_t}(x_t)\), where \(e_t\) is the unit vector for type \(t\).

A society is given by its support \(T\): the list of \(\tau\) distinct types \(t=(x_t,g_t)\) with positive binary rational masses \(\mu_t\) summing to \(1\). Destinations satisfy \(x_t\in\mathbb{Q}_{>0}\); group labels \(g_t\in\{1,\ldots,h\}\) specify a partition into \(h\) nonempty groups, independently of destinations. Let \(m\) be the number of distinct destinations, \(L\) the total input bit length, and \(\kappa\in\mathbb{Q}_{>0}\) the available taxi rate. All taxis have capacity \(5\).
A pattern is \(c\in\mathbb{Z}_{\geq0}^{T}\) with \(1\leq\sum_{t\in T}c_t\leq5\). A continuous fleet assigns real rates \(z_c\geq0\) satisfying \(\sum_c z_c c_t=\mu_t\) for every \(t\in T\) and \(\sum_c z_c\leq\kappa\).
For any pattern \(c\), define \(n_c(r)=\sum_{t:x_t\geq r}c_t\) and \(\phi_c(x)=\int_0^x n_c(r)^{-1}\,dr\), with \(\phi_c(x)=\infty\) when \(n_c(x)=0\). This is the payment for destination \(x\), with taxi cost equal to its furthest destination.
The fleet is group envy-free if, for every ordered pair \(c,d\) with \(z_c,z_d>0\), including \(c=d\) interpreted as two distinct taxi copies, and every \(t,u\) with \(c_t>0\), \(d_u>0\), and \(g_t=g_u\), one has \(\phi_c(x_t)\leq\phi_{d-e_u+e_t}(x_t)\), where \(e_t\) is the unit vector of type \(t\). Equality is permitted.

Is deciding whether a group envy-free continuous fleet exists solvable in polynomial time in \(m,\tau,h,L\), or is it NP-hard?

For finite lists of agents, existence of a feasible allocation with no envy within each part of a given partition is NP-complete, even with all taxi capacities equal to \(5\). [Discrete result](https://arxiv.org/pdf/2007.08045v5).
No result settling this exact continuous fleet problem was located in the literature search.

Proven result. The problem is polynomial-time solvable. A group envy-free continuous fleet exists if and only if \(\kappa\geq 1/5\). This holds for arbitrary destinations, masses, and group partitions.

Necessary taxi rate. Write \(|c|=\sum_{t\in T}c_t\). Every feasible fleet satisfies
\[ 1=\sum_{t\in T}\mu_t =\sum_c z_c|c| \leq 5\sum_c z_c \leq 5\kappa. \]
The equality follows by summing the type-balance constraints; the first inequality uses \(|c|\leq 5\). Consequently, feasibility requires \(\kappa\geq 1/5\), even without envy constraints.

Construction and proof of envy-freeness. For every type \(t\), use the homogeneous pattern \(c^{(t)}=5e_t\) at rate
\[ z_{c^{(t)}}=\frac{\mu_t}{5}, \]
and set every other pattern’s rate to zero. These are permitted patterns. For each type \(t\), its allocated mass is \(5(\mu_t/5)=\mu_t\), and the total taxi rate is \(\sum_t\mu_t/5=1/5\). Thus the fleet is feasible whenever \(\kappa\geq 1/5\).

Each passenger of type \(t\) in \(c^{(t)}\) pays \(\phi_{c^{(t)}}(x_t)=x_t/5\): all five passengers remain aboard throughout the interval from \(0\) to \(x_t\).

Now consider any ordered pair of used patterns \(c^{(t)},c^{(u)}\), including the same pattern interpreted as distinct copies. After replacing one passenger of type \(u\) by one of type \(t\), the receiving pattern is \(q=4e_u+e_t\). It contains five passengers, including the passenger with destination \(x_t\). Therefore, for every \(r\) with \(0<r\leq x_t\), its occupancy satisfies \(1\leq n_q(r)\leq 5\). Hence
\[ \phi_q(x_t)=\int_0^{x_t}\frac{1}{n_q(r)}\,dr \geq \int_0^{x_t}\frac15\,dr =\frac{x_t}{5} =\phi_{c^{(t)}}(x_t). \]
This proves every required envy inequality. Indeed, the argument applies to all pairs of types, regardless of their group labels.

Complexity and the discrete distinction. If \(\kappa=a/b\) with positive binary integers \(a,b\), the decision reduces to comparing \(5a\) with \(b\). This takes polynomial time in \(L\). A feasible fleet has just \(\tau\) used patterns and rational rates of polynomial encoding length.

The homogeneous construction uses fractional taxi rates, which permit every type’s mass to be served entirely in full taxis. An indivisible finite population need not permit such a construction, so the stated [discrete hardness result](https://arxiv.org/pdf/2007.08045v5) does not obstruct this continuous solution.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct. The construction satisfies the exact continuous model, and all required envy inequalities follow from the stated occupancy bound. No substantive or expositional gaps were found.

• Necessary taxi rate. Summing the balance constraints gives \(\sum_c z_c|c|=1\). Since every permitted pattern has \(|c|\leq5\) and every rate is nonnegative, \(1\leq5\sum_c z_c\leq5\kappa\). Thus \(\kappa\geq1/5\) is necessary, independently of envy-freeness.

• Permitted construction and balance. Each \(c^{(t)}=5e_t\) is a permitted pattern. Patterns corresponding to distinct types are distinct, even when those types share a destination. Assigning rate \(\mu_t/5\) serves precisely mass \(\mu_t\) of type \(t\). The total rate is \(1/5\), so the construction is feasible whenever \(\kappa\geq1/5\), including equality.

• Original payments. In \(c^{(t)}\), occupancy is \(5\) throughout the integration interval up to \(x_t\). Consequently, the asserted payment \(\phi_{c^{(t)}}(x_t)=x_t/5\) follows directly from the definition.

• Replacement payments. For any ordered pair of used patterns, replacing the selected passenger gives \(q=4e_u+e_t\). This pattern contains five passengers and includes a passenger whose destination is \(x_t\). Hence its occupancy is between \(1\) and \(5\) throughout the integration interval. In particular, \(n_q(x_t)>0\), so the infinite-payment convention does not apply. The pointwise bound \(1/n_q(r)\geq1/5\) justifies the integral inequality exactly as written.

• All envy quantifiers and edge cases. Every occupied type in a used pattern is its homogeneous type, so the checked pairs exhaust all required comparisons. The argument establishes the inequality for every pair of types and therefore for every same-group pair. When the two patterns coincide, \(t=u\) and \(q=5e_t\), yielding equality; this also covers the required interpretation as distinct taxi copies. No ordering or distinctness assumption on destinations is needed.

• Polynomial complexity. For positive binary integers \(a,b\) representing \(\kappa=a/b\), the condition is exactly \(5a\geq b\). Multiplication by a fixed integer and integer comparison take polynomial time in the input length. The supplied witness uses \(\tau\) patterns, and dividing each input mass by \(5\) increases its encoding length by only a constant amount.

• Discrete distinction. The proof uses arbitrary real taxi rates and repeated passengers of a type within a pattern, both explicitly permitted by the continuous model. The cited discrete hardness result is not used as a premise in the proof, and its verification is unnecessary for this conclusion.

Repair feedback: None required.

⟨structured verdict parsed — rendered above⟩