d4-conf-aaai-2018-0923 (d4-conf-aaai-2018-0923)

Given a finite alternative set \(A\), a finite-support rational distribution \(\mu\) over complete rankings of \(A\), a target \(c\), and rational pair thresholds \(\lambda_{\{a,b\}}\in[0,1]\), choose masses \(x_{t,R}\ge 0\) assigning each ranking type \(t\)'s mass among partial orders \(R\) consistent with \(t\), with \(\sum_R x_{t,R}=\mu_t\). Let \(\nu_R=\sum_t x_{t,R}\); require at least \(\lambda_{\{a,b\}}\) total mass to report \(a\) and \(b\) as comparable for every pair. Is there such an assignment for which \(c\) uniquely minimizes maximum plurality regret, where regret is maximized over all completions that distribute each \(\nu_R\) among complete rankings extending \(R\)?

Let \(A\) contain \(m\ge 2\) alternatives, with target \(c\in A\). A society is given by its support: the list of \(\tau\) distinct strict complete rankings \(t\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Each unordered pair has a binary-rational threshold \(\lambda_{\{a,b\}}\in[0,1]\); let \(L\) be the total input bit length.
For each type \(t\), distribute its mass using real variables \(x_{t,R}\ge0\) over all strict partial orders \(R\subseteq t\), including the empty order, with \(\sum_{R\subseteq t}x_{t,R}=\mu_t\). Set \(\nu_R=\sum_t x_{t,R}\), taking incompatible assignments as zero.
Require \(\sum_{R:\,aRb\text{ or }bRa}\nu_R\ge\lambda_{\{a,b\}}\) for every unordered pair; comparability includes all relations implied by transitivity.
A completion assigns real masses \(y_{R,r}\ge0\) to strict complete rankings \(r\) extending \(R\), with \(\sum_{r\supseteq R}y_{R,r}=\nu_R\). Completions need only respect reported orders, without preserving the original type distribution. Let \(s(a,y)\) denote the mass-weighted plurality score and define \(\operatorname{MR}(a,\nu)=\max_y\bigl(\max_{b\in A}s(b,y)-s(a,y)\bigr)\).
The decision problem asks whether an admissible assignment satisfies \(\operatorname{MR}(c,\nu)<\operatorname{MR}(a,\nu)\) for every \(a\ne c\); ties do not give a unique winner.

Is this continuous plurality manipulative-elicitation problem with pair thresholds solvable in time polynomial in \(m,\tau,L\), or is it \(\mathsf{NP}\)-hard?

For explicitly listed discrete voters and integer pair limits, the corresponding unique-winner problem is \(\mathsf{NP}\)-complete; without pair limits, discrete plurality manipulative elicitation is polynomial-time solvable. [Source](https://arxiv.org/pdf/1711.03948)
No result settling the exact divisible-mass problem above was identified in the literature search.

The divisible-mass problem is polynomial-time solvable. It admits an exact reduction to \(m(m-1)\) rational linear programs, each of polynomial size.

1. Plurality regret depends only on possible first alternatives. For a strict partial order \(R\), define
\[ M(R)=\{a\in A:\text{there is no }b\in A\text{ with }bRa\}. \]
These are precisely the alternatives that can appear first in a completion: every first alternative must belong to \(M(R)\), and any member of \(M(R)\) can be placed first, followed by a topological ordering of the remaining alternatives.

Define the possible-first mass and forced-first mass of \(a\) by
\[ U_a=\sum_{R:\,a\in M(R)}\nu_R, \qquad F_a=\sum_{R:\,M(R)=\{a\}}\nu_R. \]

For distinct \(a,b\), the maximum contribution per unit mass of \(R\) to \(s(b,y)-s(a,y)\) is:

• \(1\) if \(b\in M(R)\), by placing \(b\) first;
• \(-1\) if \(M(R)=\{a\}\), since \(a\) must appear first;
• \(0\) otherwise, by placing a member of \(M(R)\setminus\{a\}\) first.

Completion choices for different reported orders are independent. Consequently,
\[ \max_y\bigl(s(b,y)-s(a,y)\bigr)=U_b-F_a. \]
Including \(b=a\), whose score difference is zero, gives
\[ \operatorname{MR}(a,\nu) = \max\left\{0,\ \max_{b\ne a}U_b-F_a\right\}. \tag{1} \]

2. We may saturate every reported order without changing regret. Let \(o_t\) be the first alternative of type \(t\). Every order \(R\subseteq t\) has \(o_t\in M(R)\).

For any \(S\subseteq A\) containing \(o_t\), define
\[ R_t(S)=\{(a,b):a\text{ precedes }b\text{ in }t,\ b\notin S\}. \tag{2} \]
This is a strict partial order. Indeed, it is irreflexive, and if \(aR_t(S)b\) and \(bR_t(S)d\), then \(a\) precedes \(d\) in \(t\) and \(d\notin S\), so \(aR_t(S)d\).

Its maximal set is exactly \(S\): no element of \(S\) has an incoming relation, while every \(b\notin S\) has \(o_tR_t(S)b\).

Moreover, if \(S=M(R)\) and \(R\subseteq t\), then
\[ R\subseteq R_t(S). \]
For an original relation \(aRb\), the alternative \(b\) is not maximal, so that relation appears in (2).

Thus replacing each assigned order \(R\) by \(R_t(M(R))\):

• preserves its possible first alternatives and whether its first alternative is forced;
• hence preserves every regret by (1);
• weakly increases comparability for every pair.

Because all pair constraints are lower bounds, this replacement preserves admissibility. Therefore, restricting attention to orders of the form \(R_t(S)\) loses no successful assignments.

3. These distributions have an exact polynomial-size description. For each type \(t\), introduce variables
\[ z_t=\text{mass assigned to }S=\{o_t\}, \]
and, for each \(a\ne o_t\),
\[ q_{t,a}=\text{mass assigned to sets }S\text{ containing }a. \]
Put \(v_t=\mu_t-z_t\). The exact constraints describing these marginals are
\[ 0\le z_t\le\mu_t, \qquad 0\le q_{t,a}\le v_t\quad(a\ne o_t), \qquad \sum_{a\ne o_t}q_{t,a}\ge v_t. \tag{3} \]

Necessity follows because the mass \(v_t\) is assigned to sets containing at least one alternative besides \(o_t\).

For sufficiency, if \(v_t=0\), assign all mass to \(\{o_t\}\). Otherwise, set \(p_a=q_{t,a}/v_t\). The conditions in (3) give
\[ p\in Q_k = \left\{p\in[0,1]^k:\sum_{i=1}^k p_i\ge1\right\}, \qquad k=m-1\ge1. \]

We claim that \(Q_k\) is the convex hull of the incidence vectors of nonempty subsets.

To prove this, consider a point with a fractional coordinate. If its coordinate sum is strictly greater than \(1\), a sufficiently small positive and negative perturbation of that coordinate stays in \(Q_k\), so the point is not a vertex. If its coordinate sum equals \(1\) and it has at least two fractional coordinates, opposite perturbations of those two coordinates preserve the sum and again show that it is not a vertex. Exactly one fractional coordinate is impossible when the sum equals \(1\), because all other coordinates are integers.

Thus every vertex of \(Q_k\) is an incidence vector of a nonempty subset. Since \(Q_k\) is a nonempty bounded polytope, it is the convex hull of its vertices. Decomposing \(p\) accordingly, assigning total mass \(v_t\) to those nonempty extra subsets, and adding mass \(z_t\) to \(\{o_t\}\) realizes all the specified marginals.

Now let \(\ell_t(a,b)\) denote the lower-ranked member of the pair \(\{a,b\}\) in \(t\). This alternative is never \(o_t\). By (2), the pair is comparable exactly when \(\ell_t(a,b)\notin S\). Its total comparable mass is therefore
\[ 1-\sum_t q_{t,\ell_t(a,b)}. \]
The pair constraints become the linear inequalities
\[ \sum_t q_{t,\ell_t(a,b)} \le 1-\lambda_{\{a,b\}} \qquad\text{for every unordered pair }\{a,b\}. \tag{4} \]

The quantities needed for regret are also linear:
\[ U_a = \sum_{t:\,o_t=a}\mu_t + \sum_{t:\,o_t\ne a}q_{t,a}, \qquad F_a=\sum_{t:\,o_t=a}z_t. \tag{5} \]

Equations (3)–(5) are an exact description: every admissible assignment can be saturated to yield such variables, and every solution yields an admissible assignment using the orders \(R_t(S)\).

4. The strict unique-winner condition reduces to polynomially many linear programs. Enumerate all ordered pairs of distinct alternatives \((p,q)\). In the linear program for \((p,q)\), impose
\[ U_p\ge U_a\quad(a\in A), \qquad U_q\ge U_a\quad(a\ne p). \tag{6} \]
Thus \(p\) has greatest possible-first mass and \(q\) has greatest possible-first mass among the remaining alternatives. Ties are permitted.

For this fixed pair, define \(\kappa(p)=q\) and \(\kappa(a)=p\) for \(a\ne p\), and set
\[ d_a=U_{\kappa(a)}-F_a. \]
By (1) and (6),
\[ \operatorname{MR}(a,\nu)=\max\{0,d_a\}. \tag{7} \]

Add variables \(h,\varepsilon\), maximize \(\varepsilon\), and impose (3)–(6) together with
\[ 0\le h\le1,\qquad 0\le\varepsilon\le1, \qquad h\ge d_c, \qquad d_a\ge h+\varepsilon\quad(a\ne c). \tag{8} \]

We prove that the original instance is a yes-instance exactly when at least one of these linear programs has optimum strictly greater than zero.

Suppose first that a feasible solution has \(\varepsilon>0\). The distribution reconstructed in Section 3 is admissible. Since \(h\ge0\) and \(h\ge d_c\), equation (7) gives
\[ \operatorname{MR}(c,\nu)\le h. \]
For every \(a\ne c\), we have \(d_a\ge h+\varepsilon>0\), so
\[ \operatorname{MR}(a,\nu)=d_a \ge h+\varepsilon >\operatorname{MR}(c,\nu). \]
Hence \(c\) is the unique winner.

Conversely, suppose an admissible assignment makes \(c\) the unique winner. Saturate it as in Section 2, preserving all regrets, and extract its variables from Section 3. Choose \(p,q\) with greatest and second-greatest values of \(U_a\), breaking ties arbitrarily. Conditions (6) hold.

Set
\[ h=\operatorname{MR}(c,\nu), \qquad \varepsilon= \min_{a\ne c} \bigl(\operatorname{MR}(a,\nu)-\operatorname{MR}(c,\nu)\bigr)>0. \]
Every regret lies in \([0,1]\), so these choices respect the bounds in (8). Every rival has strictly positive regret, and therefore (7) gives \(d_a=\operatorname{MR}(a,\nu)\) for every \(a\ne c\). Also \(d_c\le h\). Thus all inequalities in (8) hold with positive \(\varepsilon\).

This proves the equivalence, including the strict treatment of ties.

5. Bit complexity and conclusion. There are \(m(m-1)\) linear programs. Each has \(O(\tau m+m)\) variables, if \(U_a,F_a\) are introduced explicitly, and \(O(\tau m+m^2)\) constraints. All coefficients and right-hand sides are rational and have bit lengths polynomial in \(L,m,\tau\).

Each feasible program has a finite attained optimum: the mass variables are bounded, and \(h,\varepsilon\) are bounded explicitly. Standard polynomial-time algorithms for rational linear programming can determine feasibility and compare the exact optimum with zero. Accepting precisely when some optimum is positive therefore gives an algorithm polynomial in \(m,\tau,L\). No numerical tolerance or rationality assumption on the originally permitted assignments is needed.

The convex decomposition in Section 3 uses the ability to divide each type’s mass among several reported orders. An individual discrete voter cannot be divided this way, so this conclusion is consistent with the discrete hardness result in [Dey, Theorem 4.2](https://arxiv.org/pdf/1711.03948).

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated continuous problem. The reduction is correct, handles strict uniqueness exactly, and yields an algorithm polynomial in \(m,\tau,L\). I found no major or minor mathematical issues requiring repair.

1. Regret formula

The characterization of \(M(R)\) is correct for finite strict partial orders: precisely its members can appear first in a linear extension.

For distinct \(a,b\), the three contribution cases are exhaustive and correct:

• If \(b\in M(R)\), putting \(b\) first attains contribution \(1\).
• If \(M(R)=\{a\}\), every completion contributes \(-1\).
• Otherwise, \(b\notin M(R)\) and some possible first alternative differs from \(a\); putting that alternative first attains contribution \(0\).

Completion choices are independent across reported orders under the task’s definition. In particular, they need not preserve the original type distribution. Therefore the displayed identity
\[ \max_y\bigl(s(b,y)-s(a,y)\bigr)=U_b-F_a \]
is valid.

Taking the maximum over the finitely many competitors commutes with maximizing over completions. Including \(b=a\) correctly supplies the zero term in equation (1).

Finding: Correct.

2. Saturation of reported orders

Every order \(R\subseteq t\) indeed has \(o_t\in M(R)\): no alternative precedes \(o_t\) in \(t\), so no compatible relation can point into it.

The proof that \(R_t(S)\) is irreflexive and transitive is valid. Its possible-first set is exactly \(S\):

• Elements of \(S\) have no incoming relations.
• Every element outside \(S\) has an incoming relation from \(o_t\).

For \(S=M(R)\), every relation \(aRb\) has \(b\notin S\), establishing the claimed inclusion \(R\subseteq R_t(S)\).

Consequently, saturation preserves both possible-first and forced-first masses while increasing comparability. This is the correct direction for all pair constraints, which are lower bounds.

The replacement can be performed separately for each type’s assigned mass. Aggregating identical resulting orders does not affect regret, since their possible-first sets are identical.

Finding: Correct; the restriction preserves existence of a successful assignment.

3. Exact description by marginals

The necessity of equation (3) is correct. The singleton mass \(z_t\) contributes nothing to any \(q_{t,a}\), while every set receiving the remaining mass contains at least one extra alternative.

The sufficiency argument is complete:

• The case \(v_t=0\) is explicitly handled.
• For \(v_t>0\), the normalized marginals belong to \(Q_k\).
• When the coordinate sum exceeds \(1\), a fractional coordinate admits a sufficiently small two-sided perturbation.
• When the sum equals \(1\), two fractional coordinates admit opposite perturbations.
• Exactly one fractional coordinate cannot coexist with an integral coordinate sum and all remaining coordinates integral.

Thus every vertex is a nonzero binary incidence vector. The stated bounded-polytope theorem applies: \(Q_k\) is nonempty, bounded, and defined by finitely many linear inequalities. Its vertex decomposition gives precisely the required distribution over nonempty extra subsets.

For a pair, its lower-ranked member in \(t\) is never \(o_t\). Equation (2) makes that pair comparable exactly when this member is outside \(S\). Therefore equation (4) correctly counts comparability, including transitive relations.

Equation (5) also correctly counts both relevant masses. In particular, a singleton possible-first set must be \(\{o_t\}\), so the expression for \(F_a\) omits no possibilities.

Finding: Correct; there is no missing constraint on the marginals.

4. Enumeration and strict uniqueness

Conditions (6) correctly select a greatest and a second-greatest possible-first mass. They allow ties, and every possible vector of \(U_a\) is covered by at least one enumerated ordered pair.

For \(a=p\), the largest competing mass is \(U_q\). For \(a\ne p\), it is \(U_p\). This remains true when masses tie. Hence equation (7) is valid.

Both implications involving equation (8) are correct:

• A feasible solution with positive \(\varepsilon\) bounds the target’s regret above by \(h\), while every rival’s regret is at least \(h+\varepsilon\).
• For a successful assignment, the chosen \(h\) is its target regret, and the minimum rival gap is positive because there are finitely many rivals. Every rival then has positive regret, justifying the removal of the zero truncation for those rivals.

All regrets lie in \([0,1]\), so the bounds on \(h\) and \(\varepsilon\) exclude no successful assignment.

Finding: Correct; zero regret and tied possible-first masses create no gap.

5. Polynomial time and exact arithmetic

The claimed numbers of programs, variables, and constraints are correct. Equations (5), when the auxiliary quantities are explicit variables, add only linearly many equalities.

The input coefficients are rational. Summing input masses and forming \(1-\lambda_{\{a,b\}}\) requires only polynomial bit length. No enumeration of all rankings or all reported partial orders is needed to construct the programs.

Each feasible program has a compact feasible region: the mass variables and optimization variables are bounded, and any explicit \(U_a,F_a\) variables are fixed by bounded linear expressions. The optimum is therefore attained.

The invoked rational linear-programming theorem applies to these explicitly represented rational programs and supplies polynomial-time feasibility and exact optimization. Comparing the optimum with zero is valid even if a positive optimum is very small. The original allowance of arbitrary real assignments causes no difficulty because the equivalence is established over real feasible points.

The convex decomposition serves to establish existence; the decision algorithm does not require enumerating all its potential subsets.

Finding: Correct.

6. Edge cases and cited comparison

The argument covers \(m=2\), where \(k=1\); the empty reported order, corresponding to \(S=A\); singleton possible-first sets; zero residual mass; and thresholds equal to either endpoint.

The final literature comparison accurately identifies discrete plurality hardness in [Dey, Theorem 4.2](https://arxiv.org/pdf/1711.03948). That comparison is contextual and is not needed for the continuous algorithm’s correctness.

Actionable feedback

No mathematical repair or additional clarification is required. The output establishes polynomial-time solvability for the exact divisible-mass problem as stated.

⟨structured verdict parsed — rendered above⟩