Computing a small agreeable set of indivisible items (d4-journals-ai-2019-0003)

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\).

Let \(S\) be a set of \(m\) indivisible items. A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational, with total mass \(1\); \(\tau\) is the support size, not the number of possible types. Here \(1\le\tau\le3\).
Each type has a complete, reflexive, transitive preference relation \(\succeq_j\) over subsets of \(S\), allowing indifference. Preferences are monotonic and responsive: adding an item weakly improves a set, and replacing an included item by an excluded, weakly preferred singleton weakly improves it.
A comparison oracle reports the preference between any two subsets for a specified type. Charge one unit per query; let \(L\) be the bit length of the explicit input, excluding oracle implementations.
Find an integral subset \(T\subseteq S\) satisfying \(T\succeq_j S\setminus T\) for every supported type and \(|T|\le\lceil m/2\rceil+1\).

Can this search problem be solved in polynomial time in \(m,\tau,L\), including polynomially many oracle queries, or is it NP-hard?

Known results: For three discrete players with responsive preferences, such a subset can be found in polynomial time using comparison oracles. The stated distribution problem imposes exactly the same constraints for at most three preference relations, so it is already covered by this algorithmic guarantee.

Result

The search problem is polynomial-time solvable, using the three-player algorithmic guarantee supplied in the question. The positive masses do not affect the required subset.

Supplied theorem

We use the stated known result: for three discrete players with monotonic, responsive preferences, accessible through comparison oracles, a polynomial-time algorithm finds a subset \(T\subseteq S\) such that

• \(T\succeq_i S\setminus T\) for each player \(i\in\{1,2,3\}\);
• \(|T|\le \lceil m/2\rceil+1\).

As specified in the question, this guarantee applies to the preference relations allowed here, including indifference.

Reduction to three players

Let the supported preference relations be \(\succeq_1,\ldots,\succeq_\tau\), where \(1\le\tau\le3\). Construct three virtual players by retaining every supported relation and, when necessary, duplicating the first relation. More precisely, define \(f:\{1,2,3\}\to\{1,\ldots,\tau\}\) by \(f(i)=i\) when \(i\le\tau\), and \(f(i)=1\) otherwise. Virtual player \(i\) has preference relation \(\succeq_{f(i)}\).

Every virtual relation is complete, reflexive, transitive, monotonic, and responsive because it is an unchanged copy of a supported relation. Thus the supplied theorem applies.

Implement each virtual comparison query concerning subsets \(A,B\subseteq S\) for player \(i\) by issuing the same query to supported type \(f(i)\). This gives exactly the oracle answers for the constructed three-player instance.

Run the supplied algorithm and return its subset \(T\). For every supported type \(j\), virtual player \(j\) has relation \(\succeq_j\). Consequently, the algorithm’s guarantee gives \(T\succeq_j S\setminus T\) for every supported type. It also gives the required bound \(|T|\le\lceil m/2\rceil+1\).

Complexity and the role of masses

The construction uses only three indices and requires no new preference representation. Each virtual oracle query becomes exactly one original oracle query, so the query count remains polynomial in \(m\).

Representing subsets by \(m\)-bit incidence vectors incurs at most polynomial overhead. Reading the explicit input costs polynomial time in \(L\). Hence the total running time, including oracle queries charged at one unit each, is polynomial in \(m,\tau,L\).

Finally, each positive mass merely establishes that its type is supported. Its numerical value appears in neither the preference inequalities nor the cardinality bound. Therefore, duplicating a preference relation for the three-player algorithm does not change the target constraints, and no population expansion based on rational denominators is needed.

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned search problem. Its reduction is correct, and its complexity conclusion follows from the algorithmic guarantee explicitly supplied in USER_TASK. No major or minor issues were found.

• Use of the supplied theorem. The prover states the relevant guarantee with the required preference inequalities, cardinality bound, and comparison-oracle access. USER_TASK expressly says that this guarantee covers the preference relations in the distribution problem. Thus its application to weak preferences, including indifference, is justified by the supplied premise; no external theorem verification is needed.

• Construction of virtual players. For every permitted support size \(1\le\tau\le3\), the map \(f\) is well-defined and includes every supported type among the three virtual players. Duplicating the first relation preserves completeness, reflexivity, transitivity, monotonicity, and responsiveness. The supplied guarantee imposes no requirement that players have distinct preferences.

• Oracle simulation. Redirecting a virtual player's comparison query to type \(f(i)\) returns precisely the comparison required by the constructed instance. Each simulated query uses exactly one original query.

• Correctness of the returned subset. For each supported type \(j\), virtual player \(j\) uses relation \(\succeq_j\). Therefore, the theorem's guarantee entails \(T\succeq_j S\setminus T\) for every supported type. Its cardinality guarantee is exactly \(|T|\le\lceil m/2\rceil+1\). Duplicate relations introduce only repeated constraints.

• Complexity. The virtual instance requires constant-size indexing information and no explicit preference expansion. With three players fixed, the supplied polynomial-time guarantee gives polynomially many oracle queries in \(m\). Query redirection and subset representation incur polynomial overhead, and reading the explicit input takes polynomial time in \(L\). The claimed polynomial bound in \(m,\tau,L\) follows.

• Masses and boundary cases. The numerical masses do not occur in the required inequalities or cardinality bound, so ignoring their values after identifying the support is valid. The construction covers \(\tau=1,2,3\). If an empty item set is permitted, its sole subset satisfies the constraints by reflexivity and satisfies the size bound; there is no substantive missing boundary case.

No additional clarification or repair is required. The conclusion appropriately relies on the theorem supplied by the task rather than claiming to prove that theorem independently.

⟨structured verdict parsed — rendered above⟩