d4-conf-ijcai-2018-0499 (d4-conf-ijcai-2018-0499)

Given a finite candidate set \(X\), ranking types \(T\) with positive rational masses \(\mu_t\) summing to \(1\), and an assignment \(\alpha:X\to\{\mathrm{GOOD},\mathrm{BAD}\}\), does there exist, for each type \(t\), a distribution of its mass over its preference upsets \(A\), together with an upward-closed set \(W\) of approval-mass vectors, such that each candidate’s vector \(q_x\) belongs to \(W\) exactly when \(\alpha(x)=\mathrm{GOOD}\)?

Let \(X\) be a nonempty candidate set, \(m=|X|\), and let \(\alpha:X\to\{\mathrm{GOOD},\mathrm{BAD}\}\) be given.
A society is given by its support: the list \(T\) of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\), summing to \(1\). Each type specifies a complete preorder \(\succeq_t\) on \(X\), with ties allowed. Here \(\tau=|T|\) is the support size, not the number of possible types; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
For each type, let \(\mathcal U_t=\{A\subseteq X: y\in A,\ x\succeq_t y\Rightarrow x\in A\}\); both \(\varnothing\) and \(X\) are permitted, and tied candidates cannot be separated.
A mass allocation consists of real numbers \(z_{t,A}\geq0\) satisfying \(\sum_{A\in\mathcal U_t}z_{t,A}=\mu_t\). Define each candidate's approval-mass vector by \(q_x=(\sum_{A\in\mathcal U_t:x\in A}z_{t,A})_{t\in T}\).
A winning region is any set \(W\subseteq\prod_{t\in T}[0,\mu_t]\) upward closed in the coordinatewise order: \(q\in W\) and \(q'\geq q\) imply \(q'\in W\). It is shared by all candidates; empty and full regions are allowed, with no additional boundary or additive restrictions.

