d4-conf-aaai-2020-1736

The strongest case is a mirror of the paper’s DNN-based winner determination problem, the optimization step it solves repeatedly during preference elicitation. I would name the continuous problem Mass-DNN Winner Determination.

The relevant named anchor is Theorem 1, “MIP Formulation,” proved in this paper. It says that, once the learned ReLU networks are fixed, maximizing their summed predicted values over feasible binary bundles is exactly equivalent to the paper’s mixed integer program, provided the big-\(M\) bound is large enough under Assumption 1. In the original problem, the decision is an allocation \(a\), with each bidder receiving a bundle in \(\{0,1\}^m\), each item allocated at most once, and objective \(\sum_i N_i(a_i)\). In the MIP, \(z_{i,0}=a_i\); for every bidder \(i\) and layer \(k\), the ReLU output is encoded by \(z_{i,k}-s_{i,k}=W^{i,k-1}z_{i,k-1}+b^{i,k-1}\), \(0\le z_{i,k}\le Ly_{i,k}\), \(0\le s_{i,k}\le L(1-y_{i,k})\), and binary \(y_{i,k}\). The objective is \(\sum_i z_{i,K_i}\), alongside binary bundle decisions and the item-capacity constraints. The paper uses this formulation in its experiments. It does not prove a polynomial-time or hardness result: the theorem establishes an exact encoding, not an efficient solution guarantee.

Here is the mirror. An instance has \(m\) item categories, a finite support \(T\) of valuation types, rational masses \(\mu_t\ge0\) summing to \(1\), and a fixed rational-weight ReLU network \(N_t:\{0,1\}^m\to\mathbb{Q}_{\ge0}\) for each type. A type includes everything relevant to this WDP: the predicted valuation function and any model or information that affects it. Let \(q_j\) be the supply of item \(j\) per unit of population. The decision variable \(x_{t,b}\) is the mass of type \(t\) assigned the whole, integral bundle \(b\in\{0,1\}^m\). The problem, Mass-DNN Winner Determination, is to choose \(x\) maximizing \(\sum_{t\in T}\sum_{b\in\{0,1\}^m} x_{t,b}N_t(b)\), subject to \(\sum_b x_{t,b}=\mu_t\) for every \(t\), \(\sum_{t,b}x_{t,b}b_j\le q_j\) for every item \(j\), and \(x_{t,b}\ge0\). Its solution is an optimal assignment of mass to bundles. Each person still gets an indivisible bundle; only the aggregate mass assigned to a bundle can be fractional.

A credible high-multiplicity regime is a large procurement market with thousands of small buyers and a modest set of standardized valuation schedules: buyers within a schedule have the same preferences and hence the same fitted network, while the supply of each standardized contract category scales with the market, at a fixed per-capita rate. Then \(n\gg\tau\), where \(n\) is the number of buyers and \(\tau=|T|\) the number of supported types. In a finite version, masses are \(n_t/n\) and \(q_j\) is the item supply divided by \(n\); the continuous model allows type mass to split across bundles. This is a direct aggregate form of the optimization the paper runs, with the co-modification of supply needed to make the population limit meaningful. It mirrors Theorem 1’s WDP at each elicitation round, not the whole query-selection procedure or PVM’s payments.

I expect hardness to transfer, Class B. The explicit formulation has exponentially many bundle variables, and its dual pricing problem asks, for each type, to maximize \(N_t(b)-\sum_j\lambda_jb_j\) over binary bundles. That pricing problem retains the item combinatorics. In fact, a reduction sketches NP-hardness even with one type and scarce per-capita supply: encode a 3SAT instance using two items per variable, for its true and false choices. A ReLU network can output \(1\) precisely when a bundle selects exactly one choice per variable and those choices satisfy every clause. For each clause, if \(r\in\{0,1,2,3\}\) is the number of selected satisfying literals, \(\max(0,r)-\max(0,r-1)\) is its satisfaction bit; ReLU layers can combine these bits with the exact-one checks. Set each item’s per-capita supply to \(1/2\). If the formula is satisfiable, assign half the mass a satisfying assignment and half its complement; each literal item is used by exactly half the population, and welfare is positive. If it is unsatisfiable, every bundle has value zero. The finite counterpart uses two identical bidders and one copy of each item, assigning the satisfying bundle and its complement. Thus the same item-driven hardness is present in the discrete WDP; it is not created by population multiplicity.

The continuous LP and its dual still generate useful questions: which restricted valuation classes give tractable pricing, can Theorem 1’s MIP help solve those pricing instances, and how does the continuous optimum compare with the integer high-multiplicity version as \(n\) grows? These are questions about the underlying allocation problem, rather than about making outcomes or probabilities continuous.

The soft spot is the regime evidence. The paper’s experiments have only 7–10 bidders, and its authors model their preferences with distinct networks because they are usually idiosyncratic. A large population sharing a small number of exact valuation types is a credible procurement regime, but it is an extension of their experimental setting. The mirror is strongest as a continuation of the WDP itself; it should not be presented as a continuous version of every part of their ICA.