d4-conf-ijcai-2022-0973

The strongest mirror is the paper’s winner determination problem, not its learning pipeline. The paper gives no numbered NP-hardness or polynomial-time classification result. My single computational anchor is Theorem 2 (MILP), proved here: for finitely many bidders with fixed MVNN valuations \(N_i\), the problem \(\max_{a\in\mathcal F}\sum_i N_i(a_i)\) is exactly equivalent to a mixed-integer linear program. It uses allocation variables, hidden-layer outputs and auxiliary continuous variables, plus two binary indicators for each bReLU neuron; linear constraints encode the bReLU cutoffs, and the objective maximizes the sum of network outputs. This theorem establishes an exact formulation, not a polynomial-time algorithm. The paper actually solves these formulations inside its MVNN-based MLCA experiments and reports their runtimes, so it qualifies as an anchor under the stated rule.

Here is the lead mirror: Continuous-Mass MVNN Winner Determination. A plausible setting is a large course-allocation system. Students in the same curricular cohort use the same value function over course bundles; the course-seat supply scales with the student population. A regime might have tens of thousands of students but only dozens or hundreds of distinct valuation types. This is a scenario to investigate, not a claim about every university: types must be identical in the complete sense relevant to the problem. The paper itself identifies course allocation as a combinatorial-assignment application, and its monotonicity assumption fits settings where students can drop unwanted courses.

Formally, the input has \(m\) course types, a support \(T\) of \(\tau\) valuation types with rational masses \(\mu_t\geq 0\) summing to \(1\), and rational per-capita seat supplies \(q_j\in[0,1]\). Each type’s value function \(v_t:\{0,1\}^m\to\mathbb{Q}_{\geq 0}\) is supplied as an MVNN with rational parameters. The question is to find an optimal mass assignment \(x_{t,S}\):

\[ \max \sum_{t\in T}\sum_{S\subseteq [m]} x_{t,S}v_t(S) \]

subject to

\[ \sum_{S\subseteq [m]}x_{t,S}=\mu_t \quad(t\in T),\qquad \sum_{t\in T}\sum_{S\ni j}x_{t,S}\leq q_j \quad(j\in[m]),\qquad x_{t,S}\geq 0. \]

Here \(x_{t,S}\) is the fraction of the whole population of type \(t\) assigned bundle \(S\). Every student still receives an integral bundle; fractional values of \(x\) mean that a type’s mass is split across bundles. For a finite population of size \(n\), the corresponding capacities are \(nq_j\) seats. The objective is welfare per capita. The mirror changes the population representation and scales supply with it, while keeping the underlying task—choosing bundles to maximize total value under item capacities—recognizable as the paper’s WDP.

The key computational question is whether this LP has an efficient algorithm when the valuations are given compactly as MVNNs. It has up to \(\tau 2^m\) bundle variables. Column generation would need a pricing step of the form \(\max_{S\subseteq[m]}(v_t(S)-\sum_{j\in S}\lambda_j)\) for each type and item-price vector \(\lambda\). Theorem 2 makes the connection concrete: it shows that the paper’s MVNN structure supports exact mixed-integer optimization of the underlying bundle-allocation problem. In the continuous mirror, that structure may also support practical pricing, but the theorem does not give a polynomial-time bound for it.

I would expect hardness to persist, probably in Class B, because the combinatorics remain in the bundle dimension \(m\), rather than in population size. That is a conjectural direction, not a result of this paper: mass splitting can remove integrality that a discrete-winner-determination reduction may rely on. A prover should first settle whether pricing for compact MVNNs is polynomial, and whether any discrete hardness reduction survives this relaxation. If pricing is hard, useful next questions are whether it is fixed-parameter tractable in network width or \(m\), and what additive rounding guarantee relates the continuous optimum to a finite population.

My mirror covers Theorem 2’s MVNN-based WDP. It does not claim a continuous version of the paper’s prediction experiments, MLCA incentives or payments. Its weakest point is the regime: many auction bidders are heterogeneous and relatively few, and even students in a cohort may differ in their values over bundles. The scenario is convincing only where repeated, complete valuation templates are a reasonable model. The paper’s course-allocation motivation gives that scenario a foothold; exact type repetition is still the central assumption a skeptical author or referee is likely to test.