Proportional Rankings (d4-conf-ijcai-2017-0784)

Given alternatives \(A\), approval types \(T\subseteq 2^A\), rational masses \(\mu_t\ge 0\) summing to \(1\), \(\alpha\in(0,1]\cap\mathbb{Q}\), and \(\lambda\in\mathbb{N}\), decide whether there exist masses \(z_t\in[0,\mu_t]\) with \(\sum_t z_t=\alpha\) and \(\left|\bigcap_{t:z_t>0}A_t\right|\ge\lambda\). Equivalently, decide whether some \(B\subseteq A\) with \(|B|=\lambda\) satisfies \(\sum_{t:B\subseteq A_t}\mu_t\ge\alpha\).

Let \(A\) be a finite set of \(m\ge 1\) alternatives. A society is given by its support: a list \(T\) of \(\tau\) distinct nonempty approval sets \(A_t\subseteq A\), each with a positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible approval sets.
Given binary-rational \(\alpha\in(0,1]\) and an integer \(1\le\lambda\le m\), decide whether there are real masses \(0\le z_t\le\mu_t\) satisfying \(\sum_{t\in T}z_t=\alpha\) and \(\left|\bigcap_{t:z_t>0}A_t\right|\ge\lambda\). Equivalently, decide whether some \(B\subseteq A\) with \(|B|=\lambda\) satisfies \(\sum_{t:B\subseteq A_t}\mu_t\ge\alpha\).
Let \(L\) be the total input bit length; express running times in \(m,\tau,L,\lambda\).

Is this continuous significant-group decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For an explicitly listed finite electorate of \(n\) voters with nonempty approval sets, deciding whether a group of exactly \(\lceil\alpha n\rceil\) voters commonly approves at least \(\lambda\) alternatives is \(\mathrm{NP}\)-complete (Skowron, Lackner, Brill, Peters, and Elkind, 2017).
That result classifies selection of indivisible voters; it does not give a classification for the divisible-mass problem stated above.

Classification

The continuous significant-group decision problem is \(\mathrm{NP}\)-complete when \(\lambda\) is part of the input. This holds even when all masses and the threshold are dyadic rationals.

The proof below applies directly to divisible masses.

1. Eliminating the continuous variables

For any \(B\subseteq A\), define its supporting mass by
\( w(B)=\sum_{t:B\subseteq A_t}\mu_t. \)

We first verify the stated equivalence.

Suppose feasible masses \(z_t\) exist. Since \(\alpha>0\), at least one mass is positive. Choose any \(\lambda\)-element subset \(B\) of the common intersection of the approval sets with positive mass. Every type with \(z_t>0\) then contains \(B\), so
\( w(B)\ge\sum_{t:z_t>0}z_t=\alpha. \)

Conversely, suppose \(|B|=\lambda\) and \(w(B)\ge\alpha\). Enumerate the types containing \(B\), and take mass from each successively, up to its capacity, until the total reaches \(\alpha\). This is possible because their total capacity is at least \(\alpha\). Set all other masses to zero. Every approval set receiving positive mass contains \(B\), so the resulting masses are feasible.

Thus the decision problem is exactly whether a \(\lambda\)-element set \(B\) satisfies \(w(B)\ge\alpha\).

2. Membership in \(\mathrm{NP}\)

A certificate is a list of the \(\lambda\) alternatives in \(B\). Verify that they are distinct, determine which approval sets contain them, and compare their total mass with \(\alpha\).

This comparison uses exact integer arithmetic. Write the masses and threshold as binary-encoded fractions, and let \(Q\) be the product of their denominators. The bit length of \(Q\) is \(O(L)\), because the denominator bit lengths sum to at most \(L\). Multiplying by \(Q\) therefore turns the comparison into an integer comparison involving polynomially many bits.

Hence verification takes polynomial time, and the problem belongs to \(\mathrm{NP}\).

3. A polynomial reduction from CLIQUE

