Online Elicitation of Necessarily Optimal Matchings (aaai22-20451)

Given finite applicant information types \(P\), house categories \(H\), rational masses \(\mu_p\) with \(\sum_p\mu_p=1\), capacities \(\nu_h\) with \(\sum_h\nu_h=1\), and set-compare transcripts defining feasible rankings \(\mathcal R_p\), does there exist a fixed mass allocation \(x\) with \(\sum_h x_{p,h}=\mu_p\) and \(\sum_p x_{p,h}\le\nu_h\) that is Pareto optimal for every cohort-level completion \((\rho_p)_{p\in P}\in\prod_p\mathcal R_p\)?

Definitions

A set-compare transcript for type \(p\) consists of answers \(Q(p,S)=h\in S\), each requiring \(h\) to rank above every element of \(S\setminus\{h\}\). Let \(\mathcal R_p\) be the strict total orders on \(H\) satisfying all these requirements.
A feasible allocation is \(x\in\mathbb Q_{\ge0}^{P\times H}\) with \(\sum_hx_{p,h}=\mu_p\) for every \(p\) and \(\sum_px_{p,h}\le\nu_h\) for every \(h\). For \(\rho_p\in\mathcal R_p\), \(y\) Pareto-dominates \(x\) if, for every \(p\) and \(h\), \(\sum_{g:\,g\succeq_{\rho_p}h}y_{p,g}\ge\sum_{g:\,g\succeq_{\rho_p}h}x_{p,g}\), with a strict inequality for some \(p,h\). Thus \(x\) is Pareto optimal if no feasible \(y\) Pareto-dominates it.

Target

Is deciding whether there exists a feasible \(x\) that is Pareto optimal for every \((\rho_p)_{p\in P}\in\prod_{p\in P}\mathcal R_p\) solvable in polynomial time, or is it NP-hard?

Nearest known results

For the discrete unit-capacity house-allocation problem with set-compare partial preferences, deciding whether a necessarily Pareto-optimal matching exists is NP-complete.
No result for the exact rational-mass allocation problem above was verified in the source search.

Complexity Classification

Theorem

The rational-mass decision problem is \(\mathrm{NP}\)-hard, even under the restrictions that every type has mass \(1\), every house has capacity \(1\), and the total mass equals the total capacity.

Thus fractional allocations do not make the problem polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).

Discrete source problem

Use the stated known result:

Given equally many agents and unit-capacity houses, with preferences specified by set-compare transcripts, deciding whether there exists a matching that is Pareto optimal for every compatible strict preference profile is \(\mathrm{NP}\)-complete.

For a strict preference profile \(\rho\), a matching \(N\) Pareto-dominates a matching \(M\) if every agent weakly prefers \(N(p)\) to \(M(p)\), and at least one agent strictly prefers \(N(p)\).

Reduction

Let a discrete instance have agent set \(A\), house set \(H\), and \(\lvert A\rvert=\lvert H\rvert=n\).

Construct a rational-mass instance as follows:

• Set \(P=A\).
• Set \(\mu_p=1\) for every \(p\in P\).
• Set \(u_h=1\) for every \(h\in H\).
• Copy every set-compare transcript unchanged.

This construction is polynomial-time and introduces only the rational constant \(1\).

For a matching \(M\), let \(X^M\) denote its incidence allocation, defined by \(X^M_{p,M(p)}=1\) and \(X^M_{p,h}=0\) for \(h\ne M(p)\).

Balanced allocations are doubly stochastic

Let \(x\) be feasible in the constructed instance. Its total allocated mass is

\(\sum_{p\in P}\sum_{h\in H}x_{p,h}=\sum_{p\in P}\mu_p=n\).

On the other hand, every column has load at most \(1\), and there are \(n\) columns. Hence

\(\sum_{h\in H}\sum_{p\in P}x_{p,h}\le n\).

Equality of the total sums forces every house constraint to be tight:

\(\sum_{p\in P}x_{p,h}=1\)

for every \(h\). Consequently, every feasible allocation in the reduced instance is a doubly stochastic matrix.

Lemma 1: A necessarily efficient matching gives a universally efficient fractional allocation

Let \(M\) be necessarily Pareto optimal in the discrete instance. We prove that \(X^M\) is Pareto optimal among all rational fractional allocations for every compatible strict profile.

