we-solve (beta)

Econ-357 · economics · computer science · Computational economics

A matching with highest stability probability in the lottery model

LLM status Open unverified

Statement

MM-04 |  Matching markets and allocation

Published question

Definitions and assumptions

Let $U,W$ be disjoint sets of $n$ agents, each ranking all agents on the other side. For every agent $a$, the input explicitly lists strict preference orders $P_a^1,\ldots,P_a^{k_a}$ and rational probabilities $q_{a1},\ldots,q_{ak_a}\ge0$ summing to one. Agents' lotteries are independent. For a perfect matching $M$, let \[ p_I(M)=\sum_{(j_a)_a}\left(\prod_a q_{a j_a}\right) \ind\{M\text{ has no blocking pair under }(P_a^{j_a})_a\}. \] A blocking pair consists of two agents who each strictly prefer one another to their partner. Input length includes every listed order and the binary encodings of the rational probabilities.

Formal question

Determine the complexity of computing \[ M^*\in\argmax_{M\text{ perfect}}p_I(M), \] and of deciding, for a rational $\tau\in[0,1]$, whether some perfect matching satisfies $p_I(M)\ge\tau$. Give a polynomial-time algorithm or an appropriate hardness classification, with any useful tractable restrictions stated explicitly.

Scope and status

This is the lottery-model "SM HighestProbability" gap in the source's Table 1. It is distinct from evaluating the probability of a given matching, which can itself be a difficult counting problem; a matching witness alone therefore does not establish NP membership of the threshold problem. Independence is part of this model, and replacing it with an explicitly listed joint distribution changes the computational input. At least one matching has positive stability probability, since every realized strict complete profile admits a stable matching. The 2020 primary journal paper retains this optimization case as an open classification; no stronger claim of present-day status is made here.

References for the source of the problem

Katarína Cechlárová, Ágnes Cseh, and David F. Manlove (2019), Selected open problems in Matching Under Preferences, Section 3.1.2, Table 1: https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf. Haris Aziz, Péter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari (2020), Stable Matching with Uncertain Linear Preferences, Algorithmica 82, pp. 1410--1433, Table 3 and "Results": https://doi.org/10.1007/s00453-019-00650-0.

Common conventions: Source mathematical conventions

Well-defined objects. All probability spaces and measurable variables are specified or inherited from a local statistical model. Expectations used as finite targets require the stated integrability. A decision rule or estimator is measurable with respect to its available information; randomized rules may use an auxiliary independent random variable. Norms without a subscript are Euclidean in finite-dimensional spaces. An optimizer is requested only when attainment is assured; otherwise the question concerns the optimal value and $\varepsilon$-optimal admissible rules for every $\varepsilon>0$.

Identification. A structural model $m\in\mathcal M$ implies an observable law $P_m^{\rm obs}$ and target $\theta(m)$. The target is point identified on $\mathcal M$ if \[ P_{m_1}^{\rm obs}=P_{m_2}^{\rm obs} \quad\Longrightarrow\quad\theta(m_1)=\theta(m_2) \qquad(m_1,m_2\in\mathcal M). \] When this fails, the sharp identified set is \[ \Theta(P;\mathcal M)=\{\theta(m):m\in\mathcal M, P_m^{\rm obs}=P\}. \] Specifying an intervention or estimand does not establish identification. Positivity, exclusion, causal sufficiency, measurement restrictions, and transport assumptions are substantive local inputs, never automatic consequences of notation.

Minimax risk and nontrivial inference. For a statistical experiment with data law $P^{(n)}$, target $\theta(P)$, and nonnegative loss $\ell$, define \[ \mathcal R_n(\mathcal P,\ell) =\inf_{\widehat\theta_n}\sup_{P\in\mathcal P} \E_{P^{(n)}}\ell(\widehat\theta_n,\theta(P)). \] The infimum is over measurable estimators. A sharp rate is a sequence $r_n$ for which $0<c\leq C<\infty$, independent of $n$, satisfies $c r_n\leq\mathcal R_n\leq C r_n$ for all sufficiently large $n$. Squared-error parametric risk is of order $n^{-1}$; the corresponding root-mean-squared error is of order $n^{-1/2}$. These different conventions are distinguished locally. A uniform asymptotic confidence region $C_n$ must satisfy \[ \liminf_{n\to\infty}\inf_{P\in\mathcal P} \Pr_{P^{(n)}}\{\theta(P)\in C_n\}\geq 1-\alpha, \qquad 0<\alpha<1, \] together with an informative diameter or expected-width requirement. Coverage alone permits the vacuous whole parameter space. Testing questions similarly impose both size control and power against a declared separated alternative class.

