d4-conf-ijcai-2020-0694 (d4-conf-ijcai-2020-0694)

Given a finite type set \(T\), a loopless compatibility graph \(H=(T,F)\), integer capacities \(b_t\), positive rational surpluses \(c_{tu}\), and rational masses \(\mu_t\ge 0\) summing to \(1\), form an atomless population \(\Omega=\bigsqcup_{t\in T}\Omega_t\) with \(|\Omega_t|=\mu_t\). Each individual of type \(t\) has capacity \(b_t\). For every measurable coalition \(S\subseteq\Omega\), let \(z_t(S)=|S\cap\Omega_t|\) and define \(\nu(S)=\max\{\sum_{\{t,u\}\in F}c_{tu}q_{tu}:q_{tu}\ge0,\ \sum_{u:\{t,u\}\in F}q_{tu}\le b_tz_t(S)\text{ for each }t\}\). Decide whether \(\nu(S)+\nu(R)\le\nu(S\cup R)+\nu(S\cap R)\) for every pair of measurable coalitions \(S,R\).

A society is given by its support: a list \(T\) of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not all possible types.
The input also contains a simple undirected loopless compatibility graph \(H=(T,F)\), positive integer capacities \(b_t\), and positive rational surpluses \(c_{tu}\) for \(\{t,u\}\in F\), all encoded in binary. Put \(m=|F|\), and let \(L\) be the total input bit length.
Realize the population as disjoint intervals \(\Omega_t\) of Lebesgue measure \(\mu_t\), with \(\Omega=\bigsqcup_{t\in T}\Omega_t\). Coalitions are arbitrary measurable subsets of \(\Omega\).
For a coalition \(S\), put \(z_t(S)=|S\cap\Omega_t|\) and define
\(\nu(S)=\max\{\sum_{\{t,u\}\in F}c_{tu}q_{tu}:q\in\mathbb R_{\ge0}^{F},\ \sum_{u:\{t,u\}\in F}q_{tu}\le b_tz_t(S)\text{ for every }t\in T\}\).
There are no additional edge capacities.

Is deciding whether \(\nu(S)+\nu(R)\le\nu(S\cup R)+\nu(S\cap R)\) for every pair of measurable coalitions \(S,R\) in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it NP-hard?

