Answer: Yes. The deterministic simultaneous-eating algorithm computes a rational coupling in time polynomial in \(m,\tau,L\) and guarantees welfare at least \(1/(\sqrt2+1)\) times the optimum for every compatible hidden utility matrix.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose G = (X, Y, E) is a complete bipartite graph on the set of nodes X, Y with |X| = |Y| = N. Then, the expected weight of the perfect matching M returned by Algorithm 1 is E[w(M)] ≥ 1 √ 2+1w(OPT(G)).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type sets \(\mathcal X\) and \(\mathcal Y\), rational mass distributions \(\mu^X\) and \(\mu^Y\), and an ordinal ranking of \(\mathcal Y\)-types for every \(\mathcal X\)-type, compute an ordinal-only randomized mass coupling \(\pi\) with marginals \(\mu^X\) and \(\mu^Y\) such that, for every hidden utility matrix \(w\) consistent with the rankings and satisfying \(w_{ij}\le w_{ij'}+w_{i'j}+w_{i'j'}\), \(\mathbb E[\sum_{i,j}w_{ij}\pi_{ij}]\ge \frac{1}{\sqrt{2}+1}\max_{\pi'}\sum_{i,j}w_{ij}\pi'_{ij}\).
Let \(\mathcal X,\mathcal Y\) be nonempty finite type sets, with \(m=|\mathcal Y|\) and \(\tau=|\mathcal X|+|\mathcal Y|\). A society is given by its support: the list of types with positive mass, each mass a binary rational; \(\tau\) is the total support size, not the number of possible types. Both sides have total mass \(1\); let \(L\) be the total input bit length.
For each \(i\in\mathcal X\), the input gives a strict total ranking \(\succ_i\) of \(\mathcal Y\). Hidden utilities are arbitrary \(w\in\mathbb R_{\ge0}^{\mathcal X\times\mathcal Y}\) satisfying \(j\succ_i j'\Rightarrow w_{ij}\ge w_{ij'}\) and \(w_{ij}\le w_{ij'}+w_{i'j}+w_{i'j'}\) for all indices. Utility ties are resolved by the supplied rankings; no utility normalization or further metric condition is imposed.
Define \(\Pi(\mu^X,\mu^Y)=\{\pi\ge0:\sum_j\pi_{ij}=\mu_i^X,\ \sum_i\pi_{ij}=\mu_j^Y\}\). Mass is divisible, and every type pair is allowed. An ordinal-only randomized algorithm receives only masses and rankings and outputs a rational coupling \(\pi\in\Pi(\mu^X,\mu^Y)\); expectation is over its internal randomness.
Can such an algorithm run in time polynomial in \(m,\tau,L\) and guarantee \(\mathbb E[\sum_{i,j}w_{ij}\pi_{ij}]\ge\frac{1}{\sqrt2+1}\max_{\pi'\in\Pi(\mu^X,\mu^Y)}\sum_{i,j}w_{ij}\pi'_{ij}\) for every input and every compatible hidden utility matrix?
For equal-sized finite agent sets, random serial dictatorship gives a polynomial-time ordinal-only \((\sqrt2+1)\)-approximation in expectation under these utility conditions. [Anshelevich–Zhu](https://people.cs.rutgers.edu/~lirong.xia/COMSOC18/papers/paper%2053.pdf)
No result settling this exact problem with binary-rational type masses was identified in the literature search.
Yes. A deterministic ordinal-only algorithm suffices: let every type on the \(\mathcal X\)-side simultaneously consume its favorite available \(\mathcal Y\)-type, at a rate equal to its mass.
We prove that this algorithm:
Replication is used only in the proof, never in the algorithm.
Write \(a_i=\mu_i^X\) and \(b_j=\mu_j^Y\). Initialize the allocation matrix \(P\) to zero and the residual column supplies \(r_j=b_j\).
While some column has positive residual supply:
Remove exhausted columns and repeat. All choices depend only on the masses and rankings.
To verify termination and feasibility, interpret \(\Delta\) as a time increment. Since all row types consume throughout the process, the total consumption rate is \(\sum_i a_i=1\). At elapsed time \(t\), therefore,
\(\displaystyle \sum_j r_j=1-t.\)
For \(t<1\), some column remains available, so every \(f_i\) is defined and \(\sum_j q_j=1\). Moreover,
\(\displaystyle \Delta\le \sum_{j:q_j>0}q_j\frac{r_j}{q_j}=\sum_{j:q_j>0}r_j\le 1-t.\)
Each phase exhausts at least one column. Consequently there are at most \(m\) phases. When they finish, all supplies have been consumed, so the elapsed time is exactly \(1\). Each row type has consumed mass \(a_i\), and each column has supplied mass \(b_j\). Thus \(P\in\Pi(\mu^X,\mu^Y)\).
Denote this coupling by \(P^{\mathrm{eat}}\).
Choose a common denominator \(D\) for all input masses, for example the product of their denominators. Then
\(\displaystyle a_i=A_i/D,\qquad b_j=B_j/D,\)
where the \(A_i,B_j\) are positive integers and \(\sum_i A_i=\sum_j B_j=D\). The binary length of \(D\) is \(O(L)\).
Suppose the residual supplies and allocation entries currently have a common denominator \(H\). Initially we may take \(H=D\). In a phase, write \(q_j=Q_j/D\), where
\(\displaystyle Q_j=\sum_{i:f_i=j}A_i\le D.\)
If column \(j_*\) attains the minimum defining the phase duration and \(r_{j_*}=C/H\), then
\(\displaystyle \Delta=\frac{DC}{H Q_{j_*}},\qquad a_i\Delta=\frac{A_iC}{H Q_{j_*}},\qquad q_j\Delta=\frac{Q_jC}{H Q_{j_*}}.\)
Thus every updated residual and allocation entry has common denominator \(H Q_{j_*}\). After at most \(m\) phases, a common denominator is at most \(D^{m+1}\).
Residual supplies and allocation entries lie between zero and one. Their numerators and denominators, and the temporary numbers needed for arithmetic and comparisons, therefore have \(O((m+1)(L+1))\) bits.
A direct implementation uses \(O(|\mathcal X|m^2)\) rational arithmetic operations: in each of at most \(m\) phases, it scans each ranking to find the first available column and then performs the updates. Hence the algorithm, including its output, has bit complexity polynomial in \(m,\tau,L\).
We prove the convergence needed to transfer the finite-agent guarantee.
For each positive multiple \(N\) of \(D\), create:
Each agent ranks object types according to its supplied ranking. Within an object type, use any fixed strict ordering of the copies.
Run random serial dictatorship, equivalently using a uniformly random permutation of the \(N\) agents.
After the first \(k\) agents have been processed, let \(P_{ij}^{N}(k/N)\) be the number of assignments from type \(i\) to type \(j\), divided by \(N\). Interpolate linearly between consecutive processing times.
Every coordinate of \(P^N\) is nondecreasing, takes values in \([0,1]\), and is \(1\)-Lipschitz. Define the cumulative processed row mass by
\(\displaystyle A_i^N(t)=\sum_jP_{ij}^N(t).\)
For an integer \(k\), the number of type-\(i\) agents among the first \(k\) positions of a uniform random permutation has mean \(ka_i\) and variance at most \(N\). Consequently,
\(\displaystyle \Pr\!\left(\left|A_i^N(k/N)-a_i k/N\right|>\varepsilon\right)\le \frac{1}{N\varepsilon^2}.\)
For a fixed finite time grid, Chebyshev’s inequality and a union bound show that all row deviations on the grid tend to zero in probability. Moving a grid point to a neighboring processing time changes the relevant quantities by at most \(2/N\).
Between grid points, monotonicity of \(A_i^N\), together with the fact that \(a_it\) has slope at most one, bounds the deviation by the grid deviations plus the grid spacing. First choosing a sufficiently fine fixed grid, then letting \(N\) grow, gives
\(\displaystyle \max_i\sup_{0\le t\le1}|A_i^N(t)-a_it|\longrightarrow0\quad\text{in probability}.\)
Consider any deterministic sequence of replicated RSD outcomes for which the preceding row deviation tends to zero.
Because the allocation paths are uniformly bounded and \(1\)-Lipschitz, the Arzelà–Ascoli theorem gives a uniformly convergent subsequence. Write its limit as \(P(t)\). It satisfies
\(\displaystyle \sum_jP_{ij}(t)=a_it,\qquad r_j(t):=b_j-\sum_iP_{ij}(t)\ge0,\qquad \sum_jr_j(t)=1-t.\)
We now identify the limit.
Suppose \(h\succ_i j\) and \(r_h(t)>0\). Continuity gives a neighborhood of \(t\) on which \(r_h\) is bounded away from zero. Uniform convergence implies that, for sufficiently large \(N\), column type \(h\) remains available throughout every processing step contained in that neighborhood.
An agent of type \(i\) cannot choose column type \(j\) during such a step. Hence \(P_{ij}^N\) is constant on every smaller closed interval within the neighborhood, once \(N\) is sufficiently large. Passing to the limit shows that \(P_{ij}\) is locally constant at \(t\).
Also, once \(r_j(t)=0\), no coordinate \(P_{ij}\) can increase thereafter: their sum has reached the column capacity, and all coordinates are nondecreasing.
For \(t<1\), some column is available because the total residual supply is \(1-t>0\). Let \(f_i(t)\) be row type \(i\)’s favorite available column. The preceding observations imply that, almost everywhere,
\(\displaystyle \frac{d}{dt}P_{ij}(t)= \begin{cases} a_i,&j=f_i(t),\\ 0,&j\ne f_i(t). \end{cases}\)
Indeed, every other coordinate has zero derivative, and the row-sum identity forces the derivative of the favorite coordinate to be \(a_i\).
These differential equations have a unique feasible solution. To see this explicitly, between column-exhaustion times the available set is fixed, so every \(f_i(t)\) is fixed and the consumption rates are exactly the \(q_j\) from Section 1. The next exhaustion occurs after
\(\displaystyle \min_{j:q_j>0}r_j/q_j.\)
This determines the next phase uniquely. Removing all simultaneously exhausted columns and repeating determines the entire path in at most \(m\) phases. Thus the limiting path is precisely the simultaneous-eating path.
Every convergent subsequence has this same limit. Compactness therefore implies that the original deterministic sequence converges to it.
The deterministic conclusion implies
\(\displaystyle P^N(1)\longrightarrow P^{\mathrm{eat}}\quad\text{in probability}.\)
For completeness, if this implication failed, there would be a positive separation from \(P^{\mathrm{eat}}\) along outcomes whose row deviations tend to zero. Such outcomes could be selected along a subsequence because the row deviations converge to zero in probability. Section 3.2 would then force their allocation paths to converge to the eating path, a contradiction.
For any fixed nonnegative utility matrix \(w\), normalized welfare lies in the bounded interval \([0,\max_{i,j}w_{ij}]\). Hence convergence in probability also gives convergence of expected welfare:
\(\displaystyle \lim_{\substack{N\to\infty\\D\mid N}} \mathbb E\!\left[\sum_{i,j}w_{ij}P_{ij}^N(1)\right] =\sum_{i,j}w_{ij}P_{ij}^{\mathrm{eat}}.\)
Fix a compatible hidden utility matrix \(w\), and let
\(\displaystyle \mathrm{OPT}=\max_{\pi\in\Pi(\mu^X,\mu^Y)}\sum_{i,j}w_{ij}\pi_{ij}.\)
Any perfect matching of the replicated population, divided by \(N\), gives a feasible coupling. Its welfare is therefore at most \(N\mathrm{OPT}\).
Conversely, scaling the transportation problem by \(N\) gives integer row and column margins. It has an integral optimal solution. Here is a direct justification that remains valid for arbitrary real utilities.
Take an optimal scaled transportation matrix. If it has nonintegral entries, form the bipartite graph consisting of those entries. Every incident vertex has degree at least two: exactly one nonintegral entry would contradict its integer margin. Thus this graph contains an even cycle.
Perturb its entries alternately upward and downward around the cycle. Both signs of a sufficiently small perturbation preserve feasibility. Optimality forces the objective’s directional change to be zero; otherwise one sign would improve the objective.
Continue one sign until the first cycle entry reaches an integer. All other cycle entries remain within their previous open intervals between consecutive integers. The objective stays optimal, and the number of nonintegral entries strictly decreases. Repeating produces an integral optimum.
Its integer cell counts can be realized by pairing the corresponding numbers of agent and object copies. Therefore the maximum welfare of a replicated perfect matching is exactly \(N\mathrm{OPT}\).
We use the finite-agent theorem stated in the question: random serial dictatorship guarantees expected welfare at least \(1/(\sqrt2+1)\) times the optimal perfect-matching welfare. Its hypotheses are precisely nonnegative utilities, compatible strict rankings, and the four-point inequality used here. See [Anshelevich–Zhu, Theorem 3.1 and Section 2](https://people.cs.rutgers.edu/~lirong.xia/COMSOC18/papers/paper%2053.pdf).
Assign utility \(w_{ij}\) to every pair of copies having types \(i,j\). The replicated instance satisfies every hypothesis:
Applying the finite theorem and Section 4 yields, for every positive multiple \(N\) of \(D\),
\(\displaystyle \mathbb E\!\left[\sum_{i,j}w_{ij}P_{ij}^N(1)\right] \ge \frac{\mathrm{OPT}}{\sqrt2+1}. \)
Taking the limit established in Section 3 gives
\(\displaystyle \sum_{i,j}w_{ij}P_{ij}^{\mathrm{eat}} \ge \frac{1}{\sqrt2+1} \max_{\pi'\in\Pi(\mu^X,\mu^Y)} \sum_{i,j}w_{ij}\pi'_{ij}. \)
The same ordinal-only coupling satisfies this inequality for every compatible hidden utility matrix. Its exact computation is polynomial in \(m,\tau,L\), and its deterministic welfare equals its expected welfare.
⟨structured verdict parsed — rendered above⟩
The prover resolves the intended problem in substance. The proposed deterministic algorithm produces an exactly rational feasible coupling in polynomial bit complexity, and the replication argument correctly transfers the finite-agent approximation guarantee.
There is one minor issue: the integrality argument incorrectly asserts that every cycle entry other than the first remains nonintegral. Several entries may become integral simultaneously. This does not affect feasibility, optimality, or termination of that argument.
The algorithm is well-defined on the supplied support: all masses are positive, both supports are nonempty, and each row has a strict total ranking.
Whenever residual supply remains, every row has a favorite available column. Consequently, the total consumption rate is
\[
\sum_j q_j=\sum_i a_i=1.
\]
The stated identity for total residual supply follows from the updates.
The bound on the phase duration is correct: the minimum of the ratios is at most their weighted average with weights \(q_j\), whose sum is one. Thus no phase extends past time one.
Every phase has positive duration, preserves nonnegative residual supplies, and exhausts at least one available column. Exhausted columns cannot receive further consumption. There are therefore at most \(m\) phases.
At termination, total consumption is one, each row has consumed at its constant rate throughout, and every column has exhausted its prescribed supply. This establishes all coupling constraints.
Finding: Correct. No missing domain restriction or termination case.
The common-denominator construction is valid for binary-encoded rational masses. Taking the product of input denominators gives a denominator \(D\) of binary length \(O(L)\).
The displayed formulas for the phase duration and allocation increments are correct. Updating a common denominator from \(H\) to \(HQ_{j_*}\) accommodates both old entries and new increments. Since \(Q_{j_*}\le D\), at most \(m\) updates produce a denominator bounded by \(D^{m+1}\).
Residual supplies and allocation entries remain in \([0,1]\), so their numerators have the same polynomial bit bound as their denominators. Arithmetic and comparison intermediates also have polynomial bit length.
The operation count accounts for repeated ranking scans and updates. The output matrix has only \(|\mathcal X|m\) entries, each of polynomial encoding length.
Finding: Correct. The algorithm does not require time polynomial in the numerical value of \(D\); replication is confined to the proof.
For each multiple \(N\) of \(D\), the agent and object multiplicities are integers and both populations have size \(N\).
For a fixed row type and processing position, the prefix count is hypergeometric. Its stated mean is correct, and the variance bound by \(N\) is valid. Dividing by \(N\) and applying Chebyshev gives the displayed probability bound.
The fixed-grid argument is sufficient:
Choosing the grid sufficiently fine before increasing \(N\) establishes uniform convergence of all row arrivals in probability.
Finding: Correct. No independence between different prefix counts is required.
Each coordinate path is bounded and \(1\)-Lipschitz. The domain is the compact interval \([0,1]\), and the number of coordinates is finite. Thus the stated Arzelà–Ascoli application is justified.
Uniform convergence preserves nonnegativity, monotonicity, column-capacity constraints, and the stated row-sum identities.
The preference argument is valid. If a preferred column has positive limiting residual supply at a time, continuity provides a neighborhood with residual supply bounded away from zero. Uniform convergence then ensures that column remains available in the corresponding replicated processing steps. Less-preferred assignments cannot occur there. Restricting to a smaller closed interval handles processing steps crossing neighborhood boundaries.
Once a limiting column is exhausted, its total allocation cannot increase, and coordinatewise monotonicity prevents any individual allocation into it from increasing.
The derivative conclusion holds almost everywhere. Lipschitz coordinates are differentiable almost everywhere; column-exhaustion times contribute at most finitely many additional exceptional times. For every other coordinate, the preceding observations force zero derivative, and the row-sum identity forces the favorite coordinate’s derivative to be \(a_i\).
The uniqueness argument correctly follows the successive exhaustion phases. Available columns can only disappear. Between exhaustion times, preferences and consumption rates are fixed, and the next exhaustion time is determined by the displayed minimum. Simultaneous exhaustion is explicitly handled.
Finding: Correct. The limiting path is uniquely identified with the algorithm in Section 1.
The deterministic subsequence argument is sound. Compactness and uniqueness imply that every deterministic sequence whose row deviations vanish converges to the eating path.
The contradiction argument in Section 3.3 correctly transfers this statement to convergence in probability: failure would allow a subsequence of outcomes with allocation separation bounded below while row deviations approach zero.
For each fixed compatible matrix \(w\), welfare is a continuous linear function of the allocation. Since total allocated mass is one, welfare lies in the stated bounded interval. Convergence in probability therefore yields convergence of expectations.
The quantifier order is appropriate: the argument fixes an arbitrary compatible \(w\), while the computed eating allocation depends only on masses and rankings. Uniform convergence over utility matrices is unnecessary.
Finding: Correct.
The first inequality is immediate from aggregating a perfect matching and dividing its cell counts by \(N\).
The scaled transportation problem has integer margins and an attained optimum. The cycle argument correctly handles arbitrary real utilities:
However, the following assertion is inaccurate:
“All other cycle entries remain within their previous open intervals between consecutive integers.”
Severity: minor. Multiple entries can reach integer boundaries at the same perturbation value.
A concrete example is an optimal \(2\times2\) matrix with every entry equal to \(1/2\), integer row and column margins equal to one, and zero utilities. An alternating cycle perturbation of magnitude \(1/2\) makes all four entries integral simultaneously.
This does not undermine the argument: the number of nonintegral entries still strictly decreases.
Minimum clarification needed: Allow simultaneous attainment of integer boundaries in the description of the stopping perturbation. No additional lemma is required.
Realizing the resulting integer cell counts by matching copies is valid.
The citation is accurate. Section 2 of the linked paper specifies nonnegative edge weights, strict preferences consistent with weak utility comparisons, and exactly the four-point inequality in the task. Theorem 3.1 gives the stated expected approximation guarantee for equal-sized finite populations. No additional metric or utility normalization hypothesis is imposed there. [Anshelevich–Zhu, Section 2 and Theorem 3.1](https://people.cs.rutgers.edu/~lirong.xia/COMSOC18/papers/paper%2053.pdf)
The replication satisfies these hypotheses:
The equality of optima supplies the correct normalization by \(N\). Taking the established expected-welfare limit preserves the approximation inequality.
A deterministic algorithm is an admissible special case of the requested randomized algorithm.
Finding: Correct. The target guarantee and polynomial-time requirement are established, subject only to the minor wording correction above.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.