d4-conf-atal-2017-0121 (d4-conf-atal-2017-0121)

Given a finite supported type set \(T\), rational masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\), and positive-weight rules \(r=(P_r,N_r,v_r)\) with \(P_r\neq\varnothing\), choose nonnegative team frequencies \(x_S\) for nonempty \(S\subseteq T\), subject to \(\sum_{S\ni t}x_S=\mu_t\) for each \(t\), to maximize \(\sum_{S\neq\varnothing}x_S\sum_{r:\,P_r\subseteq S,\;N_r\cap S=\varnothing}v_r\), or decide whether the value is at least a given rational \(q\). Determine its complexity and approximation guarantees as functions of \(\tau\), the number of rules, and their encoding length, including the variant whose type-level CSG-graph has at most three red edges.

A society is given by its support \(T\): the list of its \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Input also includes \(m\) explicitly listed rules \(r=(P_r,N_r,v_r)\), with \(\varnothing\ne P_r\subseteq T\), \(N_r\subseteq T\), \(P_r\cap N_r=\varnothing\), and positive binary rational \(v_r\), and a binary rational threshold \(q\). Let \(L\) be the total input bit length.
For every nonempty \(S\subseteq T\), set \(V(S)=\sum_{r:P_r\subseteq S,\,N_r\cap S=\varnothing}v_r\). A feasible allocation consists of real frequencies \(x_S\ge0\) satisfying \(\sum_{S\ni t}x_S=\mu_t\) for every \(t\in T\); a frequency \(x_S\) consumes that same mass of each type in \(S\).
Define \(\operatorname{OPT}=\max_x\sum_{\varnothing\ne S\subseteq T}x_SV(S)\). The decision problem asks whether \(\operatorname{OPT}\ge q\).
The type-level CSG-graph has rules as vertices: distinct rules \(r,s\) have a green edge when \(P_r\cap P_s\ne\varnothing\), and a red edge when \(P_r\cap N_s\ne\varnothing\) or \(P_s\cap N_r\ne\varnothing\). Count each unordered red pair once; both colors may occur on a pair.

Is this decision problem in \(\mathrm{P}\) or NP-hard, both without restrictions and when its CSG-graph has at most three red edges?
What polynomial-time approximation ratios are achievable for \(\operatorname{OPT}\) in these two classes? Express running times and ratios in \(m,\tau,L\).

