Computing Pareto Optimal Committees (d4-conf-ijcai-2016-0168)

Given a finite alternative set \(A\), committee size \(k\), a rational distribution \(\mu\) over complete weak-order types, and \(D\in\binom{A}{k}\), decide whether there exists \(W\in\binom{A}{k}\) such that \(W\succeq_t^{\mathrm{RS}}D\) for every type with \(\mu_t>0\), while \(\mu(\{t:W\succ_t^{\mathrm{RS}}D\})>0\). The question applies in particular to dichotomous types with \(\operatorname{Topwidth}\ge 3\), and asks whether \(D\) is continuously RS-efficient.

Let \(A\) contain \(m\ge1\) alternatives, let \(1\le k\le m\) be an integer, and let \(D\subseteq A\) have size \(k\).
A society is given by its support: a list of \(\tau\) distinct complete weak-order types \(\succeq_t\), each with positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length. Types are represented by ordered indifference classes.
For size-\(k\) committees, define \(W\succeq_t^{\mathrm{RS}}V\) iff there is a bijection \(f:V\to W\) with \(f(a)\succeq_t a\) for every \(a\in V\); define \(W\succ_t^{\mathrm{RS}}V\) iff \(W\succeq_t^{\mathrm{RS}}V\) and \(V\not\succeq_t^{\mathrm{RS}}W\).
A continuous RS improvement is a committee \(W\subseteq A\) of size \(k\) satisfying \(W\succeq_t^{\mathrm{RS}}D\) for every supported type and \(\sum_{t:W\succ_t^{\mathrm{RS}}D}\mu_t>0\). Call \(D\) continuously RS-efficient when no such committee exists.
Dichotomous types have exactly two nonempty indifference classes; writing \(E_t^1\) for the top class, define \(\operatorname{Topwidth}=\max_t|E_t^1|\).

Is deciding whether a continuous RS improvement exists in \(\mathrm{P}\) or NP-hard, including on dichotomous instances with \(\operatorname{Topwidth}\ge3\)? State running times in \(m,\tau,L,k\).

For finite-agent societies, RS-efficiency testing is coNP-complete even for dichotomous preferences with \(\operatorname{Topwidth}=3\), and for strict preferences; thus improvement existence is NP-complete. For dichotomous preferences with \(\operatorname{Topwidth}\le2\), an improvement can be found in polynomial time. [Verified source](https://www.cse.unsw.edu.au/~haziz/commt_journal.pdf).
No separate result for the stated distribution-input problem was located.

Result

Deciding whether a continuous RS improvement exists is \(\mathrm{NP}\)-complete, even for dichotomous instances with \(\operatorname{Topwidth}=3\) and equal positive masses. Consequently, it is \(\mathrm{NP}\)-complete on the class with \(\operatorname{Topwidth}\ge3\), and continuous RS-efficiency testing is \(\mathrm{coNP}\)-complete. The same conclusions hold for strict preferences.

For dichotomous instances with \(\operatorname{Topwidth}\le2\), an improvement can be found, or its nonexistence certified, in polynomial time.

These statements concern variable committee size \(k\)\). For each fixed \(k\)\), enumeration gives a polynomial-time algorithm; when \(k=m\)\), no improvement exists.

1. Positive masses make improvement depend only on support

For a size-\(k\)\) committee \(W\)\), define
\(I(W)=\{t:W\succ_t^{\mathrm{RS}}D\}\)\).

Because the support is finite and every \(\mu_t>0\)\),
\(\sum_{t\in I(W)}\mu_t>0\quad\Longleftrightarrow\quad I(W)\ne\varnothing\)\).

Indeed, an empty sum is zero, while a nonempty sum contains a positive summand and no negative summands. Therefore \(W\)\) is a continuous RS improvement exactly when

• \(W\succeq_t^{\mathrm{RS}}D\)\) for every supported type \(t\)\); and
• \(W\succ_t^{\mathrm{RS}}D\)\) for at least one supported type.

This is precisely finite-agent RS Pareto improvement for a society containing one agent of each supported type. Thus the numerical values and denominators of the masses do not affect the answer.

Conversely, take an explicitly listed finite-agent society. Remove duplicate preference orders, obtaining \(\tau\)\) distinct types, and assign each type mass \(1/\tau\)\). Removing duplicates preserves both universal weak improvement and the existence of a strictly improving agent. Hence it preserves improvement existence.

This conversion is polynomial in the finite-agent input length: canonicalize each ordered indifference-class representation by sorting alternative identifiers within each class, then sort and deduplicate the resulting representations. Each mass \(1/\tau\)\) requires \(O(\log(\tau+1))\)\) bits. No exponentially large population is constructed.

