Bayesian Optimization-Based Combinatorial Assignment*

The strongest honest case is a population-level version of BOCA’s winner-determination and query-generation problem. I would use one anchor only: Theorem 2, “MVNN MILP Tailored to Combinatorial Assignment,” proved in this paper (Appendix F.1). The paper has no named theorem establishing NP-hardness, membership in P, W[1]-hardness, or FPT; Theorem 2 is its strongest named computational result.

Call the mirror Continuous BOCA Batch-WDP\(_\infty\).

Consider a large university with many thousands of students and a relatively small number \(m\) of course categories. Students fall into \(\tau\) canonical types: a type includes the student’s complete valuation over course bundles, eligibility and priority parameters, the bundles already queried, and the current BOCA model state. Thus two students are the same type only if they are indistinguishable to the mechanism. Let \(\mu_t\) be the fraction of students of type \(t\). Course capacities scale with population: if \(B_j\) seats of course \(j\) are available among \(N\) students, write \(\beta_j=B_j/N\).

The individual outcome remains discrete: a student receives a bundle \(S\subseteq M\). Only the population is continuous. Let \(A_t(S)\) be the BOCA acquisition score for type \(t\), normally its MVNN upper-uncertainty bound \(M^{uUB}_t(S)\). Let \(y_{t,S}\) be the mass of type \(t\) assigned the whole bundle \(S\) in the next feasible query batch. The problem is

\[ \max \sum_{t\in T}\sum_{S\subseteq M} y_{t,S}A_t(S) \]

subject to

\[ \sum_{S}y_{t,S}=\mu_t \quad (t\in T), \]

\[ \sum_{t}\sum_{S\ni j}y_{t,S}\le \beta_j \quad (j\in M), \]

\[ y_{t,S}\ge 0, \]

with \(y_{t,S}=0\) for bundles already queried for type \(t\). A solution is an exact feasible mass allocation and its acquisition value. It is a batch of bundle queries to the population, not a fractional bundle given to an individual.

This is a direct high-multiplicity version of the paper’s equation (10): replace individual bidders \(i\) by masses of identical bidder types and replace binary assignment decisions by type–bundle masses. A discrete instance with \(n_t\) bidders of type \(t\) and \(B_j\) copies of item \(j\) maps to \(\mu_t=n_t/N\) and \(\beta_j=B_j/N\). The continuous problem is therefore not merely “Bayesian optimization is continuous”; it makes the bidder population itself the continuous object.

The regime is plausible in exactly the kind of domain the authors name. Large course-allocation markets contain repeated cohorts, standardized degree paths, common priorities, and recurring preference templates. The same construction applies to repeated spectrum-license markets or procurement settings with many bidders in the same business class. The scenario is not a seven-person hiring committee or a one-off bespoke auction. It is a market with \(N\) in the thousands or millions and \(\tau\) in the tens or hundreds. The paper’s authors should recognize the mirror because the objective, feasible allocations, bundle space, and acquisition function are unchanged; only repeated bidder identities are aggregated.

The resulting optimization is a configuration LP with exponentially many bundle columns. Its dual has one variable \(\lambda_t\) per type and one item-price variable \(p_j\), with constraints

\[ \lambda_t+\sum_{j\in S}p_j\ge A_t(S) \]

for every type and bundle. Hence the pricing problem is

\[ \max_{S\subseteq M}\left(A_t(S)-\sum_{j\in S}p_j\right). \]

This is precisely where Theorem 2 becomes relevant. The theorem gives a compact exact MILP for optimizing an MVNN over feasible bundle assignments, with four linear constraints per neuron and no big-\(M\) constraints. The same formulation can incorporate the dual item-price term and serve as an exact pricing oracle. Thus the theorem supplies the right computational bridge from the paper’s finite WDP to the continuous population LP.

My expected classification is Class B, with a genuine Class A subcase. If pricing for the relevant MVNN architectures is polynomial, column generation or separation yields a polynomial algorithm for the continuous problem. Additive valuations and bounded-interaction architectures are obvious candidates. For unrestricted MVNNs, however, the difficult combinatorics live in the bundle space and the number of items, not in bidder multiplicity. If pricing is hard, that hardness should transfer from ordinary combinatorial winner determination rather than arise because the population was continuized. This is exactly the programme’s distinction between multiplicity-driven hardness that may disappear and agenda/item-driven hardness that remains.

The paper’s Theorem 1, “MVNN-based 100%-uUB,” proved in Appendix D.1, is useful supporting evidence but I would not count it as a second anchor. It says that, when the full bundle is observed, the maximal monotone-normalized function consistent with a type’s elicited data has an exact two-hidden-layer MVNN representation. In the continuous setting, this means that every type’s uncertainty state can be represented compactly and carried as part of the population description. The theorem makes \(A_t\) a legitimate finite input to Continuous BOCA Batch-WDP\(_\infty\), rather than an informal posterior object.

The mirror covers Theorem 2 and the BOCA query-generation subproblem, not the entire experimental mechanism. It raises several natural follow-up questions: whether MVNN pricing is polynomial for useful architecture classes; how accurately the continuous LP can be rounded to a finite high-multiplicity assignment; how query observations update the distribution over information types; and whether type-level elicitation gives meaningful query savings while preserving BOCA’s incentive and individual-rationality properties.

The weakest point is that Theorem 2 proves a MILP formulation, not a polynomial-time algorithm, and the paper itself does not study high-multiplicity bidders. Moreover, collapsing bidders into exact types is only credible in repeated, standardized markets; it would be weak for heterogeneous one-off spectrum bidders. The response is that this is a deliberately chosen instance regime, exactly as high multiplicity requires. The continuous problem preserves indivisible bundles, the paper’s acquisition objective, its feasibility constraints, and its central WDP. It is therefore a faithful mirror of a real subproblem in the paper, even if its eventual complexity lies on the Class A/B boundary.