Is deciding whether there exist a mass allocation and a winning region satisfying \(q_x\in W\iff\alpha(x)=\mathrm{GOOD}\) for every \(x\in X\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

The discrete version, with one approval upset per individual and an arbitrary inclusion-upward-closed family of winning coalitions, is NP-hard; fixing all individual approval sets makes it polynomial-time solvable. [Source](https://www.ijcai.org/Proceedings/2018/0010.pdf)
No result settling this exact mass-allocation formulation was located in the literature search.

Result

The decision problem is polynomial-time solvable.

Let \(G=\alpha^{-1}(\mathrm{GOOD})\) and \(B=\alpha^{-1}(\mathrm{BAD})\). Write \(g\succ_t b\) when \(g\succeq_t b\) and \(b\not\succeq_t g\).

The exact feasibility criterion is:

\( \displaystyle \text{For every }(g,b)\in G\times B,\text{ there exists }t\in T\text{ such that }g\succ_t b. \)

If either label class is empty, this condition is vacuous, and feasibility follows by taking the winning region to be empty or full as appropriate.

1. Characterizing a winning region for fixed vectors

For any fixed allocation, a suitable upward-closed winning region exists if and only if no GOOD candidate’s vector is coordinatewise below a BAD candidate’s vector:

\( \displaystyle \forall(g,b)\in G\times B,\qquad q_g\not\leq q_b. \)

Necessity. If \(q_g\leq q_b\) and \(q_g\in W\), upward closure forces \(q_b\in W\), contradicting the prescribed labels.

Sufficiency. Define

\( \displaystyle W=\bigcup_{g\in G}\left\{q\in\prod_{t\in T}[0,\mu_t]:q\geq q_g\right\}. \)

This region is upward closed and contains every GOOD candidate’s vector. If it contained a BAD candidate’s vector \(q_b\), then \(q_b\geq q_g\) for some \(g\in G\), contrary to the condition. Thus it realizes exactly the prescribed labels.

2. Necessity of the stated criterion

Suppose the criterion fails. Then there are \(g\in G\) and \(b\in B\) such that no type strictly prefers \(g\) to \(b\).

Because each preorder is complete, this means \(b\succeq_t g\) for every \(t\in T\). By the definition of an approval upset, every \(A\in\mathcal U_t\) containing \(g\) also contains \(b\). Consequently, every mass allocation satisfies

\( \displaystyle q_{g,t}=\sum_{\substack{A\in\mathcal U_t\\g\in A}}z_{t,A}\leq\sum_{\substack{A\in\mathcal U_t\\b\in A}}z_{t,A}=q_{b,t}. \)

Hence \(q_g\leq q_b\). Section 1 shows that no suitable winning region exists.

3. Sufficiency: one allocation preserves every strict comparison

Assume the stated criterion holds.

For each type \(t\), list its nonempty indifference classes from best to worst as

\( \displaystyle E_{t,1},E_{t,2},\ldots,E_{t,k_t},\qquad 1\leq k_t\leq m. \)

Define the approval prefixes

\( \displaystyle A_{t,0}=\varnothing,\qquad A_{t,j}=\bigcup_{i=1}^{j}E_{t,i}\quad(1\leq j\leq k_t). \)

These are exactly the members of \(\mathcal U_t\): an upset must contain whole indifference classes, and containing any class forces it to contain every better class.

Allocate equal positive mass to all these prefixes:

\( \displaystyle z_{t,A_{t,j}}=\frac{\mu_t}{k_t+1}\qquad(0\leq j\leq k_t). \)

The masses are nonnegative and sum to \(\mu_t\), so this is a valid allocation. A candidate \(x\in E_{t,i}\) belongs precisely to the prefixes indexed by \(i,i+1,\ldots,k_t\). Therefore

\( \displaystyle q_{x,t}=\mu_t\frac{k_t-i+1}{k_t+1}. \)

Since \(\mu_t>0\), these approval masses strictly decrease as the indifference-class index increases. In particular,

\( \displaystyle g\succ_t b\quad\Longrightarrow\quad q_{g,t}>q_{b,t}. \)

For every \((g,b)\in G\times B\), the assumed criterion supplies such a type. Thus \(q_g\not\leq q_b\) for every GOOD–BAD pair. The winning region constructed in Section 1 completes the realization.

This proves both directions of the criterion.

4. Algorithm and running time

The decision algorithm is:

• Extract rank indices for each explicitly given preorder, assigning equal indices to tied candidates.
• For each \((g,b)\in G\times B\), check whether some type ranks \(g\) strictly above \(b\).
• Reject if any pair has no such type; otherwise accept.

The test uses at most \(m^2\tau\) rank comparisons. Under standard explicit encodings by ordered indifference classes or relation tables, preprocessing and testing take \(O(L+m^2\tau\log(m+1))\) bit operations. In particular, the conservative bound \(O(m^2\tau L)\) is polynomial in \(m,\tau,L\). The decision algorithm does not perform arithmetic on the masses; it uses only their promised positivity.

The constructive proof uses at most \(\tau(m+1)\) nonzero allocation entries. Each is rational with bit length \(O(L+\log(m+1))\), so a realizing allocation also has polynomial description length.

The cited paper establishes hardness for choosing one approval upset per individual. [Belahcene et al., Proposition 2](https://www.ijcai.org/Proceedings/2018/0010.pdf). Here, distributing each type’s positive mass across every prefix simultaneously preserves all its strict comparisons. That freedom makes the pairwise criterion sufficient.

⟨structured verdict parsed — rendered above⟩

Assessment: proved. The output resolves the exact mass-allocation problem. Its criterion, construction, and polynomial-time decision algorithm are correct. No major or minor mathematical issues were found.

• Fixed-vector characterization. Necessity correctly applies upward closure: if \(q_g\leq q_b\), accepting \(g\) forces acceptance of \(b\). For sufficiency, the proposed union of upper orthants lies within the required product domain, is upward closed, and contains every GOOD vector. Membership of a BAD vector would imply \(q_g\leq q_b\) for some GOOD candidate, exactly the excluded condition. This establishes both directions without imposing any extra restriction on the winning region.

• Necessity of the preference criterion. The quantifier negation is correct: failure produces a single pair \((g,b)\) for which every type lacks \(g\succ_t b\). Completeness implies \(b\succeq_t g\) for every such type, including when the candidates are tied. The upset definition then gives inclusion between the sets of approval upsets containing \(g\) and those containing \(b\). Nonnegativity of allocation entries justifies the coordinatewise inequalities. The fixed-vector characterization therefore rules out feasibility.

• Characterization of approval upsets. A finite complete preorder has nonempty indifference classes ordered from best to worst. An upset contains each class either wholly or not at all, and inclusion of a class forces inclusion of every better class. Thus the listed prefixes are exactly all permitted approval sets. Both the empty prefix and the full prefix are included.

• Allocation and critical calculation. There are exactly \(k_t+1\) prefixes, so allocating \(\mu_t/(k_t+1)\) to each gives positive entries summing to \(\mu_t\). A candidate in class \(i\) belongs to exactly \(k_t-i+1\) prefixes, verifying the stated formula for \(q_{x,t}\). For class indices \(i<j\), the difference between their approval masses is \(\mu_t(j-i)/(k_t+1)>0\). Consequently, the construction preserves every strict comparison simultaneously. The use of strictly positive type masses is justified by the input promise.

• Sufficiency and quantifiers. The same allocation works for all GOOD–BAD pairs. Each pair has a witnessing type by the assumed criterion, and that coordinate satisfies \(q_{g,t}>q_{b,t}\). Therefore \(q_g\not\leq q_b\) for every pair, permitting the single shared winning region already constructed. There is no unsupported exchange of pair-dependent and allocation-dependent choices.

• Edge cases and domain restrictions. Empty label classes are correctly handled by empty or full winning regions. A valid allocation still exists through the stated prefix construction. The case \(m=1\) necessarily has an empty label class. Types with one indifference class are also covered: their two prefixes produce equal approval masses for all candidates. Ties are never separated. The construction uses rational allocations, which are permitted because allocations may be arbitrary nonnegative reals; the outputs need not remain binary rationals.

• Algorithm and representation size. The algorithm tests exactly the proved criterion. It uses at most \(|G||B|\tau\leq m^2\tau\) rank comparisons. Under the stated explicit preorder encodings, the preprocessing and comparison bounds are consistent with \(O(L+m^2\tau\log(m+1))\) bit operations. The conservative bound \(O(m^2\tau L)\) is polynomial in the requested parameters. Division by \(k_t+1\leq m+1\) increases each rational entry’s encoding length by at most \(O(\log(m+1))\), validating the polynomial allocation description size.

• External citation. The cited Proposition 2 states NP-hardness for the discrete inverse sorting problem, whose model selects one approval upset per individual and an inclusion-upward-closed family of winning coalitions. The attribution is accurate. This citation supplies context; the continuous result is proved independently. [Belahcene et al., *Accountable Approval Sorting*](https://www.ijcai.org/Proceedings/2018/0010.pdf).

Required feedback: none. No additional lemma, hypothesis, or clarification is needed to verify the claimed polynomial-time result.

⟨structured verdict parsed — rendered above⟩