d4-conf-sigecom-2003-0051

I would lead with Theorem 6, proved in this paper’s Appendix D. It says that, given two agents with known MAX-SUM-ALL read-once valuations, it is NP-hard to find an item allocation whose welfare is more than one half of the optimum. The proof reduces SAT with a gap: the constructed instance has optimum \(2\) if the formula is satisfiable and at most \(1\) otherwise. This is the paper’s clearest hardness anchor.

The most credible high-multiplicity setting is a large program distributing bundles of capacity-limited goods or service entitlements to many customers. Suppose customers fall into a small number \(\tau\) of repeated preference profiles—for example, standardized household or subscription profiles—and each profile’s read-once formula fully captures its members’ preferences, including the item values. The population may contain millions of customers while \(\tau\) is in the tens or hundreds. The available quantity of each good grows with the population. That makes the population the continuous object while retaining the paper’s welfare objective: allocate goods to maximize the sum of agents’ valuations.

Here is the problem I would hand to a prover, Continuous Read-Once Welfare Allocation. An instance gives \(n\) item categories, a support \(T\) of \(\tau\) MAX-SUM-ALL read-once valuation formulas \(v_t\) with rational leaf values, rational type masses \(\mu_t\ge 0\) summing to \(1\), and rational per-person supplies \(b_i\) for each item \(i\). A person still receives an integral bundle \(S\subseteq[n]\); the continuous variable represents how much mass of a type receives each bundle. Set \(x_{t,S}\) to that mass. The constraints and objective are

\[ \sum_{S\subseteq[n]}x_{t,S}=\mu_t \quad(t\in T),\qquad \sum_{t\in T}\sum_{S\ni i}x_{t,S}\le b_i \quad(i\in[n]),\qquad x_{t,S}\ge 0, \]

\[ \text{maximize}\quad \sum_{t\in T}\sum_{S\subseteq[n]}x_{t,S}v_t(S). \]

The requested solution is the exact optimal per-person welfare and a maximizing allocation, given as a finite list of bundles with their rational assigned masses. Its complexity should be measured in \(n,\tau\), the total formula size, and input bit length \(L\). The variables describe different people receiving different whole bundles; they do not give fractional bundles to individuals.

I expect this problem to be Class A: tractable. Its configuration LP has exponentially many bundle variables, but its pricing problem for type \(t\) at item prices \(p_i\ge0\) is \(\max_S(v_t(S)-\sum_{i\in S}p_i)\). The paper’s Theorem 4, proved here, supplies the relevant algorithmic tool: given one known MAX-SUM-ALL read-once valuation and one known additive valuation, a welfare-maximizing allocation can be found in polynomial time. Assigning the additive party the prices of the items it receives is equivalent to this pricing problem up to the constant \(\sum_i p_i\). Thus each type has polynomial-time pricing, and the LP’s dual can be solved by the standard optimization–separation machinery. The theorem’s role here is technical support for the single continuous problem, rather than a second anchor.

The connection to Theorem 6 is direct but does not preserve its hardness gap. Given its two agents with valuations \(f\) and \(g\), set \(\mu_f=\mu_g=1/2\) and \(b_i=1/2\) for every item. Any discrete split \(A,[n]\setminus A\) gives a feasible continuous allocation by assigning mass \(1/2\) of type \(f\) to \(A\) and mass \(1/2\) of type \(g\) to its complement; the continuous welfare is half the discrete welfare. But the continuum can distribute different bundles among members of the same type, so its optimum may be higher. The SAT gap therefore does not automatically transfer. That is the interesting question: the paper’s two-agent hardness may dissolve when the same social-welfare problem is posed for a high-multiplicity population.

The mirror covers Theorem 6’s welfare-allocation problem for read-once preferences, not the paper’s value-query elicitation results, approximate elicitation, or Toolbox-DNF allocation. It raises follow-on questions about rounding rational mass allocations to finite populations with bounded welfare loss, robustness to changes in type masses and supplies, and whether other preference classes also admit efficient pricing.

The weakest point is the change from two agents sharing a fixed set of single items to a large population sharing per-person supplies. That is a meaningful extension, not a literal limit of the theorem’s instance. I think the authors would recognize it because the underlying decision remains allocation of goods to agents to maximize the sum of their valuations, with the same read-once preferences. Still, the scenario must be defended as a real high-multiplicity market, and the continuous result should be presented as a new population version of their problem—not as a consequence of Theorem 6.