| paper | Computing a small agreeable set of indivisible items |
| authors | Pasin Manurangsi, Warut Suksompong |
| venue | AI 2019 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), with polynomially many comparison-oracle queries, by the supplied three-player theorem. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given an item set \(S\), a rational distribution \(\mu\in\mathbb{Q}_{\ge 0}^3\) with \(\sum_j\mu_j=1\), and three complete responsive preference types supplied by comparison oracles, find an integral subset \(T\subseteq S\) such that \(T\succeq_j S\setminus T\) for every \(j\) with \(\mu_j>0\), and \(|T|\le \lceil m/2\rceil+1\).
The society is a distribution \(\mu\) over at most three responsive preference types; the decision variable is an indivisible subset \(T\subseteq S\), with objective to find a universally agreeable \(T\) of minimum or certified roughly-half cardinality. The exact unanimity constraint depends on \(\mu\) through its positive support.
Exact unanimity gives every positive-mass type a veto, so the instance can be compressed to representative preference constraints and has no mass-sensitive optimization content.
fatal: False
The mirror covers Theorem 3's three-type algorithmic bound and Theorem 1's two-type necessary-agreeability algorithm. Theorem 2's existence-only bound and the paper's other results are not independently computational anchors; weighted or \(1-\varepsilon\) satisfaction variants remain new extensions.
The strongest honest positive case is a Class A mirror of Theorem 3, with Theorem 1 as a useful secondary anchor. The paper has no named NP-hardness result; its future-work suggestions about possible TFNP hardness do not qualify as anchors.
The natural regime is a large organization choosing one common, indivisible kit of items: for example, an emergency-response or field-operation kit. There may be \(N\) thousands of participating units, but only three stable preference types, corresponding to operational roles. All units of a type have the same responsive preference over bundles. The type masses are \(\mu_1,\mu_2,\mu_3\), with \(N\mu_j\) units of type \(j\). The common decision is still one integral subset \(T\subseteq S\); the population, not the items, is continuous.
My lead problem is Three-Type Common-Agreeability\(_\infty\). An instance consists of:
Define the satisfied population mass of a subset \(T\) by
\[
\operatorname{sat}_\mu(T)
=
\sum_{j=1}^3
\mu_j\mathbf{1}\!\left[T\succeq_j S\setminus T\right].
\]
The task is to output an integral subset \(T\subseteq S\) with
\[
\operatorname{sat}_\mu(T)=1
\qquad\text{and}\qquad
|T|\le \left\lceil\frac m2\right\rceil+1.
\]
The associated optimization problem minimizes \(|T|\) subject to \(\operatorname{sat}_\mu(T)=1\); the anchored version asks for the paper’s certified roughly-half-size solution.
This is exactly the population version of the paper’s common-decision problem: every positive-mass type must weakly prefer the selected subset to its complement. For rational \(\mu\), multiplying by a common denominator produces a finite instance with many duplicated players. Conversely, any three-player instance embeds by taking, for example, \(\mu=(1/3,1/3,1/3)\). No item becomes divisible, and there is no fractional allocation of \(T\); only the electorate is represented by masses.
The anchor is Theorem 3, proved in this paper. It states in full that, for three players with responsive preferences over \(S\), there always exists an agreeable subset of size at most \(\lceil m/2\rceil+1\); that this bound is tight for some responsive preferences; and that a polynomial-time algorithm, using only polynomially many preference-oracle queries, finds such a subset. Therefore the continuous problem above is expected to be tractable for three positive-mass types, in oracle-polynomial time, independently of \(N\). The tight examples also survive: replicating each of the three preference types arbitrarily many times does not permit a smaller common subset.
A secondary, cleaner mirror is Two-Type Necessary-Agreeability\(_\infty\), anchored by Theorem 1, also proved here. Its types are rankings of the individual items. Given two positive-mass ranking types, find \(T\subseteq S\) with
\[
|T|\le \left\lceil\frac{m+1}{2}\right\rceil
\]
such that, for each represented ranking, \(T\) is agreeable under every responsive preference consistent with that ranking. Theorem 1 says that such a set always exists, that the bound is tight, and that a polynomial-time algorithm finds it using only the two singleton-item rankings. This is also a Class A mirror. It is slightly less direct than Theorem 3 because “necessary” agreeability quantifies over possible bundle preferences, but it is attractive as a high-multiplicity model with a very compact type description.
The authors should recognize these as their problems in a continuous population setting. The universal requirement is unchanged: every player, now every unit of positive-mass type, must accept the common subset. The scenario is not a claim that every committee has three preferences; it is a specific high-multiplicity regime in which many role-identical participants jointly choose one discrete bundle. This is precisely the kind of regime in which replacing named players by type masses is sensible.
The main weakness is that, under the exact unanimity condition \(\operatorname{sat}_\mu(T)=1\), the numerical values of the positive masses do not affect feasibility—only their support does. Thus this is a genuine high-multiplicity quotient, but not yet a strongly mass-sensitive optimization problem. The oracle representation is a second limitation. I would not oversell this as showing that a discrete hardness result dissolves: the paper supplies no hardness anchor, and the mirror is essentially a tractable fixed-\(\tau\) population regime.
It nevertheless generates worthwhile continuized questions: whether the bound \(\min(\lceil(m+\tau-1)/2\rceil,m)\) from Theorem 2 can be found efficiently when the number \(\tau\) of positive-mass types is part of the input; whether one can maximize \(\operatorname{sat}_\mu(T)\) subject to a smaller size bound; and what happens when only \(1-\varepsilon\) of the population must be agreeable. Those variants make the masses computationally substantive, while the exact three-type problem above is the strongest mirror directly supported by a named algorithmic theorem in the paper.
The strongest objection is that the proposed population variable disappears from the problem.
For any subset \(T\),
\[ \operatorname{sat}_{\mu}(T)=1 \quad\Longleftrightarrow\quad T\succeq_t S\setminus T \text{ for every }t\text{ with }\mu_t>0. \]
Thus two distributions with the same support induce exactly the same feasible subsets, regardless of their masses. A type occupying \(0.001\) of the population has exactly the same veto power as a type occupying \(0.999\). Duplicating players therefore contributes no numerical information: one can delete all duplicates before solving the problem.
This defeats the proposed Theorem 3 mirror. The emergency-kit scenario is a plausible high-multiplicity story, and the common subset remains indivisible, so the model is not formally nonsensical. But its continuous instance is simply three preference constraints, with the population distribution serving only to say which constraints are present. The theorem’s oracle algorithm is unchanged after replacing thousands of role-identical units by one representative of each role. Its tight examples also merely show that duplicating the same three players does not help. That is support compression, not a computational problem over a continuous society.
Theorem 1 is weaker still. Its “necessary agreeability” quantifies over all responsive bundle preferences consistent with a singleton ranking. The population masses do not enter either that quantifier or the resulting algorithm. The proposed two-type problem is exactly the finite two-ranking problem with duplicate players removed. Calling the two rankings “types” does not make the society a continuous object in any operative sense.
The same problem affects the suggested extension based on Theorem 2. Replacing \(n\) players by \(\tau\) positive-mass types gives the same finite support problem with \(n=\tau\). If \(\tau\) is fixed, this is merely a fixed-number-of-types generalization. If \(\tau\) grows, the computation is driven by the number of distinct preference relations, not by population multiplicity. In neither case does high multiplicity create the kind of mass-based optimization problem the continuization programme is meant to expose.
A better proposal would make mass matter by asking for
\[ \operatorname{sat}_{\mu}(T)\ge 1-\varepsilon \]
or by maximizing \(\operatorname{sat}_{\mu}(T)\) subject to a smaller cardinality bound. But that is no longer the paper’s common-agreeability problem. The paper’s defining requirement is that every player weakly prefer the chosen set to its complement. Replacing that universal constraint by a population-weighted objective changes the fairness criterion from veto-based individual protection to utilitarian satisfaction. Likewise, replacing ordinal preferences by an averaged cardinal welfare objective would require information absent from the paper. These may be worthwhile new problems, but they are not continuous mirrors anchored by Theorems 1 or 3.
The instability is also conceptually undesirable: a type has full influence for every positive mass and loses all influence at mass zero. There is no meaningful proportional effect in between. Any repair—almost-everywhere agreeability, an \(\varepsilon\)-tolerance, or weighted welfare—introduces a new social objective rather than revealing a continuous form already present in the paper.
The negative case is therefore strong against the exact anchors: they produce a duplicated-constraint model, not a genuinely mass-sensitive continuous society. It is not airtight against every imaginable reformulation, since a weighted-satisfaction problem could be a legitimate follow-up. But that would be a new computational social-choice problem, not a worthwhile continuization of the paper’s named results.
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.