Online matching games in bipartite expanders and applications

For the sake of this discussion, let us interpret left nodes of a graph as clients and right nodes as servers. The bipartite relation models the fact that a client can only be satisfied by certain servers. If the graph has offline matching up to $K$ elements, then for every set of at most $K$ clients, one can assign unique servers. In incremental matching up to $K$, irrevocable assignments must be made on-the-fly as clients arrive and request access to a server. The condition is that at most $K$ clients arrive. In online matching up to $K$, each client may in addition, release the assigned match. The condition is that at most $K$ clients may simultaneously need access to a server. We also allow a relaxed notion, in which a server may be assigned to up to $\ell$ clients. As mentioned, the formal definition uses a game.

Feldman, Friedman, and Pippenger [FFP88, proposition 1] have shown that if a graph has $2$-expansion up to $2K$, then it has online matching up to $K$. By a similar argument, $1$-expansion up to $K$ implies online matching up to $K$ with load $3$, see appendix A. Unfortunately, matches are computed in time exponential in $K$.

In applications, parameters $N$ and $K$ are given, and a graph is needed with left size $N$ and online matching up to $K$. It is desirable that the graph has:

– few right nodes, (ideally, close to $K$),

– few edges, (ideally, close to $N$), and

– fast matching time (ideally, the algorithm should be “local,” i.e., it should inspect only the neighborhoods of a few left nodes).

Therefore, an important open question implicitly formulated in [FFP88] is to find graphs that achieve the above 3 objectives. We come close to this goal.

We show that a graph with expansion factor equal to a large fraction of the left degree (i.e., a lossless expander) has polynomial-time online matching and, moreover, if we allow small load, it has logarithmic time online matching.

The algorithms receive the game state in the most natural way, see the first paragraphs of section 2 and the definition in section 4 below for details. The algorithms use a datastructure to store information for faster computation of future matches. The load $\ell=O(\log N)$ can be reduced to $1$, by making $\ell$ clones of the right side connected to the left side as in the original graph. This yields a graph in which the left degree and the right size increase only by a factor of $\ell$ and the runtime remains $O(\text{(left-degree)}\cdot\log N)$.

In theorem 1.2, the running time for computing a match is double exponentially faster than in [FFP88]. There exist non-explicit constructions of lossless expanders (see lemma 5.2) in which the right size is $O(K\log N)$ and the number of edges is $O(N\log N)$. Hence, the 3 objectives (the right size, number of edges, and matching time) are simultaneously optimal up to a $O(\log N)$ factor. Known explicit constructions of lossless expanders (see theorem 6.2) provide graphs with online matching in which the right size, number of edges, and matching time are optimal up to $\operatorname{quasipoly}(\log N)$.

These results add a new entry to the list of wonderful properties of lossless expanders (for an overview, see [HLW06, Chapter 10] or [CRVW02, section 1.3]). The power of the main theorem and of various related online matching games that are used in its proof will be illustrated in 3 applications below.

Proposition 1.1 is proven in section 2. The idea is to assign arbitrary free neighbors for all requested nodes, with the exception of left nodes that have 1/3 of their neighbors already assigned to other nodes. Such a node is said to be critical and is “protected” by receiving a carefully chosen virtual match. This match is converted into a real match if the node is requested and it is released if the fraction of busy neighbors decreases below 1/3. The large expansion and the unique neighbor property of lossless expanders are used to show that not too many nodes can be simultaneously critical and to find the virtual matches.

For theorem 1.2, the idea is to combine 2 matching strategies. The first one is the slower procedure from proposition 1.1. The second one, presented in section 3, is a greedy procedure that runs in time $O(D\log N)$ as required, but can not assign matches for a few problematic left nodes. Fortunately, a small subset containing these nodes can be identified well in advance, i.e., many requests before such a problematic request might happen, and handled by the slower procedure on a separate copy of the graph. In particular, this implies that there are not too many of such bad requests, and this leads to a small amortized runtime. We next interlace the two procedures on further copies of the graph. This allows de-amortization and leads to the claimed fast worst-case running time.

