## Dynamic Matching Strategies in Two-Sided Markets
### The Greedy and the Patient Matching Strategies  
Previous dynamic matching studies [20] showed that simple local algorithms that select appropriate time-matching agents but do not take advantage of the global network structure could perform near complexity optimal algorithms.  
Suppose every node has some time to wait for matching in the market. Each node tends to find a match when the node itself becomes critical, the market size becomes thicker, and the number of objects that can be paired increases. Since the market gets thicker, each node has more choice to match or to be matched. Therefore, we can divide the simple local algorithm into the greedy and patient algorithms. The greedy algorithm means that any node tries to find a match as soon as possible when it arrives at the market. If no match can be found, the node will remain in the market. The patient algorithm means that any node gets a match only when it becomes critical, where the node has exhausted its available time. In the following, we try to explain the main idea of [20] without involving too much mathematics.  
As shown in Figure 7, the node \(n_{i}\) where \(i=1,2,\ldots,5\) arrives at the market in order. If each node matches immediately upon arrival, nodes \(n_{1}\) will find a match whenever node \(n_{2}\) comes at the market, and then no node can be matched with node \(n_{3}\) when it arrives at the market. On the one hand, if each node prefers to wait for a while, nodes \(n_{1}\) will have the other matching choices. This situation is an example of the so-called timing issue. On the other hand, at this moment, node \(n_{1}\) could choose nodes \(n_{2}\) or \(n_{3}\) but not both of them; this situation clearly shows a structural issue.  
Notice that choosing the node which benefits the whole market will complicate the system a lot. For example, if node \(n_{1}\) is aware that its match with node \(n_{3}\) will make nodes \(n_{2}\) and \(n_{5}\) get matched, it leads to a better system state than its choice to match with node \(n_{2}\) directly. However, to reach such a better system state, one must globally compute all the possible linking situations of the market. Clearly, it will take \(O(n_{2})\) complexity if the market size is \(n\). Another fact is, in the dynamic matching market, if any node arrives at the market or leaves the market, all the linking possibilities must be recalculated. Unfortunately, our system is blockchain-based, and there is no centralized planner and/or executor to handle the above-mentioned global computation. Therefore, it is better to postpend the actual match somewhat to thicken the market size, which may increase the overall system matching rate.  
Figure 7: Timing issue of the matching process. (**Upper**) The matching conditions among active nodes in the market; (**Bottom**) different market states caused by different node N\({}_{i}\)’s matching choice.  
Furthermore, timing and structural issues are related to each other. If each node waits for a while to find a match, the number of nodes in the market will increase, and the nodes will have more possible links among each another. On the other hand, if the market already has sufficient thickness, each node's choice will not impact its system structure much. For example, in Figure 8, if \(n_{1}\) matches any of its neighbors, the other nodes can always find someone to match with. Compared with Figure 7, in which, if \(n_{1}\) selects its match with \(n_{2}\), the choice will make nodes \(n_{3}\) and \(n_{5}\) unable to find matches, this choice causes a higher loss to the market.  
For measuring the density of a market, we define the density parameter as \(\mathbf{d}=\mathbf{np}\), where \(\mathbf{d}\) is the number of expected node links that do not match anyone yet. After each node enters the market, there is a fixed available time, \(\mathbf{T_{a}}\). If a node continues to wait for the entire available time, the node will meet the other \(n\) nodes during this time period. Then the number of expected links of the node will be \(\mathbf{np}\).