d4-conf-ecai-2023-0086 (d4-conf-ecai-2023-0086)

Given a finite item set \(C\), a support \(T\) of strict rankings with positive rational masses \(\mu_t\) summing to \(1\), and an integer \(k\), is there a subset \(S\subseteq C\) with \(|S|\le k\) such that for every \(t\in T\), \(\sum_{c\in S}(m-\operatorname{pos}_t(c))\ge\sum_{c\in C\setminus S}(m-\operatorname{pos}_t(c))\)?

Let \(C\) be a nonempty set of \(m\) indivisible items and let \(k\) be a positive integer.
A society is given by its support: a list \(T\) of \(\tau\) distinct strict rankings of \(C\), 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 rankings.
Write \(\operatorname{pos}_t(c)\in\{1,\ldots,m\}\) for the position of item \(c\), with position \(1\) most preferred. Utilities are additive Borda utilities.
A subset \(S\subseteq C\) is agreeable if, for every \(t\in T\), \(\sum_{c\in S}(m-\operatorname{pos}_t(c))\ge\sum_{c\in C\setminus S}(m-\operatorname{pos}_t(c))\); equality counts as agreement.
Let \(L\) be the total binary input length. State running times in \(m,\tau,L,k\).

Is deciding whether an agreeable subset \(S\) with \(|S|\le k\) exists solvable in polynomial time, or is it NP-hard?

For a finite list of agents with strict rankings and additive Borda utilities, this decision problem is NP-complete.

Conclusion

The problem is NP-complete when \(k\) is part of the input, using the finite-agent NP-completeness result supplied in the question. Positive masses do not affect agreeability: the definition requires a separate inequality for every ranking in the support.

For every fixed \(k\), exhaustive search takes polynomial time. Thus the distinction between fixed and input-dependent \(k\) matters.

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

For each ranking \(t\), define \(u_t(c)=m-\operatorname{pos}_t(c)\). Since the ranking is strict, its utilities are exactly \(0,1,\ldots,m-1\), so their total is

\(B=\sum_{c\in C}u_t(c)=m(m-1)/2\).

Consequently, a subset \(S\) is agreeable exactly when, for every \(t\in T\),

\(2\sum_{c\in S}u_t(c)\ge B\).

A certificate is an \(m\)-bit indicator vector for \(S\). A verifier counts its selected items, checks \(|S|\le k\), and evaluates the displayed inequality for every ranking. Each utility sum is at most \(B\), so it uses \(O(\log(m+1))\) bits.

On the promised valid inputs, verification therefore takes \(O(L+\tau m\log(m+1))\) bit operations. No arithmetic on the masses is needed. This proves membership in \(\mathrm{NP}\).

2. Polynomial reduction from the given finite-agent problem

Use the stated premise: deciding whether a finite, explicitly listed collection of agents with strict rankings and additive Borda utilities admits an agreeable subset of size at most \(k\) is NP-complete.

Take such an instance with \(n\) agents. Keep its item set and \(k\), and delete duplicate rankings. Denote the resulting distinct rankings by \(t_1,\ldots,t_\tau\), where \(1\le\tau\le n\).

Deleting duplicates preserves feasibility. Indeed, agents with identical rankings impose identical inequalities. Thus, for every \(S\subseteq C\),

\(S\text{ satisfies all original agents}\iff S\text{ satisfies every }t_j.\)

It remains to assign positive binary rational masses summing to one. To cover even the interpretation that “binary rational” requires a finite binary expansion, set

\(b=\lceil\log_2\tau\rceil,\qquad D=2^b,\)

and choose

\(\mu_{t_j}=1/D\quad(1\le j<\tau),\qquad \mu_{t_\tau}=(D-\tau+1)/D.\)

These masses satisfy all requirements:

• Since \(D\ge\tau\), every numerator is positive.
• Their sum is \(((\tau-1)+(D-\tau+1))/D=1\).
• Their denominator is a power of two, so they have finite binary expansions.
• Each mass requires \(O(\log(\tau+1))\) bits.

For \(\tau=1\), this construction simply assigns mass \(1\).

The resulting support instance imposes precisely the inequalities of the distinct original rankings. Hence it has an agreeable subset of size at most \(k\) if and only if the original finite-agent instance does.

If the original input length is \(L_0\), duplicate removal can be performed by direct comparisons in \(O(L_0^2)\) bit operations. The added mass data occupies \(O(\tau\log(\tau+1))\) bits. The reduction therefore has polynomial running time and output size, proving NP-hardness.