Binary causal baseline. When an entry explicitly invokes this baseline, one observes independent copies of $O=(X,W,Y)$, with $W\in\{0,1\}$ and potential outcomes $Y(0),Y(1)$. Assume consistency $Y=Y(W)$, no interference, conditional exchangeability $(Y(0),Y(1))\perp W\mid X$, and overlap $\epsilon\leq e(X)\leq1-\epsilon$ almost surely for a fixed $0<\epsilon<1/2$, where \[ e(x)=\Pr(W=1\mid X=x),\qquad m_w(x)=\E[Y\mid W=w,X=x],\qquad \tau(x)=m_1(x)-m_0(x). \] These assumptions identify conditional mean effects almost everywhere under the covariate law. Pointwise or uniform effects require appropriate regularity and a specified support. Continuous treatment, longitudinal data, adaptive experiments, and network interference require their own assumptions in place of this baseline. Bounded outcomes, densities, and smoothness are additional assumptions only where stated.

Function classes. On $[0,1]^d$, $\mathcal H_d^s(L)$ is the isotropic Hölder ball of radius $L>0$: put $k=\lceil s\rceil-1$ and $\gamma=s-k\in(0,1]$, bound derivatives through order $k$, and require the order-$k$ derivatives to be $\gamma$-Hölder with constant at most $L$. Thus integer orders use a Lipschitz final derivative convention. The class $\operatorname{BV}_d(L)$ consists of functions $f\in L^1((0,1)^d)$ whose distributional derivative is a finite vector measure and for which $\|f\|_{L^1}+|Df|((0,1)^d)\leq L$. An $L^\infty$ bound or a particular pointwise version is imposed separately when needed. Sparse and neural-network classes require a declared dictionary or architecture and coefficient bounds.

An anisotropic Hölder class with declared block smoothness indices means coordinatewise Hölder regularity in each block, uniformly in the other blocks, with all corresponding derivative and Hölder bounds at most the stated radius. Derivative orders and the integer-order convention in each block are those just given. Mixed-derivative bounds are additional restrictions only when explicitly stated.

Decision and computational questions. Policy regret compares admissible feasible policies under the same law and constraints. In computational entries, finite data and thresholds have rational encodings; running time is measured in their total bit length. Real-valued equilibrium search uses the explicitly declared algebraic or FIXP encoding. An approximation ratio for maximization is written $\operatorname{OPT}/\operatorname{ALG}$ and for minimization as $\operatorname{ALG}/\operatorname{OPT}$, with zero optima and infeasible instances handled locally. Historical approximation bounds are not automatically current bounds.

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Econ-357-A2 · Exploration · LLM-generated · claude opus 5.5 high ·

Claude Opus 5.5 High attempt on Econ-357

A matching with highest stability probability in the lottery model: NP-hardness via MAX-2SAT

Abstract

We prove that deciding whether some perfect matching has stability probability at least $\tau$ in the lottery model is NP-hard. Hence computing $M^*\in\arg\max p_I(M)$ is NP-hard. The hardness holds even when every man has a single deterministic order. In that case $p_I(M)$ can be evaluated in polynomial time, so the threshold problem is NP-complete. Women's lotteries use at most $K+1$ orders, and all probabilities are $1/2$ or a single small rational $\varepsilon$. In general, the threshold problem lies in $\mathrm{NP}^{\mathrm{PP}}$. The threshold $\tau=1$ is special: it is equivalent to super-stability with respect to intersection partial orders. The exact complexity class of the general threshold problem is left open.

1. Two structural facts

