d4-conf-sagt-2022-0007 (d4-conf-sagt-2022-0007)

For the men-side variant, fix \(k\), all matching agents’ preferences other than \(\hat m\)'s, a target \(w^\star\), and an honest-mass distribution \(\mu\) over rankings \(\pi \in \mathcal R(W)\) with total mass \(1-\rho\) and support size \(\tau\), where \(\rho \in (0,1]\). Does there exist a report-mass distribution \(x_\pi \ge 0\), with \(\sum_{\pi \in \mathcal R(W)} x_\pi = \rho\), such that the Borda scores \(S(c)=\sum_{\pi \in \mathcal R(W)}(\mu_\pi+x_\pi)(k-\operatorname{pos}_\pi(c))\), ordered using the paper’s lexicographic tie-break, give \(\hat m\) the match \(w^\star\) under men-proposing Gale–Shapley?

Let \(M,W\) be disjoint sets with \(|M|=|W|=k\geq1\). The input specifies \(\hat m\in M\), \(w^\star\in W\), and strict complete preferences for all matching agents except \(\hat m\). Here \(k\) varies with the input; write \(m=k\) for the number of voting alternatives.
Let \(\mathcal R(W)\) be the strict complete rankings of \(W\). The honest society is given by its support: a list of \(\tau\) rankings with positive binary-rational masses \(\mu_\pi\), totaling \(1-\rho\), where the input \(\rho\in\mathbb Q\cap(0,1]\). Unlisted masses are zero; when \(\rho=1\), the support is empty. Thus \(\tau\) is the support size, not \(m!\).
A report distribution may assign arbitrary real masses \(x_\pi\geq0\) to any rankings in \(\mathcal R(W)\), subject to \(\sum_\pi x_\pi=\rho\), with no restriction on its support.
Define \(S(c)=\sum_{\pi\in\mathcal R(W)}(\mu_\pi+x_\pi)(k-\operatorname{pos}_\pi(c))\), with positions numbered from \(1\) through \(k\). Rank women by decreasing score, resolving equal scores by a fixed lexicographic priority on their input labels; this strict order becomes \(\hat m\)'s preference list.
The decision problem asks whether some report distribution makes men-proposing Gale–Shapley match \(\hat m\) to \(w^\star\). Let \(L\) denote the total binary input length; state running times in \(m,\tau,L\).

Is this continuous men-side coalitional manipulation problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

