Computing an Approximately Optimal Agreeable Set of Items

There is a defensible mirror here, strongest in the additive-utility part of the paper. I would present it as a Class B case: replacing a large population by a distribution over repeated utility types does not dissolve the item-selection hardness.

Take a finite item set \(S=\{x_1,\ldots,x_m\}\). A type \(t\) is a complete additive utility vector \(v_t=(v_t(x))_{x\in S}\), and the society is a rational distribution \(\mu\in\mathbb{Q}^{\tau}\). A common subset \(A\subseteq S\) is agreeable if every positive-mass type agrees with it:

\[ \mu_t>0\quad\Longrightarrow\quad \sum_{x\in A}v_t(x)\geq \sum_{x\in S\setminus A}v_t(x). \]

The main optimization problem, Continuous Minimum Agreeable Set, asks for an agreeable \(A\) minimizing \(|A|\). Items remain indivisible: every unit of population receives the same integral subset \(A\). Only the population is continuous.

This is a natural high-multiplicity regime for, say, a large organization choosing a common kit of equipment, software modules, or supplies for millions of employees or households. Individuals within a role or household category have the same utility vector, while the number of individuals in each category is represented by \(\mu_t\). For rational \(\mu\), multiplying by a common denominator gives exactly a finite election with \(N\mu_t\) agents of type \(t\). Conversely, every finite instance maps to such a distribution.

My lead anchor is Theorem 5. The paper proves here:

Even with two agents having additive utility functions, it is NP-hard to decide whether there exists an agreeable set of exactly \(m/2\) items.

The proof reduces Balanced 2-Partition: for numbers \(a_1,\ldots,a_m\), it creates items with utilities \(v_1(x_i)=a_i\) and \(v_2(x_i)=M-a_i\), where \(M=\sum_i a_i\). The theorem is proved in the paper, using the NP-hardness of Balanced 2-Partition established in its Appendix as Lemma 6.

The corresponding continuous question is Two-Type Continuous Half-Agreeability. The instance has \(m\) items, two utility types \(v_1,v_2\), and population masses \(\mu_1=\mu_2=1/2\). The question is whether there exists \(A\subseteq S\) with \(|A|=m/2\) satisfying

\[ v_1(A)\geq v_1(S\setminus A) \quad\text{and}\quad v_2(A)\geq v_2(S\setminus A). \]

This is a genuine high-multiplicity scenario: interpret the two types as two cohorts of \(K\) agents each, for arbitrarily large \(K\). The reduction is unchanged, so the continuous problem remains NP-hard even when the population has only two distinct types and \(N/\tau\) is arbitrarily large. The expected classification is therefore Class B: the hardness lives in selecting an integral subset of items, not in the number of named agents.

A second, stronger anchor is Theorem 8, proved in the paper using the cited Dinur–Steurer Set Cover hardness result, Lemma 5. It states:

For every constant \(\delta>0\), it is NP-hard to approximate minimum-size agreeable set within a factor \((1-\delta)\ln n\) of optimum, for additive utilities, where \(n\) is the number of agents.

Its continuous counterpart is Continuous Minimum Agreeable Set Approximation. Given \((S,\mu,v_1,\ldots,v_\tau)\), let \(\mathrm{OPT}\) be the minimum cardinality of an agreeable subset. The task is to output an agreeable \(A\), with approximation ratio measured against \(\mathrm{OPT}\).

The reduction has one type \(t_a\) for each element \(a\) of a Set Cover universe \(U\), with uniform mass \(\mu_a=1/|U|\). There is one item for every set in the cover instance and one special item \(t\). The utilities are exactly those in the paper’s proof: \(v_a(t)\) is the number of sets containing \(a\), minus one, while a set-item has utility \(1\) for type \(a\) precisely when it contains \(a\). An agreeable subset therefore contains a set cover. Duplicating every type \(K\) times gives a finite population of \(K|U|\) agents while leaving the same \(\tau=|U|\)-type continuous instance. Thus the logarithmic hardness survives arbitrary multiplicity:

\[ \text{no polynomial-time }(1-\delta)\ln\tau\text{-approximation} \]

unless \(\mathrm{P}=\mathrm{NP}\). This is again Class B. The reduction’s combinatorics live in the item/type-incidence structure, exactly where the programme predicts that continuization need not help.

The matching algorithmic anchor is Theorem 9, also proved in the paper, with its approximation theorem imported from the cited covering-integer-program literature:

When utilities are additive, there is a polynomial-time \(O(\ln n)\)-approximation algorithm for finding a minimum-size agreeable set.

For the continuous instance, after merging identical utility vectors, the same formulation has one covering constraint per positive-mass type:

\[ \min \sum_{x\in S}z_x \quad\text{subject to}\quad \sum_{x\in S} \frac{2v_t(x)}{\sum_{y\in S}v_t(y)}z_x\geq 1 \quad\text{for every }t, \]

with \(z_x\in\{0,1\}\). The paper uses this only as an encoding of the underlying agreeable-set problem; the mirror question remains the selection problem itself. The natural continuous prediction is an \(O(\ln\tau)\)-approximation running in time polynomial in \(m\), \(\tau\), and the utility bit length. Together with Theorem 8, this gives a virtually tight approximation landscape for the high-multiplicity version.

The mirror therefore covers the additive results, specifically Theorems 5, 8, and 9. It does not claim to continuize the ordinal or value-oracle sections. Theorem 5 is my strongest anchor because it gives hardness with only two types; Theorems 8 and 9 then show that the same mirror has a logarithmically tight approximation boundary.

The weakest point is serious: because the paper requires agreeability for every agent, the masses \(\mu_t\) matter only through their support. A type with mass \(0.0001\) constrains the solution just as much as a type with mass \(0.5\). A hostile reader can therefore say that this is population compression rather than a genuinely mass-sensitive continuous optimization problem.

I would concede that point rather than hide it. The faithful continuous analogue of unanimous agreeability really does have this support-only behavior. But that is not a defect in the mirror’s correspondence: it identifies a Class B problem whose hardness is independent of population multiplicity. It also produces natural next questions that make mass substantive, such as finding a smallest \(A\) agreeable to at least \(1-\rho\) of the population mass, or minimizing the mass of dissatisfied types. Those are new weighted continuous problems, not claimed as results of this paper.