| paper | Mechanism design for fair division: allocating divisible items without payments |
| authors | R. Cole, Vasilis Gkatzelis, G. Goel |
| venue | SIGECOM 2013 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Lemma 3.12
statement extracted from the paper’s text layer
Given divisible resources, a finite type set \(T\), rational masses \(\mu_t\), weights \(b_t\), per-capita capacities \(q_j\), and concave degree-one homogeneous valuation functions \(v_t\), compute a feasible type-level allocation \(x_t\) maximizing \(\sum_t \mu_t b_t\log v_t(x_t)\), or an \(\epsilon\)-approximation to its optimum, and classify the complexity in \(m\), \(|T|\), input length, and \(\log(1/\epsilon)\).
A continuum of agents is represented by type masses \(\mu_t\); every unit of type \(t\) receives bundle \(x_t\), resources satisfy \(\sum_t\mu_t x_{tj}\le q_j\), and the objective is \(G_\mu(x)=\exp(\sum_t\mu_t b_t\log v_t(x_t))\).
After the substitution \(y_t=\mu_t x_t\), the mass vector only changes weights and resource variables, so the mirror may be an exact compression of the paper's existing weighted PF program rather than a population-driven computational phenomenon.
fatal: False
The mirror covers Lemma 3.12 and the approximate PF subroutine used by the Partial Allocation mechanism; it leaves individual truthfulness, finite-agent externality guarantees, impossibility bounds, envy-freeness, and the Strong Demand Matching mechanism untouched.
The strongest honest mirror is a high-multiplicity version of the paper’s proportional-fairness allocation problem, not an attempted mirror of its entire truthful-mechanism result.
My anchor is Lemma 3.12, proved in this paper (with standard convex-programming machinery from Nemirovski cited in the proof). It states:
For concave, homogeneous valuation functions of degree one, there is an algorithm that computes a feasible allocation \(\bar{x}\) in time polynomial in the problem size and \(\log(1/\epsilon)\), satisfying
\(\prod_i [v_i(\bar{x})]^{b_i} \ge (1-\epsilon)\prod_i [v_i(x^*)]^{b_i}\),
where \(x^*\) is a proportionally fair allocation.
This is a genuine computational result: the paper’s Partial Allocation mechanism requires several PF allocations, and Lemma 3.12 is what makes approximate computation of those allocations polynomial-time. The paper contains no named NP-hardness result, so there is no honest hardness anchor to prefer here.
I would call the mirror PF-Mass\(_\infty\).
An instance consists of \(m\) divisible resource types with per-capita capacities \(q_1,\ldots,q_m\), and a finite set \(T\) of bidder types. Type \(t\) has mass \(\mu_t\), where \(\mu_t\ge 0\) and \(\sum_t\mu_t=1\), a weight \(b_t\), and a concave homogeneous degree-one valuation function \(v_t:\mathbb{R}_+^m\to\mathbb{R}_+\). For example, \(v_t(x)=\sum_j a_{tj}x_j\) for additive valuations, or \(v_t(x)=\min_j x_j/a_{tj}\) for Leontief valuations.
The mass represents a very large population of otherwise indistinguishable agents: \(N\mu_t\) agents have type \(t\), with \(N\) enormous and \(|T|=\tau\) fixed or moderate. A natural setting is a cloud or network resource pool with millions of jobs belonging to a small number of service classes. A type records everything relevant to the allocation problem: its valuation function and priority weight.
The decision variable is one bundle \(x_t\in\mathbb{R}_+^m\) per type, interpreted as the bundle allocated to every unit of type-\(t\) mass. Feasibility requires \(\sum_t\mu_t x_{tj}\le q_j\) for every resource \(j\). The objective is the continuous PF objective \(G_\mu(x)=\exp\!\left(\sum_t\mu_tb_t\log v_t(x_t)\right)\). The problem asks for a feasible allocation \(x\) such that \(G_\mu(x)\ge(1-\epsilon)G_\mu(x^*)\), where \(x^*\) maximizes \(G_\mu\). A valid solution is the list of type-level bundles, together with an \(\epsilon\)-approximation certificate or dual certificate.
This is genuinely a population continuization. The paper already makes the *outcome* divisible, so divisibility itself is not the new object. The new object is the society: the individual bidder list is replaced by a distribution \(\mu\) over finitely many bidder types. The per-capita capacities are the natural normalization. With \(N\mu_t\) discrete bidders and total capacity \(Nq_j\), the finite PF program is exactly the replicated version of this one; homogeneity means that the common scaling of capacities changes utility units but not the PF allocation structure.
I expect PF-Mass\(_\infty\) to be Class A — tractable. Its logarithmic formulation is the convex program \(\max \sum_t\mu_tb_t\log u_t\), subject to \(u_t\le v_t(x_t)\), \(x_t\ge0\), and \(\sum_t\mu_tx_{tj}\le q_j\). For additive and Leontief valuations this has an explicit polynomial-size formulation. More generally, with an appropriate evaluation or separation oracle for the concave valuation functions, standard convex optimization should give running time polynomial in \(m\), \(\tau\), the encoding length of \(\mu,q,b\), and \(\log(1/\epsilon)\), independent of \(N\) except through the bit-length of its multiplicities.
The paper’s authors should recognize this as their problem: it is precisely their PF allocation subproblem after grouping identical bidders. It preserves their valuation classes, their resource constraints, their PF objective, and their approximation question. It is not a story invented merely to make the optimization easy.
This mirror covers Lemma 3.12 and the computational core used by the Partial Allocation mechanism. It does not claim to mirror Theorem 3.2, Theorem 3.4, or Theorem 3.6. Those results concern individual truthfulness and finite-agent strategic deviations. In a continuum, one must specify carefully whether a unilateral deviation by a measure-zero agent can change only that agent’s bundle, the aggregate type distribution, or neither. The finite leave-one-bidder argument does not transfer automatically. In particular, an infinitesimal agent has no aggregate externality, but that alone does not make the PF allocation individually truthful.
That is my weakest point: this is a strong mirror of the paper’s named computational allocation result, but not of its full mechanism-design contribution. The natural next question is whether PF-Mass\(_\infty\) admits a truthful no-payment implementation under a principled continuum incentive model, and whether the finite impossibility of Theorem 3.6 survives when the obstruction is driven by individual bidders rather than by population multiplicity.
The proponent has identified the strongest possible mirror, but it is also where the negative case is weakest. The objection cannot be that PF-Mass\(_\infty\) is ill-defined: it is sensible, and the paper’s valuation classes survive grouping.
The stronger objection is that Lemma 3.12 does not contain a population-dependent computational problem to continuize. Its proposed mirror is algebraically the same weighted proportional-fairness program already present in the paper. Writing \(y_t=\mu_t x_t\), homogeneity gives
\[ \sum_t \mu_t b_t \log v_t(x_t) = \sum_t \mu_t b_t \log v_t(y_t) -\sum_t \mu_t b_t\log\mu_t, \]
subject to \(\sum_t y_t\le q\). The second term is constant, so the optimizer is simply a weighted PF program with weights \(w_t=\mu_t b_t\). Scaling all \(w_t\) by a common factor handles the paper’s convention \(b_i\ge1\). Thus \(\mu\) is not a new population object affecting the optimization; it is just a reparameterization of the weights and resource variables in the original convex program.
This remains true for the best richer version of the mirror. If agents of one type receive different bundles, the natural continuum objective is bounded by the equal-bundle solution through Jensen’s inequality, because \(\log v_t\) is concave:
\[ \int \log v_t(x)\,d\lambda_t(x) \le \log v_t\!\left(\int x\,d\lambda_t(x)\right). \]
So allowing measurable allocations, lotteries, or within-type heterogeneity adds no new optimum for the stated valuation class. If instead one uses an actually infinite type space, the problem ceases to have a canonical finite computational input: its difficulty depends on how the distribution and valuation field are represented, and arbitrary density or integration oracles can encode unrelated hardness. The finite-type version is the only clean one, but that version collapses to the weighted program above.
The same collapse is visible at the high-multiplicity level. For rational \(\mu_t\), the instance is exactly a finite replicated election with \(N\mu_t\) identical bidders and capacity \(Nq\). The paper’s PF formulation already permits weighted bidders and divisible allocations, so the proposed algorithm is obtained by applying the paper’s convex-programming argument to the type representatives. This is useful input compression, but not a new continuous-population computational phenomenon.
Trying to preserve the paper’s distinctive mechanism-design content fares worse. The Partial Allocation mechanism relies on removing bidder \(i\) and measuring the resulting externality. In a nonatomic society, removing one agent changes neither \(\mu\) nor the PF allocation. Truthfulness therefore becomes either vacuous for individual deviations or must be replaced by a positive-mass coalition/type-reporting concept. That would be a new mechanism-design problem, not a continuous mirror of the paper’s theorem.
Accordingly, Lemma 3.12 is a genuine computational result, so the negative case is not decisive. If the programme counts exact high-multiplicity compression of an already weighted convex program as worthwhile, PF-Mass\(_\infty\) should survive. The best case against it is narrower: the paper’s only plausible anchor is already population-insensitive, and every attempt to make the population axis computationally substantive either reduces to the same program or changes the mechanism-design problem beyond recognition.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.