d4-conf-ijcai-2011-0335 (d4-conf-ijcai-2011-0335)

Given finite role types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and a succinct nonnegative rational worth function \(w:2^T\to\mathbb{Q}_{\ge 0}\), let \(\Omega\) be a union of intervals \(\Omega_t\) of lengths \(\mu_t\). For a measurable coalition \(A\), set \(F(A)=\{t:\lambda(A\cap\Omega_t)=\mu_t\}\) and \(W(A)=w(F(A))\). Does there exist a finite measurable partition \(\Pi\) of \(\Omega\) and an integrable payoff density \(x\), individually rational at each type’s reservation rate \(w(\{t\})/\mu_t\), such that \(\int_C x=W(C)\) for every \(C\in\Pi\) and \(\int_A x\ge W(A)\) for every measurable \(A\)?

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) satisfying \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains a Boolean circuit that, on the incidence vector of \(S\subseteq T\), outputs a binary-rational worth \(w(S)\). Promise \(w(S)\ge0\) for every \(S\) and \(w(\varnothing)=0\). Let \(L\) be the total input bit length; there is no separate candidate parameter \(m\).
Let \(\Omega=[0,1)\) be partitioned into consecutive half-open intervals \(\Omega_t\) of lengths \(\mu_t\), and let \(\lambda\) denote Lebesgue measure. For every Lebesgue-measurable \(A\subseteq\Omega\), define \(F(A)=\{t\in T:\lambda(A\cap\Omega_t)=\mu_t\}\) and \(W(A)=w(F(A))\).
Call an outcome feasible if it consists of a finite partition \(\Pi\) of \(\Omega\) into measurable sets of positive measure and a real payoff density \(x\in L^1(\Omega,\lambda)\), with \(x\ge w(\{t\})/\mu_t\) almost everywhere on each \(\Omega_t\), such that \(\int_C x\,d\lambda=W(C)\) for every \(C\in\Pi\) and \(\int_A x\,d\lambda\ge W(A)\) for every measurable \(A\subseteq\Omega\).

Is deciding whether a feasible outcome exists solvable in polynomial time in \(\tau\) and \(L\), or is it NP-hard?