The conversion preserves dichotomous preferences, strict preferences, and topwidth exactly.

2. RS comparisons and polynomial verification

Fix a supported type \(t\)\), whose ordered indifference classes are
\(E_t^1,\ldots,E_t^{h_t}\)\), from best to worst. Define
\(B_t^j=\bigcup_{\ell=1}^jE_t^\ell\)\).

For any two size-\(k\)\) committees \(W,V\)\),
\(W\succeq_t^{\mathrm{RS}}V \quad\Longleftrightarrow\quad |W\cap B_t^j|\ge |V\cap B_t^j| \text{ for every }j\)\).

Necessity. Suppose a witnessing bijection \(f:V\to W\)\) exists. If \(a\in V\cap B_t^j\)\), then \(f(a)\succeq_t a\)\) implies \(f(a)\in W\cap B_t^j\)\). Injectivity gives the required inequality.

Sufficiency. List each committee in nondecreasing class rank:
\(w_1,\ldots,w_k\)\) and \(v_1,\ldots,v_k\)\).
Write \(r_t(a)\)\) for the class index of \(a\)\).

If \(r_t(w_i)>r_t(v_i)\)\) for some \(i\)\), set \(j=r_t(v_i)\)\). Then \(V\)\) has at least \(i\)\) members in \(B_t^j\)\), whereas \(W\)\) has at most \(i-1\)\), contradicting the assumed inequality. Therefore \(r_t(w_i)\le r_t(v_i)\)\) for every \(i\)\), and the bijection \(v_i\mapsto w_i\)\) witnesses RS weak preference.

Applying this characterization in both directions shows that
\(W\succ_t^{\mathrm{RS}}V\)\) holds exactly when all the displayed inequalities hold and at least one is strict.

A certificate for improvement is the list of the \(k\)\) members of \(W\)\), using \(O(k\log(m+1))\)\) bits. Check its size and distinctness, then scan every type’s ordered classes, accumulating the two prefix counts. Accept precisely when every prefix inequality holds and at least one is strict somewhere. Section 1 proves that this also verifies the positive-mass requirement. Hence improvement existence belongs to \(\mathrm{NP}\)\).

For dichotomous types, only the top-class inequality is nontrivial:
\(W\succeq_t^{\mathrm{RS}}D \Longleftrightarrow |W\cap E_t^1|\ge |D\cap E_t^1|\)\).
Strict preference corresponds to a strict inequality.

3. Hardness transfers to the distribution input

The finite-agent results supplied in the question are Theorems 3 and 6 of Aziz and Monnot: RS-efficiency testing is \(\mathrm{coNP}\)\)-complete for dichotomous preferences with topwidth exactly three, and for strict preferences. Their RS definition uses an injection between equal-size committees, which is a bijection, so it agrees with the present definition. [Verified paper](https://www.cse.unsw.edu.au/~haziz/commt_journal.pdf).

Taking complements, finite-agent improvement existence is \(\mathrm{NP}\)\)-complete on each of these restricted classes.

Apply the polynomial conversion from Section 1 to any such finite-agent instance. The resulting distribution has distinct supported types and positive binary-encoded rational masses summing to one. It admits a continuous RS improvement if and only if the original instance admits a finite-agent improvement. Its preference restriction and topwidth are preserved.

This is a polynomial many-one reduction proving \(\mathrm{NP}\)\)-hardness, even with equal masses. Together with Section 2, it proves all the completeness claims stated above.

4. Explicit polynomial algorithm for topwidth at most two

Here is a direct algorithm, including a running-time bound.

Write \(T_t=E_t^1\)\) and \(r_t=|D\cap T_t|\)\). Assume every \(|T_t|\le2\)\).

First define the forced set
\(F=\bigcup_{t:r_t=|T_t|}T_t\)\).
Every weakly improving committee must contain \(F\)\), since a type already receiving every top alternative cannot lose any of them. Also, \(F\subseteq D\)\).

Construct a graph \(G\)\) with vertex set \(A\setminus F\)\). For each type with \(|T_t|=2\)\), \(r_t=1\)\), and \(T_t\cap F=\varnothing\)\), add the edge \(T_t\)\).

Every such edge has one endpoint in \(D\setminus F\)\) and the other in \(A\setminus D\)\). Thus \(G\)\) is bipartite. Moreover, a size-\(k\)\) committee \(W\)\) weakly improves every type exactly when it contains \(F\)\) and \(W\setminus F\)\) is a vertex cover of \(G\)\). To verify this equivalence, consider all possibilities:

