d4-conf-ijcai-2019-0902 (d4-conf-ijcai-2019-0902)

Given finite types \(T\), item categories \(A\) with graph \(H\), rational type masses \(\mu_t>0\) summing to \(1\), rational per-capita supplies \(q_a>0\) summing to \(1\), valuations \(v_t(a)\), and directed influence coefficients \(\alpha_{s,t}\), does there exist \(x_{t,a}\ge 0\) with \(\sum_a x_{t,a}=\mu_t\) and \(\sum_t x_{t,a}=q_a\) such that no positive-mass assignments \(x_{t,a},x_{s,b}>0\) satisfy both \(U_t(b;x)>U_t(a;x)\) and \(U_s(a;x)>U_s(b;x)\), where \(U_t(a;x)=v_t(a)+\sum_s\alpha_{s,t}\frac{\sum_{c\in N_H(a)}x_{s,c}}{\mu_s}\)?

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=|A|\geq1\) item categories, a simple undirected compatibility graph \(H\) on \(A\), and positive binary rational supplies \(q_a\) with \(\sum_a q_a=1\). Intrinsic valuations satisfy \(v_t(a)\in\mathbb{Q}_{\geq0}\); directed influence coefficients satisfy \(\alpha_{s,t}\in\mathbb{Q}\), with \(\alpha_{t,t}=0\), and need not be symmetric.
An allocation is a real matrix \(x\geq0\) satisfying \(\sum_a x_{t,a}=\mu_t\) and \(\sum_t x_{t,a}=q_a\). Define \(U_t(a;x)=v_t(a)+\sum_{s\in T}\alpha_{s,t}\bigl(\sum_{c\in N_H(a)}x_{s,c}\bigr)/\mu_s\), where \(N_H(a)\) is the neighborhood of \(a\).
Call \(x\) pairwise stable if there are no \(t,s\in T\) and \(a,b\in A\) with \(x_{t,a}>0\), \(x_{s,b}>0\), \(U_t(b;x)>U_t(a;x)\), and \(U_s(a;x)>U_s(b;x)\). Exchanges are between infinitesimal individuals, so these comparisons keep \(x\) fixed; ties do not block.
Is deciding whether a pairwise stable allocation exists solvable in polynomial time in \(m\), \(\tau\), and the total binary input length \(L\), or is it \(\mathrm{NP}\)-hard?
For finite agents receiving distinct indivisible items, existence of an allocation admitting no swap that strictly improves both participants' utilities after the swap is \(\mathrm{NP}\)-complete. [Massand–Simon, 2019](https://www.ijcai.org/proceedings/2019/0070.pdf)
The later discrete treatment also establishes \(\mathrm{NP}\)-completeness for each fixed coalition bound \(k\geq2\). [Massand–Simon, 2025](https://link.springer.com/article/10.1007/s00224-024-10210-x)
No result settling this exact continuous decision problem was located in the literature search.

Result

Every instance satisfying the stated hypotheses admits a pairwise stable allocation. Consequently, the decision problem is polynomial-time solvable: on valid inputs, the answer is always YES.

The proof uses a fixed point of Euclidean projection onto the allocation polytope.

1. The allocation polytope and utility map

Identify allocation matrices with vectors in \(\mathbb{R}^{\tau m}\). Define

\(\displaystyle P=\left\{x\in\mathbb{R}_{\geq0}^{\tau m}:\ \sum_{a\in A}x_{t,a}=\mu_t\text{ for every }t,\quad \sum_{t\in T}x_{t,a}=q_a\text{ for every }a\right\}.\)

This set is nonempty: the matrix \(x_{t,a}=\mu_tq_a\) has the required row and column sums because both marginal vectors sum to \(1\).

The set \(P\) is convex and closed, since its defining constraints are linear. It is bounded because \(0\leq x_{t,a}\leq\mu_t\). Hence \(P\) is compact.

Let \(u(x)\in\mathbb{R}^{\tau m}\) have coordinates

\(\displaystyle u_{t,a}(x)=U_t(a;x)=v_t(a)+\sum_{s\in T}\frac{\alpha_{s,t}}{\mu_s}\sum_{c\in N_H(a)}x_{s,c}.\)

Every denominator \(\mu_s\) is positive. Thus \(u\) is an affine, continuous map.

2. A fixed point with no improving aggregate direction

For \(z\in\mathbb{R}^{\tau m}\), let \(\Pi_P(z)\) denote its Euclidean projection onto \(P\). A minimizer exists by compactness and is unique because squared Euclidean distance is strictly convex.

We first verify the projection properties needed below. If \(p=\Pi_P(z)\) and \(y\in P\), convexity gives \(p+\lambda(y-p)\in P\) for \(0\leq\lambda\leq1\). Minimality of \(p\) implies

\(\displaystyle 0\leq\|z-p-\lambda(y-p)\|^2-\|z-p\|^2=-2\lambda\langle z-p,y-p\rangle+\lambda^2\|y-p\|^2.\)

Dividing by positive \(\lambda\) and letting \(\lambda\) tend to zero yields

\[\displaystyle \langle z-p,y-p\rangle\leq0. \tag{1}\]

For \(p=\Pi_P(z)\) and \(p'=\Pi_P(z')\), applying (1) in both directions and adding gives

