d4-conf-wine-2020-0017

The strongest positive mirror I see is a large marketplace in which many customers and suppliers recur in a relatively small number of supplier classes. A supplier’s type is the pair \(t=(v_t,q_t)\): her public attractiveness score and outside-option score. Customers remain identical, as in the paper. For \(N\) customers, suppose there are about \(\rho N\) suppliers, with fraction \(\mu_t\) of them in type \(t\), where \(\sum_t\mu_t=1\) and the support size \(\tau\) is much smaller than \(N\). A rental or hiring platform with many listings in a few score and acceptance tiers is a plausible regime. The paper itself motivates bounded recommendation pages, so take a fixed display cap \(K\), such as 20.

My lead anchor is Proposition 1, the proposition labeled prop:sequential_np_hard in the supplied text. It is proved in this paper: given finite customer and supplier sets, supplier scores \(v_j\), outside-option scores \(q_j\), and the paper’s two-stage MNL choices, choosing a menu for each customer to maximize expected matches is strongly NP-hard. The proof reduces from 3-Partition; the strong NP-completeness of 3-Partition is cited, while the reduction to assortment planning is proved here.

The continuous question I would hand to a prover is the Capped Fluid Sequential Assortment Problem. An instance gives a finite supplier-type set \(T\), rational masses \(\mu_t>0\) summing to 1, rational supplier-to-customer ratio \(\rho>0\), rational scores \(v_t>0,q_t\geq 0\), a fixed menu cap \(K\), and an additive accuracy target \(\epsilon>0\). Customer mass is normalized to 1; supplier mass of type \(t\) is \(\rho\mu_t\).

A menu pattern is a vector \(a\in\mathbb Z_{\geq0}^{\tau}\) with \(\sum_t a_t\leq K\), specifying how many suppliers of each type a customer sees. The decision is a distribution \(x_a\geq0\), \(\sum_a x_a=1\): mass \(x_a\) of customers receives that integral menu pattern. Thus individual menus remain discrete; only the population shares are fractional. Under the paper’s customer choice model, the probability a customer with pattern \(a\) chooses some supplier of type \(t\) is
\[ p_t(a)=\frac{a_t v_t}{1+\sum_s a_s v_s}. \]
Let \(y_t=\sum_a x_a p_t(a)\) be the customer mass choosing type \(t\). Spread these choices evenly across the \(\rho\mu_t\) supplier mass. In the large-market limit, the number of customers choosing a given supplier of type \(t\) is Poisson with mean \(\lambda_t=y_t/(\rho\mu_t)\). If \(X\) is Poisson with mean \(\lambda\), define
\[ G_q(\lambda)=\mathbb E[h_q(X)],\qquad h_q(0)=0,\quad h_q(r)=\frac{r}{r+q}\ \text{for }r\geq1. \]
This is exactly the supplier’s expected match probability under the paper’s second-stage choice rule, including \(q=0\). The problem is to output a menu distribution \(x\) whose expected matches per unit customer mass,
\[ \Phi(x)=\rho\sum_{t\in T}\mu_t G_{q_t}\!\left(\frac{y_t}{\rho\mu_t}\right), \]
are within \(\epsilon\) of the maximum. The limit comes from the original sequential choices: each supplier receives \(O(1/N)\) selection probability from each customer, so her incoming count converges to Poisson. Type-level symmetry makes balanced allocation natural; because match probability is concave in the number of requesters, spreading requests evenly is also the favorable arrangement.

I expect this mirror to be tractable (Class A) for fixed \(K\). The sequence \(h_q(r)\) is discretely concave, so its Poisson expectation \(G_q\) is concave in \(\lambda\). Since each \(y_t\) is linear in \(x\), maximizing \(\Phi\) over the simplex of menu shares is a concave maximization problem of the standard convex-optimization kind. There are \(\binom{\tau+K}{K}\) menu patterns, polynomial in \(\tau\) for fixed \(K\); an additive-\(\epsilon\) algorithm is therefore a concrete target. The population fractions replace the discrete partition choices that drive the 3-Partition reduction. In particular, that reduction’s yes-witnesses group items in triples, so a practical cap such as 20 retains the relevant menu shape while continuous customer and supplier masses remove item indivisibility.

This mirrors Proposition 1’s underlying objective—design menus under the same sequential MNL choices to maximize expected matches—not the paper’s approximation theorem or simulations. The main vulnerability is the display cap: the paper’s formal model permits arbitrary menu sizes, so a referee could regard the capped version as a constrained relative rather than the continuous form of the exact stated problem. I think the cap is defensible for the paper’s platform setting, but the unbounded-menu fluid problem should be treated as a further question, alongside finite-\(N\) convergence guarantees and extensions to multiple customer types.