d4-conf-aaai-2022-1550 (d4-conf-aaai-2022-1550)

Given a finite type set \(T\), rational masses \(\mu_t\), and symmetric nonnegative pair utilities \(b_{tu}\), consider every even scale \(q\) for which \(q\mu_t\) is integral. People of each type arrive in uniformly random order, and a causal policy must pair everyone without rejection. What is the supremal limiting ratio of expected welfare to \(qF^*(\mu,b)\), where \(F^*\) is the type-level fluid matching optimum, and can a policy attain that ratio?

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). The support size is not the number of possible types. Pair utilities \(b_{tu}=b_{ut}\geq0\), including \(b_{tt}\), are binary rationals; \(L\) is the total input bit length.
For each \(q\in Q:=\{q\in2\mathbb N:q\mu_t\in\mathbb Z\text{ for all }t\}\), there are \(q\mu_t\) distinct people of type \(t\), arriving in a uniformly random permutation. Every pair of distinct people is allowed and contributes its pair utility once.
A randomized causal policy knows \((T,\mu,b,q)\) initially and observes each person's type upon arrival. Before the next arrival it must either irreversibly pair the current person with one waiting person or leave the current person waiting; it cannot pair two waiting people. Everyone must be paired by the final arrival for every arrival order.
Fix an ordering of \(T\). Define \(F^*(\mu,b)=\max\{\sum_{t\leq u}b_{tu}x_{tu}:x_{tu}\geq0,\ 2x_{tt}+\sum_{u<t}x_{ut}+\sum_{u>t}x_{tu}=\mu_t\text{ for all }t\}\), where \(x_{tu}\) is pair mass, and restrict to \(F^*>0\).
For a policy family \(\pi=(\pi_q)_{q\in Q}\), let \(W_q^{\pi_q}\) be total welfare and define \(R^*(\mu,b)=\sup_\pi\liminf_{q\to\infty,\ q\in Q}\mathbb E[W_q^{\pi_q}]/(qF^*(\mu,b))\); expectation includes arrival and policy randomness. State running times in \(\tau,L,q\); there is no separate candidate or resource parameter \(m\).

What is \(R^*(\mu,b)\), and can a causal policy family attain this limiting ratio for every admissible input?

