d4-conf-ijcai-2021-0156 (d4-conf-ijcai-2021-0156)

Given finite type supports \(T_L,T_R\), positive rational masses \(\mu_t\) summing to one on each side, satisfaction values \(s_t(u)\), and a welfare threshold \(\Gamma\), is there a nonnegative flow \(x_{tu}\) with \(\sum_u x_{tu}\le\mu_t\) and \(\sum_t x_{tu}\le\mu_u\), such that each type receives a common per-capita mix, \(U_t=\sum_u s_t(u)x_{tu}/\mu_t\), and for every acceptable pair \(t,u\), \(U_t\ge s_t(u)\) or \(U_u\ge s_u(t)\), while \(\sum_{t\in T_L\cup T_R}\mu_tU_t\ge\Gamma\)?

A society is given by its support: disjoint nonempty lists \(T_L,T_R\) of types with positive binary rational masses \(\mu_v\), summing to \(1\) on each side. Let \(\tau=|T_L|+|T_R|\) be the support size, not the number of possible types.
Satisfactions \(s_v(w)\) are nonnegative binary rationals for opposite-side types. Define \(E=\{(t,u)\in T_L\times T_R:s_t(u)>0\text{ or }s_u(t)>0\}\); every type has an acceptable neighbor. For each type, satisfaction values on its acceptable neighbors are pairwise distinct (strict preferences).
The input also includes \(\Gamma\in\mathbb Q_{\ge0}\). Set \(m=|E|\), and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
An allocation is a real flow \(x_{tu}\ge0\) supported on \(E\), with \(\sum_u x_{tu}\le\mu_t\) and \(\sum_t x_{tu}\le\mu_u\). Every individual of a type receives the same per-capita mix; unmatched mass contributes zero utility.
Define \(U_t=\mu_t^{-1}\sum_u s_t(u)x_{tu}\) and \(U_u=\mu_u^{-1}\sum_t s_u(t)x_{tu}\). Cardinal stability means \(U_t\ge s_t(u)\) or \(U_u\ge s_u(t)\) for every \((t,u)\in E\); equality prevents blocking.
The decision problem asks whether such a stable allocation satisfies \(\sum_{v\in T_L\cup T_R}\mu_vU_v\ge\Gamma\).

Is this continuous welfare-threshold decision problem in \(\mathsf P\), or is it \(\mathsf{NP}\)-hard?