We use the classical \(\mathrm{NP}\)-completeness of CLIQUE: given a finite simple undirected graph \(G\) and an integer \(k\), decide whether \(G\) contains a clique of size \(k\). See [Karp, *Reducibility among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Let \(G=(V,E)\), with \(n=|V|\) and \(q=|E|\).

Instances with \(k<3\), \(k>n\), or \(q<\binom{k}{2}\) can be decided directly in polynomial time. Map these cases to a fixed valid YES or NO instance of our target problem:

• A YES instance has one alternative, one approval set containing it, mass \(1\), and \(\alpha=\lambda=1\).
• A NO instance has two alternatives, their two singleton approval sets each of mass \(1/2\), and \(\alpha=\lambda=1\).

For the remaining instances, assume
\( 3\le k\le n \quad\text{and}\quad q\ge\binom{k}{2}. \)

Construction

Let \(N\) be the smallest power of two satisfying \(N\ge n+4\). Construct a graph \(H\) by adding to \(G\):

• two disjoint edges on four new vertices;
• enough isolated vertices to give \(H\) exactly \(N\) vertices.

The added edges have no endpoints in \(V\). Thus
\( N<2(n+4), \qquad |E(H)|=q+2. \)

Use the edges of \(H\) as alternatives:
\( A=E(H), \qquad m=q+2, \qquad \lambda=\binom{k}{2}, \qquad \alpha=\frac{N-k}{N}. \)

For each vertex \(v\in V(H)\), define the approval set
\( C_v=\{e\in E(H):v\notin e\}. \)

Provisionally assign mass \(1/N\) to each vertex's approval set. To obtain the required support of distinct approval sets, merge equal sets: for every distinct set \(C\) occurring among the \(C_v\), output one type with
\( A_C=C, \qquad \mu_C=\frac{|\{v\in V(H):C_v=C\}|}{N}. \)

Input requirements

Every approval set is nonempty. An original vertex avoids both added edges; an endpoint of one added edge avoids the other; and an isolated vertex avoids every edge.

The merged approval sets are distinct by construction. Their masses are positive and sum to \(1\). Because \(N\) is a power of two, all masses and \(\alpha\) are dyadic rationals. Also,
\( 0<\alpha<1, \qquad 1\le\lambda\le m, \)
using \(k\le n<N\) and \(\binom{k}{2}\le q\).

There are at most \(N=O(n)\) support types. With approval sets represented by incidence bit vectors, the output length is
\( L=O\bigl(n(q+\log(n+1))\bigr). \)
Constructing and merging the sets takes polynomial time.

4. Correctness of the reduction

For an edge set \(B\subseteq E(H)\), let
\( U(B)=\bigcup_{e\in B}e \)
be its set of endpoints.

By definition,
\( B\subseteq C_v \quad\Longleftrightarrow\quad v\notin U(B). \)

Merging equal approval sets preserves their total supporting mass. Consequently,
\( w(B) =\frac{|\{v:B\subseteq C_v\}|}{N} =\frac{N-|U(B)|}{N}. \)

For \(|B|=\lambda=\binom{k}{2}\), this gives
\( w(B)\ge\alpha \quad\Longleftrightarrow\quad |U(B)|\le k. \)

Forward direction

Suppose \(G\) has a clique \(K\) of size \(k\). Take \(B\) to be its \(\binom{k}{2}\) edges. Then \(U(B)=K\), so
\( w(B)=\frac{N-k}{N}=\alpha. \)

By Section 1, the continuous instance is a YES instance.

Reverse direction

Suppose the continuous instance is a YES instance. Section 1 supplies an edge set \(B\) with
\( |B|=\binom{k}{2}, \qquad |U(B)|\le k. \)

Put \(r=|U(B)|\). Since \(H\) is simple, there are at most \(\binom{r}{2}\) edges with both endpoints in \(U(B)\). Therefore
\( \binom{k}{2} =|B| \le\binom{r}{2} \le\binom{k}{2}. \)

If \(r<k\), then \(\binom{r}{2}<\binom{k}{2}\), since \(k\ge3\), which is impossible. Hence \(r=k\). Equality also shows that \(B\) contains every unordered pair of vertices in \(U(B)\), so \(U(B)\) is a clique of size \(k\) in \(H\).

Every added vertex has degree at most one. A vertex in a clique of size \(k\ge3\) has at least two neighbors within that clique. Thus this clique contains only original vertices and is a clique in \(G\).

This proves both directions of the reduction. Together with membership in \(\mathrm{NP}\), it establishes \(\mathrm{NP}\)-completeness.

5. Running times in the requested parameters

Two exhaustive algorithms give useful parameter bounds.

Enumerate alternatives. Enumerate all \(\binom{m}{\lambda}\) sets \(B\) and compute \(w(B)\). A conservative running-time bound, including exact rational arithmetic, is
\( O\!\left(\binom{m}{\lambda}(m\tau+L^3)\right). \)
In particular, this is polynomial for every fixed \(\lambda\), since \(\binom{m}{\lambda}\le m^\lambda\).

Enumerate support subsets. Enumerate all nonempty \(S\subseteq T\), checking
\( \sum_{t\in S}\mu_t\ge\alpha \quad\text{and}\quad \left|\bigcap_{t\in S}A_t\right|\ge\lambda. \)
These conditions are sufficient by Section 1. They are necessary because, from feasible masses, the set \(S=\{t:z_t>0\}\) satisfies both conditions. This algorithm takes
\( O\!\left(2^\tau(m\tau+L^3)\right), \)
and is polynomial for fixed support size \(\tau\).

Choosing the smaller enumeration gives the bound
\( O\!\left( \min\!\left\{\binom{m}{\lambda},2^\tau\right\} (m\tau+L^3) \right). \)

Thus divisibility permits exact trimming to the desired mass, but the unrestricted choice of commonly approved alternatives remains \(\mathrm{NP}\)-complete.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the assigned problem correctly. The argument establishes \(\mathrm{NP}\)-completeness when \(\lambda\) is part of the input, including the restriction to dyadic masses and threshold. It directly addresses divisible masses and does not rely on transferring hardness from indivisible voters.

No major or minor mathematical issues were found.

Step-by-step verification

1. Eliminating the continuous variables

Both directions are valid.

• From feasible masses, \(\alpha>0\) ensures the positive-mass support is nonempty. The intersection condition permits choosing a set \(B\) of exactly \(\lambda\) alternatives. Every positive-mass type contains \(B\), and the capacity constraints imply \(w(B)\ge\alpha\).
• Conversely, the successive allocation described in the proof terminates with total mass exactly \(\alpha\), since the finitely many supporting types have total capacity at least \(\alpha\). Each allocated mass respects its capacity, and every type receiving positive mass contains \(B\).

The proof therefore correctly replaces real-valued witnesses with finite certificates. Equality at the threshold is handled correctly.

2. Membership in \(\mathrm{NP}\)

The certificate and verification procedure are valid. A list of \(\lambda\le m\) alternative identifiers has polynomial length, and checking distinctness and containment is polynomial.

The denominator-product argument is correct: the product has bit length bounded by the sum of the input denominator bit lengths, hence \(O(L)\). Scaled numerators and their sum also have polynomial bit length. Exact comparison therefore takes polynomial time.

No assumption that feasible real masses themselves have short encodings is needed.

3. Source problem and exceptional cases

The invoked theorem is the standard \(\mathrm{NP}\)-completeness of CLIQUE for finite simple undirected graphs with the requested clique size supplied as input. This is the appropriate source problem. [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf) lists CLIQUE among its complete problems.

The preprocessing is sound:

• Sizes below three can be checked directly.
• A requested size exceeding the vertex count is impossible.
• Fewer than \(\binom{k}{2}\) edges precludes a clique of size \(k\).

The fixed target instances are valid. The YES instance has supporting mass one. In the NO instance, each possible singleton \(B\) has supporting mass one-half, below the threshold one.

4. Construction and target input requirements

The construction satisfies every stated requirement.

• The smallest power of two \(N\ge n+4\) satisfies \(N<2(n+4)\).
• Adding two disjoint edges and isolated vertices preserves simplicity and yields exactly \(q+2\) edges.
• Every approval set is nonempty for the reasons given: original vertices avoid both added edges, added endpoints avoid the other added edge, and isolated vertices avoid every edge.
• Merging equal approval sets produces distinct support types with positive masses summing to one.
• All masses and the threshold are dyadic.
• Since \(3\le k\le n<N\), the threshold lies strictly between zero and one.
• Since \(\binom{k}{2}\le q\), the requested \(\lambda\) lies within the alternative count.

The support count and output-length bounds are correct for the stated incidence-vector representation. Constructing and merging the sets takes polynomial time.

5. Supporting-mass identity

The identity
\[ B\subseteq C_v\quad\Longleftrightarrow\quad v\notin U(B) \]
is correct: all selected edges avoid \(v\) exactly when \(v\) is absent from their endpoint union.

Merging preserves the calculation because vertices with equal approval sets contribute identical containment indicators. Thus
\[ w(B)=\frac{N-|U(B)|}{N}. \]
For the constructed threshold, the claimed equivalence with \(|U(B)|\le k\) follows exactly, including equality.

6. Forward implication

A clique of size \(k\) contributes exactly \(\binom{k}{2}\) edges. Because \(k\ge3\), their endpoint union is precisely the clique’s vertex set. The resulting supporting mass equals \(\alpha\), and Section 1 supplies feasible divisible masses.

This implication is complete.

7. Reverse implication

The edge-count argument is correct. Writing \(r=|U(B)|\), simplicity gives
\[ \binom{k}{2}=|B|\le\binom{r}{2}\le\binom{k}{2}. \]

For nonnegative integer \(r<k\) with \(k\ge3\), the middle quantity is strictly smaller than \(\binom{k}{2}\). Consequently \(r=k\). Equality in the edge bound forces every pair of vertices in \(U(B)\) to be present as an edge, giving a clique.

Every added vertex has degree at most one, whereas a vertex in a clique of size at least three has at least two neighbors. The recovered clique therefore lies entirely in \(G\).

There is no soundness gap from padding, duplicate approval sets, or divisible allocation.

8. Running-time claims

Both enumerations are correct.

• Enumerating all \(\lambda\)-element alternative sets directly checks the established finite characterization.
• Enumerating nonempty support subsets is sufficient when their intersection is large enough and their total capacity reaches the threshold. It is necessary because the positive-mass support of any feasible solution satisfies both conditions.

The factor \(m\tau\) conservatively covers containment or intersection computations with incidence vectors. The \(L^3\) term conservatively covers exact rational arithmetic using elementary integer operations.

The stated combined bound
\[ O\!\left(\min\!\left\{\binom{m}{\lambda},2^\tau\right\}(m\tau+L^3)\right) \]
is valid. Polynomial time for fixed \(\lambda\), and separately for fixed support size \(\tau\), follows as claimed.

Required feedback

No mathematical repair or additional clarification is needed. The general hardness classification and the parameter-dependent algorithmic bounds are both established.

⟨structured verdict parsed — rendered above⟩