• A saturated type forces its entire top set into \(F\)\).
• A type with \(r_t=0\)\) imposes no weak-improvement constraint.
• An unsaturated type with \(r_t=1\)\) has two top alternatives and requires at least one. This is already satisfied by \(F\)\), or is represented by an edge.

Now enumerate possible witnesses of strict improvement:

• If \(r_t=0\)\), separately require each alternative \(a\in T_t\)\) to be selected.
• If \(r_t=1<|T_t|=2\)\), require both members of \(T_t\)\) to be selected.
• Saturated types cannot strictly improve.

There are at most \(2\tau\)\) such tests.

For one test, let \(S\)\) be its required set and put \(H=F\cup S\)\). Delete \(S\setminus F\)\) and its incident edges from \(G\)\), obtaining \(G'\)\). A committee satisfying this test exists exactly when
\(|H|+\operatorname{vc}(G')\le k\)\),
where \(\operatorname{vc}\)\) denotes minimum vertex-cover size.

For necessity, any satisfying committee contains \(H\)\), and its remaining members cover \(G'\)\). For sufficiency, take \(H\)\) together with a minimum vertex cover of \(G'\)\). This set satisfies every weak constraint and the designated strict constraint. If its size is below \(k\)\), add arbitrary unselected alternatives until its size is \(k\)\). Such padding is possible because \(k\le m\)\), and cannot decrease any top-class count.

Since \(G'\)\) remains bipartite, Kőnig’s theorem applies: its minimum vertex-cover size equals its maximum matching size, and a minimum cover can be recovered from a maximum matching. The standard augmenting-path algorithm computes that matching. The left side has at most \(k\)\) vertices, so at most \(k\)\) successful augmentations are possible.

If some test succeeds, the construction returns an improvement. Conversely, every improvement strictly improves some type and therefore satisfies one enumerated test. This proves correctness.

5. Running times

The following bounds use word operations on alternative identifiers and counters. Let
\(b=\lceil\log_2(L+m+\tau+2)\rceil\)\).
Multiplying each bound by \(O(b)\)\) gives a conservative bit-operation bound. Inputs are assumed to satisfy the stated promises.

| Task | Running time |
|---|---|
| Verify a proposed improvement | \(O(L+\tau m+k)\)\) |
| Decide and find an improvement by enumerating all committees | \(O(L+\binom{m}{k}\tau m)\)\) |
| Dichotomous instances with \(\operatorname{Topwidth}\le2\): decide and find an improvement | \(O(L+\tau m+\tau(k+1)(m+\tau))\)\) |

For the last bound, each residual graph has at most \(m\)\) vertices and \(\tau\)\) edges. Each augmenting-path search takes \(O(m+\tau)\)\) operations; there are at most \(k+1\)\) searches per test and at most \(2\tau\)\) tests.

Enumeration is polynomial for fixed \(k\)\), since \(\binom{m}{k}\le m^k\)\), and also for fixed \(m-k\)\). For unrestricted \(k\)\), the hardness proof rules out a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\)\).

⟨structured verdict parsed — rendered above⟩

The argument settles the target in substance: improvement existence is \(\mathrm{NP}\)-complete under the stated distribution input, including dichotomous instances with \(\operatorname{Topwidth}=3\) and equal positive masses. The polynomial algorithm for dichotomous topwidth at most two is also correct. I found no mathematical gap or false central step. The only issue is malformed mathematical delimiters throughout much of the write-up.

• Positive masses and support equivalence — correct.

For any candidate committee, the set of strictly improving supported types is finite. Since every mass is positive, its total mass is positive exactly when that set is nonempty. Consequently, both weak improvement and strict improvement depend only on the supported preference orders.

Replacing the support by one finite agent per type therefore preserves improvement existence. Conversely, deduplicating an explicitly listed finite-agent profile preserves the universal weak-improvement condition and the existential strict-improvement condition. Multiplicities play no role in either condition.

Assigning each remaining type mass \(1/\tau\) gives positive rational masses summing to one. Their binary rational representations have \(O(\log(\tau+1))\) bits each. Canonicalization and deduplication are polynomial in the original explicit input length. No population expansion is needed.

Removing duplicate orders preserves strictness, dichotomousness, and the maximum top-class size. Thus all stated preference restrictions survive the reduction.

• RS prefix characterization — correct.

Necessity follows from the witnessing bijection: every member of \(V\) in a preference prefix must map to a distinct member of \(W\) in that same prefix.

For sufficiency, the sorted committee lists and the index \(i\) are used correctly. If \(r_t(w_i)>r_t(v_i)\), the prefix ending at rank \(r_t(v_i)\) contains at least \(i\) members of \(V\) and at most \(i-1\) members of \(W\). This contradicts the assumed prefix inequalities, including when ranks are tied.