The goal is to store a subset $S$ of a large set $\{1,\ldots,N\}$ to answer membership queries “Is $x$ in $S$?”. Let $K=\#S$ be the size. A simple way is to store $S$ in a sorted list. This requires $K\lceil\log N\rceil$ bits of memory, and given $x$, one can determine whether $x$ is in $S$ by reading $(\lceil\log K\rceil+1)\cdot\lceil\log N\rceil$ bits from the table. An alternative is to have a table of $N$ bits and set bit $x$ equal to $1$ if and only if $x\in S$. Now the query “Is $x\in S$?” can be answered by reading a single bit. Also, one can insert or delete an element by modifying a single bit. The cost is that the table is long, since typically $N\gg K$. We show that the advantages of the latter approach can be obtained with a data structure whose size is close to $K\log N$.

A 1-bitprobe storage scheme (also called a bit vector) is a data structure that answers a membership query “Is $x$ in $S$?” by reading a single bit. It is a fundamental data structure introduced by Minsky and Papert in their book on perceptrons [MP69]. See [BMRV00, Rom14, GR17, DPR22] for historic and recent references. In [BMRV00], lossless expanders are used to build 1-bitprobe storage schemes with short tables in which membership queries are answered probabilistically with small error $\varepsilon$.⁵⁵5Such 1-bitprobe storage schemes are different from Bloom filters which store an approximation of the set. More precisely, a Bloom filter stores a superset S’ of the intended S. Thus for every $x$ in $S^{\prime}-S$ (the false positives) the error probability of the query “Is $x$ in $S$?” is 1, and for $x$ in $S$ or in $U-S^{\prime}$ the error probability is 0 (and the probability over the choice of the hash functions used by the Bloom filter that an element is in $S^{\prime}-S$ is $\varepsilon$). Using a non-explicit expander they obtain storage size $O(\tfrac{1}{\varepsilon^{2}}K\log N)$. Note that this is close to the lower bound $K\log N-O(1)$ for any set data structure. They also have an explicit construction achieving storage size $O((\tfrac{1}{\varepsilon}K\log N)^{2})$. Ta-Shma [Ta-02] and Guruswami, Umans, and Vadhan [GUV09, Theorem 7.4] give explicit constructions with smaller storage size. In all these schemes, making a membership query (i.e., finding the location in the data structure of the bit that is probed) takes time $\operatorname{poly}(\log(N/\varepsilon))$.

These 1-bitprobe storage schemes work for static sets, in the sense that any updating of $S$ requires the recomputation of the entire data structure, which takes time $\operatorname{poly}(K\log(N/\varepsilon))$. We obtain explicit 1-bitprobe storage schemes for dynamic sets. Membership queries also take time $\operatorname{poly}(\log(N/\varepsilon))$. Insertion and deletion of an element takes time $\operatorname{quasipoly}(\log(N/\varepsilon))$. The storage size is smaller than in the previous explicit schemes for static sets provided $\varepsilon\geq 1/K^{1/\log^{2}\log K}$, see table 1. Full definitions are given in section 7. The proofs only depend on sections 3 and 6.

All previous explicit 1-bitprobes required lossless expanders with a special “list-decoding” property (see [GUV09, theorem 7.2]), while our approach works with any lossless expander. Thus future improvements in explicit lossless expanders will give better dynamic 1-bitprobes. This feature of our method also opens the possibility of implementations that are attractive in practice by using constructions based on tabulation hashing [Tho13] or empirical hashing methods, see the remark on page 7.

We show that a graph with $((1-\varepsilon)D)$-expansion up to $2K$ has $(2\varepsilon)$-rich online matching up to $K$ with load $O(\log K)$ in the game with $K$-expiration. This follows by a modification of the greedy algorithm in section 3. The modification is given in section 6 (sections 2 and 4 are not needed for this application). Next, composing such a graph with a certain graph based on simple hashing, we obtain explicit graphs with the same type of matching but with load $1$. Moreover, the right size is $K\cdot\operatorname{quasipoly}(\log(NT))$, which is almost optimal, see corollary 6.3. A slightly weaker result is proven in [BZ23, corollary 2.13], without explicitly referring to matching.

