| paper | d4-conf-atal-2014-0051 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even for fixed \(\varepsilon=1/4\), \(H=3\), and \(C=0\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Lemma 4.2
statement extracted from the paper’s text layer
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 distribution \(\mu\) over complete meeting-request types, with each type’s mass assigned among its integral scheduling options under scaled capacities. The energy-saving value \(V(q)\) comes from the resulting fluid scheduling optimization; the requested allocation is its Aumann–Shapley credit by type.
Lemma 4.2 only handles independent request groups; identical recurring types share capacity in the coupled case, and the convergence of finite Shapley credits to the proposed Aumann–Shapley allocation is unproved.
fatal: False
The mirror covers fair credit allocation for meeting flexibility and its decomposition across independent request groups. It leaves out robust rescheduling, the integrated deployment, and the paper’s empirical results.
The paper has no numbered theorem classifying a problem as polynomial-time solvable or hard. Its strongest named computational anchor is the structural result used to justify partitioning the Shapley computation.
Anchor — Lemma 4.2, proved here. If meeting-request subsets \(R_1\) and \(R_2\) are independent, and \(i\in R_1\), then \(\phi_i(R_1\cup R_2,v)=\phi_i(R_1,v)\). Independence is defined by additive energy consumption, \(e(R_1\cup R_2)=e(R_1)+e(R_2)\). In words, adding an independent block of requests does not change a request’s Shapley value. The companion Lemma 4.1 establishes that the characteristic function is inessential for independent meetings; Lemma 4.2 uses that property to support separate computation on independent groups.
The mirror I would put to the authors is Continuous Shapley credit computation for meeting flexibility. Consider a large university or corporate estate with many recurring meetings: standardized seminars, classes, office hours, or team meetings. A type specifies the complete request information relevant to THINC’s scheduling and credit calculation—preferred times and locations, duration, attendees, flexibility, comfort requirements, and energy parameters. The society is a distribution \(\mu\) over those types. The intended regime has many requests and substantially fewer recurring request types. Requests with different prices, preferences, or other relevant attributes belong to different types.
For high multiplicity to be meaningful, room and time capacity and energy use scale with the meeting population—for example, across many equivalent room banks or buildings. Let \(q_t\in[0,\mu_t]\) be the mass of type \(t\) that offers flexibility. The scheduling decision assigns mass of each type across its allowed integral time-and-location options. A fractional assignment means that different requests of the same type take different options; each individual meeting still receives an ordinary schedule. Let \(E(q)\) be the minimum normalized energy of the resulting schedule, using THINC’s time, location, comfort, and energy-saving interactions. Define \(V(q)=E(0)-E(q)\), the savings when mass \(q\) offers flexibility relative to the all-fixed baseline.
The problem is to compute each type’s per-capita credit density \(a_t\), and hence its total credit \(\mu_t a_t\), under the high-multiplicity limit of the finite Shapley allocation. Where the derivative exists, that limit is \(a_t=\int_0^1 \partial_t V(\lambda\mu)\,d\lambda\). Thus the instance consists of the finite request-type support and rational masses, the scheduling options and scaled capacities, the energy and comfort data, and a requested precision \(\varepsilon\); a solution gives credits within \(\varepsilon\) of the limit allocation. This is the same fairness question THINC asks—how much energy-saving credit each kind of flexible request earns through its marginal contribution—expressed for a population rather than a named list of meetings.
The connection to Lemma 4.2 is concrete. If two groups of requests use separate room and energy systems, so their scheduling values add, the credit density for a type in one group should be unchanged when the other group is added. In the continuous definition, this follows because the derivative for that type depends only on its own group’s value along the path \(\lambda\mu\). This mirrors the lemma’s exact independence property and gives the model a recognizable connection to THINC’s Shapley computation.
I expect additive approximation of these credits to be tractable (Class A): the scheduling value is an optimization problem over type masses, and for a continuous linear-programming formulation its value function is piecewise linear. Sampling points on the path and using optimality information offers a plausible route to approximate the integral. Exact computation could be harder if the value function has many breakpoints. Lemma 4.2 itself guarantees neither running time nor polynomial-time computation; it gives an exact decomposition property that can help.
This mirror covers THINC’s fair credit allocation and its decomposition of independent request groups. It does not cover the robust BM-MDP rescheduling contribution, the deployment, or the paper’s empirical claims. Its weakest point is that the continuous credit formula is a proposed high-multiplicity limit, not a result established in the paper. Also, scaling room and time capacity is plausible across a large estate or many equivalent buildings, but is a modeling choice; it could distort a single building’s tightly constrained daily schedule.
Lemma 4.2 is the strongest anchor, and the negative case is that it is a separability identity, not a computational result. It says that when the characteristic function splits across independent groups, adding another group leaves a player’s Shapley value unchanged. The proposed continuous formula, \(a_t=\int_0^1 \partial_t V(\lambda\mu)\,d\lambda\), does not continue that lemma in any substantial way: for an additive value function, the same independence follows directly from separability of the derivative.
The best repeated-meeting scenario sharpens the problem. Requests of the same complete type have the same time and location options, so they overlap in THINC’s graph and belong to the same connected component. Lemma 4.2 cannot decompose that high-multiplicity mass. If the scenario instead uses independent room banks or buildings, the components’ values add, and the lemma’s continuous counterpart is immediate. The interesting shared-capacity case requires a fluid scheduling model with scaled capacity and fractional mass assignments. That may be coherent, but its computational question is the Aumann–Shapley allocation of a new LP value function.
THINC’s Shapley contribution is a collection of approximation methods evaluated empirically. The paper gives no numbered result establishing the complexity of the finite problem, nor a result showing that its finite Shapley allocations converge to the proposed integral. Establishing a scaling limit, a credit normalization, and an approximation algorithm for the fluid model would be a new research project. The anchor does not supply those results or a computational decomposition for the coupled case.
This is a strong argument against treating Lemma 4.2 as a continuous mirror. It does not establish the broader claim that no worthwhile mirror exists. A fluid Shapley-credit problem for recurring meetings could be interesting on its own, and the authors might recognize it as an extension of their credit-allocation work. The honest weakness in the negative case is that it rules out the paper’s named anchor as a substantial mirror; it cannot rule out that adjacent research question.
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.