Democratic Fair Allocation of Indivisible Goods (d4-conf-ijcai-2018-0219)

Given indivisible goods \(G\), two groups, and for each group \(i\) a finite-support rational distribution \(\mu_i\) over binary approval types \(S\subseteq G\), decide whether there is an integral partition \(G=X_1\dot\cup X_2\) such that \(H_i(X_i)=\sum_{S:S\cap X_i\neq\varnothing}\mu_{i,S}=1\) for both groups.

Definitions

Let \(G\) be a finite set of indivisible goods. For each group \(i\in\{1,2\}\), the input gives a finite-support rational distribution \(\mu_i\) over approval types \(S\subseteq G\). For \(X\subseteq G\), define \(H_i(X)=\sum_{S:S\cap X\ne\varnothing}\mu_{i,S}\).

Target

Is deciding whether there exists an integral partition \(G=X_1\dot\cup X_2\) with \(H_1(X_1)=H_2(X_2)=1\) NP-hard or in \(\mathrm{P}\)?

Nearest known results

For finite lists of binary-approval agents in two groups, deciding whether every agent receives a positively valued good is NP-complete.
No verified result was located for the distribution-over-types formulation above.

Result

The decision problem is NP-complete, even when every approval type has size two or three. The proof uses a polynomial-time reduction from 3-SAT.

1. Full coverage is equivalent to hitting every positive-probability type

For group \(i\), let \(\mathcal S_i=\{S\subseteq G:\mu_{i,S}>0\}\) be its support. Since \(\mu_i\) is a probability distribution,
\[ 1-H_i(X)=\sum_{S:S\cap X=\varnothing}\mu_{i,S}. \]
Every summand is nonnegative. Consequently,
\[ H_i(X)=1 \quad\Longleftrightarrow\quad S\cap X\ne\varnothing\text{ for every }S\in\mathcal S_i. \]
Thus the precise positive probability values do not affect feasibility; only the supports matter.

2. Membership in NP

A certificate specifies, for each good, which of the two groups receives it. This specifies an integral partition \(G=X_1\dot\cup X_2\).

For each explicitly listed positive-probability type of group \(i\), check that it intersects \(X_i\). These checks take polynomial time in the input length and, by Section 1, are equivalent to the required equalities. Therefore the problem belongs to NP.

3. Polynomial-time reduction from 3-SAT

We use the standard NP-completeness of satisfiability for Boolean formulas in conjunctive normal form with three literals on distinct variables in every clause.

Let such a formula have variables \(v_1,\ldots,v_n\) and clauses \(C_1,\ldots,C_m\). We may assume \(n\ge 1\), adding an unused variable if necessary.

For every variable \(v_j\), create two distinct goods \(g_j^+\) and \(g_j^-\), representing its positive and negative literals. Set
\[ G=\{g_j^+,g_j^-:1\le j\le n\}, \qquad P_j=\{g_j^+,g_j^-\}. \]
For every clause \(C_k\), let \(Q_k\) be the set of its three literal goods: replace \(v_j\) by \(g_j^+\) and \(\neg v_j\) by \(g_j^-\).

Construct the distributions as follows:

• For group 1, take the list \(P_1,\ldots,P_n,Q_1,\ldots,Q_m\), assigning mass \(1/(n+m)\) to each occurrence.
• For group 2, assign mass \(1/n\) to each \(P_j\).

Repeated types in the first list are merged by adding their masses. Equivalently, for each distinct type \(S\) in that list, define
\[ \mu_{1,S} = \frac{\text{number of occurrences of }S\text{ in the list}}{n+m}. \]
Both distributions have total mass one. Their support sizes are at most \(n+m\) and \(n\), respectively. All numerators and denominators have bit length \(O(\log(n+m+1))\), so the construction has polynomial size and can be performed in polynomial time.

Satisfiability implies a feasible partition

Suppose the formula has a satisfying truth assignment. If \(v_j\) is true, place \(g_j^+\) in \(X_1\) and \(g_j^-\) in \(X_2\). If \(v_j\) is false, reverse those placements.

Each pair \(P_j\) intersects both parts. Each clause has a true literal, whose corresponding good belongs to \(X_1\); hence each \(Q_k\) intersects \(X_1\).

Every support type of each group therefore intersects its assigned part. Section 1 gives \(H_1(X_1)=H_2(X_2)=1\).

A feasible partition implies satisfiability

