| paper | Approval-Based Voting with Mixed Goods |
| authors | — |
| venue | AAAI 2023 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.11
statement extracted from the paper’s text layer
Given mixed divisible and indivisible goods, capacity alpha, finitely many approval types with rational masses, compute the deterministic mass-Generalized-MES allocation and establish its mass-EJR-1 guarantee in time polynomial in the type count, resource description, and encoding length.
A finite-type society has rational masses \(\mu_t\) over complete approval bundles (cake intervals and indivisible goods). The allocation remains an integral choice of indivisible goods plus a measurable cake piece of total size at most \(\alpha\); each type has per-agent budget \(\alpha\), aggregate budget \(\mu_t \alpha\), and pays the Generalized MES affordability rate. The computational task is to batch identical types, compute all affordability events and the resulting allocation, and verify mass-EJR-1.
The mirror may be computationally routine because it is exact batching of duplicate approval types rather than a new optimization or separation problem.
fatal: False
The mirror covers Theorem 3.11 and its Generalized MES computation and EJR-1 guarantee; it leaves the existence, proportionality-degree, and Generalized PAV or EJR-M results untreated.
My lead, and the only anchor I would use, is Theorem 3.11. It is proved in this paper and states that Generalized MES satisfies EJR-1 and can be implemented in polynomial time. The theorem is genuinely computational; the surrounding EJR-M and proportionality results are mainly existence or axiomatic statements, so I would not pad the case with them.
The natural mirror keeps the mixed resource exactly as the paper defines it and continuizes only the population. Let the resource be a cake \(C=[0,c]\), indivisible goods \(G=\{g_1,\ldots,g_m\}\), and capacity \(\alpha\). A type \(t\) is a complete approval bundle \(R_t=(C_t,G_t)\), where \(C_t\) is a finite union of cake intervals and \(G_t\subseteq G\). The society is a rational distribution \(\mu\) over \(\tau\) such types. Its mass \(\mu_t\) is the fraction of residents with that exact approval bundle.
A feasible decision is still an ordinary mixed-goods allocation \(A=(C_A,G_A)\), with \(G_A\) integral and \(\ell(C_A)+|G_A|\leq\alpha\). Type \(t\)'s utility is
\[ u_t(A)=\ell(C_t\cap C_A)+|G_t\cap G_A|. \]
Thus the cake remains divisible and the goods remain indivisible; the only new continuous object is the population distribution \(\mu\).
To preserve the paper’s EJR semantics exactly, represent a possible coalition by a submass vector \(z\), with \(0\leq z_t\leq\mu_t\). Its mass is \(|z|=\sum_t z_t\), and its common approval bundle is the intersection of the approval bundles of all types with \(z_t>0\). For \(\theta>0\), call \(z\) \(\theta\)-cohesive if
\[ |z|\geq \theta/\alpha \]
and its common approved resource has size at least \(\theta\). The allocation \(A\) satisfies mass-EJR-1 if every such coalition contains some positive submass of a type \(r\) with
\[ u_r(A)>\theta-1. \]
This is not an invented aggregate-welfare relaxation: when \(\mu_t=n_t/n\), choosing \(z_t\) corresponds exactly to choosing \(n_t'\) of the \(n_t\) finite voters of type \(t\). The condition is therefore the high-multiplicity form of the paper’s Definition 3.1.
The named computational problem I would propose is Mass-Generalized-MES-EJR-1:
Given \(C,G,\alpha\), the finite approval-type list \((R_t)_{t\in T}\), and rational masses \(\mu\), compute a feasible allocation \(A\) produced by the mass version of Generalized MES, with the guarantee that \(A\) satisfies mass-EJR-1.
The mass version is exact, not merely analogous. Give every type initially a per-agent budget \(\alpha\), so its cohort has total budget \(\alpha\mu_t\). On a good \(g\), a candidate payment rate \(\rho\) is affordable when
\[ \sum_{t:g\in G_t}\mu_t\min(b_t,\rho)\geq 1, \]
where \(b_t\) is the remaining per-agent budget of type \(t\). On a cake segment of length \(x\) approved by the relevant types, affordability is determined by
\[ \sum_t \mu_t\min(b_t,\rho x)\geq x. \]
The rule selects the affordable good or cake segment with minimum \(\rho\), charges each participating type \(\min(b_t,\rho)\) per capita for a good or \(\min(b_t,\rho x)\) for a segment, removes types whose budget is exhausted, and continues with deterministic tie-breaking. This is precisely the paper’s Generalized MES after multiplying all individual budgets and prices by \(n\).
I would expect this mirror to be Class A. Types with identical approval bundles always have identical budgets, payments, and removal times, so the finite procedure can be batched by type. A rational finite society with masses \(n_t/n\) expands to \(n_t\) voters and gives the same allocation; conversely, a repeated-voter election compresses to \(\mu\). The relevant implementation target is therefore polynomial in \(m\), \(\tau\), the number of approval-interval endpoints, and the bit length of the rational data—not in the denominator \(n\). The affordability equations are piecewise-linear weighted sums, so an event-based implementation should aggregate all identical types and solve only the resulting rational rate equations.
The regime is credible in the paper’s own applications: a city, university, platform, or public agency selects a package of whole projects, whole files, indivisible time slots, and divisible capacity. Millions of residents or users may fall into a few dozen or few hundred standardized approval profiles. A type might be, for example, residents approving a particular set of infrastructure projects and a set of time intervals for a public facility. The high-multiplicity assumption is not that named individuals have identical identities; it is that the problem only uses their approval bundle, and many agents share that complete bundle.
The authors should recognize this as their problem. The mirror preserves the same resource, the same approval utilities, the same capacity parameter, the same budget mechanism, and the same EJR-1 threshold. It does not fractionalize committees, replace goods by expected allocations, or turn representation into average utility. It simply asks whether their polynomial-time MES result survives when the population is supplied as a distribution over repeated approval types.
The scope is deliberately narrow: this covers the algorithmic content of Theorem 3.11. I would not claim to mirror the paper’s full contribution. Theorem 3.8 gives existence of an EJR-M allocation but not a polynomial-time algorithm; that becomes a useful follow-up question rather than a second anchor. Likewise, the proportionality-degree theorems and the negative results for Generalized PAV and Generalized MES are not needed here.
The main weakness is that this may look like weighted-voter compression rather than a qualitatively new continuous problem. The paper already contains divisible goods, and its original MES algorithm is polynomial in the explicitly listed voters. The positive claim therefore depends on accepting high multiplicity as the relevant computational regime: the gain is dependence on \(\tau\) and encoding length rather than on the expanded electorate. If the standard demands a continuum-specific phenomenon beyond exact batching of duplicates, this case is modest. But under the programme’s stated definition of continuization, it is a faithful Class-A mirror, and it generates substantive next questions: whether EJR-M can be computed in compressed form, whether mass-EJR-1 can be efficiently verified, and whether the paper’s proportionality guarantees survive this population-level formulation.
The strongest negative case is that Theorem 3.11 is a poor anchor for ChoCo because its computation is already completely insensitive to population multiplicity. Generalized MES only uses agents through their approval sets, budgets, and aggregate affordability sums. Agents with the same approval type have identical budgets, payments, and removal times. Replacing them by a mass therefore merely collects repeated summands in the paper’s existing algorithm.
That makes the proponent’s finite-type mirror exact, but also almost mechanical. For rational masses, expanding each mass into repeated voters gives precisely the same allocation and EJR-1 guarantee; batching the repeated voters gives the proposed weighted algorithm. The improvement from dependence on \(n\) to dependence on \(\tau\) and encoding length is a succinct-input implementation observation, not a new optimization problem, separation problem, or complexity boundary. The rule’s homogeneity under cloning is already doing all the work.
A more ambitious mirror does not rescue the case cleanly. One could let approval bundles vary continuously—for example, by giving agents continuously varying endpoints for the cake intervals. But then the paper’s finite approval-incidence structure disappears. There may be infinitely many breakpoints, and computing the affordability events requires a representation and integration problem that is external to Theorem 3.11. EJR-1 also needs a new measure-theoretic interpretation: an existential “some agent” condition may be satisfied by a null set, while requiring a positive-mass set changes the axiom. If one restricts the model enough to avoid these problems, one returns to finitely many approval types and the same batching exercise.
Nor can the cake component count as an independent continuous mirror: it is continuity of the resource, not of the society, and is explicitly outside ChoCo’s scope. Existing cake-sharing results likewise do not answer the population-continuization question.
This is nevertheless a weak negative case. The proposed finite-type model is natural—public projects, facilities, and mixed resources can easily attract millions of users with a small number of approval profiles—and its mass-EJR-1 definition is genuinely equivalent to the paper’s finite version on rational instances. The theorem is also unmistakably computational. Thus “the answer is just a weighted restatement” is not, under the programme’s rules, a decisive objection: high-multiplicity compression is itself admissible. I cannot honestly defeat this anchor universally. At most, I would argue that it is a modest, probably routine Class-A mirror rather than a high-value target for the programme.
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.