For finite lists of unit-capacity agents, the corresponding cardinally stable fractional-matching welfare decision problem is NP-complete even in bipartite markets with strict preferences ([Chen, Roy, and Sorge](https://www.ijcai.org/proceedings/2021/0013.pdf)).
No result settling the exact mass formulation above was identified in the literature search.

Result. The problem is \(\mathsf{NP}\)-complete. Hardness holds even when every type has the same mass and that mass is a reciprocal power of two.

1. The source problem.

We use Chen, Roy, and Sorge’s Theorem 5.7: deciding whether a bipartite instance with strict preferences admits a cardinally stable fractional matching of welfare at least a given threshold is \(\mathsf{NP}\)-complete. Their hardness construction uses integer satisfactions and an integer threshold. Their definitions also require no isolated vertices and define acceptability by positivity of at least one directed satisfaction, exactly as in the present task. [Chen, Roy, and Sorge, Sections 2 and 5](https://www.ijcai.org/proceedings/2021/0013.pdf).

Write a source instance as follows:

• Its disjoint agent sets are \(A,B\), and its acceptable edge set is \(F\).
• Its satisfaction function is \(s\), and its welfare threshold is \(\gamma\).
• A fractional matching \(y\) satisfies \(y_e\ge 0\) and \(\sum_{e\ni v}y_e\le 1\).
• Its utilities and welfare are \(V_v(y)=\sum_{w:\{v,w\}\in F}s_v(w)y_{vw}\) and \(W(y)=\sum_v V_v(y)\).
• Cardinal stability requires \(V_a(y)\ge s_a(b)\) or \(V_b(y)\ge s_b(a)\) for each acceptable pair.

Let \(N=|A|+|B|\) and \(r=|F|\).

2. Construction of a normalized society.

First take two disjoint copies of the source instance, exchanging the sides in the second copy. Thus the first copy has sides \(A,B\), while the second has sides \(B',A'\). Every directed satisfaction is copied without changing its value. Together, these copies have exactly \(N\) types on each side.

Let \(q=2^{\lceil\log_2 N\rceil}\) and \(h=q-N\). Add \(h\) disjoint dummy pairs, each consisting of one new left type and one new right type. Each dummy type has satisfaction \(1\) toward its partner. All satisfactions between different components are zero.

There are now exactly \(q\) types on each side. Set

\(\mu_v=1/q\)

for every type, and set the target threshold to

\(\Gamma=(2\gamma+2h)/q.\)

This is a valid instance:

• Every mass is positive, dyadic, and the masses sum to \(1\) on each side.
• Every type has an acceptable neighbor.
• Original types retain exactly their original acceptable neighbors and strict preferences.
• Dummy types have one acceptable neighbor, so their preferences are strict.
• The threshold is a nonnegative binary rational.

The output parameters satisfy

\(\tau=2q<4N,\qquad m=2r+h.\)

The construction has polynomial output bit length and takes polynomial time. In particular, adding the dummy pairs does not require expanding any population represented by a mass.

3. Exact correspondence of allocations and fractional matchings.

For an allocation \(x\) in the constructed society, define \(y_e=qx_e\). The capacity constraints become

\(\sum_{e\ni v}y_e=q\sum_{e\ni v}x_e\le q\mu_v=1.\)

Conversely, any unit-capacity fractional matching \(y\) on the constructed graph gives a feasible allocation \(x_e=y_e/q\). These maps are inverse.

For every type, the per-capita utility is

\(U_v(x)=\mu_v^{-1}\sum_w s_v(w)x_{vw}=q\sum_w s_v(w)(y_{vw}/q)=V_v(y).\)

Consequently, every cardinal-stability inequality is preserved exactly, including equality.

For a dummy pair with edge \(d\), both endpoints have utility \(y_d\). Stability therefore requires \(y_d\ge 1\), while feasibility requires \(y_d\le 1\). Thus every stable solution has \(y_d=1\), and each dummy pair contributes exactly \(2\) to unit-capacity welfare.

Let \(y^{(1)},y^{(2)}\) denote the restrictions to the two source copies. Because no acceptable edges join different components, stability of the complete allocation implies stability in each copy. Its welfare is

\(\sum_v\mu_vU_v(x)=\bigl(W(y^{(1)})+W(y^{(2)})+2h\bigr)/q.\)

We can now prove both directions of the reduction.

If the source instance has a stable matching \(z\) with \(W(z)\ge\gamma\), use \(z\) in both copies and give every dummy edge weight \(1\). Scaling by \(1/q\) gives a stable allocation with welfare at least \(\Gamma\).

Conversely, suppose the constructed society has a stable allocation with welfare at least \(\Gamma\). The preceding identity implies

\(W(y^{(1)})+W(y^{(2)})\ge 2\gamma.\)

At least one of these two welfare values is at least \(\gamma\): otherwise their sum would be strictly less than \(2\gamma\). That copy, after undoing the relabeling if necessary, is a stable fractional matching satisfying the source threshold.

Thus the construction is a polynomial-time many-one reduction, proving \(\mathsf{NP}\)-hardness.

4. Membership in \(\mathsf{NP}\) and running times.

The use of real allocations does not prevent membership in \(\mathsf{NP}\). A certificate consists of one chosen endpoint for each acceptable edge: the endpoint whose stability inequality is to hold.

For a fixed choice, solve the following rational linear feasibility problem in the \(m\) variables \(x_e\):

• Nonnegativity: \(x_e\ge 0\).
• Capacities: \(\sum_{e\ni v}x_e\le\mu_v\).
• For every edge \((t,u)\), impose the chosen inequality, either

\(\sum_w s_t(w)x_{tw}\ge\mu_t s_t(u)\), or
\(\sum_w s_u(w)x_{wu}\ge\mu_u s_u(t)\).

• Welfare: \(\sum_{(t,u)\in E}(s_t(u)+s_u(t))x_{tu}\ge\Gamma\).

Multiplying the original utility inequalities by the positive masses justifies the third group. Expanding the definition of welfare justifies the fourth.

This system has \(m\) variables, \(O(m+\tau)\) constraints, and encoding length polynomial in \(m,\tau,L\). Exact feasibility of rational linear inequalities is decidable in polynomial bit time; its hypotheses apply because all displayed coefficients are rational and have polynomial encoding length.

If a stable allocation exists, choose a satisfied endpoint inequality on every edge. The resulting linear system is feasible. Conversely, any feasible system obtained from such choices supplies a stable allocation satisfying the welfare threshold.

Hence an \(m\)-bit certificate can be verified in \(\operatorname{poly}(m,\tau,L)\) time, proving membership in \(\mathsf{NP}\). Enumerating all choices also gives a deterministic algorithm with running time \(2^m\operatorname{poly}(m,\tau,L)\).

Together with the reduction, this establishes \(\mathsf{NP}\)-completeness for the exact continuous mass formulation.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The reduction preserves the exact per-capita stability definition and welfare threshold, and the certificate argument establishes membership in \(\mathsf{NP}\). No major or minor mathematical issues were found.

• The cited source problem is applicable.

Chen, Roy, and Sorge’s Theorem 5.7 establishes \(\mathsf{NP}\)-completeness of the cardinally stable fractional-matching welfare decision problem for bipartite graphs with strict preferences. Their preliminaries impose no isolated vertices, define acceptability by positivity of at least one directed satisfaction, and define strict preferences by distinct satisfaction values on each neighborhood. Their fractional matchings have unit capacity, and their blocking inequalities use strict comparisons, so equality prevents blocking. These definitions agree with the source problem stated by the prover. [Chen, Roy, and Sorge, Sections 1–2 and Theorem 5.7](https://www.ijcai.org/proceedings/2021/0013.pdf).

The cited hardness construction uses integer satisfaction values and an integer, nonnegative welfare threshold. Thus the reduction can use a finitely encoded hard source family; it does not depend on encoding an arbitrary real threshold. [Chen, Roy, and Sorge, Figures 3–4 and proof of Theorem 5.7](https://www.ijcai.org/proceedings/2021/0013.pdf).

• The normalized society satisfies every input restriction.

The first copy contributes \(|A|\) left types and \(|B|\) right types. The copy with exchanged sides contributes \(|B|\) left types and \(|A|\) right types. Hence there are exactly \(N\) types on each side before padding.

For the nonempty source instances used in the hardness reduction, \(N\ge 2\). The definition of \(q\) gives \(N\le q<2N\), so \(h=q-N\) is a nonnegative integer. Adding \(h\) dummy pairs produces exactly \(q\) types on each side.

Each mass \(1/q\) is positive and dyadic, and each side’s masses sum to \(1\). Original types retain their acceptable neighborhoods and distinct satisfaction values. Dummy types have exactly one acceptable neighbor. Zero satisfaction in both directions between components creates no additional acceptable edges and imposes no additional strict-preference requirements.

The threshold \(\Gamma=(2\gamma+2h)/q\) is nonnegative and has a finite binary rational encoding.

• The size and encoding claims are correct.

The counts \(\tau=2q<4N\) and \(m=2r+h\) follow directly from the construction.

Copying the source satisfactions, adding polynomially many types, and encoding \(q\), the masses, and the threshold require polynomial output length. Even if all opposite-side satisfaction entries are explicitly recorded, the number of entries remains polynomial in the source size. There is no expansion proportional to a denominator or to a represented population.

• The allocation correspondence is exact.

Since every constructed mass is \(1/q\), the transformation \(y_e=qx_e\) converts each capacity constraint into the corresponding unit-capacity constraint. Its inverse is \(x_e=y_e/q\), and both transformations preserve nonnegativity and edge support.

The displayed utility calculation is correct: \(U_v(x)=V_v(y)\) for every type. Consequently, the entire stability disjunction on every acceptable edge is preserved, including its weak inequalities and equality cases.

Exchanging the sides in the second copy only relabels agents. Copying directed satisfactions preserves the source utilities and stability conditions there as well.

• The dummy contribution is forced.

Both endpoints of a dummy edge have utility \(y_d\). Its stability disjunction therefore reduces to \(y_d\ge 1\). Feasibility gives \(y_d\le 1\), forcing \(y_d=1\).

Each dummy pair consequently contributes exactly \(2\) to unit-capacity welfare and \(2/q\) to the society’s welfare. This reasoning also covers \(h=0\), when there are no dummy contributions.

• Both directions of the many-one reduction hold.

In the forward direction, using a qualifying source matching in both copies gives combined source welfare at least \(2\gamma\). Together with the forced dummy contributions, scaling gives welfare at least \(\Gamma\). Stability holds component by component because there are no acceptable edges between components.

In the reverse direction, restricting a stable allocation to either source copy preserves feasibility and stability. The welfare identity yields
\[ W(y^{(1)})+W(y^{(2)})\ge 2\gamma. \]
At least one summand must be at least \(\gamma\). Undoing that copy’s relabeling supplies a qualifying source matching.

This is a valid equivalence of decision instances, including at exact threshold equality. It establishes the claimed hardness for equal masses that are reciprocals of powers of two.

• Membership in \(\mathsf{NP}\) is correctly established.

One endpoint choice per acceptable edge is an \(m\)-bit certificate. For each fixed certificate, every displayed constraint is a non-strict rational linear inequality in the \(m\) allocation variables.

Multiplication by the positive mass preserves each chosen utility inequality. The welfare constraint is also correct: expanding \(\sum_v\mu_vU_v\) assigns coefficient \(s_t(u)+s_u(t)\) to \(x_{tu}\).

There are \(O(m+\tau)\) constraints. Products of input rationals and repeated satisfaction coefficients have polynomial total encoding length in \(m,\tau,L\). The standard polynomial bit-time theorem for feasibility of finite rational linear systems therefore applies.

A stable allocation permits a satisfied endpoint choice on every edge. Conversely, feasibility for a certificate enforces at least one stability inequality on every edge and the welfare threshold. A certificate need not explicitly encode the real allocation because the verifier decides the associated linear feasibility problem.

• The running-time and final classification claims follow.

Certificate verification takes \(\operatorname{poly}(m,\tau,L)\) time. Enumerating all endpoint choices gives the stated deterministic bound \(2^m\operatorname{poly}(m,\tau,L)\).

Combining membership with the valid reduction establishes \(\mathsf{NP}\)-completeness for the exact continuous mass formulation. No additional lemma or clarification is needed.

⟨structured verdict parsed — rendered above⟩