d4-conf-aaai-2016-0435 (d4-conf-aaai-2016-0435)

Given a finite set of provider types \(T\), population masses \(\mu_t>0\) summing to \(1\), and type profiles specifying depots, per-provider demand templates, revenues, costs, and vehicle capacities, define \(v(x)\) as the profit of the fluid routing game for coalition masses \(0\leq x\leq\mu\), with demand and vehicle mass scaled by type mass and route flows allowed to be fractional. Assume \(v\) is differentiable, \(v(0)=0\), and \(v(\mu)>0\); define \(\phi_t=\mu_t\int_0^1 \frac{\partial v(s\mu)}{\partial x_t}\,ds\) and \(\rho_t=\phi_t/v(\mu)\), with \(\phi_t\geq0\). Find nonnegative payment rates \(p_t\) and minimum subsidy \(\delta\geq0\) such that \(\mu_t p_t=(v(\mu)+\delta)\rho_t\) for every \(t\), and \(\sum_t x_t p_t\geq v(x)\) for every coalition mass vector \(x\in[0,\mu]\).

A society is given by its support: the list of \(\tau\) provider types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Type \(t\) has depot \(d_t\), a disjoint finite request template \(M_t\), and fleet size \(b_t>0\) per unit provider mass. All vehicles have common capacity \(Q>0\). Request \(j\) has quantity \(0<q_j\leq Q\) and revenue \(r_j>0\). Traversal costs \(c_{uv}\geq0\) are common to all providers on the complete directed network of depots and requests. All numerical input is binary rational; \(m\) is the number of network vertices and \(L\) the total input bit length.
A route from \(d_t\) returns to \(d_t\), visits no other depot, visits each selected request once, and satisfies \(\sum_{j\text{ visited}}q_j\leq Q\). Its profit is the sum of visited-request revenues minus traversal costs. Requests may be left unserved.
For a coalition \(x\in[0,\mu]\), assign nonnegative real flows \(z_{t,R}\) to such routes. Require \(\sum_R z_{t,R}\leq b_tx_t\) and, for every \(j\in M_u\), \(\sum_{t,R:j\in R}z_{t,R}\leq x_u\). Define \(v(x)\) as the maximum total route profit weighted by these flows; route families are implicit, not listed in the input.
Assume \(v(0)=0\), \(v(\mu)>0\), and differentiability on \([0,\mu]\), interpreted relative to this domain at its boundary. Define \(\phi_t=\mu_t\int_0^1\partial_t v(s\mu)\,ds\) and \(\rho_t=\phi_t/v(\mu)\); assume the integrals exist and \(\phi_t\geq0\). These quantities are defined by the routing instance, not supplied by an oracle.
A feasible subsidized allocation consists of rates \(p_t\geq0\) and subsidy \(\delta\geq0\) satisfying \(\mu_tp_t=(v(\mu)+\delta)\rho_t\) for every type and \(\sum_t x_tp_t\geq v(x)\) for every \(x\in[0,\mu]\).

Is deciding, for a binary-rational bound \(B\geq0\), whether a feasible allocation exists with \(\delta\leq B\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\).

