d4-conf-aaai-2018-0659

The strongest mirror I believe is a Mass-SDSQ for large event audiences organized into socially connected cohorts. Picture a major tournament with many viewers, a short list of simultaneous camera feeds, and large fan communities. A type records both a viewer’s exact preferences over those feeds and their social cohort. There may be millions of viewers but only hundreds of preference-and-cohort types, each with rational population mass \(\mu_t\). For this mirror, cohorts form a block social graph: viewers within a cohort are mutually connected, and an edge between two cohorts means every viewer in one is connected to every viewer in the other. That is a restrictive social-network regime, but a concrete one—for example, a platform where watch-room membership supplies the social connection.

Here is the lead question. Given channels \(C\), their weighted diversity graph, types \(T\) with masses \(\mu_t\) and preference sets \(P_t\), a block social graph \(H\), a hop bound \(h\ge1\), and an interest floor \(\rho\), choose a nonempty channel set \(K\) and selected masses \(x_t\in[0,\mu_t]\). Require that each selected channel \(q\in K\) is preferred by at least \(\rho\) selected population mass, so \(\sum_{t:q\in P_t}x_t\ge\rho\); every type with \(x_t>0\) prefers some channel in \(K\); and every pair of types with positive selected mass is at social distance at most \(h\) in \(H\). Maximize the paper’s objective, \(\sum_{[q,r]\in D(K)}W[q,r]/|K|\). The solution is an optimal pair \((x,K)\), or a report that no feasible pair exists. The population is the continuous object here; channels and the diversity objective remain as the paper defines them.

The co-modification is to express the paper’s minimum interest count \(p\) as a share of the whole population: for a finite audience of \(N\) viewers, set \(\rho=p/N\). That preserves a meaningful per-capita interest requirement as the audience grows. It also makes the answer directly interpretable as “at least this fraction of the audience,” which suits a large watch-room service better than a fixed count of a few friends. The type masses describe the audience; \(x_t\) describes how much of each type joins the soiree.

My anchor is Theorem 1, proved in this paper: SDSQ is NP-hard and, unless \(P=NP\), is inapproximable within any finite factor. The paper proves this by reducing from the NP-hard Maximum Diameter-Bounded Subgraph problem, cited to Asahiro, Miyano, and Samizo (2010). That problem asks, given a graph and integers \(k,d\), whether it contains a subgraph of at least \(k\) vertices whose vertices are pairwise at distance at most \(d\). In the paper’s reduction, each graph vertex becomes a viewer, all viewers prefer both of two channels, those channels have one diversity edge of weight \(1\), \(p=k\), and \(h=d\). Thus an SDSQ solution exists exactly when the source graph has such a diameter-bounded subgraph.

The same reduction gives a continuous-population hardness result for Mass-SDSQ. For a source graph on \(n\) vertices, make one type per vertex, each with mass \(1/n\), use the source graph as the type social graph, set \(h=d\) and \(\rho=k/n\), and again let every type prefer both channels. A feasible selected mass must have support on at least \(k\) types, since each type contributes at most \(1/n\); that support must have pairwise distance at most \(d\). Conversely, a qualifying \(k\)-vertex subgraph supplies feasible mass. In a yes-instance, selecting both channels gives positive objective \(1/2\); in a no-instance there is no feasible solution. So this is hardness that survives the mass formulation, rather than a claim that any continuous relaxation must become easy.

The construction also admits genuine high multiplicity: replace each type by \(r\) socially identical viewers, with complete connections within and between adjacent cohorts. Then \(N=rn\) while the support still has \(n\) types, and \(N/\tau=r\) can be large. The exact social-distance condition survives this blow-up. For the general Mass-SDSQ problem, I therefore expect hardness to transfer. The reduction locates the difficulty in choosing a socially tight support over types, not in assigning an integer identity to every viewer.

The weakest point is that the reduction’s combinatorics still grow with the number of types, \(\tau\), and its social graph is block-structured. It does not show hardness when \(\tau\) is fixed and only the mass per type grows. Also, because the objective rewards channel diversity but neither penalizes nor caps the selected group, any feasible \(x_t>0\) can be increased to \(\mu_t\) without harming feasibility. Fractional selected masses may therefore be redundant at an optimum; the hard choice remains which types and channels to include. These limits matter, but they do not erase the mirror: it asks the same joint question about social tightness, preference coverage, and channel diversity for a large audience represented by population mass. They leave sharp follow-up questions: does the problem become tractable for fixed \(\tau\), or with restrictions on the type social graph, and can SDSSel’s approximation guarantee be adapted to weighted type masses?