For finite-player games with succinct polynomial-time evaluable worth functions, coalition-structure core nonemptiness is \(\Delta_2^P\)-complete ([Greco et al., 2011](https://www.ijcai.org/Proceedings/11/Papers/047.pdf)); its hardness construction uses nonnegative rational worths and zero empty-coalition worth.
No result settling the exact continuous decision problem defined above was located in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, even when every singleton has worth zero and every coalition worth belongs to \(\{0,2,3\}\). The reduction uses positive dyadic masses and a polynomial-size Boolean circuit.

First, we establish that the measurable formulation is exactly equivalent to a finite coalition-structure core problem. We then give a direct reduction from Boolean satisfiability.

1. Equivalence with finite feasibility

For a vector \(y\in\mathbb R^T\), write \(y(S)=\sum_{t\in S}y_t\). Call a pair \((\mathcal P,y)\) finitely feasible if \(\mathcal P\) is a partition of \(T\) into nonempty blocks and

• \(y_t\ge w(\{t\})\) for every \(t\in T\);
• \(y(B)=w(B)\) for every \(B\in\mathcal P\);
• \(y(S)\ge w(S)\) for every \(S\subseteq T\).

This is the finite coalition-structure core definition used in [Greco et al., Section 2](https://www.ijcai.org/Proceedings/11/Papers/047.pdf).

Proposition. A continuous feasible outcome exists if and only if a finitely feasible pair exists.

Continuous feasibility implies finite feasibility

Let \((\Pi,x)\) be continuously feasible, and define
\(y_t=\int_{\Omega_t}x\,d\lambda\).
The density lower bound gives \(y_t\ge w(\{t\})\ge0\), and also \(x\ge0\) almost everywhere.

For \(S\subseteq T\), put \(U_S=\bigcup_{t\in S}\Omega_t\). Positivity of all masses implies \(F(U_S)=S\). Stability therefore gives
\(y(S)=\int_{U_S}x\,d\lambda\ge w(S)\).

For each cell \(C\in\Pi\), let \(S_C=F(C)\). By definition, \(U_{S_C}\setminus C\) has measure zero. Since \(x\) is integrable and nonnegative almost everywhere,

\(y(S_C)=\int_{C\cap U_{S_C}}x\,d\lambda\le\int_Cx\,d\lambda=w(S_C)\).

Together with the preceding stability inequality, this yields
\(y(S_C)=w(S_C)\).

The sets \(S_C\) are pairwise disjoint. Indeed, if a type belonged to both \(S_C\) and \(S_D\) for distinct cells, the disjoint sets \(C\cap\Omega_t\) and \(D\cap\Omega_t\) would each have measure \(\mu_t>0\), which is impossible inside \(\Omega_t\).

Let \(U=\bigcup_{C\in\Pi}S_C\) and \(Z=T\setminus U\). Summing the cell equalities gives

\(y(T)=\int_\Omega x\,d\lambda=\sum_{C\in\Pi}w(S_C)=\sum_{C\in\Pi}y(S_C)=y(U)\).

Thus \(y(Z)=0\). Since every coordinate is nonnegative, \(y_t=0\) for every \(t\in Z\); consequently \(w(\{t\})=0\) there.

Take as \(\mathcal P\) all nonempty sets \(S_C\), together with the singleton blocks \(\{t\}\) for \(t\in Z\). They partition \(T\), and the equalities above verify block efficiency. Individual rationality and all coalition inequalities were already proved. Hence \((\mathcal P,y)\) is finitely feasible.

Finite feasibility implies continuous feasibility

Conversely, let \((\mathcal P,y)\) be finitely feasible. Define
\(x(\omega)=y_t/\mu_t\) on \(\Omega_t\), and let
\(\Pi=\{U_B:B\in\mathcal P\}\).

Every cell has positive measure. The density is integrable and satisfies the required lower bound. Also,

\(\int_{U_B}x\,d\lambda=y(B)=w(B)=W(U_B)\).

For any measurable \(A\), let \(S=F(A)\). Then \(U_S\setminus A\) is null. Since \(x\ge0\),

\(\int_Ax\,d\lambda\ge\int_{A\cap U_S}x\,d\lambda=y(S)\ge w(S)=W(A)\).

Thus the constructed outcome is continuously feasible. This proves the proposition.

2. A direct reduction from satisfiability

Let \(\varphi\) be a Boolean formula with variables \(z_1,\ldots,z_n\). Introduce variable types \(v_1,\ldots,v_n\) and three additional types \(a,b,c\). Set

\(T=\{v_1,\ldots,v_n,a,b,c\}\), \(G=\{a,b,c\}\), \(\tau=n+3\).

For \(S\subseteq T\), let \(\alpha_S\) be the assignment in which \(z_i\) is true exactly when \(v_i\in S\).

Define worths by the following ordered rules:

• If \(G\subseteq S\) and \(\alpha_S\) satisfies \(\varphi\), set \(w(S)=3\).
• Otherwise, if \(S\subseteq G\) and \(|S|\ge2\), set \(w(S)=2\).
• Otherwise, set \(w(S)=0\).

These rules give nonnegative integer worths, \(w(\varnothing)=0\), and \(w(\{t\})=0\) for every type.

Satisfiability implies feasibility

Suppose \(\alpha\) satisfies \(\varphi\). Let \(H\) contain exactly the variable types assigned true by \(\alpha\).

Use the partition consisting of \(B=G\cup H\) and singleton blocks for the remaining variable types. Set

\(y_a=y_b=y_c=1\), \(y_{v_i}=0\) for every \(i\).

The block \(B\) has worth and total payoff both equal to \(3\). Every remaining singleton has worth and payoff zero.

For an arbitrary coalition \(S\):

• If \(w(S)=0\), then \(y(S)\ge0=w(S)\).
• If \(w(S)=2\), then \(S\) contains at least two members of \(G\), so \(y(S)\ge2\).
• If \(w(S)=3\), then \(G\subseteq S\), so \(y(S)=3\).

Hence this pair is finitely feasible, and the proposition supplies a continuous feasible outcome.

Unsatisfiability implies infeasibility

Suppose \(\varphi\) is unsatisfiable. The first worth rule never applies. Every positive-worth coalition is therefore a subset of \(G\) containing at least two members, and has worth \(2\).

Any two such coalitions intersect: two subsets of a three-element set, each of size at least two, cannot be disjoint. Consequently, any partition of \(T\) contains at most one positive-worth block. Block efficiency in a finitely feasible pair would therefore imply \(y(T)\le2\).

But stability for the three pair coalitions gives

\(y_a+y_b\ge2\), \(y_a+y_c\ge2\), \(y_b+y_c\ge2\).

Adding these inequalities yields \(2(y_a+y_b+y_c)\ge6\), hence \(y(G)\ge3\). Individual rationality gives nonnegative payoffs for all other types, so \(y(T)\ge y(G)\ge3\), a contradiction.

Thus no finite feasible pair exists, and the proposition excludes continuous feasibility.

3. Encoding and conclusion

Choose \(q=\lceil\log_2\tau\rceil\). In any fixed ordering of the types, assign mass \(2^{-q}\) to the first \(\tau-1\) types and mass \(1-(\tau-1)2^{-q}\) to the last.

All masses are dyadic, sum to one, and are positive: the last mass is at least \(2^{-q}\) because \(\tau\le2^q\). Their total encoding length is \(O(\tau\log\tau)\).

The worth circuit evaluates \(\varphi\) on the variable incidence bits and checks the two elementary set conditions above. It has polynomial size and outputs one of three two-bit integers. Thus the entire instance, including its input length \(L\), is constructed in polynomial time.

We have proved that \(\varphi\) is satisfiable exactly when the constructed society admits a feasible outcome. Therefore the requested decision problem is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(\tau\) and \(L\) would imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the requested decision problem: continuous feasible-outcome existence is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. No major or minor mathematical issues were found.

• Finite feasibility and the cited definition.

The finite formulation explicitly requires individual rationality, efficiency for every partition block, and stability against every subset of \(T\). These conditions agree with the coalition-structure core definition in [Greco et al., Section 2](https://www.ijcai.org/Proceedings/11/Papers/047.pdf).

The reduction is proved directly; it does not depend on importing the paper’s complexity theorem.

• Continuous feasibility implies individual rationality and finite stability.

Each \(y_t=\int_{\Omega_t}x\,d\lambda\) is a finite real number because \(x\) is integrable. Integrating the stipulated density lower bound gives \(y_t\ge w(\{t\})\). Nonnegative singleton worths also imply that \(x\ge0\) almost everywhere and that every coordinate of \(y\) is nonnegative.

For every \(S\subseteq T\), the union \(U_S\) contains exactly the full intervals indexed by \(S\). Positive masses ensure that no type outside \(S\) belongs to \(F(U_S)\), so \(F(U_S)=S\). Finite additivity of the integral then gives the claimed stability inequality \(y(S)\ge w(S)\). This includes \(S=\varnothing\).

• The full types in a continuous cell form an efficient finite block.

For \(S_C=F(C)\), each interval indexed by \(S_C\) is contained in \(C\) up to a null set. Since \(T\) is finite, \(U_{S_C}\setminus C\) is null. Integrability therefore justifies
\[ y(S_C)=\int_{C\cap U_{S_C}}x\,d\lambda. \]
Nonnegativity of \(x\) gives the upper bound by the integral over \(C\), and cell efficiency identifies that integral with \(w(S_C)\). The previously established finite stability inequality supplies the reverse bound. Thus \(y(S_C)=w(S_C)\).

This reasoning also covers \(S_C=\varnothing\), using \(w(\varnothing)=0\).

• The finite partition extracted from continuous cells is valid.

Distinct partition cells cannot both contain a full positive-mass type: their intersections with that type interval are disjoint, and two such intersections of measure \(\mu_t\) cannot fit inside an interval of measure \(\mu_t\). Hence the sets \(S_C\) are pairwise disjoint.

Both partitions and the type set are finite, so all summations in
\[ y(T)=\sum_{C\in\Pi}w(S_C)=\sum_{C\in\Pi}y(S_C)=y(U) \]
are justified. Consequently \(y(Z)=0\). Nonnegative coordinates force \(y_t=0\) on \(Z\), and individual rationality together with nonnegative worths forces \(w(\{t\})=0\) there.

Removing empty sets \(S_C\) and adding singleton blocks for \(Z\) therefore produces a partition of all of \(T\) into nonempty efficient blocks. No assumption that every type was originally contained wholly in one cell is needed.

• Finite feasibility implies continuous feasibility.

Positive masses make the ratios \(y_t/\mu_t\) well-defined. The constructed density is measurable and integrable because it takes finitely many finite values on measurable intervals. Individual rationality gives its required lower bound and nonnegativity.

Each block union has positive measure, the block unions partition \(\Omega\), and \(F(U_B)=B\). Their payoff integrals therefore satisfy cell efficiency.

For every measurable \(A\), the assertion that \(U_{F(A)}\setminus A\) is null follows directly from the definition of \(F(A)\) and finiteness of \(T\). Nonnegativity and invariance of integrals under null-set changes justify the displayed inequality proving stability. This covers arbitrary measurable sets, including null sets. The equivalence proposition is established in both directions.

• The worth rules meet the promises.

The ordered rules define a worth for every incidence vector and always output one of \(0,2,3\). The empty coalition and all singletons receive zero: none contains all three members of \(G\), and none meets the second rule’s size condition.

Rule precedence is explicit. In particular, if the all-false assignment satisfies the formula, \(G\) receives worth \(3\), as required by the satisfying-case construction.

• A satisfying assignment yields a feasible finite pair.

The block \(B=G\cup H\) encodes exactly the chosen assignment, so its worth is \(3\). Its total payoff is also \(3\). All remaining variable types form singleton blocks with zero worth and payoff. Thus the partition covers every type and satisfies block efficiency and individual rationality.

The three stability cases are exhaustive. A coalition of worth \(2\) contains at least two gadget types; a coalition of worth \(3\) contains all three. Since only those types receive positive payoffs, the stated payoff bounds hold. The equivalence proposition transfers this witness to the continuous problem.

• An unsatisfiable formula excludes every finite feasible pair.

Unsatisfiability disables the first rule for every coalition. The positive-worth coalitions are exactly the subsets of \(G\) of size at least two, each worth \(2\). Such subsets pairwise intersect, so a partition contains at most one positive-worth block. Summing block efficiency therefore gives \(y(T)\le2\).

Each of the three gadget pairs has worth \(2\). Adding their stability inequalities counts each gadget payoff twice, giving
\[ 2(y_a+y_b+y_c)\ge6, \]
hence \(y(G)\ge3\). All other coordinates are nonnegative, so \(y(T)\ge3\), contradicting the partition bound. The equivalence proposition therefore excludes continuous feasibility as well.

• Encoding and complexity conclusion.

Here \(\tau=n+3\ge3\). With \(q=\lceil\log_2\tau\rceil\), the first \(\tau-1\) masses are positive dyadic rationals, and the last satisfies
\[ 1-(\tau-1)2^{-q}\ge2^{-q}>0. \]
The masses sum to one. Their numerators and denominators require \(O(\log\tau)\) bits each, giving the claimed total bound.

Formula evaluation and the set tests admit polynomial-size Boolean circuits; the output integers require only constant space. The explicit support has polynomial size in the source formula, so the complete instance is constructible in polynomial time.

The two implications establish the required many-one reduction from Boolean satisfiability. Since the support is listed explicitly, \(\tau\) is also bounded by the input length. Thus a polynomial-time algorithm in \(\tau\) and \(L\) would yield a polynomial-time satisfiability algorithm. The proof establishes the requested hardness; it makes no unsupported completeness or membership claim.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