we-solve (beta)

Econ-169 · economics · computer science · Computational economics

Approximating the least unpopularity margin

LLM status Open unverified

Statement

MM-02 |  Matching markets and allocation

Published question

Definitions and assumptions

In a house-allocation instance $I$, applicants $A$ strictly rank acceptable houses $H$, and houses have no preferences. A matching assigns at most one acceptable house to each applicant and at most one applicant to each house. Every acceptable house is preferred to being unmatched. For matchings $M,N$, let $\phi(N,M)$ count applicants strictly preferring their assignment in $N$ to their assignment in $M$. Set \[ \mu_I(M)=\max_{N\in\mathcal M(I)}[\phi(N,M)-\phi(M,N)], \qquad \mu^*(I)=\min_{M\in\mathcal M(I)}\mu_I(M). \] The comparison $N=M$ ensures $\mu_I(M)\ge0$. A matching is popular when no other matching receives more votes against it, equivalently when its margin is zero.

Formal question

Determine the approximation threshold for minimizing $\mu_I(M)$. For a multiplicative guarantee, require an algorithm to output $M$ with \[ \mu_I(M)\le\rho\mu^*(I) \] on every instance; in particular, it must output a popular matching whenever $\mu^*(I)=0$. Also characterize the best attainable additive guarantee $\mu_I(M)\le\mu^*(I)+g(|A|+|H|)$ and prove matching hardness bounds where possible.

Scope and status

The 2019 source identifies the optimization problem as NP-hard and explicitly asks for better approximation or inapproximability results. Computing the margin of a specified matching and optimizing over matchings are separate tasks. The zero optimum causes no undefined division in the displayed guarantee; however, a claimed ratio obtained by dividing by $\mu^*(I)$ would require a separate zero case. Additive approximation is a precise supplementary formulation of the source's broader approximation agenda, rather than a separately quoted conjecture. The entry makes no assertion that a particular contemporary approximation threshold is known.

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, Bulletin of EATCS 128, Section 3.1.1, Theorems 2--3 and concluding paragraph: https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf. Robert M. McCutchen (2008), The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences, LATIN 2008, pp. 593--604, is the primary paper cited for these criteria.

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 1

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

GPT 6 Astra Ultra attempt on Econ-169

Least unpopularity margin Additive amplification and deletion certificates

Problem ID: C78-165. Status: Unresolved; restricted results and reductions.

Target and scope

The target minimizes the maximum net number of votes against a house allocation. Write $n=|A|$, $N=|A|+|H|$, and $\Delta(Q,M)=\phi(Q,M)-\phi(M,Q)$. Thus $\mu(M)=\max_Q\Delta(Q,M)$ and $\mu^*=\min_M\mu(M)$. Preferences are strict, unacceptable assignments are prohibited, and unmatched is worse than every acceptable house.

The source survey [survey, Section 3.1.1, Theorems 1--3] distinguishes polynomial evaluation, polynomial recognition of a popular matching, and NP-hard minimization of the margin. Its final paragraph asks for stronger approximation results. We derive a precise additive hardness consequence of that stated NP-hardness, whose primary proof is [mcc, Theorem 5.2], and an additive algorithm parameterized by a small deletion certificate. These are self-contained reductions except for the two explicitly cited established algorithmic facts. No optimal multiplicative threshold is claimed.

A computable objective and its exact product structure

For a fixed matching $M$ append one private dummy house $d_a$ for each applicant, representing being unmatched. Every applicant must now be assigned a house, and only $a$ may use $d_a$. Give acceptable edge $(a,h)$ weight $1,0,-1$ according as $h$ is better than, equal to, or worse than $M(a)$. Give $(a,d_a)$ the corresponding weight for unmatched.
Lemma (Evaluation and certificates): The maximum weight of an applicant-saturating matching in this augmented bipartite graph equals $\mu(M)$. In particular $\mu(M)$ is an integer in $[0,n]$ and is computable in polynomial time, together with a maximizing challenger.
Proof: Remove dummy edges from any augmented matching to obtain a feasible original matching $Q$. Each applicant contributes exactly her vote to $\Delta(Q,M)$, including the unmatched case. Conversely every $Q$ has a unique augmentation by the private dummies, with that same weight. Maximizing proves the identity. Choosing $Q=M$ gives nonnegativity and there are only $n$ summands, each at most one. A maximum-weight bipartite assignment is computable in polynomial time; the dummy extension always makes an applicant-saturating assignment feasible. ∎
Proposition (Disjoint instances add): Suppose the acceptable graph is the disjoint union of instances $I_1,\ldots,I_t$, with no applicant accepting a house in another component. For every matching $M=\bigcup_jM_j$, \[ \mu_I(M)=\sum_{j=1}^t\mu_{I_j}(M_j),\qquad \mu_I^*=\sum_{j=1}^t\mu_{I_j}^*. \]
Proof: Every challenger is uniquely a tuple $(Q_1,\ldots,Q_t)$ and its vote margin is the sum of the component margins. Independent maximization over the finite sets of component challengers gives the first equality. Independent minimization over the finite sets of component matchings gives the second. In particular isolated applicants and houses contribute zero and cause no exceptional case. ∎

