d4-conf-ijcai-2022-0515

The strongest honest case rests on one anchor: Theorem 1, proved in this paper (Appendix B.2). It is a formulation result rather than a complexity classification, but the paper uses the resulting MIPs in its allocation procedures, so it qualifies as an anchor. In full, it says that for bidders with \(k\)-Fourier-sparse value approximations, the Fourier-transform-based winner determination problem has an equivalent MIP. The MIP maximizes \(\sum_i\langle\phi_{\tilde v_i}|_{S_i},\alpha_i\rangle\), with \(a\in F\), binary \(\beta_i\in\{0,1\}^k\), and one set of transform-specific constraints for each bidder. For FT3 those are \(\alpha_i\ge 1_k-W_i(1_m-a_i)\), \(\alpha_i\le 1_k-W_i(1_m-a_i)+C\beta_i\), and \(0_k\le\alpha_i\le C(1_k-\beta_i)\). For FT4 they replace \(W_i(1_m-a_i)\) with \(W_i a_i\). For WHT they are \(\alpha_i=-2\beta_i+1_k\), \(\beta_i=W_i a_i-2\gamma_i\), and \(\gamma_i\in\mathbb Z^k\). Here \(C>0\) exists so that the selected formulation is equivalent to FT-WDP. I rely on the WHT version.

My mirror is WHT Type-Mass Winner Determination. The input is \(m\) item categories, a finite set \(\mathcal T\) of \(\tau\) buyer types, rational masses \(\mu_t\) summing to one, a rational per-capita supply \(q_j\) for each category \(j\), and for each type a WHT-sparse approximation \(\tilde v_t\) specified by its support and coefficients. A type means agents with the same complete reported value function over bundles. The question is to find an optimal allocation of type mass among integral bundles \(x\in\{0,1\}^m\). Let \(z_{t,x}\) be the mass of type \(t\) assigned bundle \(x\). The task is to maximize \(\sum_{t\in\mathcal T}\sum_{x\in\{0,1\}^m}z_{t,x}\tilde v_t(x)\), subject to \(\sum_x z_{t,x}=\mu_t\) for each type, \(\sum_{t,x}x_jz_{t,x}\le q_j\) for each category, and \(z_{t,x}\ge0\). A solution is an optimal set of such masses. Each agent still gets an integral bundle; only the type-level allocation is fractional. The succinct input size is governed by \(m,\tau\), the total Fourier support size, and the bit length \(L\), while the direct LP has exponentially many bundle variables.

A plausible regime is a recurring market with many buyers and replicated stocks of standardized license or service categories. For example, firms could fall into a modest number of classes with exactly the same reported bundle values, while the number of firms is in the thousands and the stock of each category scales with the market. Then mass is the share of each buyer class, and \(q_j\) is the stock per buyer. In a finite market of \(N\) buyers, \(N\mu_t\) agents have type \(t\) and there are \(Nq_j\) units of category \(j\), when those counts are integral. This keeps the paper’s bundle-value welfare objective intact while making the population genuinely high-multiplicity.

The authors should recognize this as their FT-WDP with repeated buyer types and per-capita supplies: the bundle choices, value functions, Fourier representation, and welfare objective remain. The mirror does not relax individual bundles or restrict valuations to make the question easy. It covers Theorem 1’s winner-determination problem and its use as an allocation subroutine; it does not claim to continuize the paper’s query-learning process, VCG payments, or experimental comparisons.

I expect hardness transfers for this unrestricted mirror. For a graph \(G=(V,E)\), take one type and use its value for bundle \(x\) to be the number of edges crossing the cut represented by \(x\). This is WHT-sparse: each edge contributes \(\tfrac12(1-\chi_{\{u,v\}}(x))\), so the support has at most \(|E|+1\) coefficients. Set every category’s per-capita supply to \(\tfrac12\). Half the mass can receive a maximum-cut bundle and half its complement; this meets every supply constraint and achieves the maximum cut value. No allocation can do better, since every bundle’s value is at most that value. Thus solving this continuous problem exactly solves Max-Cut. The same construction works with an even number of identical discrete buyers and half as many units of each category, so the hardness comes from bundle choices in \(m\), not from population multiplicity. In the LP’s dual, this obstruction appears as pricing: maximize \(\tilde v_t(x)-p\cdot x\) over bundles. WHT sparsity alone does not make that optimization easy.

That leaves useful further questions: which restrictions on Fourier interactions make pricing polynomial, whether bounded structural parameters yield FPT algorithms, and how well finite markets with many copies of each type approximate the mass-allocation optimum. The weakest point is the market modification: the paper studies a small number of bidders competing for single-copy items, whereas this mirror scales stock with population and assumes exact repeated value types. That is a real change in regime, though it is the kind of co-modification the continuous-population programme permits. It is also why I would treat this as a credible mirror of one computational core, not as a continuization of the whole paper.