\(\displaystyle \|p-p'\|^2\leq\langle z-z',p-p'\rangle\leq\|z-z'\|\,\|p-p'\|.\)

Therefore \(\|\Pi_P(z)-\Pi_P(z')\|\leq\|z-z'\|\), so projection is continuous.

Now define the continuous map

\(\displaystyle F:P\longrightarrow P,\qquad F(x)=\Pi_P(x+u(x)).\)

The finite-dimensional Brouwer fixed-point theorem applies to every continuous self-map of a nonempty compact convex set. All these hypotheses have been verified, so there exists \(x^*\in P\) with

\(\displaystyle x^*=\Pi_P(x^*+u(x^*)).\)

Taking \(z=x^*+u(x^*)\) and \(p=x^*\) in (1), we obtain

\[\displaystyle \langle u(x^*),y-x^*\rangle\leq0\qquad\text{for every }y\in P. \tag{2}\]

Equivalently, \(x^*\) maximizes the linear objective

\(\displaystyle y\longmapsto\sum_{t\in T}\sum_{a\in A}y_{t,a}U_t(a;x^*)\)

over \(P\), with utilities evaluated at the fixed allocation \(x^*\).

3. The fixed point is pairwise stable

Suppose, toward a contradiction, that \(t,s,a,b\) form a blocking exchange at \(x^*\). Then

\(\displaystyle x^*_{t,a}>0,\qquad x^*_{s,b}>0,\qquad U_t(b;x^*)>U_t(a;x^*),\qquad U_s(a;x^*)>U_s(b;x^*).\)

These strict inequalities require \(t\neq s\) and \(a\neq b\): otherwise one obtains contradictory comparisons or compares an item with itself.

Choose \(0<\delta\leq\min\{x^*_{t,a},x^*_{s,b}\}\). Construct \(y\) by decreasing entries \((t,a)\) and \((s,b)\) by \(\delta\), increasing entries \((t,b)\) and \((s,a)\) by \(\delta\), and keeping all other entries unchanged.

The choice of \(\delta\) preserves nonnegativity. Each affected row and column has one increase and one decrease of equal size, so all marginal constraints remain satisfied. Thus \(y\in P\).

But

\(\displaystyle \langle u(x^*),y-x^*\rangle=\delta\bigl(U_t(b;x^*)-U_t(a;x^*)+U_s(a;x^*)-U_s(b;x^*)\bigr)>0.\)

This contradicts (2). Therefore \(x^*\) is pairwise stable.

4. Decision complexity and the discrete comparison

For the promised class of valid inputs, the decision algorithm simply returns YES. No allocation must be computed to decide existence. If input validity must also be checked, the stated rational and graph conditions can be checked in polynomial time.

The cited discrete model evaluates each participant’s utility after the indivisible swap. [Massand–Simon, 2019](https://www.ijcai.org/proceedings/2019/0070.pdf) Here, both comparisons use the same fixed allocation \(x^*\), exactly as required in the calculation above. The discrete hardness result therefore does not contradict this existence theorem.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The argument establishes that every valid instance admits a pairwise stable allocation, so the requested existence decision is polynomial-time solvable. No mathematical gaps or incorrect steps were found.

• Allocation polytope. The proposed allocation \(x_{t,a}=\mu_tq_a\) satisfies both sets of marginal constraints and nonnegativity. Thus \(P\) is nonempty. Its linear constraints make it closed and convex, and \(0\leq x_{t,a}\leq\mu_t\) makes it bounded. Compactness follows in the finite-dimensional ambient space.

• Utility map. Every denominator \(\mu_s\) is strictly positive, and every sum is finite. Consequently \(u\) is an affine, continuous map on \(P\). Negative or asymmetric influence coefficients do not invalidate this statement.

• Projection existence and uniqueness. Compactness ensures that squared distance attains its minimum on \(P\). Strict convexity of squared Euclidean distance, together with convexity of \(P\), ensures uniqueness. This also covers singleton polytopes.

• Projection inequality and continuity. The squared-distance expansion is correct. Dividing by \(\lambda>0\) and taking \(\lambda\to0^+\) gives precisely inequality (1). Applying that inequality to the two projections and adding produces the stated bound with the correct sign. Cauchy–Schwarz then establishes continuity; when the projections coincide, the claimed bound holds directly.

• Fixed-point theorem. The prover states the applicable finite-dimensional compact-convex form of Brouwer’s theorem and verifies every hypothesis: \(P\) is nonempty, compact, and convex, and \(F\) is a continuous self-map. Full dimension is not required, so the marginal equalities create no problem. Substitution of the fixed-point identity into (1) correctly yields (2) for every \(y\in P\).

• Blocking-exchange contradiction. A blocking exchange necessarily has \(t\neq s\) and \(a\neq b\), as stated. Therefore the four modified coordinates are distinct. The positive occupied entries permit a positive \(\delta\), and its upper bound preserves nonnegativity. Equal increases and decreases preserve every row and column sum. The inner-product calculation correctly equals \(\delta\) times the sum of the two strictly positive utility differences, contradicting (2). Crucially, all utilities remain evaluated at \(x^*\), exactly as the task requires.

• Edge cases and quantifiers. The argument applies to every valid instance without additional assumptions. It covers \(m=1\), \(\tau=1\), zero intrinsic valuations, arbitrary permitted influence coefficients, and utility ties. In the first two cases no blocking exchange can exist; ties never supply the strict inequalities needed for the contradiction.

• Decision complexity. Universal existence justifies returning YES on every promised valid input. The task asks for an existence decision, so no algorithm for computing the fixed point or an allocation is required. The optional input-validation claim is also sound: the listed graph conditions, rational signs, zero diagonal, and marginal sums can be checked using polynomial-time exact arithmetic in the binary input length.

• Discrete comparison. The cited paper defines blocking through utility improvement at the allocation resulting from the swap. The prover accurately distinguishes this from the task’s fixed-allocation comparisons. This explanatory citation is consistent with the source and is not needed for the existence proof. [Massand–Simon, 2019, Section 2](https://www.ijcai.org/proceedings/2019/0070.pdf)

Repair feedback: None required. The prover resolves the assigned continuous decision problem.

⟨structured verdict parsed — rendered above⟩