Fix an arbitrary compatible profile \(\rho\). Suppose, for contradiction, that a feasible fractional allocation \(y\) stochastically Pareto-dominates \(X^M\).

For each \(p\), apply the dominance inequality at the cutoff \(M(p)\). Because \(X^M\) assigns all mass to \(M(p)\),

\(\sum_{g:\,g\succeq_{\rho_p}M(p)}X^M_{p,g}=1\).

Therefore,

\(\sum_{g:\,g\succeq_{\rho_p}M(p)}y_{p,g}\ge 1\).

The row sum of \(y\) is exactly \(1\), so equality holds and \(y_{p,g}=0\) whenever \(M(p)\succ_{\rho_p}g\). Thus every house in the support of row \(p\) is weakly preferred by \(p\) to \(M(p)\).

Moreover, strict stochastic dominance implies that \(y\ne X^M\). Hence there exist \(p\) and \(g\) such that \(y_{p,g}>0\) and \(g\succ_{\rho_p}M(p)\).

By the preceding section, \(y\) is doubly stochastic. The Birkhoff–von Neumann theorem therefore gives matchings \(N_1,\ldots,N_k\) and positive coefficients \(\lambda_1,\ldots,\lambda_k\) with \(\sum_i\lambda_i=1\) such that

\(y=\sum_{i=1}^k\lambda_iX^{N_i}\).

Every edge used by any \(N_i\) has positive \(y\)-value. Consequently, every agent weakly prefers \(N_i(p)\) to \(M(p)\). Since some strictly better edge has positive \(y\)-value, at least one matching \(N_i\) uses such an edge. That \(N_i\) Pareto-dominates \(M\), contradicting Pareto optimality of \(M\) under \(\rho\).

Because \(\rho\) was arbitrary, \(X^M\) is Pareto optimal for every compatible profile.

Lemma 2: A universally efficient fractional allocation contains a necessarily efficient matching

Suppose \(x\) is a feasible allocation that is Pareto optimal for every compatible strict profile.

Since \(x\) is doubly stochastic, the Birkhoff–von Neumann theorem implies that its support contains a perfect matching \(M\). Thus

\(x_{p,M(p)}>0\)

for every \(p\). Because \(x\) is rational, the number

\(\varepsilon=\min_{p\in P}x_{p,M(p)}\)

is a positive rational.

We prove that \(M\) is necessarily Pareto optimal. Suppose otherwise. Then there are a compatible profile \(\rho\) and a matching \(N\) that Pareto-dominates \(M\) under \(\rho\).

Define

\(z=x+\varepsilon(X^N-X^M)\).

This allocation is nonnegative because \(\varepsilon\le x_{p,M(p)}\) for every \(p\). Both \(X^N\) and \(X^M\) have every row sum and every column sum equal to \(1\), so \(z\) has the same row and column sums as \(x\). Hence \(z\) is feasible. It is also rational.

For any type \(p\) and cutoff \(h\), the change in its upper-contour mass is

\(\varepsilon\bigl(\mathbf 1[N(p)\succeq_{\rho_p}h]-\mathbf 1[M(p)\succeq_{\rho_p}h]\bigr)\).

Because \(N(p)\succeq_{\rho_p}M(p)\), this quantity is nonnegative for every \(h\). If \(N(p)\succ_{\rho_p}M(p)\), then at the cutoff \(h=N(p)\) it equals \(\varepsilon>0\).

At least one agent strictly prefers its assignment under \(N\). Therefore \(z\) stochastically Pareto-dominates \(x\), contradicting the assumed Pareto optimality of \(x\) under \(\rho\).

Thus \(M\) is Pareto optimal under every compatible profile.

Correctness of the reduction

The two lemmas prove the equivalence

\(\text{a necessarily Pareto-optimal matching exists}\)

if and only if

\(\text{a universally Pareto-optimal rational fractional allocation exists}\).

The reduction is polynomial-time, and the source problem is \(\mathrm{NP}\)-hard. Therefore the target rational-mass problem is \(\mathrm{NP}\)-hard.

This argument does not establish membership in \(\mathrm{NP}\); it settles the requested polynomial-time-versus-\(\mathrm{NP}\)-hard classification through the latter alternative.

⟨structured verdict parsed — rendered above⟩

Verification Report

Overall assessment