For discrete societies, feasible allocations are partitions of individually listed agents, with welfare equal to the sum of coalition values. This problem is strongly NP-hard and admits no polynomial-time \(O(m^{1-\varepsilon})\)-approximation for any fixed \(\varepsilon>0\) unless \(\mathrm{P}=\mathrm{NP}\); it remains NP-hard with at most three red edges, where a polynomial-time \(3\)-approximation exists. [Lesca, Perny and Yokoo (2017)](https://aamas.csc.liv.ac.uk/Proceedings/aamas2017/pdfs/p308.pdf)
No result settling exactly the mass-frequency formulation above was located in the literature search.

Results

The unrestricted decision problem is \(\mathrm{NP}\)-complete. It admits a polynomial-time \(m\)-approximation, but, unless \(\mathrm{P}=\mathrm{NP}\), no polynomial-time \(O(m^{1-\varepsilon})\)-approximation exists for any fixed \(\varepsilon>0\).

With at most three red edges, the mass-frequency problem is polynomial-time solvable exactly. Thus its achievable approximation ratio is \(1\). More generally, with \(k\) red edges, exact optimization takes \(2^{O(k)}\operatorname{poly}(m,\tau,L)\) time.

| Class | Decision complexity | Achievable ratio | Running time |
|---|---|---|---|
| Unrestricted | \(\mathrm{NP}\)-complete | \(m\) | \(O(m\tau\,\operatorname{poly}(L))\) |
| At most three red edges | \(\mathrm{P}\) | \(1\), exact | \(\operatorname{poly}(m,\tau,L)\) |

The unrestricted inapproximability also holds with \(m\) replaced by \(\tau\). These bounds exclude improvements by a fixed polynomial power; they do not assert that logarithmic improvements over the \(m\) guarantee are impossible.

If \(m=0\), then \(\operatorname{OPT}=0\). Below, assume \(m>0\).

1. A packing formulation

Write \(U=\bigcup_r P_r\), and extend the definition by \(V(\varnothing)=0\). Consider the packing problem

\( \displaystyle \operatorname{PACK}=\max\left\{\sum_{\varnothing\ne S\subseteq U}x_SV(S):x_S\ge0,\ \sum_{S\ni t}x_S\le\mu_t\text{ for every }t\in U\right\}. \)

We first prove \(\operatorname{PACK}=\operatorname{OPT}\).

Given an original feasible allocation, replace each coalition \(S\) by \(S\cap U\), discard empty coalitions, and combine repeated coalitions. Removing types outside \(U\) cannot destroy any rule’s positive requirements. It can only remove negative requirements that prevented activation. Because all rule values are positive,

\( V(S\cap U)\ge V(S). \)

This includes the empty-intersection case: if \(S\cap U=\varnothing\), no rule could have been active on \(S\). The resulting frequencies satisfy the packing constraints. Consequently, \(\operatorname{PACK}\ge\operatorname{OPT}\).

Conversely, complete any packing by adding singleton frequency equal to each type’s unused mass. This gives an original feasible allocation. Existing coalitions retain their values, and added singleton values are nonnegative. Hence \(\operatorname{OPT}\ge\operatorname{PACK}\).

Every feasible packing also satisfies

\( \displaystyle \sum_Sx_S\le\sum_S|S|x_S=\sum_{t\in U}\sum_{S\ni t}x_S\le\sum_{t\in U}\mu_t\le1. \)

This bound will justify an explicit upper bound in the compact linear program.

2. Unrestricted hardness and membership in \(\mathrm{NP}\)

Let \(G=(W,E)\) be an instance of maximum independent set, with \(n=|W|\ge1\). Define

\( p=2^{\lceil\log_2(n+1)\rceil}. \)

Create one type \(a\), one type \(t_w\) for each \(w\in W\), and \(p-n-1\) additional types that occur in no rule. Give every type mass \(1/p\). Thus \(\tau=p\), all masses are positive dyadic rationals, and their sum is \(1\).

For each \(w\in W\), create the rule

\( \displaystyle P_w=\{a,t_w\},\qquad N_w=\{t_z:\{w,z\}\in E\},\qquad v_w=1. \)

These rules satisfy all input requirements, and \(m=n\).

For a coalition \(S\) containing \(a\), let \(I(S)\) be the vertices whose rules are active on \(S\). This is an independent set: if adjacent vertices \(w,z\) both belonged to \(I(S)\), activation of \(w\)’s rule would require \(t_z\notin S\), while activation of \(z\)’s rule would require \(t_z\in S\). Therefore

\( V(S)=|I(S)|\le\alpha(G), \)

where \(\alpha(G)\) is the maximum independent-set size. Coalitions without \(a\) have value zero. Every feasible allocation consequently satisfies

\( \displaystyle \sum_Sx_SV(S)\le\alpha(G)\sum_{S\ni a}x_S=\frac{\alpha(G)}p. \)

For the reverse inequality, choose a maximum independent set \(I\). Assign frequency \(1/p\) to the coalition

\( S_I=\{a\}\cup\{t_w:w\in I\}, \)

and put all remaining types into singleton coalitions with frequency \(1/p\). Exactly the rules indexed by \(I\) activate on \(S_I\). Thus

\( \displaystyle \operatorname{OPT}=\frac{\alpha(G)}p. \)

Taking \(q=\ell/p\) gives a polynomial-time reduction from the independent-set decision problem. In particular, normalization of masses and fractional frequencies do not invalidate the reduction.

To prove membership in \(\mathrm{NP}\), consider the original finite linear program with its \(2^\tau-1\) variables. Its feasible region is nonempty, since singleton frequencies suffice, and compact, since each variable satisfies \(x_S\le\min_{t\in S}\mu_t\). An optimal extreme point therefore exists.

At an extreme point, the incidence columns corresponding to positive variables must be linearly independent. Otherwise, a nonzero dependence permits sufficiently small perturbations in both directions while preserving feasibility, contradicting extremality. Hence at most \(\tau\) frequencies are positive.

These frequencies have polynomial bit length. Indeed, choose a nonsingular square submatrix of their incidence columns. Its entries are in \(\{0,1\}\). Clear the denominators of the corresponding masses using their product, whose bit length is \(O(L)\). Cramer’s rule and Hadamard’s determinant bound give frequency encodings of length \(O(L+\tau\log\tau)\).

A certificate can therefore list at most \(\tau\) coalitions and their rational frequencies. All mass equations and the threshold inequality can be checked exactly in polynomial time. The decision problem is \(\mathrm{NP}\)-complete.

3. Unrestricted approximation

For each rule, define

\( \displaystyle b_r=\min_{t\in P_r}\mu_t. \)

In any feasible allocation, the total frequency of coalitions activating rule \(r\) is at most \(b_r\). To see this, every such coalition contains every type in \(P_r\), so its combined frequency is bounded by each corresponding mass. Reordering the finite objective sum yields

\( \displaystyle \operatorname{OPT}\le\sum_r v_rb_r. \)

Choose a rule \(r^\star\) maximizing \(v_rb_r\). Allocate frequency \(b_{r^\star}\) to \(P_{r^\star}\) and complete the allocation with singleton frequencies. Since \(P_{r^\star}\cap N_{r^\star}=\varnothing\), that coalition activates \(r^\star\). Its welfare is therefore at least

\( \displaystyle v_{r^\star}b_{r^\star}\ge\frac1m\sum_rv_rb_r\ge\frac{\operatorname{OPT}}m. \)

Computing these minima and comparing the products uses \(O(m\tau)\) rational operations on polynomial-bit numbers. The output has at most \(\tau+1\) coalitions.

For inapproximability, use the reduction in Section 2. From any explicitly represented feasible allocation of welfare \(W_{\mathrm{alg}}\), one can extract an independent set of size at least \(pW_{\mathrm{alg}}\), because

\( \displaystyle pW_{\mathrm{alg}}=\sum_{S\ni a}(px_S)|I(S)|,\qquad \sum_{S\ni a}px_S=1. \)

The right-hand side is a convex combination of the extracted independent-set sizes. Thus some listed coalition gives an independent set at least as large as the average. A \(\rho\)-approximation for the allocation problem would give a \(\rho\)-approximation for maximum independent set.

Zuckerman proved that, for every fixed \(\delta>0\), approximating maximum clique within \(n^{1-\delta}\) is \(\mathrm{NP}\)-hard; complementing the graph gives the identical statement for maximum independent set. [Zuckerman (2007)](https://www.theoryofcomputing.org/articles/v003a006/)

Since \(m=n\), an \(O(m^{1-\varepsilon})\)-approximation would contradict that theorem, absorbing the constant by using a smaller positive exponent. Moreover,

\( n+1\le\tau=p<2(n+1), \)

so the same argument excludes \(O(\tau^{1-\varepsilon})\)-approximation unless \(\mathrm{P}=\mathrm{NP}\).

4. A compact exact linear program for few red edges

Let \(B\) be the rules incident to at least one red edge, and let \(R_0\) be the remaining rules. If there are \(k\) red edges, then

\( |B|\le2k. \)

A crucial property is

\( N_r\cap U=\varnothing\qquad\text{for every }r\in R_0. \)

Indeed, if \(t\in N_r\cap P_s\), then \(s\ne r\), because \(P_r\cap N_r=\varnothing\). The pair \(r,s\) would have a red edge, contradicting \(r\notin B\). Consequently, on coalitions contained in \(U\), each rule in \(R_0\) activates exactly when all its positive types are present.

Let \(\mathcal A\) contain all subsets \(A\subseteq B\) with no red edge between two members. For each such \(A\), define

\( P_A=\bigcup_{r\in A}P_r,\qquad N_A=\bigcup_{r\in A}N_r. \)

Then \(P_A\cap N_A=\varnothing\): an intersection would witness either a forbidden self-intersection or a red pair inside \(A\). Also,

\( K:=|\mathcal A|\le2^{|B|}\le2^{2k}. \)

Introduce these nonnegative variables for every \(A\in\mathcal A\):

• \(z_A\): total frequency assigned to this block;
• \(u_{A,t}\), for \(t\in U\): frequency within this block consuming type \(t\);
• \(y_{A,r}\), for \(r\in R_0\): frequency credited with activating rule \(r\).

The linear program maximizes

\( \displaystyle F=\sum_{A\in\mathcal A}\left(z_A\sum_{r\in A}v_r+\sum_{r\in R_0}v_ry_{A,r}\right), \)

subject to

\( 0\le z_A\le1,\qquad 0\le u_{A,t}\le z_A, \)

\( u_{A,t}=z_A\quad(t\in P_A),\qquad u_{A,t}=0\quad(t\in N_A\cap U), \)

\( 0\le y_{A,r}\le u_{A,t}\quad(r\in R_0,\ t\in P_r), \)

and

\( \displaystyle \sum_{A\in\mathcal A}u_{A,t}\le\mu_t\quad(t\in U). \)

Rules in \(B\setminus A\) are not required to be inactive in block \(A\). The proof below explains why their possible extra activation causes no difficulty.

We prove that the optimum of this linear program equals \(\operatorname{OPT}\).

Every packing gives a feasible LP point of the same value.

For each coalition \(S\subseteq U\), classify it by the set \(A\) of rules in \(B\) that it activates. Two rules joined by a red edge cannot activate on the same coalition, so \(A\in\mathcal A\).

Within each class, set \(z_A\) to its total frequency, \(u_{A,t}\) to the frequency containing \(t\), and \(y_{A,r}\) to the frequency activating \(r\). The total-frequency bound from Section 1 gives \(z_A\le1\). Activation of every rule in \(A\) gives the forced-presence and forced-absence constraints. Activation of a rule in \(R_0\) implies presence of each type in its positive set, giving \(y_{A,r}\le u_{A,t}\).

The objective is exactly the packing’s welfare, since it counts every active rule. Therefore the LP optimum is at least \(\operatorname{PACK}=\operatorname{OPT}\).

Every feasible LP point gives a packing with at least its objective value.

Fix a block \(A\). For \(0<h\le z_A\), define

\( S_A(h)=\{t\in U:u_{A,t}\ge h\}. \)

Use each constant interval of this nested family as a coalition frequency equal to the interval’s length. Discard empty coalitions. This is a finite construction: its breakpoints are the values \(u_{A,t}\), together with \(0\) and \(z_A\).

Each type \(t\) occurs for total frequency exactly \(u_{A,t}\). Hence combining all blocks respects the mass capacities.

Every rule in \(A\) activates throughout its block: positive types have \(u_{A,t}=z_A\), and negative types in \(U\) have \(u_{A,t}=0\). Negative types outside \(U\) never occur.

For \(r\in R_0\), we have \(N_r\cap U=\varnothing\). Its activation frequency in the nested family is therefore exactly

\( \displaystyle \min_{t\in P_r}u_{A,t}\ge y_{A,r}. \)

Thus every block earns at least its credited objective contribution. Additional rules in \(B\setminus A\) can only increase welfare because their values are positive.

The resulting packing consequently has welfare at least \(F\). Section 1 completes it to an original feasible allocation without decreasing welfare. Therefore \(\operatorname{OPT}\ge F\) for every feasible LP point.

The two inequalities prove exactness.

5. Complexity and consequences

The compact LP has

\( O(K(m+\tau)) \)

variables and

\( O\!\left(\tau+K(m\tau+\tau+1)\right) \)

constraints. Its coefficients consist of input masses and values, their sums, and \(0,\pm1\). Its encoding length is therefore polynomial in \(K,m,\tau,L\).

The standard polynomial-time theorem for rational linear programming applies: this is an explicitly encoded rational LP, it is feasible at the zero point, and all variables are bounded by \(1\). Exact optimization and comparison with the rational threshold take

\( \displaystyle 2^{O(k)}\operatorname{poly}(m,\tau,L) \)

bit time. The nested construction recovers an optimal rational allocation using at most

\( K(|U|+1)+\tau \)

coalitions, also in polynomial time for fixed \(k\).

For at most three red edges, \(K\le64\), giving polynomial-time exact optimization and approximation ratio \(1\).

The discrete NP-hardness with three red edges established by [Lesca, Perny and Yokoo (2017)](https://aamas.csc.liv.ac.uk/Proceedings/aamas2017/pdfs/p308.pdf) therefore does not extend to this mass-frequency formulation. The exactness proof above uses fractional frequencies to realize nested coalitions within each block.

⟨structured verdict parsed — rendered above⟩

The prover’s output resolves both requested classes. The unrestricted problem is \(\mathrm{NP}\)-complete, with the stated approximation guarantee and hardness. The problem with at most three red edges is exactly solvable in polynomial time. I found no major or minor mathematical issues.

• Packing equivalence

The restriction to \(U=\bigcup_r P_r\) is valid. Removing types outside \(U\) preserves every positive requirement and can remove negative blockers. Positivity of rule values therefore justifies \(V(S\cap U)\ge V(S)\). If the intersection is empty, the original coalition activates no rule because every \(P_r\) is nonempty and contained in \(U\).

The projected frequencies satisfy the packing capacities. Conversely, filling unused mass with singleton frequencies produces an allocation satisfying every original mass equality. Adding these frequencies cannot decrease welfare.

Both directions establish \(\operatorname{PACK}=\operatorname{OPT}\). The total-frequency bound is also correct: every retained coalition is nonempty, so its frequency contributes at least once to total mass consumption. This justifies the later bound \(z_A\le1\).

• Unrestricted hardness

The reduction respects the input requirements. The chosen \(p\) satisfies \(p\ge n+1\), so the number of padding types is nonnegative. There are exactly \(p\) types, each with positive mass \(1/p\), and their masses sum to \(1\). The construction has polynomial encoding length.

For the standard simple-graph independent-set problem, each rule has disjoint positive and negative sets. Its positive set is nonempty and its value is positive.

The argument that simultaneously active vertex rules form an independent set is correct. Adjacent vertices would impose contradictory presence and absence requirements on a vertex type. Every coalition with positive value contains \(a\), whose total available frequency is \(1/p\). Thus the upper bound \(\operatorname{OPT}\le\alpha(G)/p\) follows.

The proposed allocation attains that bound. Its main coalition activates precisely the rules indexed by the chosen independent set, and all remaining singleton coalitions have value zero because they lack \(a\). Every type receives exactly its prescribed mass.

Consequently, the identity \(\operatorname{OPT}=\alpha(G)/p\) and the threshold reduction \(q=\ell/p\) are valid.

• Membership in \(\mathrm{NP}\)

The original feasible region is nonempty and compact. Singleton frequencies establish feasibility; each nonempty coalition variable is bounded by the mass of any type it contains.

The support-size argument is correct. A linear dependence among positive incidence columns permits sufficiently small perturbations in both directions that preserve the mass equations and nonnegativity, contradicting extremality. An optimal extreme point therefore has at most \(\tau\) positive variables.

The rational-size argument also holds. Independent positive columns admit a nonsingular square row submatrix. Clearing the corresponding mass denominators requires \(O(L)\) bits, and the determinant bounds for a binary matrix give the stated polynomial frequency encoding length.

The certificate lists polynomially many explicitly represented coalitions and rational frequencies. Their feasibility and welfare can be checked exactly in polynomial time. Together with the reduction, this proves \(\mathrm{NP}\)-completeness.

• Unrestricted approximation guarantee

For every rule \(r\), its activation frequency is bounded by each mass in \(P_r\), hence by \(b_r\). Summing its contribution over rules therefore gives the valid upper bound \(\operatorname{OPT}\le\sum_r v_rb_r\).

Allocating frequency \(b_{r^\star}\) to \(P_{r^\star}\) is feasible, and this coalition activates \(r^\star\) because its positive and negative sets are disjoint. Singleton completion preserves feasibility and cannot reduce welfare.

The displayed inequalities correctly establish the \(m\)-approximation. The operation count \(O(m\tau)\), with polynomial bit cost per rational operation, supports the claimed \(O(m\tau\,\operatorname{poly}(L))\) running time. The output-size bound is valid.

• Unrestricted approximation hardness

The extraction argument is correct for an explicitly represented feasible allocation. The coefficients \(px_S\) of coalitions containing \(a\) are nonnegative and sum to \(1\). Their independent-set sizes therefore have weighted average \(pW_{\mathrm{alg}}\), so some listed coalition yields an independent set at least that large.

Combined with the exact optimum identity, this transfers the approximation factor without loss.

The cited theorem has the stated strength: Zuckerman establishes \(\mathrm{NP}\)-hardness of approximating maximum clique within \(n^{1-\delta}\) for every fixed positive \(\delta\). Graph complementation transfers it to independent set. [Zuckerman (2007)](https://www.theoryofcomputing.org/articles/v003a006/)

The constant hidden in \(O(m^{1-\varepsilon})\) can be absorbed by choosing a smaller positive exponent, as stated. Since \(m=n\) and \(n+1\le\tau<2(n+1)\), both claimed inapproximability parameterizations follow.

• Structure with few red edges

The bound \(|B|\le2k\) correctly counts endpoints of the \(k\) unordered red pairs.

The crucial assertion \(N_r\cap U=\varnothing\) for \(r\in R_0\) is valid. Any contrary intersection would either violate the rule’s own disjointness requirement or create a red edge incident to \(r\).

For every permitted \(A\), the disjointness \(P_A\cap N_A=\varnothing\) follows from exactly the same two possibilities: a forbidden self-intersection or a red pair within \(A\). The enumeration bound \(K\le2^{2k}\) is correct.

• Packing-to-LP direction

Classifying a coalition by its active rules in \(B\) gives a permitted block: two rules connected by a red edge cannot both activate.

All stated LP constraints follow from the corresponding frequencies. Forced presence and absence hold for every coalition in a block; activation frequencies for rules in \(R_0\) are bounded by the frequency containing each required positive type.

The objective counts every active rule exactly once. Thus this direction correctly establishes that the LP optimum is at least \(\operatorname{OPT}\).

• LP-to-packing direction

The nested family is finite after dividing at its breakpoints. A type \(t\) occurs for total frequency exactly \(u_{A,t}\), so the combined construction satisfies the packing capacities.

Every rule in \(A\) activates throughout its block because its positive types have frequency coordinate \(z_A\), while its negative types have coordinate zero or lie outside \(U\). For nonempty \(A\), discarding empty coalitions cannot remove credited activation, since \(P_A\) is nonempty.

A rule in \(R_0\) has no negative type in \(U\). Its activation frequency in the nested family is consequently exactly \(\min_{t\in P_r}u_{A,t}\), which is at least \(y_{A,r}\). Breakpoint endpoints have zero interval length and do not affect these frequency calculations.

Possible activation of additional rules only increases welfare. An empty coalition carries no credited contribution because every positive set is nonempty.

This establishes the reverse inequality and proves exactness of the compact LP. The construction does not require unproved compatibility conditions among the credited \(R_0\) rules.

• Complexity and edge cases

The variable and constraint counts are valid upper bounds. All coefficients are rational with encoding length polynomial in the stated parameters; summing input rule values preserves polynomial bit length.

The rational LP theorem applies to an explicitly encoded, feasible, bounded LP. Nonemptiness of every \(P_r\) also ensures that each \(y_{A,r}\) is bounded by \(1\). Exact optimization and rational threshold comparison therefore have the claimed \(2^{O(k)}\operatorname{poly}(m,\tau,L)\) bit complexity.

The allocation recovery bound follows from the number of breakpoint intervals per block and the singleton completion. For \(k\le3\), \(K\le64\), giving polynomial-time exact optimization and approximation ratio \(1\).

The case \(m=0\) is correctly separated: welfare is identically zero, and the decision reduces to comparison with \(q\). Arbitrary rational thresholds introduce no additional difficulty.

No repair or additional mathematical clarification is needed. The distinction from discrete partitions is supported by the proof: the reverse LP construction uses fractional coalition frequencies.

⟨structured verdict parsed — rendered above⟩