The discrete version with indivisible, unweighted voters is \(\mathrm{NP}\)-complete even with two manipulators; its single-manipulator restriction is polynomial-time solvable. [Source](https://arxiv.org/html/2207.04912v2)
No result settling this exact continuous problem was located in the literature search.

Result. The continuous men-side coalitional manipulation problem is in \(\mathrm{P}\). An exact algorithm uses at most \(m\) Gale–Shapley runs and one rational linear program with \(m^2+1\) variables. The proof covers arbitrary real report masses and the specified lexicographic tie-breaking.

1. Reducing matching success to score comparisons.

Fix all preferences except those of \(\hat m\). For each strict complete ranking \(R\) of \(W\), let \(f(R)\) be the woman matched to \(\hat m\) by men-proposing Gale–Shapley. Define the set of attainable partners
\[ \]
\(A=\{f(R):R\in\mathcal R(W)\}.\)

We use the standard proposer-strategyproofness theorem: for any strict complete rankings \(R,T\), with all other preferences fixed, \(f(R)\) is weakly preferred to \(f(T)\) according to \(R\). This is the dominant-strategy property of the men-optimal matching procedure. Its hypotheses hold here: matching is one-to-one, preferences are strict and complete, and the designated agent belongs to the proposing side. See [Roth, Theorem 5](https://kylewoodward.com/blog-data/pdfs/references/roth-mathematics-of-operations-research-1982A.pdf).

Lemma 1. For every ranking \(R\), \(f(R)\) is the highest-ranked member of \(A\) according to \(R\).

*Proof.* Let \(a\) be the highest-ranked member of \(A\) according to \(R\). By the definition of \(A\), some ranking \(T\) satisfies \(f(T)=a\). Strategyproofness, treating \(R\) as \(\hat m\)'s true preference, implies that \(f(R)\) is weakly preferred to \(a\) according to \(R\). But \(f(R)\in A\), and \(a\) is the unique highest-ranked member of \(A\). Therefore \(f(R)=a\). \(\square\)

Consequently,
\[ \]
\(f(R)=w^\star\quad\Longleftrightarrow\quad w^\star\in A\ \text{and}\ w^\star\text{ precedes every member of }A\setminus\{w^\star\}\text{ in }R.\)

The set \(A\) can be computed without enumerating rankings. For each \(c\in W\), choose a ranking \(R_c\) placing \(c\) first, with the remaining women in any fixed order. Lemma 1 gives
\[ \]
\(c\in A\quad\Longleftrightarrow\quad f(R_c)=c.\)

Thus \(m\) Gale–Shapley runs compute \(A\). Each run takes \(O(m^2)\) operations using precomputed preference positions, so this stage takes \(O(m^3)\) operations.

If \(w^\star\notin A\), the answer is immediately no.

2. An exact polynomial-size description of continuous reports.

Define the honest scores
\[ \]
\(h_c=\sum_{\pi\text{ in the honest support}}\mu_\pi\bigl(m-\operatorname{pos}_\pi(c)\bigr).\)

These require \(O(\tau m)\) rational arithmetic operations.

For a report distribution, define its position masses by
\[ \]
\(y_{cj}=\sum_{\pi:\operatorname{pos}_\pi(c)=j}x_\pi,\qquad c\in W,\quad 1\leq j\leq m.\)

They satisfy
\[ \]
\(y_{cj}\geq0,\qquad \sum_{j=1}^m y_{cj}=\rho\quad(c\in W),\qquad \sum_{c\in W}y_{cj}=\rho\quad(1\leq j\leq m).\)

Its total score for \(c\) is
\[ \]
\(S_c(y)=h_c+\sum_{j=1}^m(m-j)y_{cj}.\)

Lemma 2. Every nonnegative matrix satisfying these row and column sums comes from a report distribution of total mass \(\rho\). Such a distribution can use at most \(m^2\) rankings.

*Proof.* We give the decomposition argument explicitly. Start with the residual matrix \(Z=y\), whose row and column sums all equal \(r=\rho>0\). Construct a bipartite graph between women and positions, joining \(c\) to \(j\) exactly when \(Z_{cj}>0\).

For any set \(U\) of women, let \(N(U)\) be its neighboring positions. All mass in rows \(U\) lies in columns \(N(U)\), so
\[ \]
\(|U|r=\sum_{c\in U}\sum_{j\in N(U)}Z_{cj}\leq\sum_{j\in N(U)}\sum_{c\in W}Z_{cj}=|N(U)|r.\)

Since \(r>0\), Hall’s condition holds. Therefore there is a perfect matching, represented by a permutation matrix \(P\), all of whose selected entries are positive. Set
\[ \]
\(\alpha=\min\{Z_{cj}:P_{cj}=1\}>0.\)

Subtract \(\alpha P\). The residual remains nonnegative, all row and column sums become \(r-\alpha\), and at least one positive entry becomes zero. No zero entry becomes positive.

Repeat whenever the common residual sum is positive. There are at most \(m^2\) positive entries initially, so the procedure terminates within \(m^2\) steps. A nonnegative residual with zero row sums is the zero matrix. Hence
\[ \]
\(y=\sum_{\ell=1}^{t}\alpha_\ell P^\ell,\qquad t\leq m^2,\qquad \sum_{\ell=1}^{t}\alpha_\ell=\rho.\)

Each \(P^\ell\) specifies one strict complete ranking. Assign that ranking mass \(\alpha_\ell\), combining masses if necessary. This gives exactly the required position masses and total report mass. \(\square\)

Thus the matrix formulation describes attainable scores exactly; it is not merely a relaxation.

3. Handling tie-breaking by one linear program.

Assume \(w^\star\in A\). Partition its attainable competitors into
\[ \]
\(B_{\mathrm{weak}}=\{b\in A\setminus\{w^\star\}:w^\star\text{ has priority over }b\},\)
\[ \]
\(B_{\mathrm{strict}}=\{b\in A\setminus\{w^\star\}:b\text{ has priority over }w^\star\}.\)

The score-induced ranking places \(w^\star\) above all these competitors exactly when
\[ \]
\(S_{w^\star}(y)-S_b(y)\geq0\quad(b\in B_{\mathrm{weak}}),\)
\[ \]
\(S_{w^\star}(y)-S_b(y)>0\quad(b\in B_{\mathrm{strict}}).\)

Introduce one variable \(\varepsilon\). Solve the rational linear program that maximizes \(\varepsilon\), subject to
\[ \]
\(y_{cj}\geq0,\qquad \sum_j y_{cj}=\rho,\qquad \sum_c y_{cj}=\rho,\)
\[ \]
\(0\leq\varepsilon\leq1,\)
\[ \]
\(S_{w^\star}(y)-S_b(y)\geq0\quad(b\in B_{\mathrm{weak}}),\)
\[ \]
\(S_{w^\star}(y)-S_b(y)\geq\varepsilon\quad(b\in B_{\mathrm{strict}}).\)

Reject if this program is infeasible. Otherwise, accept exactly when its optimum is strictly positive, using exact rational comparison.

Lemma 3. This acceptance rule is equivalent to the existence of a successful report distribution.

*Proof.* Suppose a successful distribution exists, and form its matrix \(y\). Lemma 1 implies that its induced ranking places \(w^\star\) above every other member of \(A\). Hence all the required weak and strict score inequalities hold.

If \(B_{\mathrm{strict}}\) is nonempty, choose
\[ \]
\(\varepsilon=\min\bigl(\{1\}\cup\{S_{w^\star}(y)-S_b(y):b\in B_{\mathrm{strict}}\}\bigr)>0.\)

If \(B_{\mathrm{strict}}\) is empty, choose \(\varepsilon=1\). Either choice gives a feasible solution with positive objective.

Conversely, suppose the program has a feasible solution with \(\varepsilon>0\). Its inequalities and the priority rule place \(w^\star\) above every other member of \(A\). Lemma 2 supplies a report distribution realizing \(y\). Lemma 1 then implies that Gale–Shapley matches \(\hat m\) to \(w^\star\).

Finally, every feasible entry satisfies \(0\leq y_{cj}\leq\rho\), and \(0\leq\varepsilon\leq1\). The feasible set is closed and bounded, so a feasible program attains its optimum. Therefore checking whether that optimum is positive is exact. \(\square\)

4. Running time and witness size.

The algorithm consists of:

• Computing honest scores in \(O(\tau m)\) rational arithmetic operations.
• Computing \(A\) in \(O(m^3)\) matching operations.
• Solving one rational linear program with \(m^2+1\) variables, \(2m\) row and column equalities, and \(O(m^2)\) inequalities.

The honest scores have binary encoding length \(O(L+\log m)\): a common denominator can be chosen as the product of the input mass denominators, whose total bit length is bounded by the input length, and each score lies between zero and \(m-1\). The linear program’s coefficients therefore have bit length \(O(L+\log m)\). Its sparse encoding has total length
\[ \]
\(B=O\bigl(m^2(L+\log m)\bigr).\)

Let \(T_{\mathrm{LP}}(n,q,B)\) denote the bit running time of a polynomial-time exact rational linear-programming algorithm, with \(n\) variables, \(q\) constraints, and encoding length \(B\). A conservative total bound is
\[ \]
\(O\bigl((\tau m+m^3)(L+\log m)^2\bigr)+T_{\mathrm{LP}}\bigl(m^2+1,O(m^2),O(m^2(L+\log m))\bigr).\)

This is polynomial in \(m,\tau,L\). In particular, no enumeration of the \(m!\) rankings occurs.

On a yes instance, a rational optimal solution of polynomial encoding length exists by the standard rational-polytope vertex bounds. The decomposition in Lemma 2 then produces a successful rational report distribution supported on at most \(m^2\) rankings. Thus arbitrary real masses do not require irrational witnesses.

For \(m=1\), the answer is always yes. For \(\rho=1\), the honest scores vanish and the same algorithm applies with empty honest support.

The exact continuous problem is therefore polynomial-time solvable.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument establishes a polynomial-time algorithm for the exact continuous problem, including arbitrary real report masses and lexicographic tie-breaking. I found no major or minor mathematical issues.

1. Strategyproofness and attainable partners

The strategyproofness statement used is correct: fixing every other agent’s reported preference, a proposing man cannot obtain a partner strictly better according to his true ranking by reporting another ranking. This is the content of the cited [Roth, Theorem 5](https://kylewoodward.com/blog-data/pdfs/references/roth-mathematics-of-operations-research-1982A.pdf).

Its hypotheses are satisfied: the market is balanced and one-to-one, preferences are strict and complete, and \(\hat m\) belongs to the proposing side. The theorem applies for every choice of the designated man’s true ranking; it does not require the other agents’ fixed preferences to have any additional property.

Lemma 1 is valid. For any ranking \(R\), the highest-ranked element \(a\) of \(A\) is realized by some report \(T\). Strategyproofness compares \(f(R)\) and \(f(T)=a\) according to \(R\). Since \(f(R)\) itself belongs to \(A\), strictness forces \(f(R)=a\).

There is no circularity: \(A\) is first defined as the range over all rankings, and the lemma subsequently provides a way to compute that range.

The characterization of success follows directly. Likewise, testing each woman \(c\) using a ranking that puts \(c\) first correctly determines membership in \(A\):

• If \(c\in A\), Lemma 1 forces \(f(R_c)=c\).
• If \(f(R_c)=c\), membership follows from the definition of \(A\).

Thus the claimed \(m\) Gale–Shapley runs suffice. Complete preferences and equal market sizes ensure that \(f(R)\) is always a woman, so unmatched outcomes need no additional treatment.

2. Exact representation of continuous reports

The position-mass equations are necessary. Each ranking assigns every woman exactly one position and fills every position exactly once. Consequently, both the row sums and column sums equal the total report mass \(\rho\).

The score expression is also exact: a woman occupying position \(j\) receives contribution \(m-j\), and aggregating these contributions depends only on the position masses.

Lemma 2 is valid for arbitrary real entries. At each positive-residual stage, the displayed mass inequality proves Hall’s condition for every subset of women. Both bipartition classes have size \(m\), so Hall’s theorem supplies the required perfect matching.

The subtraction step preserves all necessary invariants:

• The selected entries are positive, so \(\alpha>0\).
• Subtracting their minimum preserves nonnegativity.
• Exactly one entry per row and column is reduced by \(\alpha\).
• At least one positive entry disappears, and none is created.

The common residual sum remains nonnegative. If it remains positive, the argument can repeat. Since each iteration strictly decreases the number of positive entries, termination within \(m^2\) iterations is justified. A nonnegative residual with zero row sums is zero.

The resulting permutation matrices specify strict complete rankings, and their coefficients total \(\rho\). This proves sufficiency, rather than merely providing a relaxation. No integrality or rationality assumption is used in this equivalence.

3. Tie-breaking and the linear program

The competitor partition uses the priority rule correctly:

• When \(w^\star\) wins the tie against \(b\), a nonnegative score difference suffices.
• When \(b\) wins the tie, the score difference must be strictly positive.

Only competitors in \(A\) require comparisons, by Lemma 1. The relative positions of women outside \(A\) impose no further condition on the resulting partner.

Lemma 3 is valid. If a successful report exists, the finitely many required strict differences have a positive minimum. Capping this minimum at \(1\) gives a feasible positive value of \(\varepsilon\). When there are no strict competitors, choosing \(\varepsilon=1\) correctly makes acceptance depend only on feasibility of the weak inequalities.

Conversely, any feasible solution with positive \(\varepsilon\) enforces every necessary strict comparison. Lemma 2 realizes its position masses as a report distribution, and Lemma 1 then establishes the desired match.

The optimization handles strict inequalities exactly. Every entry satisfies \(0\leq y_{cj}\leq\rho\), and \(\varepsilon\) is bounded between \(0\) and \(1\). Hence the feasible set is closed and bounded, and a nonempty feasible set attains its maximum. Exact comparison of that maximum with zero is therefore legitimate.

4. Running time and rational witnesses

The variable and constraint counts are correct: there are \(m^2+1\) variables, \(2m\) marginal equalities, \(m^2\) nonnegativity inequalities, two bounds on \(\varepsilon\), and at most \(m-1\) competitor inequalities.

The honest-score encoding bound is justified. The product of the input mass denominators has bit length bounded by their total input length. Together with the score bound between zero and \(m-1\), this gives bit length \(O(L+\log m)\). The coefficients, right-hand sides, and sparse indexing consequently fit the stated encoding bound.

The stated preprocessing bound is conservative and polynomial. The rational LP has polynomial dimension and encoding length, so polynomial-time exact rational linear programming applies. Boundedness supplies the required finite optimum whenever the program is feasible.

The witness claim also satisfies the standard rational-polytope bounds: a nonempty bounded rational feasible polytope has an optimal rational vertex with polynomial encoding length. Applying the stated decomposition to such a matrix gives rational masses and at most \(m^2\) rankings. Thus allowing arbitrary real masses does not introduce an unresolved irrational-witness issue.

5. Edge cases and assignment coverage

For \(m=1\), the sole woman is necessarily the designated man’s partner. For \(\rho=1\), the support is empty and the honest scores are zero, exactly as required. Empty strict-competitor sets and infeasible LPs are explicitly handled.

The output resolves the assigned continuous problem and states running times in \(m,\tau,L\). It does not rely on enumerating rankings or transferring hardness from the discrete problem. No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