The resulting positionwise bijection satisfies the original RS definition. Applying the characterization in both directions also correctly establishes that strict RS preference means all forward prefix inequalities hold and at least one is strict. Equal committee sizes are essential here and are explicitly assumed.

• Membership in \(\mathrm{NP}\) — correct.

A committee certificate has polynomial length. Checking membership in \(A\), cardinality, distinctness, all prefix inequalities, and at least one strict inequality verifies precisely the requested improvement condition.

The write-up explicitly mentions size and distinctness; checking that identifiers belong to \(A\) is implicit in checking a committee certificate and is routine. No rational summation is necessary under the promised positive-mass input.

For dichotomous orders, the full-alternative prefix always has count \(k\), so only the top-class comparison matters. Both the weak and strict comparison statements are correct.

• Hardness transfer and cited theorems — correct.

I checked the cited paper. Theorem 3 states dichotomous RS-efficiency hardness, and its proof explicitly treats topwidth exactly three. Theorem 6 establishes the strict-preference result. The paper defines RS using an injection between equal-size committees, which is a bijection, and uses the same Pareto-improvement criterion. [Aziz–Monnot, *Computing and Testing Pareto Optimal Committees*](https://www.cse.unsw.edu.au/~haziz/commt_journal.pdf).

Taking complements correctly changes finite-agent efficiency testing from \(\mathrm{coNP}\)-complete to improvement existence being \(\mathrm{NP}\)-complete. Composing with the support conversion gives a polynomial many-one reduction to the stated distribution problem.

Equal masses, distinct support types, and exact topwidth three are all preserved. Hardness on the larger class with topwidth at least three follows because it contains these instances. Together with membership in \(\mathrm{NP}\), this establishes the claimed completeness results.

• Forced set and graph characterization — correct.

A saturated top class must remain entirely selected, so every weakly improving committee contains \(F\). Since each saturated top class is contained in \(D\), the assertion \(F\subseteq D\) is valid.

Every inserted edge contains exactly one alternative in \(D\setminus F\) and one outside \(D\). Thus the stated bipartition is valid, including isolated vertices.

The case analysis covers every nonempty top set of size at most two: saturated sets, sets with baseline count zero, and unsaturated two-element sets with baseline count one. Therefore containment of \(F\), together with the vertex-cover condition, is exactly equivalent to weak improvement.

• Strict-improvement tests and residual-cover criterion — correct.

For baseline count zero, selecting either top alternative witnesses strict improvement. For a two-element top set with baseline count one, both alternatives must be selected. Saturated types cannot improve strictly. These cases exhaust the possible strict improvements and give at most \(2\tau\) tests.

For each test, deleting the required vertices outside \(F\) removes precisely the graph edges already covered by those selections. The necessity and sufficiency arguments for
\(|H|+\operatorname{vc}(G')\le k\)
are valid.

In the sufficiency direction, \(H\) and the residual cover are disjoint. Padding to size \(k\) is possible because \(k\le m\), preserves every weak top-count constraint, and preserves the designated strict constraint.

Kőnig’s theorem applies because every residual graph remains finite and bipartite. The stated matching equality and standard cover recovery justify both decision and committee construction.

• Running times and boundary cases — correct under the stated computational model.

After input preprocessing, each committee verification scans at most \(m\) alternatives per type. The verification and enumeration bounds correctly account for these scans; certificate handling and committee generation are absorbed because \(k\le m\) and \(\tau\ge1\).

Each residual graph has at most \(m\) vertices and \(\tau\) edges. Its left side has at most \(k\) vertices, so an augmenting-path algorithm performs at most \(k\) successful searches and one final unsuccessful search. Graph construction, cover recovery, and padding fit within the stated per-test bound. Multiplication by at most \(2\tau\) tests gives the displayed polynomial running time.

The conservative \(O(b)\) factor for bit operations is consistent with the stated word model and promised input validity.

Enumeration is polynomial for fixed \(k\), and for fixed \(m-k\). When \(k=m\), the only committee is \(A=D\), so strict improvement is impossible. When \(m=1\), this same boundary case applies. Dichotomous instances with two nonempty classes do not exist when \(m=1\).

• Minor issue and minimum repair.

Sections 1–5 repeatedly nest mathematical delimiters, for example \(k\)\). These are malformed and can prevent rendering. Replace each nested pair by a single pair. This is a purely expositional correction; no mathematical argument needs repair.

⟨structured verdict parsed — rendered above⟩