d4-conf-aaai-2016-0565 (d4-conf-aaai-2016-0565)

Given finite types \(T\), positive rational masses \(\mu_t\) summing to \(1\), and strict rankings \(P_t\) of partner types, including same-type partners, promised consistent with a hidden symmetric metric \(d\) on \(T\), is there a randomized algorithm running in time polynomial in \(\tau=|T|\) and input bit length \(L\) that outputs a feasible mass matching \(Y=(y_{tu})\) with \(\mathbb{E}[W_d(Y)]\ge \frac{5}{8}\operatorname{OPT}_\mu(d)\) for every consistent \(d\)? Here \(y_{tu}\ge0\), \(y_{tu}=y_{ut}\), each type satisfies \(\sum_{u\ne t}y_{tu}+2y_{tt}=\mu_t\), welfare is \(W_d(Y)=\sum_{t<u}y_{tu}d(t,u)\), and \(\operatorname{OPT}_\mu(d)\) is the maximum welfare over feasible mass matchings.

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; the number of partner types is \(m=\tau\), and \(L\) is the total input bit length.
Each type has a strict ranking \(P_t\) of all partner types, including itself. The input is promised consistent with a hidden real-valued symmetric metric \(d\) on \(T\): if \(u\) precedes \(v\) in \(P_t\), then \(d(t,u)\ge d(t,v)\). Equal distances may be ordered arbitrarily; \(d(t,t)=0\), and distinct types have positive distance. Larger distances are preferred.
A feasible mass matching is a symmetric nonnegative matrix \(Y=(y_{tu})\) satisfying \(\sum_{u\ne t}y_{tu}+2y_{tt}=\mu_t\) for every \(t\). The diagonal represents pairs of distinct individuals of the same type and contributes zero welfare.
For any fixed ordering of \(T\), define \(W_d(Y)=\sum_{t<u}y_{tu}d(t,u)\) and \(\operatorname{OPT}_\mu(d)=\max_{Y\text{ feasible}}W_d(Y)\).

Does there exist a randomized algorithm, using only the support, masses, and rankings, running in time polynomial in \(m,\tau,L\), that outputs a binary rational feasible mass matching \(Y\) with \(\mathbb{E}[W_d(Y)]\ge\frac58\operatorname{OPT}_\mu(d)\) for every consistent metric \(d\)?