For the 1-bitprobe, we use a graph $G$ that has $\varepsilon$-rich matching (with load $1$) up to $K+1$ for the game with $2K$ expiration. To each right node we associate 1 bit of the bitvector and initially all these bits are set to $0$. When an element $x$ is inserted in $S$, it is matched with $(1-\varepsilon)$ fraction of its neighbors and the associated bits are set to $1$. When we query some $x\not\in S$, we can still match $x$ with $(1-\varepsilon)$ fraction of its neighbors (because $G$ has matching up to $K+1$ and there exist only at most $K$ matches for the elements in $S$) which means that the associated bits are set to $0$. Therefore for every $x$, $(1-\varepsilon)$ fraction of its neighbors indicate if $x$ is in $S$ or not. This assumes that the game has $2K$-expiration, but this requirement can be easily satisfied by periodically refreshing the matches of nodes with old assignments.

A dictionary is a datastructure for storing a set $S$ of items, where an item is a pair (key, value) and no two items have the same key. The keys are elements of a large ambient set, called the Universe. We ignore in our discussion the value component because in most implementations from the location of the item in the datastructure, the associated value can be retrieved in constant time. Therefore we view the datastructure as a table of cells, where each cell can store a key $x$. The static dictionary supports the operation query($x)$, which returns the index of the cell containing $x$ if $x\in S$, and NIL, otherwise. Note that this is stronger than the membership query from Application 1 with bitprobe storage, which only had to return 1 bit indicating if $x$ is in $S$ or not. The dynamic dictionary supports in addition the operations insert($x$) and delete($x$) for updating the dictionary.

The standard implementations use hash functions and various strategies for handling collisions such as chaining, linear probing, cuckoo chaining, and so on. The perfect hashing scheme for static dictionaries of Fredman, Komlós and Szemerédi [FKS84] does the query operation in $O(1)$ time. Dietzfelbinger at al. [DKM⁺94] have a scheme for dynamic dictionaries with update operations running in expected amortized $O(1)$ time. There are various improvements in various aspects but it is not in our scope to present this vast and important area. We refer the reader to [LPPZ23, PY20, LPP⁺24] for discussions of the literature that is relevant for our application.

An operation($x$) (where operation is one of query, insert or delete) is non-adaptive if the locations in the datastructure that are accessed during its execution are a function (possibly probabilistic) of $x$ only (so, they are independent of previous operations).

Note that all the schemes based on hash functions are adaptive: first a description of the hash function $h$ stored in the datastructure has to be retrieved in order to calculate $h(x)$, and next the cell with address $h(x)$ in the hash table must be probed. In many schemes, subsequent additional adaptive probes are required to handle collisions. Binary search and binary search trees (which are stronger than hash tables because they also support predecessor search) also have adaptive access to the memory.

Are there efficient schemes with non-adaptive operations? This is an interesting theoretical question. It also has practical implications because non-adaptive probing is suitable for parallel algorithms which can reduce the overall response latency. Persiano and Yeo [PY20, LPP⁺24] have shown lower bounds implying that query cannot be done non-adaptively with $O(1)$ probes. However, if the probes are done in parallel the query time can still be constant.

As in Application 1, let $N$ be the size of the Universe and $K$ the size of $S$ (for the dynamic version, the set $S$ has during its entire history at most $K$ items).⁶⁶6Many papers (for instance [LPPZ23, LPP⁺24]) in the datastructure literature use $u$ for the size of the Universe and $n$ for the size of $S$. Typically, $N\gg K$. The lower bound in [PY20] is in the standard cell probe model in which computation is free of charge and the data structure consists of $s$ memory cells, each cell having size $w$ bits. The lower bound in [PY20] is more general, but in the particular and natural setting $w=\Theta(\log N)$, it states that for a static dictionary with non-adaptive query (which can be randomized, but with error probability $0$) the expected number of probes is $t=\Omega(\log(N/K)/\log(s/K))$. Recently, Larsen et al. [LPPZ23, LPP⁺24] have shown that this lower bound is tight, improving upon [BHP⁺06]. Their construction is non-explicit (more precisely, they build using the probabilistic method a graph with $1$-expansion up to $K$ which is assumed to be available to query) and they ask for an efficient explicit scheme. We present such schemes for both static and dynamic dictionaries (note that the result in [LPPZ23, LPP⁺24] is only for the static case).