Together with membership, this proves NP-completeness.

3. Running time and the fixed-\(k\) case

There is also a direct exact algorithm. Borda utilities are nonnegative, so adding items to an agreeable subset preserves agreeability. Writing \(k'=\min(k,m)\), an agreeable subset of size at most \(k\) exists exactly when one of size exactly \(k'\) exists.

After constructing the utility table, enumerate all \(\binom{m}{k'}\) subsets of size \(k'\). Evaluating one candidate requires \(\tau\) sums of \(k'\) utilities. This gives the bit-operation bound

\(O\!\left(L+\tau m\log(m+1)+\binom{m}{k'}\,\tau k'\log(m+1)\right).\)

For fixed \(k\), this is polynomial in \(m,\tau,L\). For unrestricted input-dependent \(k\), the decision problem is NP-complete.

⟨structured verdict parsed — rendered above⟩

The argument establishes NP-completeness in substance. The reduction preserves the relevant constraints, the masses satisfy the input requirements, and the running-time bounds are valid. There is one minor omission concerning the source problem’s domain.

1. Membership in NP

For every strict ranking, the Borda utilities are precisely \(0,\ldots,m-1\). Therefore their total is \(B=m(m-1)/2\), independently of the ranking.

The agreement inequality is correctly rewritten as
\[ 2\sum_{c\in S}u_t(c)\ge B. \]
This equivalence preserves equality as agreement.

An \(m\)-bit indicator vector specifies a certificate. Checking its cardinality and each ranking’s inequality is sufficient. All intermediate sums and their doubles have \(O(\log(m+1))\) bits. The stated verification bound,
\[ O(L+\tau m\log(m+1)), \]
is valid on the promised valid inputs.

Ignoring the masses during this verification is justified: agreement is required separately for every support ranking, regardless of its positive mass.

2. NP-hardness reduction

The finite-agent NP-completeness result is supplied by the task, so invoking it does not require an independent proof or external citation. Its explicitly listed rankings, additive Borda utilities, cardinality constraint, and agreement convention match the target problem.

Deleting duplicate rankings preserves feasibility: repeated identical inequalities impose no additional restriction. The stated equivalence holds for every subset \(S\).

For \(\tau\ge1\), the mass construction is correct:

• \(D=2^{\lceil\log_2\tau\rceil}\ge\tau\), so every mass is positive.
• The numerators sum to \(D\), giving total mass \(1\).
• The denominator is a power of two.
• Each numerator and denominator requires \(O(\log(\tau+1))\) bits.
• When \(\tau=1\), the assigned mass is \(1\).

The resulting support therefore imposes exactly the original distinct agreement constraints. Both directions of the reduction follow.

Direct pairwise comparisons give the claimed polynomial bound for duplicate removal. The additional mass data also has polynomial size. Thus the reduction is polynomial.

Minor issue — source instances with no agents. The statement \(1\le\tau\le n\) assumes \(n\ge1\). The supplied premise says “a finite list of agents” without explicitly excluding an empty list. For an empty list, \(\tau=0\), and the displayed mass construction is undefined. The minimum clarification is to state explicitly that the NP-complete source problem is being used with at least one agent, and justify that restriction if the supplied premise permits empty lists. This is a routine domain clarification and does not undermine the hardness argument in substance.

3. Exact algorithm and fixed \(k\)

All Borda utilities are nonnegative, so enlarging an agreeable subset preserves each agreement inequality. Consequently, the equivalence between existence at size at most \(k\) and existence at size exactly \(k'=\min(k,m)\) is correct.

There are exactly \(\binom{m}{k'}\) candidates. Evaluating each requires \(\tau k'\) additions of quantities with \(O(\log(m+1))\) bits. Candidate enumeration fits within the stated bound because \(\tau\ge1\) and \(k'\ge1\).

The total bound
\[ O\!\left(L+\tau m\log(m+1)+\binom{m}{k'}\tau k'\log(m+1)\right) \]
is therefore valid. For every fixed \(k\), it is polynomial in \(m,\tau,L\).

The edge cases \(m=1\), \(\tau=1\), and \(k\ge m\) are handled correctly. No claim of polynomial time for arbitrary input-dependent \(k\) is made.

Assessment

The output resolves the intended complexity question, subject only to the minor source-domain clarification above. No false mathematical step, substantive missing lemma, or incorrect running-time claim was found.

⟨structured verdict parsed — rendered above⟩