For finite vertex coalitions, convexity of the corresponding integral multiset \(b\)-matching game is decidable in \(O(n\log n+m\alpha(n))\) arithmetic operations, where \(n\) counts vertices and \(\alpha\) is the inverse Ackermann function. [Kumabe–Maehara (2020)](https://www.ijcai.org/proceedings/2020/0037.pdf)
The same source claims that relaxing matching integrality preserves convexity for finite vertex coalitions; this does not address arbitrary measurable coalitions. No result settling the stated atomless decision problem was located.

Result

The decision problem is in \(\mathrm{P}\). More precisely, the required inequality holds for every pair of measurable coalitions if and only if \(m=0\).

The atomless quantifier is decisive: even a graph consisting of a single positive-surplus edge fails, because one endpoint type can be split into two competing portions.

Proof

Value of a coalition supported on two adjacent types

Fix an edge \(\{t,u\}\in F\). If a coalition \(Q\) contains agents only from \(\Omega_t\) and \(\Omega_u\), then every matching variable except \(q_{tu}\) must be zero.

Indeed, every other edge has an endpoint \(v\notin\{t,u\}\), since the graph is simple and loopless. Its variable is zero because the capacity constraint at \(v\) has right-hand side \(b_vz_v(Q)=0\), and all matching variables are nonnegative.

Consequently,

\(\displaystyle \nu(Q)=c_{tu}\min\{b_tz_t(Q),\,b_uz_u(Q)\}.\)

The upper bound follows from the two endpoint constraints, and it is attained by setting \(q_{tu}\) equal to the displayed minimum.

Every edge gives a strict violation

Suppose \(F\ne\varnothing\), and fix \(\{t,u\}\in F\). Define

\(\displaystyle \lambda=\min\left\{\frac{b_t\mu_t}{2},\,b_u\mu_u\right\}>0.\)

Thus \(2\lambda/b_t\le\mu_t\) and \(\lambda/b_u\le\mu_u\). Because the type populations are intervals, we can choose disjoint measurable subsets \(A_1,A_2\subseteq\Omega_t\) and a measurable subset \(B\subseteq\Omega_u\) with

\(\displaystyle |A_1|=|A_2|=\frac{\lambda}{b_t},\qquad |B|=\frac{\lambda}{b_u}.\)

For example, choose two consecutive disjoint subintervals in \(\Omega_t\) and one subinterval in \(\Omega_u\).

Set \(S=A_1\cup B\) and \(R=A_2\cup B\). Their intersection is \(B\), and their union is \(A_1\cup A_2\cup B\).

In each of \(S\) and \(R\), both endpoint capacities equal \(\lambda\). In the union, the capacity at \(t\) equals \(2\lambda\), while the capacity at \(u\) remains \(\lambda\). Therefore the preceding formula gives

\(\displaystyle \nu(S)=\nu(R)=c_{tu}\lambda,\qquad \nu(S\cup R)=c_{tu}\lambda.\)

The intersection contains only type \(u\). Since there are no loops, \(\nu(S\cap R)=0\). Hence

\(\displaystyle \nu(S)+\nu(R)=2c_{tu}\lambda>c_{tu}\lambda=\nu(S\cup R)+\nu(S\cap R),\)

where strictness follows from \(c_{tu}>0\) and \(\lambda>0\). This disproves the required property whenever an edge exists.

An edgeless graph satisfies the property

If \(F=\varnothing\), the objective is an empty sum, so \(\nu(Q)=0\) for every measurable coalition \(Q\). The required inequality therefore holds with equality.

Together, these arguments prove the characterization.

Algorithm and scope

Read the edge list and return yes exactly when it is empty. Including input reading, this takes \(O(L+m+\tau)\) time, hence time polynomial in \(m,\tau,L\). No expansion of the binary-encoded capacities or population discretization is needed.

This obstruction explains why the [finite vertex-coalition result](https://www.ijcai.org/proceedings/2020/0037.pdf) does not settle the atomless problem. With only two finite vertices, a single positive edge yields a supermodular game: incomparable coalitions are the two singleton coalitions, whose values are zero. The measurable model additionally permits the disjoint portions \(A_1,A_2\) used above.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The characterization holds: the required inequality is valid for every pair of measurable coalitions if and only if \(m=0\). The argument establishes a polynomial-time decision procedure and contains no substantive or minor gaps.

• Restriction to two adjacent types. Fix \(\{t,u\}\in F\). Every other edge has an endpoint outside \(\{t,u\}\), because the graph is simple and loopless. For a coalition supported on these two types, the capacity at each outside type is zero. Nonnegativity of the matching variables therefore forces every other edge variable to zero. The remaining variable satisfies precisely

\[ 0\le q_{tu}\le\min\{b_tz_t(Q),b_uz_u(Q)\}. \]
Since \(c_{tu}>0\), the stated value formula follows, including attainment. This reasoning also covers coalitions supported on only one of the two types.

• Positivity and feasibility of the chosen measures. Both \(b_t\mu_t/2\) and \(b_u\mu_u\) are strictly positive, so the defined \(\lambda\) is strictly positive. Its definition gives \(2\lambda/b_t\le\mu_t\) and \(\lambda/b_u\le\mu_u\), exactly the bounds needed to choose the three subsets. The interval realization permits disjoint measurable subsets of the stated measures, including when either bound is attained. Subinterval endpoints can be assigned to keep the subsets disjoint without changing their measures.

• Union and intersection. The sets \(A_1,A_2\) are disjoint, and \(B\) lies in a different type population. Consequently, the asserted identities \(S\cap R=B\) and \(S\cup R=A_1\cup A_2\cup B\) hold. All constructed coalitions are measurable and thus belong to the task’s quantified domain.

• Value calculations. Each of \(S\) and \(R\) has endpoint capacities \(\lambda,\lambda\), while their union has capacities \(2\lambda,\lambda\). Applying the verified two-type formula gives all three stated values. The intersection contains only type \(u\); every edge has an endpoint with zero coalition mass, so its value is zero. No edges elsewhere in the graph can contribute.

• Strict violation. The proposed inequality for these coalitions reduces to \(2c_{tu}\lambda\le c_{tu}\lambda\), which is false because \(c_{tu}\lambda>0\). The construction applies to any selected edge, irrespective of other edges, capacities, or relative population masses. It therefore proves failure for every valid input with \(m>0\).

• Edgeless case. When \(F=\varnothing\), the empty variable vector is feasible and the objective is zero. Every coalition has value zero, establishing the property for all measurable pairs. Together with the preceding construction, this proves both directions of the characterization.

• Complexity and scope. Testing whether the supplied edge list is empty decides the property. Including input reading, the stated \(O(L+m+\tau)\) bound is polynomial in the requested parameters. Binary-encoded capacities require no expansion. The finite two-vertex comparison is also correct: the only incomparable coalitions are the two singletons, both with value zero. No external theorem is needed for the proof or this comparison.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