Our static dictionary has $s=\color[rgb]{1,0.4,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.4,0.4}5\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}K$ (with cell size $w=\log N$)⁷⁷7For simplicity, we did not optimize $s$. In fact, for any $\varepsilon>0$, one can achieve $s=(4+\varepsilon)K$ (with $w=\log N$), with easy adjustments in the proof. and the number of non-adaptive probes is $t=\Theta(\log^{5}N)$. It is explicit and deterministic and the runtime for computing one probe (i.e., computing the location in the datastructure that is read) is $\operatorname{poly}(\log N)$. The dictionary in [LPPZ23, LPP⁺24] achieves the better parameters $s=2K$ (with $w=\log N$) and $t=\log(N/K)+5$ but, as mentioned, is non-explicit (we note that their scheme also works for larger $s$ in which case $t$ is smaller).

For the dynamic version, we have two schemes which are similar, however one is probabilistic, and the other one is deterministic. Since we use an explicit graph, in both schemes the runtime for doing one probe in the datastructure is $\operatorname{poly}(\log N)$. In the probabilistic version, all operations are non-adaptive, the datastructure size is $s=O(K\log N)$ (with cell size $w=\Theta(\log N)$) and the number of probes is $t=O(\log^{6}N)$. The operations query and delete succeed with probability 1, and each execution of insert($x$) fails to insert $x$ with probability at most $2^{-\Omega(N)}$, where the probability is over the randomness of the previous $N^{3}$ update operations. As far as we know, this is the first dynamic dictionary in which all operations are non-adaptive (if we ignore the trivial solution of using a bitvector of length $N$). In the deterministic version, query and delete are non-adaptive but insert is adaptive.⁸⁸8If the history of the dictionary is limited to $O(N)$ operations (for instance, if the dictionary is reconstructed after every batch of $O(N)$ operations), then all operations can be made non-adaptive. The advantage is that $s=O(K)$ (with $w=\Theta(\log N)$) is optimal (up to the constant in $O()$) and $t=O(\log^{5}N)$.

Östlin and Pagh [ÖP02] and Berger et al. [BHP⁺06] have also used a type of online matching in expanders to implement dynamic dictionaries in which query is non-adaptive and insert and delete are adaptive. Compared to our approach, the main difference is that they allow the Matcher to change previous matches. This makes the matching strategy easier but causes the dictionary updates to be adaptive. Also, they use lossless expanders whereas we use graphs with 1-expansion and for this reason we obtain smaller $s$.

Proof ideas. For the static dictionary we present here the entire proof. Exactly as in [LPPZ23], we take a bipartite expander that has the set of left nodes = Universe and $1$-expansion up to $K$. Each right node is associated with a memory cell in which elements of the Universe can be written (recall that cell size $w=\Theta(\log N)$). By Hall’s theorem for any subset $S$ of the left side of size at most $K$, there is an injective mapping $f$ from $S$ to the right side. We store every element $x$ in $S$ at the memory cell $f(x)$. When we do query$(x)$ for an arbitrary $x$ in Universe, we inspect every right neighbor of $x$ to see if one of them contains $x$. [LPPZ23] obtains the graph with the probabilistic method. Instead, we use the explicit $1$-expander in proposition 1.3 and we obtain the static dictionary with the parameters claimed above.

The proof is given in section C. It relies on the dispersers in [TSUZ07] and it improves similar constructions in [BMVZ18, section 3.2], [Teu14], and [Zim14, Lemma 4].

For the dynamic dictionary (both the probabilistic and the deterministic versions) the proof is similar but instead of using offline matching guaranteed by Hall’s theorem, we do online matching in the game with the $T$-expiration restriction (recall that this means that no match is allowed to last more than $T$ rounds). The key fact is that in section 3 we design a Matcher strategy for these games that finds a match for a left node only by inspecting its neighbors, and so it is non-adaptive. As in the static case, we associate to each right node a memory cell and when $x$ is inserted it is written in the cell matching it. To do query($x$), we check if the cell associated to some neighbor of $x$ contains $x$ or not. By proposition 3.1, the Matcher strategy wins in graphs with 1-expansion and then, essentially, by instantiating with the graph in LABEL:{t:constexpander} we obtain small $s$ and $t$.

Like in 1-bitprobes, it remains to satisfy the expiration restriction by refreshing the matches of some elements. The choice of which element is refreshed is essentially the difference between the probabilistic and the deterministic versions. In the probabilistic version, we play the online matching game with $N^{3}$-expiration. When we do an insert we also refresh a random element of Universe (which, recall, has size $N$). Note that insert remains non-adaptive. The probability that some matching is not refreshed for more than $N^{3}$ rounds is $2^{-\Omega(N)}$. In the deterministic version, we play the online matching game with $K$-expiration, and now when we do an insert, we refresh the oldest element in the dictionary. This causes insert to be adaptive. The advantage is that the expiration parameter is smaller ($K$ compared to $N^{3}$) and therefore we can win the game in a graph with a smaller number of clones, implying a smaller $s$ in the deterministic version.

