Answer: \(\mathrm{NP}\text{-hard}\), even for fixed \(\varepsilon=1/4\), \(H=3\), and \(C=0\).
Lemma 4.2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateAssume that two meeting request subsets R1 and R2 (⊆R) are independent. If meeting request i is in R1, then the Shapley value satisfies: φi(R1 ∪R2, v) = φi(R1, v). PROOF. (Sketch) Let S = S1 ∪S2, where S1 ⊆R1 and S2 ⊆ R2. Since R1 and R2 satisfy independence, S1 and S2 also hold the same property.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of meeting-request types with rational masses \(\mu_t\), discrete time-and-location options, and energy, comfort, and capacity parameters that scale with the population, define \(E(q)\) as the minimum normalized energy when flexible mass \(q_t\in[0,\mu_t]\) of each type offers flexibility. Let \(V(q)=E(0)-E(q)\). Compute, within additive precision \(\varepsilon\), each type’s per-capita credit \(a_t=\int_0^1 \partial_t V(\lambda\mu)\,d\lambda\) (with the derivative taken almost everywhere) and total credit \(\mu_t a_t\).
A society is given by its support: the list of the \(\tau\) meeting-request types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(H\) discrete time slots and \(r\) room categories, with \(m=Hr\) time-location options. Category \(\ell\) has positive binary-rational room supply \(k_\ell\) per unit population and integer attendee capacity \(h_\ell>0\).
Type \(t\) specifies nonempty allowed start-time and room sets \(T_t,L_t\), integer duration \(\delta_t>0\), integer attendee count \(n_t>0\), and a distinguished baseline option \(b_t\). An option \((s,\ell)\in T_t\times L_t\) is admissible when its duration fits within the horizon, \(n_t\le h_\ell\), and its rational satisfaction \(S_{t,s,\ell}\ge B\), where \(B>0\); every baseline is admissible.
A room timeline is a sequence of admissible meetings whose occupied intervals \([s,s+\delta_t)\) do not overlap. Scheduling allows arbitrary nonnegative real masses of each timeline in each room category, totaling at most \(k_\ell\); across these timelines, the total occurrence mass of type \(t\) must equal \(\mu_t\), and its occurrence mass away from \(b_t\) must be at most \(q_t\in[0,\mu_t]\). Timelines are specified implicitly by these rules, not enumerated in the input.
All energy coefficients \(E_{t,s,\ell}\) and the common saving \(C\) are nonnegative binary rationals. A meeting costs \(E_{t,s,\ell}\) unless the preceding meeting on its timeline ends exactly at \(s\), in which case it costs \(\max\{0,E_{t,s,\ell}-C\}\). A timeline's cost is the sum of its meeting costs; normalized energy is the sum of timeline costs multiplied by their masses.
Let \(E(q)\) be the minimum normalized energy over these schedules, and \(V(q)=E(0)-E(q)\). Promise baseline feasibility and that every ordinary partial derivative \(\partial_tV(\lambda\mu)\) exists for almost every \(\lambda\in(0,1)\) and is integrable. Define the per-capita credit \(a_t=\int_0^1\partial_tV(\lambda\mu)\,d\lambda\) and total credit \(\mu_ta_t\).
Can all per-capita and total credits be computed with additive error at most a given binary-rational \(\varepsilon\in(0,1)\) in time polynomial in \(m,\tau,L,1/\varepsilon\), where \(L\) is the total input bit length, or is this additive-approximation problem NP-hard?
For discrete games whose savings decompose across independent groups for every coalition, individual Shapley credits are unchanged when another independent group is added; this is a structural result, not a complexity classification. [Discrete independence result](https://ifaamas.org/AAMAS/aamas2014/proceedings/aamas/p925.pdf)
On the continuous side, Aumann–Shapley prices have an established computation algorithm for transportation cost functions; that result does not classify the meeting-credit problem defined here. [Transportation cost allocation](https://www.tau.ac.il/~samet/papers/transpotation.pdf)
The additive-approximation problem is \(\mathrm{NP}\)-hard, even with \(H=3\), \(C=0\), attendee counts and room capacities equal to \(1\), and fixed error \(\varepsilon=1/4\).
The reduction below produces a designated type whose total credit is \(0\) in the negative case and at least \(2\) in the affirmative case. It also verifies baseline feasibility and the derivative promise.
The allowance of binary-encoded, numerically large energy coefficients is essential to the amplification used in this proof.
We use the following properties of the successive-shortest-path construction of [Disser and Skutella, Lemmas 1–2 and Appendix A](https://arxiv.org/pdf/1311.5935).
An instance of \(\mathrm{PARTITION}\) can be transformed in polynomial time into an acyclic directed network with source \(s\), sink \(t\), positive integer arc capacities, rational arc costs, and a distinguished arc \(e\) of capacity \(1\). The maximum flow value is an integer \(K\), unchanged by deleting \(e\). Writing \(F(d,u)\) for the minimum cost of a real \(s\)-\(t\) flow of value \(d\), with the capacity of \(e\) replaced by \(u\), the construction has these properties:
These value properties follow from the optimal intermediate flows of the algorithm: the negative case avoids \(e\), while the affirmative case has a strictly cheaper cross-gadget augmentation at an odd integer demand.
We first make all arc costs positive integers, preserving these properties. Choose a topological numbering \(i\) and an integer \(P>\max_a|c_a|\). Replacing the cost of \(a=(v,w)\) by \(c_a+P(i(w)-i(v))\) makes it positive. For every flow of value \(d\), this adds exactly \(P(i(t)-i(s))d\), independently of \(u\). Multiplying by a common denominator then makes every cost integral. Both operations have polynomial bit complexity.
Henceforth \(c_a\) denotes these positive integer costs, and \(U_a\) denotes the original integer capacities; in particular, \(U_e=1\). Set \(c_{\max}=\max_a c_a\) and \(J=|V_{\mathrm{net}}|c_{\max}\).
For all \(d\in[0,K]\) and \(u\in[0,1]\), the value has a representation
\(F(d,u)=\max_{p\in\mathcal P}\{\alpha_p d+\beta_p u+\gamma_p\}\),
where \(\mathcal P\) is finite, all coefficients are integers, and
\(|\alpha_p|\le 2J,\qquad -3J\le\beta_p\le0.\)
Here is a direct justification. Take \(\mathcal P\) to be all integer vertex-potential vectors with coordinates in \([-J,0]\). Define
\(y_a(p)=\max\{0,p_{\operatorname{head}(a)}-p_{\operatorname{tail}(a)}-c_a\}\),
\(\alpha_p=p_t-p_s,\qquad \beta_p=-y_e(p),\qquad \gamma_p=-\sum_{a\ne e}U_a y_a(p).\)
For any feasible flow \(z\), summing the inequalities
\(c_a z_a\ge(p_{\operatorname{head}(a)}-p_{\operatorname{tail}(a)})z_a-y_a(p)U_a\)
gives the corresponding affine lower bound on its cost.
Conversely, an optimal flow has no negative-cost residual cycle: augmentation around such a cycle would strictly decrease its cost. Add an auxiliary vertex with zero-cost arcs to every vertex and take shortest-path distances in the residual network. These distances are integers in \([-J,0]\), because residual arc costs have absolute value at most \(c_{\max}\), shortest paths can be chosen simple, and the direct auxiliary arcs give distance at most \(0\).
The residual shortest-path inequalities imply equality in the summed lower bound: an unsaturated arc has \(y_a=0\), and a positive-flow arc satisfies the complementary equality. Thus some \(p\in\mathcal P\) attains the optimal value. The coefficient bounds follow immediately from the bounds on \(p\).
In particular, \(F\) is continuous and piecewise affine, and, for fixed \(u\),
\(|F(d_2,u)-F(d_1,u)|\le2J|d_2-d_1|.\)
Suppose the instance is affirmative, and choose the integer \(d_0\) from Section 2. Put
\(\Delta=F(d_0,0)-F(d_0,1)>0.\)
We claim that
\(F(d_0,u)=F(d_0,0)-\Delta u\quad\text{for every }u\in[0,1],\)
and that \(\Delta\) is a positive integer.
To prove linearity, write the flow problem in standard form using capacity slacks:
\(B'z=d_0 b',\qquad z+w=U(u),\qquad z,w\ge0,\)
where \(B'\) contains independent conservation equations. Its constraint matrix is totally unimodular: directed incidence matrices are totally unimodular, and appending unit rows and unit columns preserves this property.
Consequently, every basic variable has the form \(a+bu\), with \(a\in\mathbb Z\) and \(b\in\{-1,0,1\}\). Its nonnegativity can change only at an integer value of \(u\). The set of feasible bases is therefore constant throughout \((0,1)\).
On that interval, the optimal value is the minimum of the affine costs of a fixed finite collection of feasible bases, so it is concave. It is also convex, because convex combinations of feasible flows remain feasible for the corresponding convex combination of capacities. It is thus affine. Continuity from Section 3.1 identifies its endpoint values. At either endpoint all right-hand sides are integral, so total unimodularity and integral costs give integral optimal values. Therefore \(\Delta\ge1\).
We next make this capacity price stable under a small demand perturbation. Define
\(\eta=\frac{1}{64(J+1)}.\)
Then, whenever \(|d-d_0|\le\eta\) and \(u\in[1/8,1/4]\),
\(\partial_uF(d,u)=-\Delta.\)
Indeed, consider an affine function \(\ell(d,u)=\alpha d+\beta u+\gamma\) in the representation from Section 3.1. If \(\beta\ne-\Delta\), the affine function
\(g(u)=F(d_0,0)-\Delta u-\ell(d_0,u)\)
is nonnegative at both \(0\) and \(1\), and has a nonzero integer slope. Hence
\(g(u)\ge\min\{u,1-u\}\ge1/8\)
on the stated interval. At \(d_0,u\), at least one active affine function has \(u\)-slope \(-\Delta\). Perturbing \(d\) changes the difference between it and \(\ell\) by at most
\(4J|d-d_0|\le4J\eta<1/8.\)
Thus no affine function with a different \(u\)-slope can become active. All active functions have slope \(-\Delta\), which proves the asserted ordinary partial derivative.
We initially use unnormalized masses and supplies. Normalization is performed in Section 6.
Use slots \(0,1,2\), with horizon \([0,3)\). Every attendee count and room attendee capacity is \(1\), and set \(C=0\).
For each network vertex \(v\), create a room category \(v\). For each arc \(a\), create a private category \(g_a\), and create one further category \(g_*\).
Choose a power of two \(M>16(J+K+1)\), and define
\(D=M/2,\qquad R=2J+1,\qquad R_{\mathrm d}=R+1.\)
For every arc, put
\(P_a=4U_a,\qquad M_a=\begin{cases}1/4,&a=e,\\4U_a,&a\ne e.\end{cases}\)
The meeting types are as follows. An option is written as \((\text{start},\text{category})\).
| Type | Raw mass | Duration | Baseline | Other admissible options |
|---|---:|---:|---|---|
| \(A_a\), for \(a=(v,w)\) | \(M_a\) | \(2\) | \((1,v)\) | \((1,g_a)\) |
| \(B_a\), for \(a=(v,w)\) | \(P_a\) | \(1\) | \((1,g_a)\) | \((1,w)\) |
| \(Z_a\) | \(P_a-U_a\) | \(1\) | \((2,g_a)\) | None |
| \(A_*\) | \(M\) | \(2\) | \((0,g_*)\) | \((1,g_*)\), \((1,s)\) |
| \(B_*\) | \(4K\) | \(1\) | \((1,t)\) | \((1,g_*)\) |
| \(Z_*\) | \(M-D\) | \(1\) | \((2,g_*)\) | None |
| \(D_v\), for each vertex \(v\) | \(1\) | \(1\) | \((1,v)\) | None |
Raw room supplies are
\(k_{g_a}^{\mathrm{raw}}=P_a,\qquad k_{g_*}^{\mathrm{raw}}=M,\)
\(k_v^{\mathrm{raw}}=1+\sum_{a:\operatorname{tail}(a)=v}M_a+4K\,\mathbf1_{\{v=t\}}.\)
All are positive. All listed masses are positive as well.
Set the satisfaction threshold to \(B=1\). Give satisfaction \(1\) to exactly the listed options and \(0\) to any unwanted pair in the relevant Cartesian product. Thus the required admissible-option sets can be represented by the input format.
For the unscaled energies:
At slot \(1\), the baseline load equals the supply in every vertex category and every gate category. At slot \(2\), the fillers fit: \(P_a-U_a<P_a\) and \(M-D<M\). In category \(g_*\), the baseline meetings occupy slots \(0,1\), and the filler occupies slot \(2\). These baseline meetings therefore admit room timelines with the stated supplies.
Let \(x_a\) and \(y_a\) be the away masses of \(A_a\) and \(B_a\). Let \(x\) be the mass of \(A_*\) at \((1,g_*)\), let \(f\) be its mass at \((1,s)\), and let \(y_*\) be the away mass of \(B_*\).
Every non-filler meeting in the table occupies slot \(1\), regardless of its option. Their total mass equals the sum of the supplies of the vertex and gate categories. Consequently, every such category must be saturated at slot \(1\).
Saturation in \(g_a\) gives
\(P_a-y_a+x_a=P_a,\quad\text{so }x_a=y_a.\)
Saturation in \(g_*\) gives
\(M-f+y_*=M,\quad\text{so }y_*=f.\)
Saturation in each vertex category then gives
\(\sum_{a:\operatorname{tail}(a)=v}x_a- \sum_{a:\operatorname{head}(a)=v}x_a =f(\mathbf1_{\{v=s\}}-\mathbf1_{\{v=t\}}).\)
Thus the \(x_a\) form an \(s\)-\(t\) flow of value \(f\). Slot \(2\) in \(g_a\) imposes \(x_a\le U_a\), while slot \(2\) in \(g_*\) imposes \(x\le D\). The away-budget constraints impose their corresponding bounds on these variables, including \(x+f\le Q_{A_*}\), where \(Q\) denotes raw budgets.
These conditions are also sufficient. Assign the meetings occupying slot \(1\) disjoint subsets of a room interval of length equal to the category supply. In \(g_a\), the room mass free at slot \(2\) is \(P_a-x_a\), enough for its filler exactly when \(x_a\le U_a\). In \(g_*\), it is \(M-x\), enough exactly when \(x\le D\). All remaining categories have no additional meetings at slot \(2\). Finite subdivisions of these room intervals yield finitely many timelines with the prescribed masses.
The raw energy consequently equals
\(R_{\mathrm d}M-R_{\mathrm d}x-Rf+\sum_a c_a x_a.\)
Writing \(V_{\mathrm{raw}}\) for raw savings, its maximization objective is therefore
\(R_{\mathrm d}x+Rf-\sum_a c_a x_a.\)
Let \(w\) be the raw mass vector and take raw budgets \(Q=\lambda w\).
For \(0<\lambda<1/2\), the schedule \(x=\lambda M\), \(f=0\) is feasible. Any feasible schedule has savings at most
\(R_{\mathrm d}x+Rf\le R_{\mathrm d}(x+f)\le R_{\mathrm d}Q_{A_*},\)
because arc costs are nonnegative and \(R<R_{\mathrm d}\). Hence, locally around each such diagonal point,
\(V_{\mathrm{raw}}(Q)=R_{\mathrm d}Q_{A_*}.\)
For \(\lambda>1/2\), every arc quota except that of \(A_e\) is slack relative to its fixed capacity. The quota of \(B_*\) also exceeds \(K\). The effective capacity of \(e\) is
\(u(\lambda)=Q_{A_e}=\lambda/4.\)
An optimum fills the dummy alternative to \(x=D\). To see this, if \(x<D\) and \(f>0\), decrease the entire flow proportionally and transfer the released \(A_*\) budget to \(x\). Arc cost decreases, and the reward increases because \(R_{\mathrm d}>R\). If \(f=0\), increasing \(x\) is feasible until \(D\) is reached.
After setting \(x=D\), the flow value is
\(d(\lambda)=\min\{M(\lambda-1/2),K\}.\)
Indeed, Section 3.1 bounds every marginal flow cost by \(2J<R\), so savings strictly increase with flow value until the budget or maximum-flow bound is reached. Thus
\(V_{\mathrm{raw}}(\lambda w)=R_{\mathrm d}D+R\,d(\lambda)-F(d(\lambda),u(\lambda)).\)
Locally, this depends only on \(Q_{A_*}\) and \(Q_{A_e}\), with \(d=\min\{Q_{A_*}-D,K\}\) and \(u=Q_{A_e}\).
We now verify the derivative promise. On the interval
\(1/2<\lambda<1/2+K/M,\)
an affine function from Section 3.1 restricts to a line with slope \(\alpha_pM+\beta_p/4\). Two different pairs \((\alpha_p,\beta_p)\) cannot give the same slope: their coefficients are integers, \(|\beta_p-\beta_{p'}|\le3J\), and \(M>16J\).
Therefore, except at finitely many line intersections, all active affine functions have the same gradient. Every ordinary partial derivative exists there. Before this interval the savings are affine; after it, the only varying argument of \(F(K,u)\) is \(u\), giving a one-variable piecewise-affine function. All other budget coordinates are locally irrelevant.
Thus every partial derivative exists except at finitely many diagonal parameters and is bounded and integrable. The constructed instances satisfy the promise in both cases.
For a negative instance, \(F(d,u)\) is independent of \(u\) throughout the relevant rectangle, by monotonicity in capacity and the equal endpoint values. Hence the raw per-capita credit of \(A_e\) is \(0\).
For an affirmative instance, let \(d_0,\Delta,\eta\) be as in Section 3.2, and put
\(\lambda_0=1/2+d_0/M.\)
For
\(\lambda\in[\lambda_0-\eta/M,\lambda_0+\eta/M],\)
we have \(|d(\lambda)-d_0|\le\eta\). This interval lies strictly inside the interval where \(d(\lambda)=M(\lambda-1/2)\), since \(d_0\) is an interior integer demand and \(\eta<1/2\). Moreover,
\(u(\lambda)\in[1/8,1/4],\)
because \(K/M<1/16\). Section 3.2 therefore gives
\(\partial_{Q_{A_e}}V_{\mathrm{raw}}(\lambda w) =-\partial_uF(d(\lambda),u(\lambda))=\Delta\ge1.\)
Savings are nondecreasing in each budget, so this derivative is nonnegative wherever it exists elsewhere. Consequently, the raw per-capita credit satisfies
\(a_{A_e}^{\mathrm{raw}}\ge\frac{2\eta}{M} =\frac{1}{32(J+1)M}.\)
Let \(W\) be the sum of the raw masses in the table. Choose a power of two \(N>W\). Add one fixed type of mass \(N-W\), with a single duration-\(1\), zero-energy meeting in its own category of supply \(N-W\).
Divide every mass and supply by \(N\). The masses now sum to \(1\). They and the supplies are positive dyadic rationals, because the raw quantities have denominators dividing \(4\).
Finally, multiply every energy coefficient by the integer
\(\Gamma=256N(J+1)M.\)
For normalized budgets \(q\), scaling timeline masses gives
\(V(q)=\frac{\Gamma}{N}V_{\mathrm{raw}}(Nq).\)
Thus normalized per-capita credits equal \(\Gamma\) times their raw counterparts. Since \(\mu_{A_e}=1/(4N)\), an affirmative instance satisfies
\(\mu_{A_e}a_{A_e} \ge\frac{\Gamma}{4N}\frac{1}{32(J+1)M}=2.\)
For a negative instance this total credit is exactly \(0\).
All promises remain valid under these scalings. There are \(O(|V_{\mathrm{net}}|+|\mathcal A|)\) types and categories, and \(H=3\). The powers of two \(M,N\), the multiplier \(\Gamma\), and every input coefficient have polynomial bit length. Hence the whole society is constructed in polynomial time.
With \(\varepsilon=1/4\), an approximate designated total credit lies at most \(1/4\) above \(0\) in the negative case and at least \(7/4\) in the affirmative case. Comparing it with \(1\) decides \(\mathrm{PARTITION}\).
The per-capita credit alone also distinguishes the cases, since its affirmative lower bound is \(8N\). Therefore approximation of either all per-capita credits or all total credits is \(\mathrm{NP}\)-hard.
For completeness, this hardness does not arise from evaluating \(E(q)\).
For each category, create a directed acyclic graph whose vertices are its admissible meeting occurrences. Add a source arc to each occurrence, charging its ordinary energy. Connect occurrence \(v\) to occurrence \(w\) when \(v\) ends no later than \(w\) starts. Charge the cost of \(w\), using its discounted cost exactly when the two times coincide. Add zero-cost sink arcs.
Source-to-sink paths correspond exactly to room timelines, with matching costs. Nonnegative flows decompose into such paths. Bound each category’s source flow by its room supply, impose the type-occurrence equalities, and impose the away-mass inequalities.
There are at most \(\tau m\) occurrence vertices and polynomially many arcs. This gives a polynomial-size rational linear program for \(E(q)\). The reduction above establishes hardness specifically for integrating the individual marginal savings, despite this pointwise tractability.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed hardness in substance. I found no false central step or major gap. One minor clarification is needed in Section 2: the consequences extracted from the cited algorithmic construction should be distinguished explicitly from the published lemma itself.
The cited Lemma 2 concerns whether successive shortest paths ever augment along the distinguished arc. The reduction needs stronger, precisely quantified statements about optimal values: equality for every real demand in the negative case, strict inequality at an interior integer demand in the affirmative case, and preservation of maximum flow under deletion.
I checked the construction and Appendix A. They support the claimed consequences, including the strict cross-gadget cost improvement; this is more than merely an algorithm choosing an arc among tied optima. The network is acyclic, the distinguished capacity is \(1\), and the construction has polynomial encoding size. [Disser–Skutella, Section 3 and Appendix A](https://arxiv.org/pdf/1311.5935).
Minor issue: the write-up compresses these consequences into “These value properties follow from the optimal intermediate flows.” For a fully explicit verification, identify the intermediate-flow optimality statement being used, explain its applicability to real demands between augmentations, and identify why deleting the arc preserves the maximum value. These are routine clarifications of the cited construction, not new mathematical ingredients.
A topological numbering makes every arc’s numbering difference positive. Therefore the chosen potential shift makes every cost positive.
The added cost telescopes to \(P(i(t)-i(s))d\), independently of the distinguished capacity. Consequently, comparisons between capacities at the same demand are preserved. Clearing rational denominators preserves strict inequalities and has polynomial bit complexity.
The later use of integral costs is therefore justified.
The affine functions are valid lower bounds by conservation and the capacity inequalities. For the distinguished arc, its capacity in this calculation is the replacement value \(u\).
Optimality excludes negative residual cycles. The auxiliary-source shortest-path potentials consequently exist, are integral, and lie in the stated bounded interval. The residual inequalities give the complementary conditions necessary for the lower bound to attain the optimum.
Thus the finite maximum representation holds throughout the feasible rectangle. Its slope bounds imply the claimed continuity and demand Lipschitz bound. The constants \(2J\) and \(3J\) are conservative but valid.
The displayed standard-form matrix is totally unimodular: the capacity equations add identity rows to the incidence part, and the slack variables add unit columns.
Only one right-hand-side coordinate varies with \(u\). Hence each basic variable has an integral intercept and coefficient in \(\{-1,0,1\}\). Its feasibility cannot change strictly inside \((0,1)\).
The minimum over a fixed collection of feasible affine basis costs is concave on that interval. Feasible-flow interpolation establishes convexity. Together with the already established continuity, this proves the asserted endpoint interpolation.
Integral endpoint data and integral costs justify integral optimal values, so \(\Delta\ge1\).
For an affine piece with slope different from \(-\Delta\), the difference function is nonnegative at both endpoints and has nonzero integral slope. The stated interior lower bound of \(1/8\) follows.
The perturbation estimate is valid:
\(4J\eta=J/(16(J+1))<1/8\).
Therefore every active piece in the specified neighborhood has capacity slope \(-\Delta\). This establishes the ordinary capacity partial derivative, including points where several demand slopes remain active.
All raw masses and supplies are positive. The listed durations fit the horizon, and attendee feasibility is automatic. Satisfaction filtering can realize the listed options despite the Cartesian-product input format.
The baseline loads fit the room supplies at every occupied slot. In particular, the baseline \(A_*\) meetings end at slot \(2\), allowing the slot-\(2\) filler to follow them.
No baseline feasibility failure appears.
Every non-filler meeting occupies slot \(1\), and their total mass equals total room supply. This forces saturation category by category.
The gate equations correctly yield \(x_a=y_a\) and \(y_*=f\). Vertex saturation gives the displayed flow-conservation equations with the correct signs.
The slot-\(2\) constraints correctly impose \(x_a\le U_a\) and \(x\le D\). Conversely, the room-interval subdivision argument realizes meetings satisfying these constraints as finitely many valid timelines. It also accommodates the slot-\(0\) baseline meetings in \(g_*\).
With \(C=0\), timeline adjacency has no effect on cost. The raw energy and savings formulas are correct.
Before \(\lambda=1/2\), assigning the entire \(A_*\) quota to the dummy alternative attains the stated upper bound. This remains feasible in a neighborhood of each such diagonal point.
After \(\lambda=1/2\), every non-designated arc quota strictly exceeds its fixed capacity, and the \(B_*\) quota strictly exceeds \(K\). The only variable effective arc capacity is therefore \(u=\lambda/4\).
The transfer argument justifies filling the dummy alternative to \(D\). The demand Lipschitz bound and \(R>2J\) justify maximizing flow value up to the remaining budget or \(K\).
Thus the displayed local formula for savings is valid.
During the demand ramp, distinct integral coefficient pairs cannot have equal restricted slopes: the possible difference in capacity coefficients is too small to cancel a nonzero demand coefficient multiplied by \(M\).
Except at finitely many intersections, active affine functions consequently have identical gradients. This verifies ordinary coordinate partial derivatives, rather than merely differentiation along the diagonal.
Before the ramp the value is locally affine. After the ramp the demand budget is locally slack, and only the capacity coordinate remains relevant. All remaining budget coordinates are locally irrelevant.
The exceptional set is finite, and the derivatives are bounded and integrable. The promise is satisfied.
In the negative case, capacity monotonicity and equal endpoint values imply capacity independence throughout the rectangle. The designated credit is therefore zero.
In the affirmative case, the interval around \(\lambda_0\) remains strictly inside the demand ramp and keeps \(u\) in the required range. Its length and the derivative lower bound give
\(a_{A_e}^{\mathrm{raw}}\ge1/(32(J+1)M)\).
The normalization identity correctly gives a factor of \(\Gamma\) for per-capita credits. Multiplying by the normalized designated mass gives the claimed total-credit lower bound of \(2\); the per-capita lower bound is \(8N\).
All generated coefficients have polynomial bit length. Fixed additive error \(1/4\) separates the cases by comparison with \(1\). This addresses the requested approximation problem directly.
The occurrence graph is acyclic because meeting durations are positive and every transition advances time. Its paths represent precisely the allowed timelines, and transition costs correctly implement the predecessor discount.
Flow decomposition, room-supply bounds, type equalities, and away-budget inequalities give the claimed polynomial-size rational linear program. This supplementary result is consistent with hardness of integrating individual marginal savings.
The minimum requested revision is an explicit explanation of the source-to-value-function implications in Section 2. No change to the reduction, derivative argument, or amplification is indicated by this audit.
⟨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.