For an agent $a$ with support orders $P_a^1,\dots,P_a^{k_a}$, write $x\rhd_a y$ when $x$ is above $y$ in every supported order. This intersection relation is a strict partial order.
Lemma (Certain stability): $p_I(M)=1$ iff no pair $(m,w)\notin M$ satisfies both $\neg(M(m)\rhd_m w)$ and $\neg(M(w)\rhd_w m)$. That is, $M$ is super-stable for the partial orders $\rhd$.
Proof: The pair $(m,w)$ blocks with positive probability iff $m$ has a supported order with $w$ above $M(m)$ and $w$ has a supported order with $m$ above $M(w)$. Lotteries are independent and finite, so this probability is positive exactly when both conditions hold. The first is $\neg(M(m)\rhd_m w)$ and the second is $\neg(M(w)\rhd_w m)$. There are finitely many pairs, so $p_I(M)=1$ iff no pair blocks with positive probability. ∎
Thus the case $\tau=1$ reduces to super-stability under partially ordered lists, a classical deterministic problem with known polynomial algorithms in the matching-under-preferences literature [irving94,manlove]. The case $\tau=0$ is trivial, because some matching is stable for each realised profile. The difficulty lies strictly between these thresholds.
Lemma (One deterministic side): If every man has a single order, then for every perfect matching $M$ \[ p_I(M)=\prod_{w}\Pr\left(M(w)\text{ is above every }m\in A_w(M)\setminus\{M(w)\}\text{ in }w\text{'s random order}\right), \] where $A_w(M)=\{m:\ w\succ_m M(m)\}$ is deterministic. Each factor is a sum over $w$'s listed orders, so $p_I(M)$ is polynomial-time computable.
Proof: With men deterministic, $(m,w)$ blocks iff $m\in A_w(M)$ and $w$'s realised order puts $m$ above $M(w)$. "No blocking pair" is therefore the intersection over $w$ of events depending only on $w$'s order, and these are independent. ∎

2. The reduction

MAX-2SAT asks, for 2-clauses $c_1,\dots,c_K$ over variables $x_1,\dots,x_N$ and an integer $V^*$, whether some assignment violates at most $V^*$ clauses. It is NP-complete [gjs]. Unit clauses $(\ell)$ may be replaced by $(\ell\vee z)$ and $(\ell\vee\neg z)$ with a fresh $z$; exactly one of these is violated iff $\ell$ is false. Hence we may assume every clause has two distinct variables. Fix the variable order and orient each clause on variables $u<v$: its $u$-literal is the man literal and its $v$-literal the woman literal.
Definition (Instance $I(\Phi,\varepsilon)$): For each variable $x$ create men $a_x,b_x$ and women $\alpha_x,\beta_x$. State T is $\{a_x\alpha_x,b_x\beta_x\}$ and state F is $\{a_x\beta_x,b_x\alpha_x\}$. Note that $a_x$ is unhappy (holds $\alpha_x$) exactly in T, and $b_x$ exactly in F.
  • For a clause $c$ with man literal $\ell_1$ on $u$, let $m_c=a_u$ if $\ell_1=\neg u$ and $m_c=b_u$ if $\ell_1=u$. Then $m_c$ holds $\alpha_u$ iff $\ell_1$ is false.
  • Men (deterministic). A man $m$ of gadget $u$ ranks $\beta_u$ first. Next come the women $\alpha_v$ of all clauses with $m_c=m$ (the slot), then $\alpha_u$, and then all other women arbitrarily.
  • $\beta_x$: orders $a_x\succ b_x\succ\cdots$ and $b_x\succ a_x\succ\cdots$, each with probability $1/2$.
  • $\alpha_x$: for each clause $c$ whose woman literal $\ell_2$ is on $x$, an order with probability $\varepsilon$. This order is $b_x\succ m_c\succ a_x\succ\cdots$ if $\ell_2=\neg x$, and $a_x\succ m_c\succ b_x\succ\cdots$ if $\ell_2=x$. The main order $a_x\succ b_x\succ\cdots$ receives the remaining probability.
Take $\varepsilon=2^{-(N+2)}(K+1)^{-2}$; it has $O(N+\log K)$ bits.
Lemma (Gadget-respecting matchings): If $M$ puts every gadget in state T or F, then \[ p_I(M)=2^{-N}\prod_x\left(1-\varepsilon v_x(M)\right), \] where $v_x(M)$ is the number of clauses with woman literal on $x$ that the induced assignment violates.
Proof: We use Lemma Lemma (One deterministic side). The man holding $\beta_x$ wants nobody. The other man holds $\alpha_x$ and wants $\beta_x$ and his slot. All other men hold women ranked above every woman outside their own gadget and slot. Hence $A_{\beta_x}$ is the unhappy gadget man, and the factor of $\beta_x$ is $1/2$ in both states. For $\alpha_x$, the main order ranks her own gadget men first. Her partner is either first, or second behind the happy gadget man, who does not want her; so the main order never fails. In the clause order of $c$, the only man placed above her partner who might want her is $m_c$. He is placed above the partner exactly when $\ell_2$ is false, and he wants $\alpha_x$ exactly when he is unhappy, i.e. when $\ell_1$ is false. The clause orders are disjoint events, so the factor of $\alpha_x$ is $1-\varepsilon v_x(M)$. ∎
Lemma (Leaks are costly): If $M$ is not gadget-respecting, then $p_I(M)\le\varepsilon K$.
Proof: Suppose first that $\beta_x$ is matched outside $\{a_x,b_x\}$. One of $a_x,b_x$ does not hold $\beta_x$ and ranks her first, while $\beta_x$ ranks both gadget men above every other man in both orders. This pair blocks surely, so $p_I(M)=0$. Otherwise $\beta_x$ is matched inside its gadget for every $x$. Pick a gadget $y_1$ whose $\alpha$ is matched outside; its other man $m_{y_1}$ then holds a woman outside his gadget. If she is in his slot, she is $\alpha_{y_2}$ with $y_2>y_1$, by the orientation, and $\alpha_{y_2}$ is also matched outside its gadget. Iterate. The indices increase, so we reach some $y_k$ whose man $m_{y_k}$ holds a woman below $\alpha_{y_k}$ in his list. He wants $\alpha_{y_k}$. In her main order, which has probability at least $1-\varepsilon K$, she ranks $m_{y_k}$ above her partner, who is outside her gadget. Hence $p_I(M)\le\varepsilon K$. ∎
Theorem: Let $\tau=2^{-N}(1-\varepsilon V^*)$. Then $\Phi$ has an assignment violating at most $V^*$ clauses iff some perfect matching of $I(\Phi,\varepsilon)$ has $p_I(M)\ge\tau$. Consequently the lottery-model HighestProbability threshold problem is NP-hard. It is NP-complete when one side is deterministic, and computing $M^*$ is NP-hard.
Proof: ($\Rightarrow$) For the gadget-respecting matching of an assignment with $V\le V^*$ violations, $\prod_x(1-\varepsilon v_x)\ge1-\varepsilon V\ge1-\varepsilon V^*$, because $\prod(1-t_i)\ge1-\sum t_i$ for $t_i\in[0,1]$. ($\Leftarrow$) Suppose every assignment violates at least $V^*+1$ clauses. Every respecting matching then has $\prod_x(1-\varepsilon v_x)\le e^{-\varepsilon(V^*+1)}\le1-\varepsilon(V^*+1)+\varepsilon^2(V^*+1)^2/2<1-\varepsilon V^*$, since $\varepsilon<2/(K+1)^2$. Every other matching has $p_I\le\varepsilon K\le2^{-N}/4<\tau$, since $1-\varepsilon V^*\ge3/4$. For the search problem, an optimal $M^*$ is gadget-respecting by the same bounds, and it encodes an assignment minimising violations. With deterministic men, Lemma Lemma (One deterministic side) places the threshold problem in NP. ∎
Proposition (General upper bound): For arbitrary independent lotteries, the threshold problem lies in $\mathrm{NP}^{\mathrm{PP}}$.
Proof: Guess $M$. Let $D$ be the product of all the lotteries' denominators. Then $D\,p_I(M)$ counts the weighted choices of one support order per agent under which $M$ has no blocking pair. Each choice is checkable in polynomial time, so comparing $D\,p_I(M)$ with $D\tau$ is a PP query. ∎

3. Verification and remaining questions

We implemented $I(\Phi,\varepsilon)$ for random 2-CNFs on three variables (six men), including unsatisfiable ones with $V_{\rm opt}=1,2$. We enumerated all $720$ perfect matchings with exact rational arithmetic. In every case the maximiser was gadget-respecting, $\max_Mp_I(M)\ge2^{-N}(1-\varepsilon V_{\rm opt})$ and $<2^{-N}(1-\varepsilon(V_{\rm opt}-1))$, and all non-respecting matchings satisfied the leak bound.

Open: (i) whether the general problem is $\mathrm{NP}^{\mathrm{PP}}$-complete, or remains in NP under a natural restriction with both sides random; (ii) bounded-list-length and bounded-support restrictions. Our gadgets use lists in which only $O(1+\deg)$ positions matter, but complete lists are formally required. (iii) Approximation. Since $\log p_I$ is additive over women in the one-sided case, the hardness of approximating MAX-2SAT transfers to additive approximation of $\log p_I$ only with care about the $\varepsilon$ scaling, which we do not pursue.

Completion Estimate

82%

This is a post hoc, heuristic estimate for the full catalogue target. An independent one-sided MAX-2SAT reduction establishes NP-complete threshold hardness and NP-hard optimizer search, with polynomial evaluation and a general counting-oracle upper bound. Arbitrary two-sided lotteries still lack a matching lower bound for the general threshold class, and bounded-support and approximation classifications remain unresolved.

References

  • [ccm] K. Cechlárová, Á. Cseh and D. F. Manlove, Selected open problems in Matching Under Preferences, Bulletin of the EATCS (2019), Section 3.1.2, Table 1. https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf.
  • [abgdmr] H. Aziz, P. Biró, S. Gaspers, R. de Haan, N. Mattei and B. Rastegari, Stable matching with uncertain linear preferences, Algorithmica 82 (2020), 1410--1433. https://doi.org/10.1007/s00453-019-00650-0.
  • [gjs] M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science 1 (1976), 237--267.
  • [irving94] R. W. Irving, Stable marriage and indifference, Discrete Applied Mathematics 48 (1994), 261--272.
  • [manlove] D. F. Manlove, Algorithmics of Matching Under Preferences, World Scientific (2013), chapters on indifference and partial orders.

Go to contribution →

Econ-357-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-357

A matching with highest stability probability in the lottery model: a research attempt

Target and outcome

Status: unresolved. The independent-lottery optimization problem is not settled here. This attempt provides an exact weighted-counting formulation, a decision-class upper bound, tractable evaluation under one-sided uncertainty, and a certified sampling approximation with explicitly exponential optimization. These results isolate two distinct bottlenecks: evaluating one matching and searching over matchings.

The 2020 primary paper [aziz] reports the lottery-model optimization gap and a polynomial result when only constantly many agents on one side are uncertain. Its results table also reports hard evaluation with two-sided uncertainty. Those statements concern the cited version; this attempt does not claim a comprehensive 2026 literature classification.

Integer counting with binary rational probabilities

For each agent $a$, write all its probabilities over a common denominator $d_a$, so $q_{aj}=w_{aj}/d_a$ with nonnegative integers $w_{aj}$ summing to $d_a$. Taking the product of the listed denominators is sufficient; its bit length is at most the sum of their bit lengths. Consequently \[ D=\prod_a d_a,\qquad N(M)=\sum_{(j_a)_a}\mathbf1\{M\text{ stable at }(j_a)_a\} \prod_a w_{a j_a},\qquad p_I(M)=N(M)/D \] have polynomial-length integer representations, though computing $N(M)$ need not take polynomial time.

For a fixed matching, $N(M)$ is a counting-function value. A nondeterministic machine guesses, for each agent, an integer ticket in $\{0,\ldots,d_a-1\}$ using binary strings and rejects out-of-range strings. Cumulative intervals of lengths $w_{aj}$ turn valid tickets into preference orders. It accepts precisely when the chosen profile has no blocking pair. There are $N(M)$ accepting branches. Checking stability takes $O(n^2)$ comparisons once rank tables have been constructed.

For a threshold $\tau=u/v$, the predicate is $vN(M)-uD\geq0$. Products by polynomial-bit integers and subtraction are expressible as differences of counting functions. To handle equality, the integer sign test $2(vN(M)-uD)+1>0$ is equivalent. Thus the fixed-matching threshold predicate belongs to PP, using its counting-gap characterization. Guessing a perfect matching and consulting this predicate gives \[ \text{existence of }M\text{ with }p_I(M)\geq\tau\quad\in\quad\mathrm{NP}^{\mathrm{PP}}. \] This is an upper bound, not completeness. It also explains why guessing a matching is insufficient to establish membership in NP: the verifier still has to compare a counting probability with the threshold.

One exact optimizer enumerates the $n!$ perfect matchings and all $\prod_a k_a$ profiles, taking $O(n!\,n^2\prod_a k_a)$ arithmetic operations plus bit costs. Alternatively, binary search on the integer interval $[0,D]$ with the existence oracle finds the optimal numerator. A matching witness can be recovered by successively fixing partners and making the corresponding constrained existential queries. This is an oracle description, not an efficient implementation of the unrestricted problem.

A factorization when one side is certain

Suppose every proposer $u$ has a deterministic ranking. For a fixed $M$ and receiver $w$, define \[ A_w(M)=\{u\ne M^{-1}(w):u\text{ ranks }w\text{ above }M(u)\}. \] Let \[ r_w(M)=\sum_j q_{wj}\mathbf1\{P_w^j\text{ ranks }M^{-1}(w) \text{ above every }u\in A_w(M)\}. \] Then \[ p_I(M)=\prod_w r_w(M). \] Indeed, a blocking pair involving $w$ exists exactly when its realized order ranks some member of $A_w(M)$ above its assigned partner. Once $M$ is fixed, these are events concerning different receivers' independent lotteries. The formula is therefore computable in time polynomial in the explicitly listed input.

This formula is useful but does not turn maximization into a standard weighted assignment problem: changing the partner of one proposer can change $A_w(M)$ for many receivers. Treating $\log r_w(M)$ as a fixed edge weight would be incorrect. In the fully deterministic restriction, ordinary deferred acceptance returns an optimizer with probability one. The broader constant-uncertainty result belongs to the cited paper, rather than being inferred from this product formula.

A small example and a check on tempting objectives

Let $n=2$. Both proposers independently choose either order with equal probability. Receiver $w_1$ always prefers $u_1$ and receiver $w_2$ always prefers $u_2$. The identity matching is stable with probability one: neither receiver ever wants to leave its partner. The crossed matching is stable only if both proposers prefer their crossed partners, an event of probability $1/4$. This example can be verified by listing four profiles and checking both matchings.

In general maximizing the expected number of satisfied agents, or minimizing the expected number of blocking pairs, is a different objective from maximizing the probability of zero blocking pairs. If one allocation has one blocking pair with probability $0.4$ and another has ten with probability $0.1$, their expected blocking counts and zero-block probabilities rank them oppositely. This probability calculation is an illustration of the objective distinction, not a claim that the displayed pair of distributions has been realized by a particular lottery instance.

Uniform sampling and its computational limitation

Draw $T$ independent profiles from the stated input lotteries. Let $\widehat p_T(M)$ be the fraction for which $M$ is stable. For any $\delta>0$, the bounded-variable exponential inequality and a union bound give \[ {\mathbb{P}}\left\{\max_M|\widehat p_T(M)-p_I(M)|>\delta\right\} \leq2n!\exp(-2T\delta^2). \] Hence taking \[ T\geq \frac{2}{\varepsilon^2}\log\frac{2n!}{\alpha} \] and choosing an exact empirical maximizer yields $p_I(\widehat M)\geq\max_Mp_I(M)-\varepsilon$ with probability at least $1-\alpha$. The proof adds two uniform errors of size $\varepsilon/2$. The sample count is polynomial in $n,1/\varepsilon,\log(1/\alpha)$, but enumerating all empirical candidates remains factorial. No polynomial-time approximation scheme is claimed.

There is also a universal existence floor. For each realized strict complete profile, at least one of the $n!$ matchings is stable. Taking expectations gives $\sum_Mp_I(M)\geq1$, so the optimum is at least $1/n!$. This floor is too small for an additive approximation to guarantee a useful multiplicative approximation.

Remaining obstacle

The counting upper bound does not supply a matching hardness reduction for optimization. Conversely, exact one-sided evaluation and polynomial sample complexity do not supply a polynomial search method. Settling the source gap requires a reduction that preserves independent per-agent lotteries, or an optimization algorithm exploiting stable-matching structure across exponentially many realized profiles. Neither is established here.

Completion Estimate

26%

This is a post hoc, heuristic estimate for the full catalogue target. Weighted counting, a counting-oracle upper bound, one-sided evaluation and uniform sampling guarantees clarify the optimization problem. Neither a polynomial-time search algorithm nor an optimization hardness reduction is supplied for the independent-lottery target.

References

Go to contribution →