Switching networks are used for the transfer of information between a large number of nodes. For example, in the early days of telephone networks, when there were only a few phones in a town, people made pairwise connections between all phones. When the number of phones grew, this was no longer feasible, and switching stations were introduced. Their theoretical study was initiated by Shannon [Sha50] and was the motivation for introducing expander graphs [BP73, Mar73]. Currently there is a large literature, both in the engineering and the theoretical computer science fields. See the book [Hwa04] for more history.

Nowadays, switching networks are important in various engineering applications where a large number of components need to communicate. Unlike telephone networks, these applications mainly concern a bipartite variant with inputs on one side and outputs on the other side, see [Hwa04]. In such graphs, the aim is to connect all output nodes to any permutation of input nodes using node disjoint paths.

An $N$-network is a directed acyclic graph in which $N$ nodes are called inputs and $N$ nodes are called outputs. Its size is the number of edges. A rearrangeable $N$-network is such a network in which for every 1-to-1 function $f$ from outputs to inputs, there exist $N$ node disjoint paths that connect each output node $f(i)$ to the input node $i$.

For example, a fully connected bipartite graph with left and right sets of size $N$ defines a rearrangeable $N$-network with $N^{2}$ edges. Another example is given in figure 1. The goal is to construct networks with a minimal number of edges. Since there are $N!$ different mappings, the minimum is at least $\log N!$, which is at least $N(\log N-2)$ by Stirling’s formula.

We use a generalized variant of rearrangeability, in which several output nodes may be connected to the same input, but each output is connected to at most 1 input. In terms of broadcasting, this means that several outputs can listen to the same input. Moreover, the connection problem needs to be solved dynamically. For this, 2 closely related requirements exist, which are called strict-sense non-blocking connector and wide-sense non-blocking connector, see [Hwa04]. We use the second one, which is weaker, and is defined by a game.

At his turn, Requester may remove zero or more trees. Afterwards, he may select an input $x$ and an output $y$ such that $y$ does not lay on any of the trees.

At her turn, Connector may create or extend a tree so that the above conditions are satisfied. Afterwards, there should be a tree in which $x$ is the root and $y$ is a leaf. If this is not true, she looses.

A fully connected bipartite graph is an $N$-connector. An $N$-connector was given in [FFP88] that has $O(N\log N)$ edges. This is optimal within a constant factor. The graph is explicit but the path finding algorithm (which is the algorithm that computes Connector’s reply) is very slow. Afterwards, in [ALM96] an explicit $N$-connector is constructed of size $O(N\log N)$ in which also the runtime of the path finding algorithm is $O(\log N)$, and this is optimal within a constant factor. See [ALM96] or [Hwa04, chapter 2].

The depth of a network is the length of the longest path between an input and an output. We focus on constant depth $N$-connectors. In [PY82] it is shown that $N$-connectors of depth $t$ have at least $tN^{1+1/t}$ edges. In [FFP88] non-explicit constructions of $N$-connectors are given of size $O(N^{1+1/t}\log^{1-1/t}N)$, but again the path finding algorithm runs in time exponential in $N$. They ask whether a generalized connector exists with small size and an efficient path finding algorithm. They do not specify explicitly, but “small size” is usually considered to be a value that is $N^{1+1/t}\cdot N^{o(1)}$, see [WZ99], and “efficient” should ideally mean that the runtime is $\operatorname{poly}(\log N)$. Some explicit constant-depth $N$-connectors are known with path finding algorithms running in time $\operatorname{poly}(\log N)$, but their size is not optimal, see [Hwa04, chapter 2]. For instance, for odd $t$, the Clos network of depth $t$ has size $\Theta_{t}(N^{1+2/(t+1)})$.

In [WZ99, Th. 5.4] an explicit construction of size $N^{1+1/t}\exp((\log\log N)^{O(1)})$ was obtained, but the path finding algorithm is the same slow one from [FFP88].

