d4-conf-atal-2010-0069 (d4-conf-atal-2010-0069)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), a weighted undirected compatibility graph on types, a threshold \(q\), nonnegative type payoff rates \(r_t\) with \(\sum_{t\in T}\mu_t r_t=1\), and \(\varepsilon\geq 0\), decide whether every coalition mass vector \(x\) with \(0\leq x_t\leq\mu_t\) satisfies \(\sum_{t\in T}r_t x_t\geq v_q(x)-\varepsilon\). Here \(v_q(x)=1\) exactly when a matching flow using mass from coalition \(x\) reaches value at least \(q\), with a same-type pair consuming two units of that type; otherwise \(v_q(x)=0\).

A society is given by its support \(T\): the list of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) counts listed types, not all possible types.
The input includes an undirected compatibility graph \((T,E)\), allowing loops, with \(m=|E|\) and nonnegative binary-rational edge weights \(w_e\). Set \(a_{te}=2\) for a loop at \(t\), \(a_{te}=1\) for a nonloop incident to \(t\), and \(a_{te}=0\) otherwise.
For a coalition \(x\in\mathbb R^T\) with \(0\le x_t\le\mu_t\), a matching flow is any \(y\in\mathbb R_{≥0}^{E}\) satisfying \(\sum_{e\in E}a_{te}y_e\le x_t\) for every \(t\); its value is \(\sum_{e\in E}w_ey_e\). Unmatched mass is allowed.
The binary-rational threshold \(q>0\) must be attainable by a matching flow for \(x=\mu\). Define \(v_q(x)=1\) if some matching flow for \(x\) has value at least \(q\), and \(v_q(x)=0\) otherwise.
Also given are nonnegative binary-rational payoff rates \(r_t\) with \(\sum_{t\in T}\mu_tr_t=1\), and a binary-rational \(\varepsilon\ge0\). Membership means \(\sum_{t\in T}r_tx_t\ge v_q(x)-\varepsilon\) for every coalition \(x\), including \(0\) and \(\mu\). Let \(L\) be the total binary input length.

Is this continuous \(\varepsilon\)-core membership problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?