Conversely, suppose a partition satisfies \(H_1(X_1)=H_2(X_2)=1\). Every pair \(P_j\) has positive probability in both distributions. Section 1 therefore implies
\[ P_j\cap X_1\ne\varnothing \quad\text{and}\quad P_j\cap X_2\ne\varnothing. \]
Because \(P_j\) contains exactly two goods and the parts are disjoint, exactly one of its goods belongs to each part.

Define \(v_j\) to be true precisely when \(g_j^+\in X_1\). The splitting property then implies that a literal is true precisely when its corresponding good belongs to \(X_1\).

Each \(Q_k\) has positive probability in group 1, so \(Q_k\cap X_1\ne\varnothing\). Thus each clause contains a true literal. The formula is satisfiable.

4. Conclusion

The construction is a polynomial-time many-one reduction from 3-SAT, proving NP-hardness. Together with membership in NP, it proves NP-completeness.

⟨structured verdict parsed — rendered above⟩

The proof is correct under the explicit finite-support encoding used in the write-up. It establishes NP-completeness, including the restriction that every positive-probability approval type has size two or three. No mathematical gaps or false steps were found.

Step-by-step verification

• Full coverage and support hitting.

The identity
\(1-H_i(X)=\sum_{S:S\cap X=\varnothing}\mu_{i,S}\)
follows from normalization of the probability distribution and the partition of its types into those intersecting \(X\) and those disjoint from \(X\).

Because the support is finite and every support weight is strictly positive, this sum vanishes exactly when no support type is disjoint from \(X\). Thus the equivalence in Section 1 is valid.

Zero-probability types impose no constraint. An empty type with positive probability makes full coverage impossible, and the equivalence correctly captures this edge case.

• Membership in NP.

The certificate assigns each good to exactly one group, so it describes the required integral partition. Checking intersection with every explicitly listed positive-probability type takes polynomial time in the input length.

Section 1 makes these combinatorial checks sufficient; exact addition of rational probabilities is unnecessary. The NP-membership argument is valid.

This complexity statement uses explicit support lists with binary-encoded rational weights, as the proof specifies. It does not assert membership in NP for an unspecified succinct representation of distributions.

• Source problem.

The cited theorem is the standard NP-completeness of satisfiability for conjunctive normal form formulas having exactly three literals on distinct variables in each clause. This is a valid NP-complete restriction of 3-SAT, and the reduction consistently uses these hypotheses.

In particular, distinct variables ensure that each clause produces three distinct literal goods. No additional restriction on literal signs is assumed or needed.

• Construction and probability normalization.

The goods associated with different variables and signs are distinct, so every \(P_j\) has exactly two elements and every \(Q_k\) has exactly three.

The assumption \(n\geq 1\) ensures that both denominators are positive, including when \(m=0\). Adding an unused variable preserves satisfiability.

Group 1 assigns total mass \((n+m)/(n+m)=1\); group 2 assigns total mass \(n/n=1\). Merging repeated clause types preserves total mass and positivity. Types of size two cannot coincide with types of size three.

Each merged numerator is at most \(n+m\), and each denominator is at most \(n+m\). The claimed bit bound \(O(\log(n+m+1))\) is correct. There are \(2n\) goods and at most \(2n+m\) support entries across both groups, each containing at most three goods. The output size and construction time are polynomial.

• Satisfiability implies feasibility.

The prescribed placements allocate every good exactly once. Each variable pair intersects both parts. Every satisfied clause has a literal whose corresponding good lies in \(X_1\), so its type intersects \(X_1\).

These checks cover all support types of both distributions. Applying Section 1 therefore establishes both required coverage equalities.

• Feasibility implies satisfiability.

Every variable pair has positive probability in both distributions. Feasibility forces that pair to intersect both disjoint parts. Since the pair has exactly two goods, it must have exactly one good in each part.

Consequently, the stated truth assignment makes a positive or negative literal true exactly when its corresponding good lies in \(X_1\). Each clause type has positive probability in group 1 and therefore intersects \(X_1\), supplying a true literal in every clause.

This proves the reverse implication without additional assumptions.

• Conclusion and assignment coverage.

The two implications establish a polynomial-time many-one reduction. Together with membership in NP, they prove the claimed NP-completeness. The construction also verifies the asserted restriction on type sizes.

The output directly resolves the distribution-over-types question rather than relying on an unverified transfer from the agent-list formulation.

Feedback

No repair is required. For standalone presentation, explicitly stating the support-list input encoding at the outset would make the complexity convention clearer; the proof already states and consistently uses it.

⟨structured verdict parsed — rendered above⟩