| paper | d4-conf-sagt-2022-0021 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; a group envy-free continuous fleet exists if and only if \(\kappa\geq 1/5\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.21
statement extracted from the paper’s text layer
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 nonatomic population with rational masses over destination-and-fairness-group types, served by a fleet represented as rates of integer passenger-composition patterns of capacity \(5\); the decision is whether those rates meet every type's mass and fleet limits while satisfying the paper's Shapley-payment groupwise envy comparisons.
Covers the groupwise envy-free existence question in the capacity-\(5\) regime of Theorem 4.21; it leaves Theorem 4.20's split-condition hardness, the other envy-free algorithms, and Theorem 5.1's stability and social-optimality result untouched.
The strongest anchor is Theorem 4.21, proved in this paper by reduction from Numerical 4-Dimensional Matching; the paper cites Garey and Johnson’s Theorem 4.3 for the source problem’s hardness. Theorem 4.21 says: given a partition \({\cal S}\) of the agents, it is NP-complete to decide whether there is a feasible taxi allocation that is envy-free within every part of \({\cal S}\). The paper’s reduction uses destination classes as those parts, \({\cal S}=\{S(x)\}\), where \(S(x)\) contains the agents with destination \(x\).
A continuous version I would hand to a prover is Destination-Class Envy-Free Fleet Mix. A type is \(t=(x,g)\): destination \(x\) and fairness group \(g\). The input gives finitely many types with rational masses \(\mu_t\geq 0\), summing to \(1\), and a fleet rate \(\kappa\), measured in taxis per population member. Take taxis of capacity \(5\), as in the hardness construction. A taxi pattern is a nonempty integer vector \(c\in\mathbb Z_{\geq0}^{T}\) with \(\sum_t c_t\leq5\). Let \(z_c\geq0\) be the rate of taxis using pattern \(c\). Feasibility requires
\[
\sum_c z_c c_t=\mu_t\quad\text{for each }t,
\qquad
\sum_c z_c\leq\kappa.
\]
For a pattern \(c\), let \(n_c(r)=\sum_{t:x_t\geq r}c_t\), and let \(\phi_c(x)=\int_0^x 1/n_c(r)\,\mathrm dr\), with \(\phi_c(x)=\infty\) if the pattern has no passenger whose destination is at least \(x\). This is the paper’s Shapley payment for a passenger at \(x\).
The question is whether there is a feasible vector \(z\) such that no passenger envies another passenger in the same group. Precisely, for every pair of patterns \(c,d\) with \(z_c,z_d>0\), and every \(t\in c\), \(u\in d\) with \(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 solution is the vector \(z\) itself. This preserves the paper’s individual replacement comparison and Shapley payments; the population is continuous through the masses and fleet rates, while each ride still has an integral passenger composition.
The regime is a large recurring shuttle market: many riders share a limited set of destinations and fairness groups, and the fleet grows with the population. Destination and group together are the complete type, so riders of one type are indistinguishable in all the features this model uses. This seems like a question the authors would recognize: they study envy within specified groups, explicitly discuss status groups, and their hardness construction uses destination groups. It covers Theorem 4.21’s groupwise-fairness question, not the paper’s open problem for full envy-freeness.
For the general variable-support version, my provisional expectation is Class C: after choosing which taxi patterns occur, feasibility is linear in the masses, but the occurring patterns must satisfy pairwise envy conditions. Choosing that support looks like a genuine combinatorial problem that could remain hard after population mass becomes divisible. That is a conjecture, not a consequence of Theorem 4.21. It generates a sharper question: can the pattern-support problem be solved in time polynomial in the number of types and input bit length, or is it hard even with capacity \(5\)?
My weakest point is the gap between the anchor’s hardness proof and the high-multiplicity regime. In its N4DM construction, the input numbers have distinct destinations, so the number of destination types grows with the number of agents. The reduction relies on matching individual items; divisible masses may admit fractional matchings and erase that hardness. The theorem therefore makes this a well-motivated mirror, but does not establish that its hardness survives continuization.
Theorem 4.21 is a genuine computational result, and the paper cites no continuous treatment that already answers its question. The strongest argument against this anchor is narrower: the theorem’s hardness reduction is unusually dependent on individually specified items. Its N4DM agents receive distinct destinations, so almost every destination group in the reduction is a singleton; the replicated group is the agents at the common destination \(60p\). The reduction’s combinatorics come from which distinct numerical items share a taxi. In a continuous type model, mass at an item’s type can be divided among taxi patterns. The discrete reduction therefore gives little evidence that its hardness survives; its exact matching constraints may relax to fractional ones.
That weakens the case for this particular hardness result, but it does not defeat the proposed mirror. A recurring shuttle service with many riders at each of several destinations and fairness groups is a plausible high-multiplicity setting. With capacity five and fleet rate \(\kappa\), the pattern variables \(z_c\) give a coherent population model, and groupwise envy remains a meaningful comparison between passengers in different taxis.
The sharper criticism is computational. With \(p\) supported types and capacity five, there are only \(O(p^5)\) taxi patterns. Once the occupied patterns are chosen, feasibility is a linear program; the unresolved search is which patterns may coexist without envy. With a fixed number of types, one can enumerate the pattern supports and solve the resulting linear programs. The potentially hard regime therefore needs a growing set of exact destination types, where the problem becomes a discrete support-selection problem over taxi patterns. That may offer little of the continuous-optimization leverage that motivates ChoCo.
This is the strongest case against the anchor: its hardness witness relies on individually distinguished items, while its most natural fixed-type version appears straightforward, and the remaining variable-type question concentrates on discrete pattern selection. The case is still weak. Pattern-support complexity is a legitimate question about a continuous population, and a tractable answer would be informative too. I cannot honestly argue that Theorem 4.21 has no worthwhile continuous mirror in any scenario.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.