Discrete threshold matching \(\varepsilon\)-core membership is reported \(\mathrm{NP}\)-hard via an oracle reduction, even on disjoint edges ([Aziz, Brandt and Harrenstein](https://dss.in.tum.de/files/brandt-research/monocoop.pdf)).
For finite-player fractional matching games without thresholding, the least core and nucleolus are polynomial-time computable ([Chen, Lu and Zhang](https://www.hongyangzhang.com/cooperative_games_aaai12.pdf)); this concerns a different valuation and coalition domain. No result settling the exact continuous problem above was located.

Result

The continuous \(\varepsilon\)-core membership problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). It reduces exactly to a rational linear program with \(m\) variables and \(\tau+m+1\) inequalities.

1. Losing coalitions impose no additional constraint

Write the payoff of a coalition \(x\) as \(p(x)=\sum_{t\in T}r_tx_t\).

Because \(r_t,x_t,\varepsilon\) are nonnegative, every losing coalition satisfies
\[ p(x)\ge 0\ge -\varepsilon=v_q(x)-\varepsilon. \]

Thus membership is equivalent to requiring \(p(x)\ge 1-\varepsilon\) for every winning coalition.

The included endpoint coalitions cause no difficulty: \(q>0\) implies \(v_q(0)=0\), while attainability and normalization give \(v_q(\mu)=1\) and \(p(\mu)=1\).

2. A linear program for the minimum winning payoff

Let \(A=(a_{te})_{t\in T,e\in E}\), and define the edge cost
\[ c_e=\sum_{t\in T}r_ta_{te}. \]
Hence \(c_e=r_u+r_v\) for a nonloop edge joining \(u,v\), and \(c_e=2r_t\) for a loop at \(t\).

Consider the linear program
\[ \alpha=\min\left\{\sum_{e\in E}c_ey_e: y\in\mathbb R_{\ge0}^{E},\quad Ay\le\mu,\quad \sum_{e\in E}w_ey_e\ge q \right\}. \]

Its feasible set is nonempty by the attainability promise. It is closed, since all its constraints are non-strict linear inequalities. It is also bounded: every column of \(A\) sums to \(2\), including loop columns, so every feasible \(y\) satisfies
\[ 2\sum_{e\in E}y_e =\sum_{t\in T}(Ay)_t \le\sum_{t\in T}\mu_t =1. \]
Therefore the feasible set is compact and the minimum is attained.

Claim. The value \(\alpha\) is exactly the minimum payoff of a winning coalition.

Proof. Let \(x\) be any winning coalition. By definition, there exists \(y\ge0\) with \(Ay\le x\) and \(\sum_e w_ey_e\ge q\). Because \(x\le\mu\), this \(y\) is feasible for the linear program. Moreover, nonnegativity of the payoff rates gives
\[ p(x)\ge r^{\mathsf T}Ay =\sum_{e\in E}c_ey_e \ge\alpha. \]

Conversely, let \(y^\star\) be an optimal solution and set \(x^\star=Ay^\star\). Then \(0\le x^\star\le\mu\), so \(x^\star\) is an allowed coalition. The flow \(y^\star\) is feasible for \(x^\star\) and attains value at least \(q\); hence \(x^\star\) is winning. Its payoff is
\[ p(x^\star)=r^{\mathsf T}Ay^\star =\sum_{e\in E}c_ey^\star_e =\alpha. \]
This proves the claim.

Consequently, the exact membership criterion is
\[ \boxed{\text{Membership holds if and only if }\alpha\ge1-\varepsilon.} \]

In particular, equality gives membership. If \(\alpha<1-\varepsilon\), the coalition \(x^\star=Ay^\star\) explicitly witnesses nonmembership.

3. Polynomial running time and exact comparison

We use the standard rational linear programming theorem: a linear program with binary-encoded rational coefficients can be solved in time polynomial in its dimensions and total encoding length; when a finite optimum is attained, an exact rational optimal solution can be obtained. Polynomial-time solvability in the rational bit model is reviewed in [Adler and Beling, *Polynomial Algorithms for Linear Programming over the Algebraic Numbers*](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).

All hypotheses apply here:

• There are \(m\) variables and \(\tau+m+1\) inequalities, counting nonnegativity.
• The entries of \(A\) belong to \(\{0,1,2\}\).
• All other coefficients are rational input data or the costs \(c_e\). Each cost is a sum of two input rates or twice one input rate, so its encoding length is polynomial in \(L\).
• The feasible set is nonempty and compact, as proved above.

Even a dense encoding of the program has length polynomial in \(m,\tau,L\). Thus an exact optimizer \(y^\star\), and hence the rational value \(\alpha\), can be computed in polynomial time. Comparing \(\alpha\) with the rational number \(1-\varepsilon\) by integer cross-multiplication is also polynomial-time. No numerical tolerance or strict-feasibility approximation is needed.

4. Why continuous coalitions permit this reduction

The decisive step is that \(x=Ay\) is itself an admissible coalition: each type contributes exactly the mass consumed by the flow. This removes unmatched mass without increasing payoff.

For coalitions restricted to selecting whole discrete players, that construction need not produce an admissible coalition. Thus a hardness argument for that discrete domain does not invalidate the exact linear-programming algorithm proved here.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated continuous problem correctly. The reduction preserves the full coalition domain, handles loops and boundary cases, and supports exact polynomial-time membership testing. No major or minor mathematical issues were found.

1. Losing coalitions and endpoints

The argument correctly uses \(r_t\ge 0\), \(x_t\ge 0\), and \(\varepsilon\ge 0\) to obtain \(p(x)\ge 0\ge-\varepsilon\). Thus every losing coalition satisfies its membership inequality.

For the zero coalition, feasibility requires \(Ay\le 0\). Since \(y\ge 0\) and every edge consumes mass at an incident type, this forces \(y=0\). Its value is zero, below \(q>0\), so \(v_q(0)=0\).

The attainability promise gives \(v_q(\mu)=1\), and normalization gives \(p(\mu)=1\). Its membership inequality holds for every allowed \(\varepsilon\).

Consequently, reducing membership to the inequalities for winning coalitions is valid.

2. Linear-program formulation

The objective coefficients are correct: \(c_e=\sum_t r_ta_{te}\) equals \(r_u+r_v\) for a nonloop and \(2r_t\) for a loop. Therefore the objective is exactly \(r^{\mathsf T}Ay\).

The constraints \(y\ge0\), \(Ay\le\mu\), and \(\sum_e w_ey_e\ge q\) express precisely the flows witnessing the threshold within the available population.

The stated count is correct: \(m\) variables, \(\tau\) capacity inequalities, \(m\) nonnegativity inequalities, and one threshold inequality.

3. Feasibility and attainment

Nonemptiness follows directly from the threshold-attainability promise.

Closedness follows from the finite collection of non-strict linear inequalities. The boundedness calculation is correct because every column of \(A\) sums to \(2\), including a loop column:

\(2\sum_e y_e=\sum_t(Ay)_t\le\sum_t\mu_t=1\).

Together with nonnegativity, this bounds every coordinate. Hence the feasible set is compact, and its continuous linear objective attains a minimum.

This reasoning remains valid when some weights or payoff rates are zero, or when types are isolated. An empty edge set cannot satisfy the promised positive attainable threshold, so it introduces no omitted valid instance.

4. Equality with the minimum winning payoff

Both directions are justified.

For any winning coalition \(x\), its witnessing flow satisfies \(Ay\le x\le\mu\) and the threshold constraint, so it is feasible for the program. Nonnegative rates give \(p(x)\ge r^{\mathsf T}Ay\ge\alpha\). This establishes the lower bound for every winning coalition.

Conversely, an attained optimizer \(y^\star\) produces \(x^\star=Ay^\star\). Nonnegative incidence coefficients and flow coordinates give \(x^\star\ge0\); the capacity constraints give \(x^\star\le\mu\). Thus this is an admissible continuous coalition. The same flow witnesses that it is winning, and its payoff equals \(\alpha\).

The claim therefore establishes an attained minimum, rather than merely an infimum. No rounding or discrete-coalition assumption enters the argument.

5. Membership criterion and boundary cases

Since losing coalitions automatically satisfy their inequalities and the minimum winning payoff is \(\alpha\), membership is equivalent to \(\alpha\ge1-\varepsilon\).

The direction of comparison and treatment of equality are correct. If the inequality fails, the constructed winning coalition violates membership strictly.

The reasoning also covers \(\varepsilon\ge1\): the required winning payoff is then nonpositive, while every payoff is nonnegative.

6. Polynomial time and exact arithmetic

The invoked rational linear-programming theorem is stated sufficiently precisely for this application: binary-encoded rational linear programs admit polynomial-time solution, including an exact rational optimizer when a finite attained optimum exists. The cited paper explicitly reviews polynomial-time solvability of rational linear programs in terms of binary input length. [Adler and Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).

All required hypotheses are verified in the write-up:

• The program has polynomially bounded dimensions.
• Its coefficients are rational.
• Each constructed cost uses only two input rates, counting a loop rate twice, so coefficient lengths remain polynomial.
• Even the dense matrix representation has polynomial total length.
• Feasibility and a finite attained optimum have already been established.

The theorem supplies an exact optimizer with polynomial output length. Computing its rational objective and comparing it with \(1-\varepsilon\) by integer cross-multiplication therefore takes polynomial time. The argument does not require positive interior volume, strict feasibility, or a numerical tolerance.

7. Relation to the discrete problem

The explanation identifies the actual domain-dependent step: \(Ay^\star\) is an admissible coalition in the stated continuous model. It makes no unsupported claim that this construction preserves admissibility for whole-player coalitions.

The continuous polynomial-time conclusion therefore does not depend on resolving either cited discrete result.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