For arbitrary finite weighted complete graphs, a polynomial-time no-rejection secretary algorithm has asymptotic competitive factor \(3.34\), measured in expected welfare. [Goyal](https://arxiv.org/pdf/2112.07140)
When rejection is allowed and weights are initially unknown, the optimal discrete secretary welfare guarantee is \(5/12\). [Ezra et al.](https://arxiv.org/abs/2011.01559) No result settling the exact normalized, known-type problem above was located.

Result

For every admissible input,
\(R^*(\mu,b)=1\).

A deterministic causal policy family attains this limit. In fact, its welfare loss relative to \(qF^*(\mu,b)\) is bounded independently of \(q\), for every arrival order.

1. Every matching satisfies the fractional upper bound

Fix \(q\in Q\), and write \(N_t=q\mu_t\). For any realized perfect matching, let \(M_{tu}\) be its number of pairs of types \(t,u\), indexed by \(t\leq u\).

Every person is paired exactly once, so
\(2M_{tt}+\sum_{u<t}M_{ut}+\sum_{u>t}M_{tu}=N_t\).

Consequently, \(x_{tu}=M_{tu}/q\) is feasible for the defining program of \(F^*(\mu,b)\). The realized welfare therefore satisfies
\(W_q=\sum_{t\leq u}b_{tu}M_{tu}\leq qF^*(\mu,b)\).

This bound holds for every arrival order and every realization of policy randomness. Hence \(R^*(\mu,b)\leq1\).

2. A virtual perfect matching can be implemented causally

Lemma. Create \(N_t\) distinct virtual people of each type \(t\), labeled \((t,1),\ldots,(t,N_t)\). Any predetermined perfect matching of these virtual people can be realized by a deterministic causal policy, with exactly the same welfare, for every arrival order.

Proof. Assign the \(k\)-th actual arrival of type \(t\) to virtual person \((t,k)\). This assignment uses only the observed history.

When a person arrives, inspect the predetermined partner of its assigned virtual person.

• If that partner has not arrived, leave the current person waiting.
• If that partner has arrived, pair the current person with the corresponding waiting person.

The partner in the second case is necessarily still waiting: its only permitted pairing under this policy is with the current virtual person, which has just arrived.

Thus each predetermined pair is completed precisely when its second member arrives. Every pairing involves the current arrival and one waiting person. By the final arrival, every virtual person has been assigned, so every predetermined pair has been completed. Types are preserved by the assignment, and therefore welfare is preserved. This proves the lemma.

In particular, choosing an optimal virtual perfect matching shows that the finite offline optimum is causally attainable for every \(q\). For the limiting question, the following explicit construction suffices.

3. Constructing a plan with bounded loss

The fractional program is feasible: take \(x_{tt}=\mu_t/2\) and all off-diagonal variables zero. Summing its degree constraints gives
\(2\sum_{t\leq u}x_{tu}=1\).

Its feasible region is therefore closed and bounded, so an optimum \(x^*\) exists.

For each \(q\in Q\), define integer pair counts
\(K_{tu}=\lfloor qx^*_{tu}\rfloor\).

The number of type-\(t\) virtual people used by these pairs satisfies
\(2K_{tt}+\sum_{u<t}K_{ut}+\sum_{u>t}K_{tu}\leq q\mu_t=N_t\).

We can consequently allocate distinct virtual people to all these prescribed pairs. For a diagonal pair, allocate two distinct people of its type.

Let the remaining number of type-\(t\) virtual people be
\(D_t=N_t-2K_{tt}-\sum_{u<t}K_{ut}-\sum_{u>t}K_{tu}\).

Every \(D_t\) is a nonnegative integer, and
\(\sum_tD_t=q-2\sum_{t\leq u}K_{tu}\)
is even. Pair these remaining virtual people arbitrarily. This is possible because every pair of distinct people is allowed.

Define the input-dependent constant
\(C(b)=\sum_{t\leq u}b_{tu}\).

The arbitrary completion contributes nonnegative welfare. Thus the resulting perfect matching has welfare at least
\(\sum_{t\leq u}b_{tu}\lfloor qx^*_{tu}\rfloor\).

Using \(\lfloor a\rfloor\geq a-1\) and \(b_{tu}\geq0\), this is at least
\(q\sum_{t\leq u}b_{tu}x^*_{tu}-\sum_{t\leq u}b_{tu}=qF^*(\mu,b)-C(b)\).

Implement this virtual matching using the lemma. We obtain a deterministic causal policy \(\pi_q\) satisfying, for every arrival order,
\(qF^*(\mu,b)-C(b)\leq W_q^{\pi_q}\leq qF^*(\mu,b)\).

4. Attainment of the limiting ratio

Because the masses are rational, there is a common positive denominator \(d\). Every positive multiple of \(2d\) belongs to \(Q\), so \(Q\) is unbounded.

For the policy family just constructed, taking expectations and dividing by the positive quantity \(qF^*(\mu,b)\) yields
\(1-\frac{C(b)}{qF^*(\mu,b)} \leq\frac{\mathbb E[W_q^{\pi_q}]}{qF^*(\mu,b)} \leq1\).

The input is fixed as \(q\) tends to infinity. Therefore,
\(\lim_{q\to\infty,\ q\in Q}\frac{\mathbb E[W_q^{\pi_q}]}{qF^*(\mu,b)}=1\).

Together with the upper bound, this proves \(R^*(\mu,b)=1\), with attainment by a deterministic causal policy family. The proof does not require randomness in the arrival order.

5. Running time

There are \(\tau(\tau+1)/2\) fractional variables and \(\tau\) equality constraints. Standard exact rational linear programming computes a rational optimum \(x^*\), of polynomial encoding length, in time polynomial in \(\tau,L\). Its hypotheses hold here: all coefficients are rational, and the feasible region is nonempty and bounded.

For each \(q\), computing \(N_t\) and \(K_{tu}\) takes time polynomial in \(\tau,L,\log q\). The virtual matching can then be stored as a partner array on the \(q\) virtual people.

With types indexed by the given ordering, constructing that array takes \(O(q+\tau^2)\) word operations. Processing each arrival takes \(O(1)\) word operations: increment its type counter, inspect its virtual partner, and either store or pair the person. The indices require \(O(\log q)\) bits; indeed, positivity and admissibility imply \(N_t\geq1\), hence \(\tau\leq q\).

Thus the construction uses polynomial preprocessing in \(\tau,L,\log q\), followed by \(O(q+\tau^2)\) word operations and \(O(q+\tau^2)\) words of storage. In particular, its total bit complexity is polynomial in \(\tau,L,q\). There is no additional candidate or resource parameter.

⟨structured verdict parsed — rendered above⟩

The output fully resolves the assigned problem. The causal implementation is valid, the rounding loss is bounded independently of \(q\), and the limiting ratio is attained. I found no mathematical or computational gaps requiring repair.

• Fractional upper bound. For every realized perfect matching, the counts \(M_{tu}\) are nonnegative integers and satisfy the stated degree equations. Dividing by \(q\) gives a feasible point of the defining program for \(F^*(\mu,b)\). The objective is exactly realized welfare divided by \(q\), including diagonal pairs, whose utilities are counted once while consuming two people.

Consequently, \(W_q\leq qF^*(\mu,b)\) holds pointwise. It therefore bounds expectations, the liminf for every policy family, and their supremum. The conclusion \(R^*(\mu,b)\leq1\) is justified.

• Causal implementation lemma. Assigning the \(k\)-th arrival of type \(t\) to \((t,k)\) uses only observed history. Since there are exactly \(N_t\) actual arrivals of that type, this assignment eventually gives a bijection between actual and virtual people.

For any predetermined pair, its first arriving member waits. It cannot be paired with anyone else under this policy, because the policy consults only predetermined partners. When the second member arrives, the first is therefore still waiting, and the pair can be completed legally.

This verifies causality, irreversibility, the restriction against pairing two waiting people, and completion by the final arrival for every order. The reasoning also covers pairs whose members have the same type. Type preservation establishes equality of welfare. The claim that a predetermined optimal virtual matching is causally attainable is thus valid.

• Existence of a fractional optimum. The diagonal assignment \(x_{tt}=\mu_t/2\) satisfies every degree constraint and nonnegativity. Summing the constraints counts every pair variable twice, giving

\[ 2\sum_{t\leq u}x_{tu}=1. \]
This establishes boundedness. The feasible region is closed, and the objective is continuous, so an optimum exists. All necessary hypotheses are established.

• Feasibility of rounded pair counts. Since \(x^*_{tu}\geq0\), the counts \(K_{tu}=\lfloor qx^*_{tu}\rfloor\) are nonnegative integers. Rounding down preserves the stated upper bounds on consumption of each type, including the factor of two for diagonal pairs. Thus enough distinct virtual people exist for all prescribed pairs.

Each residual count \(D_t\) is a nonnegative integer. Their total is even because \(q\) is even and each prescribed pair consumes two people. Completeness of the allowed pairing graph permits arbitrary pairing of all residual people, including the case of no residual people. No type-specific parity condition is needed.

• Welfare bound. Nonnegative utilities justify discarding the completion’s contribution when obtaining a lower bound. Applying \(\lfloor a\rfloor\geq a-1\) separately to each coordinate, with nonnegative multipliers \(b_{tu}\), gives precisely the claimed loss bound

\[ qF^*(\mu,b)-C(b)\leq W_q^{\pi_q}\leq qF^*(\mu,b). \]
The constant \(C(b)\) is finite and depends only on the fixed input. The bound remains valid when its lower endpoint is negative, and when some utilities or optimal coordinates vanish.

• Limit and attainment. A common denominator \(d\) exists for the rational masses. Every positive multiple of \(2d\) is even and makes all population counts integral, so \(Q\) is unbounded.

The assumption \(F^*(\mu,b)>0\) permits division by the normalization. For a fixed input, \(C(b)/(qF^*(\mu,b))\) tends to zero along all admissible \(q\). The displayed bounds therefore establish an actual limit of one for the constructed family. Combined with the universal upper bound, this proves both \(R^*(\mu,b)=1\) and attainment. Uniform randomness of arrival order is unnecessary because the bounds hold for every order.

• Running time. The cited rational linear programming result is stated with the relevant guarantees: an exact rational optimum of polynomial encoding length can be computed in polynomial time. The program has rational data, polynomially many variables and constraints, and a nonempty bounded feasible region, so its hypotheses are satisfied.

Exact arithmetic for \(N_t\) and \(K_{tu}\) has polynomial bit complexity in \(\tau,L,\log q\). Allocating the prescribed pairs and their completion supports the claimed \(O(q+\tau^2)\) word-operation bound. A partner array, type counters, and stored arrival references support constant word-operation processing per arrival.

Positivity and admissibility imply \(N_t\geq1\), hence \(\tau\leq q\); the stated index sizes are consequently sufficient. Polynomial total bit complexity in \(\tau,L,q\) follows. The analysis introduces no separate candidate or resource parameter.

No corrective feedback is necessary.

⟨structured verdict parsed — rendered above⟩