In section 5, we present a non-explicit constant depth $N$-connector whose size is optimal up to factors $\operatorname{poly}(\log N)$ and with a path finding algorithm running in time $\operatorname{poly}(\log N)$. Here we assume that the input of this algorithm is a description of the state of the connection game that includes the graph⁹⁹9For each node the input specifies the degree and a list of neighbors in arbitrary order. and the algorithm may use a data structure.

Theorem 1.2 assumes large expansion, logarithmic load, and that the algorithm uses a data structure. We do not know if we can strengthen any of these assumptions. The strongest claim that we can not refute is the following.

The following open question is weaker than the above open question. However, if true, then the size of explicit connectors with depth $t$ can be further improved to $N^{1+1/t}\operatorname{poly}(\log N)$ instead of $N^{1+1/t}\operatorname{quasipoly}(\log N)$. (Recall that the lower bound is $tN^{1+1/t}$.)

A further relaxation of the last open question is to require $\operatorname{poly}(N)$ runtime instead of $\operatorname{poly}(\log N)$. Proving that such an algorithm does not exist requires some hardness assumption because if P = NP, the algorithm from [FFP88, proposition 1] runs in time $\operatorname{poly}(DN)$.

The main result is only used for the 3rd application, and the other applications follow from parts of its proof. The question is whether the main result can be strengthened to get all applications from a single result. We tried hard to use a single result to obtain both the 1st and 3rd application. Therefore, we expect a negative answer to the following question.

We analyze 3 related online matching games in bipartite graphs.

1. (A)

   The basic game, defined on page 1.

2. (B)

   The game with $T$-expiration, which adds the requirement that Requester must drop any assignment after at most $T$ rounds.

3. (C)

   The $\varepsilon$-rich matching game with $T$-expiration, which adds to game (B) the constraint that the Matcher must match a requested node with $(1-\varepsilon)$-fraction of its neighbors.

From the point of view of the Matcher’s strategy, game (B) is easier than game (A), and game (C) is more difficult than game (B) and incomparable with game (A). The logical dependencies between technical results and applications is given in the following figure. Game (A) is used for application 3 ($N$-connectors), game (B) for application 2 (dictionaries with non-adaptive probes), and game (C) for application 1 (1-bit probes).

The table below provides a summary of various “Hall-type” results for online matching. If a graph with $N$ left nodes and left degree $D$ satisfies the expansion condition in column 1, then it has matching with the features in columns 2, 3, and 4. The 4-th column is the worst case runtime for finding or retracting one matching assignment.

For game (C), any graph with $(1-\varepsilon)D$-expansion up to $2K$ has $T$-expiration online $(2\varepsilon)$-rich matching up to $K$ with load $O(\log T)$, in which a matching assignment/retraction can be done in time $O(D\log(TN))$. We show this for $K$-expiration in section 6. The case of general $T$-expiration can be shown similarly to proposition 3.1.

Technically, the most difficult is the main result, theorem 1.2. It shows that lossless expanders admit fast strategies for matching up to $K$ in the basic game (A). In combination with known non-explicit and explicit constructions, it yields bipartite graphs that solve the main question in a classical paper of Feldman, Friedman, and Pippenger [FFP88]. These graphs have surprisingly strong properties. Note that the right size is only $K\cdot\text{(small-factor)}$ (where (small-factor) is $O(\log N)$ in the non-explicit case and quasipoly$(\log N)$ in the explicit case) and hence the neighborhoods of the $N$ left nodes overlap a lot. Still, for each online matching assignment of a left node, we only inspect its neighborhood and make a few additional simple computations that take less time than scanning the neighborhood.

The proof uses game (B). This game admits a greedy strategy, that only inspects the neighborhood of the requested node (and also updates a few associated counters). This feature of the algorithm is important for the application 2. In fact, this simple strategy makes the bulk of the assignments. A few remaining assignments theoretically may still exist (we proved this for the adversarial setting of the game, but it is unlikely that this happens in practice). For them, a more complex strategy (from proposition 1.1) is used, but running it requires only $O(1)$ time per assignment.

The matching strategy for game (C) is a variant of the strategy for game (B). In the open question 3, we ask whether we can obtain a strategy for game (C) without the condition of $T$-expiration. Fortunately, in application (1), $T$-expiration is not a big issue, because the condition can be satisfied by just refreshing old matches, which adds only a constant factor to the runtime of the insertion algorithm.