For finite individual agents, a polynomial-time randomized ordinal algorithm guarantees expected maximum-weight matching welfare at least \(\frac58\) of optimum under hidden metric weights ([Anshelevich–Sekar](https://arxiv.org/pdf/1512.05504)).
No prior guarantee for this exact support-encoded mass model was located in the literature search.

Result

Yes. A deterministic polynomial-time algorithm achieves the required guarantee. It outputs a feasible rational mass matching \(Y\) satisfying
\[ W_d(Y)\ge \frac58\operatorname{OPT}_\mu(d) \]
for every consistent metric \(d\).

The construction adapts the greedy-and-completion idea in [Anshelevich–Sekar, Algorithm 3](https://arxiv.org/pdf/1512.05504). Divisible mass allows the completion to be expressed directly as a rational matrix. The proof below establishes the guarantee and the support-level running time.

1. Constructing a partial greedy mass matching

Initialize a symmetric matrix \(G=0\), residual masses \(r_t=\mu_t\), and total selected pair mass \(s=0\). Continue until \(s=\frac13\).

Call a pair of distinct active types \(u,v\) undominated if its distance is at least every available distance incident to either endpoint. Here a type is active when its residual mass is positive.

An undominated pair can be found using only rankings. When at least two types are active, let \(f(t)\) be the highest-ranked active type different from \(t\). The directed graph \(t\mapsto f(t)\) contains a cycle. Write its vertices as \(t_0,\ldots,t_{\ell-1}\), with indices taken cyclically. Ranking consistency and symmetry give
\[ d(t_i,t_{i+1})\ge d(t_i,t_{i-1}) =d(t_{i-1},t_i). \]
These inequalities around the cycle force all its edge distances to be equal. Since every outgoing cycle edge is a highest-distance available edge at its initial vertex, every cycle edge is undominated.

Choose one such pair \(u,v\), set
\[ \delta=\min\left\{r_u,r_v,\frac13-s\right\}, \]
increase both \(G_{uv}\) and \(G_{vu}\) by \(\delta\), decrease \(r_u,r_v\) by \(\delta\), and increase \(s\) by \(\delta\).

If only one active type \(t\) remains, increase \(G_{tt}\) by \(\frac13-s\), decrease \(r_t\) by twice this amount, and terminate. This is feasible: throughout the construction,
\[ \sum_t r_t=1-2s, \]
so in this case \(r_t/2=\frac12-s>\frac13-s\).

Every nonfinal update eliminates an active type. Consequently, there are at most \(\tau\) updates.

Let \(b_t\) be the final residual mass. Then
\[ \sum_t b_t=\frac13, \qquad \sum_{u\ne t}G_{tu}+2G_{tt}=\mu_t-b_t. \]

The crucial property is
\[ W_d(G)\ge\frac12\operatorname{OPT}_\mu(d). \]
We prove it next.

2. A finite charging lemma

Lemma. Let \(N\) be divisible by \(6\). Suppose nonnegative symmetric edge weights satisfy the triangle inequality. Select \(k=N/3\) disjoint edges sequentially, each undominated among the vertices still available when it is selected. Let \(M\) be the resulting matching. Then every perfect matching \(M^\star\) satisfies
\[ w(M^\star)\le 2w(M). \]

Zero distances between distinct vertices are allowed in this lemma.

Proof. Partition the edges of \(M^\star\) into two classes:

• \(I\): edges having at least one endpoint covered by \(M\);
• \(J\): edges having neither endpoint covered by \(M\).

Set \(p=|I|\) and \(q=|J|\). Since \(M^\star\) is perfect,
\[ p+q=\frac N2. \]
Only \(N-2k=N/3\) vertices are uncovered by \(M\), so
\[ q\le\frac N6. \]

For each edge \(e^\star\in I\), charge it to the first selected edge of \(M\) that covers one of its endpoints. Both endpoints of \(e^\star\) were available immediately before that selection. Undominatedness therefore implies that the receiving edge has weight at least \(w(e^\star)\).

Let \(c_e\) be the number of edges charged to \(e\in M\). Each endpoint of \(e\) belongs to exactly one edge of \(M^\star\), hence
\[ 0\le c_e\le2, \qquad \sum_{e\in M}c_e=p. \]
Writing \(C=\sum_{e\in M}c_e w(e)\), we obtain \(w(I)\le C\).

Let \(\lambda=\min_{e\in M}w(e)\). For any edge \((a,b)\in J\), both endpoints remain available throughout the greedy construction. If \((x,y)\in M\), undominatedness at \(x\) and the triangle inequality give
\[ w(a,b)\le w(a,x)+w(x,b)\le2w(x,y). \]
This holds for every selected edge, so \(w(J)\le2q\lambda\).

Finally,
\[ 2w(M)-C =\sum_{e\in M}(2-c_e)w(e) \ge(2k-p)\lambda. \]
Using the preceding counting identities,
\[ 2k-p=\frac{2N}{3}-\left(\frac N2-q\right) =\frac N6+q\ge2q. \]
Therefore \(2w(M)-C\ge w(J)\), and
\[ w(M^\star)=w(I)+w(J)\le C+w(J)\le2w(M). \]
This proves the lemma.

3. Applying the lemma to rational masses

Fix any consistent metric \(d\).

The feasible mass-matching set is a nonempty compact rational polytope: the diagonal matching \(y_{tt}=\mu_t/2\) proves nonemptiness, and the mass constraints bound every coordinate. A linear objective attains its maximum at a vertex. Every vertex is rational, because it is determined by a nonsingular system of rational linear equations. Thus there is a rational optimal matching \(Z\), even when \(d\) has irrational entries.

Choose an integer \(N\), divisible by \(6\), clearing the denominators of all entries of \(\mu,G,Z\). This integer is used only in the proof.

Replace each type \(t\) by \(N\mu_t\) distinct labeled copies. Give two copies the distance of their types, including distance zero between copies of the same type. These weights are nonnegative, symmetric, and satisfy the triangle inequality.

Realize each greedy update of size \(\delta\) by \(N\delta\) individual edges, in the order of the updates. Cross-type updates use that many copies of each endpoint type; diagonal updates use twice that many copies of their type. Residual-mass feasibility ensures that these copies exist.

Each resulting edge is undominated when selected. For a cross-type update, its type pair was undominated at the start of the update, and removing copies can only reduce the available alternatives. For a diagonal update, all remaining copies have the same type and all available weights are zero.

The resulting individual matching \(M\) has exactly \(N/3\) edges and weight
\[ w(M)=N W_d(G). \]

Likewise, \(Z\) can be realized as an individual perfect matching \(M^\star\): allocate \(Nz_{tu}\) copies of each endpoint to each cross-type pair, and allocate \(2Nz_{tt}\) copies to the diagonal pairs of type \(t\). The feasibility equations allocate exactly \(N\mu_t\) copies of every type. Its weight is
\[ w(M^\star)=N\operatorname{OPT}_\mu(d). \]

The finite lemma now yields
\[ W_d(G)\ge\frac12\operatorname{OPT}_\mu(d). \]

No expanded population is constructed by the algorithm.

4. The output matching

Using the computed residual vector \(b\), define the symmetric output matrix by
\[ Y_{tu}=\frac34G_{tu} +\frac34\left(b_t\mu_u+\mu_t b_u\right) \quad\text{for }t\ne u, \]
and
\[ Y_{tt}=\frac34G_{tt}+\frac34b_t\mu_t. \]

Every entry is nonnegative. To verify feasibility, use \(\sum_u\mu_u=1\) and \(\sum_u b_u=\frac13\):
\[ \begin{aligned} \sum_{u\ne t}Y_{tu}+2Y_{tt} &=\frac34(\mu_t-b_t) +\frac34\left(b_t\sum_u\mu_u+\mu_t\sum_u b_u\right)\\ &=\frac34(\mu_t-b_t)+\frac34b_t+\frac14\mu_t\\ &=\mu_t. \end{aligned} \]
Thus \(Y\) is a feasible mass matching.

5. Welfare guarantee

Define
\[ H_d=\sum_{t,u\in T}b_t\mu_u d(t,u). \]
Symmetry and zero diagonal distances give
\[ W_d(Y)=\frac34W_d(G)+\frac34H_d. \]

We show that \(H_d\ge\frac13\operatorname{OPT}_\mu(d)\). For any feasible matching \(Z\) and any type \(t\), apply the triangle inequality to every pair, including diagonal pairs:
\[ \begin{aligned} W_d(Z) &=\sum_{u\le v}z_{uv}d(u,v)\\ &\le\sum_{u\le v}z_{uv}\left(d(u,t)+d(t,v)\right)\\ &=\sum_u\mu_u d(t,u). \end{aligned} \]
The final equality uses the feasibility equations, with each diagonal entry contributing twice.

Apply this inequality to an optimal \(Z\), multiply by \(b_t\), and sum over \(t\). Since \(\sum_t b_t=\frac13\),
\[ H_d\ge\frac13\operatorname{OPT}_\mu(d). \]

Combining the two proved bounds,
\[ W_d(Y) \ge\frac34\cdot\frac12\operatorname{OPT}_\mu(d) +\frac34\cdot\frac13\operatorname{OPT}_\mu(d) =\frac58\operatorname{OPT}_\mu(d). \]

The algorithm uses only rankings and masses. The argument applies separately to every consistent metric, so the same output enjoys the guarantee for all of them.

6. Encoding and running time

Represent rationals by binary numerator–denominator pairs. Write the input masses as \(\mu_t=p_t/q_t\), and let \(Q=\prod_t q_t\). The bit length of \(Q\) is \(O(L)\).

All greedy quantities can be represented with denominator \(3Q\). Cross-type updates preserve this denominator. A diagonal update is final and has size exactly \(\frac13-s\), which also has denominator dividing \(3Q\). The output entries can consequently be represented with the common denominator \(36Q^2\), whose bit length is \(O(L)\).

There are at most \(\tau\) greedy updates. Finding the highest-ranked active partners and a directed cycle takes polynomial time per update; a direct implementation uses \(O(\tau^3)\) ranking inspections overall. Computing the output requires \(O(\tau^2)\) rational operations, all on integers of polynomial bit length.

Hence the algorithm runs in time polynomial in \(m,\tau,L\). As a randomized algorithm it may simply ignore its random bits, giving the requested expected-welfare guarantee.

⟨structured verdict parsed — rendered above⟩

The output resolves the task. The construction, welfare bound, and polynomial running time are correct as written. No mathematical gaps or false steps were found. Here “binary rational” is understood as a rational represented by binary numerator and denominator, as specified in the prover’s encoding section.

• Finding an undominated pair.

With at least two active types, every active type has a highest-ranked distinct active partner, so the resulting finite directed graph has a cycle. Ranking consistency and symmetry give the stated cyclic inequalities. These force all cycle-edge distances to agree.

Each cycle edge is maximal among available distances at its initial endpoint. Equality with the next cycle edge also makes it maximal at its other endpoint. Thus the selected pair is undominated for every consistent metric. A cycle of length two causes no exception. Same-type distances are zero and cannot exceed a selected cross-type distance.

• Greedy feasibility and termination.

Each cross-type update preserves nonnegativity and the residual-mass identity
\[ \sum_t r_t=1-2s. \]
A nonfinal update exhausts at least one active type. If one active type remains while \(s<1/3\), the required diagonal update consumes
\[ 2(1/3-s)<1-2s=r_t, \]
so it is feasible.

The procedure reaches selected pair mass \(1/3\), uses at most \(\tau\) updates, and leaves total residual mass \(1/3\). This also covers \(\tau=1\).

• Finite charging lemma.

The partition into \(I\) and \(J\) is exhaustive, and the uncovered-vertex count gives \(q\le N/6\).

Charging an edge of \(I\) to the first selected edge covering an endpoint is valid: both endpoints of the charged edge are still available at that selection. Undominatedness therefore bounds its weight by the receiving edge’s weight. Each selected edge receives at most two charges.

For an edge \((a,b)\in J\), both endpoints remain available during every selection. Consequently, for every selected \((x,y)\),
\[ w(a,b)\le w(a,x)+w(x,b)\le 2w(x,y). \]
The minimum selected weight \(\lambda\) therefore gives \(w(J)\le2q\lambda\).

The final counting calculation is correct:
\[ 2k-p=N/6+q\ge2q. \]
It supplies sufficient unused charging capacity to bound \(J\), proving the lemma. The argument remains valid when \(\lambda=0\).

• Passage from rational masses to individual copies.

The feasible set is a nonempty bounded rational polytope. A real linear objective attains its maximum at a vertex, and its vertices are rational. Thus the assertion that a rational optimum exists remains valid for irrational metric entries.

The proof-only integer \(N\) can simultaneously clear all required denominators and be divisible by six. The described realizations of \(G\) and \(Z\) allocate the correct numbers of copies, including twice the diagonal pair count.

Every individual greedy edge remains undominated as copies are removed. A diagonal update occurs only when all remaining copies have one type, so all available weights are zero. The constructed matchings therefore satisfy the finite lemma’s hypotheses, and the weight scaling establishes
\[ W_d(G)\ge\tfrac12\operatorname{OPT}_\mu(d). \]

• Output feasibility.

The output is symmetric and nonnegative. The displayed row-sum calculation correctly includes twice the diagonal entry and yields \(\mu_t\). Hence the output is a feasible mass matching.

• Welfare guarantee.

The identity
\[ W_d(Y)=\tfrac34W_d(G)+\tfrac34H_d \]
correctly accounts for both orientations in \(H_d\).

For each type \(t\), summing the triangle inequality over a feasible matching gives the stated upper bound by \(\sum_u\mu_ud(t,u)\). Diagonal terms contribute twice on the right, exactly as required by feasibility.

Weighting this inequality by \(b_t\) establishes \(H_d\ge\operatorname{OPT}_\mu(d)/3\). Combining the bounds gives precisely \(5/8\) of optimum. All steps hold for an arbitrary consistent metric, while the algorithm uses only rankings and masses, so the same output satisfies the guarantee for every such metric.

• Encoding and running time.

The product \(Q\) has bit length \(O(L)\). Denominator \(3Q\) suffices for all greedy quantities, and \(36Q^2\) is a valid common denominator for the output entries. Numerator lengths are also polynomial: the greedy quantities are bounded, and feasibility bounds the output entries.

There are at most \(\tau\) updates; partner searches, cycle detection, and matrix construction require polynomially many operations on polynomial-length integers. No expanded population is constructed. A deterministic algorithm is a valid randomized algorithm that ignores its random bits.

No repair or additional clarification is needed. The argument is self-contained; its correctness does not depend on invoking the cited finite-agent approximation theorem.

⟨structured verdict parsed — rendered above⟩