For discrete cooperative vehicle-routing games, an iterative allocation algorithm achieves stability and proportionality to normalized Shapley values with minimum subsidy; this is a correctness result, without a polynomial-time guarantee ([source](https://ojs.aaai.org/index.php/AAAI/article/download/9912/9771)).
No result settling the exact continuous problem above was located in the literature search.

Result. Every instance satisfying the stated assumptions admits a feasible allocation with \(\delta=0\). Thus the promised decision problem is in \(\mathrm{P}\): always answer “yes.” Reading the input takes \(O(L)\) time; no route enumeration or numerical optimization is required.

The differentiability assumption is consequential: together with homogeneity, differentiability at the origin forces the entire value function to be linear. Moreover, zero subsidy also follows under the weaker assumption of differentiability only along the interior proportional path.

1. Homogeneity of the routing value.

There are finitely many admissible routes, since each route is determined by its depot and an ordered list of distinct requests. For any coalition \(x\), its feasible flow set is nonempty, closed, and bounded: zero flows are feasible, and each route flow is bounded by its provider’s fleet constraint. Hence the maximum defining \(v(x)\) exists.

Fix \(x\in[0,\mu]\) and \(\lambda>0\) such that \(\lambda x\in[0,\mu]\). Multiplication by \(\lambda\) gives a bijection between the feasible flows for \(x\) and those for \(\lambda x\). Indeed, every fleet bound and every request bound scales by exactly \(\lambda\). The objective scales by the same factor. Therefore

\[ v(\lambda x)=\lambda v(x). \]

Also, \(v(x)\geq0\), because serving no requests is feasible.

2. Differentiability at the origin forces linearity.

By differentiability relative to the box at \(0\), there is a vector \(a\in\mathbb{R}^{\tau}\) such that

\[ v(h)=v(0)+a\cdot h+o(\lVert h\rVert) \]

as \(h\to0\) within \([0,\mu]\).

Fix a nonzero \(x\in[0,\mu]\), and substitute \(h=\varepsilon x\), where \(\varepsilon\downarrow0\). Since \(v(0)=0\) and homogeneity gives \(v(\varepsilon x)=\varepsilon v(x)\), we obtain

\[ \varepsilon v(x)=\varepsilon a\cdot x+o(\varepsilon\lVert x\rVert). \]

Dividing by \(\varepsilon\) and taking the limit proves

\[ v(x)=a\cdot x \qquad\text{for every }x\in[0,\mu]. \]

For each type \(t\), positivity of \(\mu_t\) permits a coalition \(h e_t\) with \(h>0\). Thus \(h a_t=v(h e_t)\geq0\), proving \(a_t\geq0\).

At every interior point \(s\mu\), where \(0<s<1\), the partial derivative is consequently \(\partial_t v(s\mu)=a_t\). Endpoint values do not affect the assumed integrals. Hence

\[ \phi_t=\mu_t a_t, \qquad v(\mu)=\sum_t\mu_t a_t, \qquad \rho_t=\frac{\mu_t a_t}{v(\mu)}. \]

Choose \(p_t=a_t\) and \(\delta=0\). These rates are nonnegative, and proportionality holds because

\[ \mu_t p_t=\mu_t a_t=v(\mu)\rho_t. \]

For every coalition,

\[ \sum_t x_t p_t=a\cdot x=v(x), \]

so all stability constraints hold with equality. Because subsidies must be nonnegative, the minimum subsidy is exactly \(0\).

3. The conclusion does not depend solely on differentiability at the origin.

Even if differentiability at the origin were omitted, differentiability at every \(s\mu\), \(0<s<1\), would suffice for zero subsidy.

First, \(v\) is concave. If \(z\) and \(z'\) are optimal flows for \(x\) and \(x'\), respectively, then \(\theta z+(1-\theta)z'\) is feasible for \(\theta x+(1-\theta)x'\). Its objective is \(\theta v(x)+(1-\theta)v(x')\), proving concavity.

Fix \(s\in(0,1)\), set \(y=s\mu\), and write \(g(s)=\nabla v(y)\). Concavity implies the supporting inequality

\[ v(x)\leq v(y)+g(s)\cdot(x-y) \]

for every \(x\in[0,\mu]\). Explicitly, apply concavity to \(y+\varepsilon(x-y)\), rearrange, divide by \(\varepsilon>0\), and let \(\varepsilon\downarrow0\); differentiability at the interior point \(y\) justifies the limit.

Homogeneity gives \(v(s\mu)=s v(\mu)\). Differentiating this identity in \(s\) yields

\[ g(s)\cdot\mu=v(\mu), \qquad g(s)\cdot y=v(y). \]

The supporting inequality therefore becomes \(v(x)\leq g(s)\cdot x\). Integrating over \(s\) gives

\[ v(x)\leq\sum_t x_t\frac{\phi_t}{\mu_t}, \qquad \sum_t\phi_t=v(\mu). \]

Thus \(p_t=\phi_t/\mu_t\), together with \(\delta=0\), again satisfies stability and proportionality. Nonnegativity follows from the assumed \(\phi_t\geq0\).

4. Running time and scope.

Since \(B\geq0\), every promised input satisfies the requested subsidy bound. The decision algorithm uses \(O(1)\) work beyond reading the input, or \(O(L)\) total time, which is polynomial in \(m,\tau,L\).

This conclusion concerns the decision problem on inputs satisfying the stated promises. It does not require verifying differentiability or computing a numerical allocation.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The argument correctly establishes that every instance satisfying the stated promises admits a feasible allocation with zero subsidy. The promised decision problem therefore has an \(O(L)\)-time algorithm. No major or minor mathematical issues were found.

• Existence of an optimal flow.

The admissible route families are finite: the network has finitely many requests, and each route uses an ordered list of distinct requests and a specified depot.

For each fixed coalition \(x\), the feasible region is nonempty because it contains the zero flow. It is closed because its constraints are finitely many non-strict linear inequalities. It is bounded because nonnegativity and the fleet constraint give \(0\leq z_{t,R}\leq b_tx_t\) for every route variable. Thus the linear objective attains a finite maximum. This justifies the subsequent use of optimal flows.

• Homogeneity.

For \(\lambda>0\), with both \(x\) and \(\lambda x\) in the coalition box, scaling every route flow by \(\lambda\) scales every fleet and request constraint by the same factor. Division by \(\lambda\) supplies the inverse map, so the asserted correspondence is a bijection.

Route profits are fixed coefficients, so the objective also scales by \(\lambda\). Consequently, \(v(\lambda x)=\lambda v(x)\) holds on precisely the stated domain. Nonnegativity of \(v\) follows from feasibility of the zero flow, even when some route profits are negative.

• Linearity from differentiability at the origin.

The expansion \(v(h)=v(0)+a\cdot h+o(\lVert h\rVert)\), with \(h\) restricted to the box, is the appropriate statement of relative differentiability used here.

For any fixed nonzero \(x\in[0,\mu]\), the vectors \(\varepsilon x\) remain in the domain for sufficiently small positive \(\varepsilon\). Homogeneity and \(v(0)=0\) therefore give
\(\varepsilon v(x)=\varepsilon a\cdot x+o(\varepsilon\lVert x\rVert)\).
After division by \(\varepsilon\), the remainder tends to zero because \(x\) is fixed. Hence \(v(x)=a\cdot x\). The case \(x=0\) follows from \(v(0)=0\).

Each \(\mu_t\) is strictly positive, so a positive coordinate-axis coalition \(he_t\) is available. Applying nonnegativity of \(v\) proves \(a_t\geq0\). No coordinate or zero-coalition case is omitted.

• Shares and feasibility of the allocation.

Since the value function is linear throughout the box, its partial derivatives at every interior point \(s\mu\), for \(0<s<1\), equal \(a_t\). Under the assumed integrals, endpoint values do not change the result. Thus \(\phi_t=\mu_ta_t\).

The identities \(v(\mu)=\sum_t\mu_ta_t\) and \(\rho_t=\mu_ta_t/v(\mu)\) follow, with the denominator strictly positive by the task’s promise.

The proposed rates \(p_t=a_t\) are nonnegative. With \(\delta=0\), they satisfy every proportionality equation and every stability inequality, the latter with equality. Since negative subsidies are prohibited, the claimed minimum subsidy of zero follows.

• The additional argument using interior differentiability.

This argument is also valid independently of differentiability at the origin, retaining the other stated assumptions.

The convex combination of two feasible optimal flows satisfies the coalition constraints for the corresponding convex combination of coalitions. Its objective has the claimed value, proving concavity.

For \(s\in(0,1)\), positivity of all masses makes \(y=s\mu\) an interior point. The supporting inequality follows from concavity along the segment from \(y\) to \(x\), followed by differentiation at \(y\). This also covers boundary coalitions \(x\).

Differentiating \(v(s\mu)=sv(\mu)\) gives \(g(s)\cdot\mu=v(\mu)\), and therefore \(g(s)\cdot y=v(y)\). Substitution into the supporting inequality gives \(v(x)\leq g(s)\cdot x\).

Integration is justified by the assumed existence of the component integrals and the finite number of types. It yields both the stated stability bound and \(\sum_t\phi_t=v(\mu)\). The resulting rates satisfy proportionality, and their nonnegativity follows from the retained assumption \(\phi_t\geq0\). Here, differentiability at points of the proportional path means full multivariate differentiability there, as the section explicitly uses.

• Decision complexity and scope.

The task assumes the differentiability and positivity promises; it does not ask the algorithm to recognize whether they hold. Accordingly, an algorithm that answers “yes” on every promised input correctly decides the requested existence question for every \(B\geq0\).

Reading the input takes \(O(L)\) time, with \(O(1)\) additional decision work. This is polynomial in \(m,\tau,L\). The proof establishes existence without requiring computation of the allocation, which is sufficient for the decision task.

Required clarification or repair: none.

⟨structured verdict parsed — rendered above⟩