| paper | d4-conf-sagt-2023-0015 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 7 gives a lower bound on the price-of-equity ratio, and Theorem 5 gives an equality for a balanced subclass; neither states a computational guarantee, hardness result, or computation-dependent formulation. The proposed mass-allocation tasks are coherent extensions, but they do not make either named theorem a computational result, so bit (a) fails.
fails bit a — no named computational result to mirror
The proposals cover Theorem 7's two-type binary-submodular lower-bound construction and Theorem 5's balanced binary-additive identity; they leave the other price-of-equity bounds, the broader \(p\)-mean results, and the chores discussion aside.
The paper has no named computational-complexity result: none of its numbered theorems says that an allocation problem is in \(P\), NP-hard, fixed-parameter tractable, or similar. Theorems 2–8 give bounds on the price of equity, and Theorem 5 gives an exact welfare identity. So there is no anchor that meets your strict complexity-result criterion. The strongest honest positive case is a continuous mirror of the paper’s quantitative problem, led by Theorem 7. I’ll use Theorems 7 and 5 as quantitative anchors, without presenting either as a complexity result.
The mirror has population mass \(\mu_t\) on each of finitely many complete valuation types \(t\), with \(\sum_t\mu_t=1\). It also has a finite catalogue \(G\) of good types, each with rational supply \(q_g\) per unit population. An allocation is a set of masses \(x_{t,B}\): mass \(x_{t,B}\) of type \(t\) receives the integral bundle \(B\subseteq G\). It must satisfy \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=q_g\). Thus goods are indivisible within each person’s bundle, while the population and supply are represented by mass.
For bundles \(B,B'\) appearing with positive mass, require EQ1 in the paper’s sense: for every ordered pair of assigned bundles \((t,B),(t',B')\) with \(B'\ne\varnothing\), some \(g\in B'\) satisfies \(u_t(B)\ge u_{t'}(B'\setminus\{g\})\). The underlying computational problem is to find both the utilitarian-welfare-maximizing allocation and the EQ1-constrained utilitarian-welfare-maximizing allocation, then report their ratio. Inputs can give binary additive valuations or explicit matroid-rank valuations, with rational \(\mu\) and \(q\).
My lead is Theorem 7, proved in this paper. It states that for binary submodular valuations, the utilitarian price of equity is at least \(n/6\), even with just two agent types. In the paper’s construction, the two types have matroid-rank valuations over \(k+1\) groups of \(k\) goods: type 1 values the first group as \(k\) independent vectors and everything else at zero; type 2 sees each group as those same \(k\) independent vectors. There are \(k\) agents of each type, so \(n=2k\).
The continuous mirror keeps exactly those two types but sets \(\mu_1=\mu_2=1/2\). Give each of the \(k(k+1)\) goods supply \(1/(2k)\). Each type’s value for the full catalogue is \(k\). The unrestricted allocation has average welfare \((k+1)/2\): type 1 gets value \(1\) per person and type 2 gets value \(k\). The construction’s EQ1 argument bounds average EQ1 welfare by \(3/2\). It therefore yields a price of equity at least \((k+1)/3\), in particular at least \(k/3\), matching the paper’s \(n/6\) lower bound after normalization.
This is a credible high-multiplicity regime: two large cohorts share exactly two valuation functions, and population mass is the honest unit. A plausible setting is allocation of slots or permits to two standardized cohorts with different matroid-style eligibility across resource categories. The paper itself defines agent types by identical valuations and studies bounds in terms of their number, so its authors would likely recognize this population model. Existing type-based work supports the regime; it does not make a continuum mirror a collision.
The corresponding named question is: Two-Type Continuum Matroid-Rank Price of Equity. Given rational type masses and good supplies, and explicit binary matroid-rank valuations for two types, compute the two optimal mass allocations and their utilitarian price-of-equity ratio. The family above asks whether a two-type society can have a ratio growing with the per-capita rank and supply scale \(k\). The expected quantitative answer is yes: the Theorem 7 construction gives an \(\Omega(k)\) lower bound.
This is my strongest anchor because it shows a sharp, relevant limit: few types alone do not bound the price of equity. But that is a quantitative statement, not a complexity classification. Theorem 7 gives no basis for calling the allocation problem tractable, hardness-transferring, or continuum-specifically hard. The further questions are whether the lower bound is tight as a function of \(k\), whether any bound can depend only on the type count under additional restrictions, and how hard it is to compute an EQ1-optimal mass allocation.
A second, supporting anchor is Theorem 5, also proved in the paper. It says that for doubly normalized binary additive instances, the price of equity is exactly \(1\) for every \(p\le1\). Its continuous mirror restricts to additive types with \(\sum_g v_t(g)=W\) and balanced supply: \(\sum_t\mu_t v_t(g)=W_cq_g\) for each good type \(g\). The question is whether an EQ1 mass allocation can attain the unconstrained optimum for every \(p\le1\). A solution is an allocation distribution assigning mass to integral bundles, with equality between the EQ1-constrained and unrestricted optimum. This is plausible because the paper’s proof uses a bipartite matching / total-unimodularity decomposition; in the mass setting, a distribution over whole-bundle allocations is natural. I expect this balanced restriction to be tractable (Class A), though that is an inference from the proof, not a complexity result stated by the theorem.
The proposed mirrors cover the paper’s two-type binary-submodular utilitarian lower bound and its balanced binary-additive welfare identity. They do not claim to mirror the full family of \(p\)-mean bounds, all additive instances, or the chores discussion.
The weakest point is also the decisive qualification: Theorem 7’s growth in \(n\) becomes growth in the per-capita rank and supply parameter \(k\). It does not show that the price grows merely because a fixed continuum population is replicated. Theorem 5’s balanced result may also carry over through familiar matching machinery. So the positive case is that the paper supplies unusually clear, type-based quantitative questions for a continuous population model—not that it supplies the computational-complexity anchor the programme normally seeks.
The strongest objection is that this paper has no named computational-complexity result to continuize. Theorems 2–8 bound the price of equity or identify when it equals \(1\); none classifies an allocation problem by its running time or complexity. The proponent’s questions therefore add a new task—computing welfare-optimal and EQ1-optimal allocations in a mass model—to results that are quantitative, not computational. That task may be worthwhile, but it is not a mirror of a computational result in this paper.
Theorem 7 is the better of the two proposed anchors, but its \(\Omega(k)\) ratio is not a limit effect at fixed society structure. In the construction, \(n=2k\), while the matroid rank and goods catalogue also grow with \(k\). If those are held fixed and the population is replicated with per-capita supplies held fixed, the ratio does not grow with population size. The continuum version is still a coherent two-type allocation problem, but the lower bound motivates a question about rank and resource scale, not what continuizing the population changes.
Theorem 5 offers a cleaner mass model, but the proposed weighted balance condition needs care: the theorem assumes each *individual good* has the same number of valuers. With multiple copies per good type, that property concerns the fraction of population valuing each copy; it does not generally scale with the type’s total supply \(q_g\). A faithful equal-popularity version appears to inherit the paper’s bipartite matching and total-unimodularity argument, so it may be an immediate extension. A broader supply-weighted version would be a new hypothesis and problem, rather than a mirror established by Theorem 5.
The paper plainly has a sensible high-multiplicity regime: it explicitly studies repeated valuation types, and its results depend on their number. There is no honest objection based on identity dependence, vanishing utility, or “already continuous” prior art. So the negative case can establish that this is not already a ChoCo-style complexity paper, and that Theorem 7’s growth is not population growth alone. It cannot establish the universal claim that no worthwhile continuous mirror exists. In particular, the two-type EQ1 mass-allocation problem remains well-posed; defeating it would require a stronger argument than the paper’s lack of complexity theorems.
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.