What replication actually proves about additive error

An additive guarantee is measured in $N$, the total number of vertices, not the bit length of the displayed preference lists.
Theorem (Polynomial-power additive hardness): Fix constants $C>0$ and $0<\epsilon\leq1$. A deterministic polynomial-time algorithm that always returns $M$ satisfying \[ \mu_I(M)\leq\mu_I^*+C N^{1-\epsilon} \] would yield a deterministic polynomial-time exact optimizer. Consequently such an algorithm is impossible unless $\mathrm P=\mathrm{NP}$, using the NP-hardness recorded in [survey, Theorem 3]. More generally the same implication holds for an error function $g$ if there is a polynomially bounded, polynomially computable integer $t(N)$ such that $g(t(N)N)<t(N)$.
Proof: Given a nonempty instance $I$, make $t$ disjoint labeled copies. Run the hypothetical algorithm on their union and write its restriction to copy $j$ as $M_j$. Proposition Proposition (Disjoint instances add) gives \[ \sum_{j=1}^t\mu_I(M_j)\leq t\mu_I^*+g(tN). \] If $g(tN)<t$, the average of the integer component margins is strictly less than $\mu_I^*+1$. Therefore at least one component has margin at most $\mu_I^*$. No component can have margin less than the optimum. Evaluate all $t$ margins by Lemma Lemma (Evaluation and certificates) and return a minimum one. This is an exact optimum, even when that optimum is zero.

For the displayed power bound, choose an integer $t$ strictly larger than $(C N^{1-\epsilon})^{1/\epsilon}$. Then $C(tN)^{1-\epsilon}/t=C N^{1-\epsilon}t^{-\epsilon}<1$. Since $C,\epsilon$ are fixed, a sufficiently large fixed constant times an integer power of $N$ supplies such $t$ with polynomial bit length and polynomially many copies. The transformed explicit input therefore has polynomial length and the reduction is polynomial. The empty instance is solved directly. ∎

This proof does not establish hardness for every $g(N)=o(N)$. For example, take $g(N)=N/\log(N+2)$. Then $g(tN)/t$ is of order $N/\log(tN)$ and need not be below one for polynomial $t$. The replication rate is an essential hypothesis. Randomized guarantees would require corresponding randomized complexity assumptions and a specified success probability; they are not included in the theorem.

An additive certificate from a popular core

Delete a set $B$ of applicants, keeping all houses and the preferences of the remaining applicants. Denote the resulting instance by $I-B$.
Theorem (Deletion sensitivity and a parameterized algorithm): For every $B\subseteq A$ with $|B|=k$, \[ |\mu_I^*-\mu_{I-B}^*|\leq k. \] If $I-B$ admits a popular matching $M_0$, any extension of $M_0$ obtained by assigning applicants of $B$ to unused acceptable houses, or leaving them unmatched, has margin at most $k$. Hence it has additive error at most $k$. For every fixed $k$, one can find such a certificate and matching, or correctly report that no deletion set of size at most $k$ leaves a popular instance, in $n^{O(k)}\operatorname{poly}(N)$ time.
Proof: Take an optimum $M_0$ in $I-B$ and extend it while preserving its assignments. In any challenger $Q$, the applicants outside $B$ contribute at most $\mu_{I-B}(M_0)$: restricting $Q$ to these applicants is a feasible challenger in $I-B$, even if it uses houses assigned to $B$ by the extended matching. The $k$ deleted applicants contribute at most $k$. This proves $\mu_I^*\leq\mu_{I-B}^*+k$ and the popular-core assertion.

Conversely restrict any $M$ in $I$ to the core. Choose a maximizing challenger $Q_0$ there and leave every applicant of $B$ unmatched in the full challenger. Its core margin is $\mu_{I-B}(M|_{A\setminus B})$ and the remaining contribution is at least $-k$. Consequently $\mu_I(M)\geq\mu_{I-B}^*-k$; minimize over $M$.

Enumerate all subsets of size at most $k$ and apply the polynomial popular-matching recognition and construction algorithm of [survey, Theorem 1]. If one succeeds, use its popular matching and the extension just proved. If all fail, there is no such deletion set. There are at most $\sum_{j=0}^k\binom nj\leq(k+1)\max\{1,n\}^k$ subsets. ∎

The existence of a deletion certificate is not implied by a small optimum margin. No approximation ratio for the minimum deletion number has been proved here. The method is useful when a small exceptional set is independently known or can be enumerated.

Remaining problem

The power-error obstruction rules out a substantial family of additive improvements under the cited complexity assumption, but leaves errors such as $N/\log N$ and all sharp multiplicative guarantees open. The deletion theorem identifies a tractable structural promise, rather than removing this gap. In particular no division by a possibly zero optimum occurs anywhere in the argument. All results above are analytic; no experimental enumeration is used to infer complexity.

References

Completion Estimate

40%

Go to contribution →