d4-conf-ijcai-2016-0541

The strongest honest anchor is Theorem 3, proved in this paper; the paper has no named hardness result to anchor a hardness-transfer question. The theorem says: if \(s_c\) is the probability that column \(c\) is all ones, and \(\mu_c\) is the expected number of inspections in that column, conditional on its being inspected and infeasible, when its entries are inspected in nondecreasing order of their success probabilities, then an optimal policy inspects whole columns consecutively, orders entries within each column by nondecreasing success probability, and orders columns by nondecreasing \(\mu_c(1-s_c)/s_c\). The paper derives a polynomial-time algorithm from this characterization.

Lead: Rare-Conflict Continuum Matrix Inspection. Consider an organization with \(N\) invitees, drawn from a fixed set \(T\) of \(\tau\) roles or availability profiles, where \(N\) is large and \(\tau\) is small. Let \(\mu_t>0\) be the fraction of invitees in type \(t\), with \(\sum_t\mu_t=1\), and let \(C\) be the \(m\) proposed meeting times. This is a deliberately narrow but plausible regime: the times have been pre-screened, so individual conflicts are rare even though the meeting requires everyone to be available.

For each type and time, the instance gives a positive failure rate \(\lambda_{tc}\). In the finite society corresponding to the instance, each type-\(t\) invitee is independently unavailable at time \(c\) with probability \(\lambda_{tc}/N\), for \(N\) large enough that this is at most one. In the continuum, represent type \(t\) by an interval of mass \(\mu_t\). For each \(t,c\), place independent Poisson failure points on that interval at rate \(\lambda_{tc}\) per unit mass. A time is feasible exactly when its type intervals contain no failure points.

A policy is a fixed measurable scan order over the type-mass intervals for all proposed times. It scans mass, at unit cost per unit scanned, until it finds a failure point in a time’s column, which certifies that time infeasible; it stops if it scans an entire column with no failure points, or once every column has been rejected. The question is to output a scan order minimizing expected total scanned mass. This cost is the limit of the discrete expected number of inspections divided by \(N\). Thus the mass is the population share of each type, and the action is scanning invitee mass for a particular time.

This is a genuine high-multiplicity regime: many invitees share each type’s relevant attributes, while their availability outcomes remain independent as in the paper. In the finite model, \(n_t=N\mu_t\) invitees of type \(t\) have failure probability \(\lambda_{tc}/N\). Their failures converge to the stated Poisson process, and a column’s feasibility probability converges to
\[ s_c=\exp\!\left(-\Lambda_c\right),\qquad \Lambda_c=\sum_{t\in T}\mu_t\lambda_{tc}. \]
The continuum keeps the paper’s all-available criterion, independent uncertainty, inspection action, and stopping logic. I expect the mirror to be tractable: its natural policy scans types within each column in decreasing order of \(\lambda_{tc}\), then orders columns by the limit of Theorem 3’s index.

In detail, let \(t_1,\ldots,t_\tau\) order the types for column \(c\) by decreasing \(\lambda_{tc}\), and put \(H_{j-1}=\sum_{i<j}\mu_{t_i}\lambda_{t_i c}\). The expected mass scanned in that column, conditional on finding a failure, is
\[ \eta_c= \frac{\displaystyle\sum_{j=1}^{\tau} e^{-H_{j-1}}\frac{1-e^{-\lambda_{t_jc}\mu_{t_j}}}{\lambda_{t_jc}}} {1-e^{-\Lambda_c}}. \]
The proposed column index is \(\eta_c(e^{\Lambda_c}-1)\), and columns are scanned in increasing order of this index. This is the direct limit of Theorem 3: within a column, smaller finite success probabilities correspond to larger failure rates; the discrete conditional expected inspection count divided by \(N\) tends to \(\eta_c\); and \(s_c\) tends to \(e^{-\Lambda_c}\). In a real-arithmetic model the policy takes \(O(m\tau\log\tau+m\log m)\) sorting and arithmetic operations. A bit-complexity treatment would need to specify how the exponential index values are compared, especially near ties.

I think the authors would recognize this as a continuous asymptotic form of their underlying matrix-inspection problem, rather than a different outcome-space or axiomatic question. It covers their general independent-entry result, Theorem 3; it does not cover their probability-estimation discussion or the different batched-query model.

The weak point is the rare-conflict scaling. If each person’s failure probability stays bounded away from zero as \(N\) grows, the probability that any proposed time is available to everyone tends to zero. The per-capita expected inspection objective then loses the paper’s interesting trade-off. The mirror therefore describes a specific, restrictive regime, not a universal continuization of the paper. That restriction is also what makes the limit meaningful: it preserves a nonzero chance of a unanimously feasible time while taking the population to a continuum.

The main questions for a prover are whether the finite optimal values converge to this continuum optimum, and whether the exchange arguments behind Theorem 3 rule out every measurable interleaving policy in the limit. Further extensions could examine non-unit inspection costs, correlations between invitees, and how robust the policy is when the rare-failure rates are estimated rather than known.