The reduction is mathematically sound conditional on the discrete NP-hardness theorem holding for balanced instances with equally many agents and houses. Both Birkhoff–von Neumann arguments are correct.

However, the supplied USER_TASK states NP-completeness only for the “discrete unit-capacity house-allocation problem”; it does not explicitly state NP-hardness under the additional restriction \( |A|=|H| \). The prover silently strengthens the source theorem to precisely the balanced form needed by the reduction. Without verification of that restriction, the claimed NP-hardness conclusion is not established from the supplied premise.

Step-by-step audit

1. Construction

The assignments \(P=A\), \(\mu_p=1\), and \(u_h=1\), together with copying the transcripts, form a polynomial-time construction. All introduced numerical data have constant encoding length.

The construction depends critically on \( |A|=|H| \). This equality is what makes the total allocated mass equal the total capacity and hence makes every feasible matrix doubly stochastic.

2. Tightness of the capacity constraints

Assuming \( |P|=|H|=n \), every feasible allocation has total mass

\[ \sum_{p,h}x_{p,h}=n. \]

The total available capacity is also \(n\). Since each column load is at most \(1\), equality of the aggregate load and aggregate capacity forces every column load to equal \(1\). This step is correct.

Thus every feasible allocation in the constructed balanced instance is doubly stochastic.

3. Lemma 1

Fixing a compatible profile \(\rho\), dominance of \(X^M\) at the cutoff \(M(p)\) gives

\[ \sum_{g:\,g\succeq_{\rho_p}M(p)}y_{p,g}\ge 1. \]

Because the row sum of \(y\) is \(1\), all mass in row \(p\) must lie on houses weakly preferred to \(M(p)\). This is correct.

Since the orders are strict, if \(y\ne X^M\), some row assigns positive mass to a house strictly preferred to \(M(p)\). Strict stochastic dominance indeed implies \(y\ne X^M\).

Applying the Birkhoff–von Neumann theorem is justified because \(y\) is doubly stochastic. In a decomposition with positive coefficients, an edge appearing in a component matching necessarily has positive \(y\)-value. Therefore every component matching weakly improves every agent over \(M\), and at least one component uses a strictly improving edge. That component matching Pareto-dominates \(M\).

Consequently Lemma 1 is correct.

4. Lemma 2

A doubly stochastic matrix has a Birkhoff–von Neumann decomposition, so its positive support contains a perfect matching \(M\). This is correct.

For nonempty \(P\),

\[ \varepsilon=\min_{p\in P}x_{p,M(p)} \]

is positive and rational. The perturbation

\[ z=x+\varepsilon(X^N-X^M) \]

is nonnegative and preserves every row and column sum. Hence it remains feasible.

If \(N(p)\succeq_{\rho_p}M(p)\), then for every cutoff \(h\),

\[ \mathbf 1[N(p)\succeq_{\rho_p}h] - \mathbf 1[M(p)\succeq_{\rho_p}h]\ge 0. \]

If \(N(p)\succ_{\rho_p}M(p)\), the difference at \(h=N(p)\) is \(1\). Thus \(z\) stochastically Pareto-dominates \(x\). Lemma 2 is correct.

There is a minor unhandled empty-instance case: when \(n=0\), the displayed minimum defining \(\varepsilon\) is undefined. The equivalence is trivial in that case, but the proof does not state a positive-size assumption or treat the case separately.

5. Source-theorem application

The prover states:

Given equally many agents and unit-capacity houses [...]

But the supplied known result does not explicitly include “equally many.” The proof supplies neither a citation confirming that balanced restriction nor a reduction from the stated general discrete problem to the balanced version.

This is a major verification gap because the double-stochastic argument—and therefore both directions of the equivalence—depends on total capacity equaling total mass. The minimum clarification needed is an exact statement of the known discrete theorem confirming NP-hardness for \( |A|=|H| \), with its source or other verification. If that is confirmed, the reduction establishes the claimed hardness, subject only to the empty-instance detail.

Genuine progress

The prover establishes a correct equivalence between necessarily Pareto-optimal perfect matchings and universally Pareto-optimal rational allocations for balanced unit-mass, unit-capacity instances. The remaining blocker concerns whether the required balanced discrete source problem is actually covered by the known NP-completeness result.

⟨structured verdict parsed — rendered above⟩