d4-conf-wine-2024-0022

The strongest case is a narrow mirror of the paper’s linear one-sided Fisher Nash-bargaining model, LiF. The paper already allows fractional allocations, so that feature alone is not the continuization. The change is to make the population—and its supply of interchangeable goods—distributions over types rather than lists of named units.

A plausible regime is a large annual assignment of students to standardized housing or program places. There may be tens of thousands of students and places, but far fewer complete utility profiles and place categories, with many students and places in each category. A student type must specify their utility for every place category; students who differ in any parameter the model uses belong to different types. A place type groups places that are interchangeable to every student type. This is a scenario-specific claim, not a claim that matching markets generally have few types.

Call the mirror Continuous-Type LiF. An instance gives finite supports \(A_0\) of student types and \(G_0\) of place types; rational masses \(\alpha_a,\beta_g\geq 0\) with \(\sum_a\alpha_a=\sum_g\beta_g=1\); and rational utilities \(u_{ag}\). The masses are fractions of the population and of the total place supply. A feasible decision is a transport plan \(x_{ag}\geq 0\), where \(\sum_g x_{ag}=\alpha_a\) and \(\sum_a x_{ag}=\beta_g\). Type \(a\)’s per-person utility is \(v_a(x)=\sum_g u_{ag}x_{ag}/\alpha_a\). The question is to find a feasible plan maximizing \(F(x)=\sum_a\alpha_a\log v_a(x)\), or, for an approximation version, return a plan within \(\varepsilon\) of the optimum. The mass-weighted logarithm matters: it is the continuum form of summing individual log utilities, not a Nash product over the types themselves.

This is recognizably the paper’s underlying problem. In a finite replication with identical utility profiles and integral type counts, one can average an allocation over permutations of agents and places within each type. The averaged allocation remains feasible, gives every member of a student type the same expected utility, and does not reduce the concave Nash-welfare objective. Conversely, a type-level plan lifts to a fractional matching of the replicated units; the paper’s Birkhoff–von Neumann rounding then gives a lottery over integral assignments with the same expected utilities. Rational masses and plans can be represented by sufficiently large finite replications. The continuous instance therefore gives a high-multiplicity formulation of the same allocation question, while making support size rather than the number of named participants central.

My anchor is Theorem 18, proved in this paper. For LiF, under its normalization \(\max_j u_{ij}=1\) and \(\sum_j u_{ij}\geq 1/\kappa\) for every agent \(i\), the theorem says that Algorithm \(\ref{alg:fw_eg_mod}\) returns an allocation \(x\) whose quadratic-extension objective satisfies \(\psi(x^*)-\psi(x)\leq\varepsilon\) in \(O(n^3\kappa^2/\varepsilon)\) iterations, with \(O(n^3)\) time per iteration. Here \(\psi(x)=\sum_i\eta(u_i(x);1/(2\kappa n))\), and \(x^*\) is optimal for the modified program. Lemmas 16 and 17, also proved here, connect that computation back to the original Nash-welfare objective: the modified and original programs have the same optima, and a sufficiently small \(\psi\)-gap yields a correspondingly small gap in the original objective. This is an algorithmic anchor; the paper has no numbered in-paper hardness result for this market. Its introduction cites PPAD-completeness for the different HZ mechanism from prior work, which is not an anchor for LiF.

I expect Continuous-Type LiF to be Class A, tractable. Its feasible region is a transportation polytope and its objective is concave; its linear optimization step is a maximum-weight transport problem over the type supports. That suggests algorithms parameterized by \(\tau_A=|A_0|\), \(\tau_G=|G_0|\), input bit length \(L\), conditioning parameters, and requested accuracy. Theorem 18 does not itself prove that support-sensitive bound: its stated rate is for the paper’s finite, unit-mass-per-agent instance. Establishing the weighted type-mass version and its dependence on small positive masses is part of the proposed question, not a result I am attributing to the authors.

The mirror covers LiF and Theorem 18 only. It does not extend this claim to LiAD, SPLC utilities, two-sided markets, or the non-bipartite model. It also raises useful follow-ups: whether the finite and continuous optima admit an exact dictionary under rational replication; how to round type-level plans while preserving each type’s expected utility; and how the support-sensitive complexity changes with endowments or piecewise-linear utilities.

The weakest point is the type regime. In many real markets, cardinal utilities are individualized, so the number of complete utility types could approach the population size. This mirror is persuasive only in settings with a genuinely small menu of shared profiles and place categories. A second concern is that the original paper already has fractional outcomes, and its LiF algorithm is polynomial in the finite instance size. But those facts do not make its society continuous: the paper still lists individual agents and goods. In the proposed regime, mass is the population representation, type-level averages are the decision variables, and support size is the relevant scale.