An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models

[ALT21] An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models, reading note.

Auction is an amazing algorithm!

Introduction

Auction algorithm is a powerful algorithm which can efficiently solve $(1 + \varepsilon)$-approximate maximum matching problem.

The standard auction algorithm treats the vertices on the two sides of the bipartition as bidders and items, respectively. The auction then starts with every bidder as unallocated and every item with price $0$. In each iteration of the auction, an arbitrary unallocated bidder is selected to report an item with minimum price among the items he desires (i.e., are in the neighborhood of the corresponding vertex in the graph). The price of this item is then increased by and it will be reallocated to this bidder. This process is continued while keeping the price of items capped at $1$ (i.e., the items with price $1$ are no longer reallocated).

Algorithm

[ALT21] introduces a new strategy to update currently matching in each iteration during the auction algorithm.

W.l.o.g, we can assume that $1 / \varepsilon$ is an integer. Then the upper bound of prices is $1$.

Correctness

Defn 3.1. (Utility) For each allocated bidder $u \in L$, we define its utility as $\text{util}(u) = 1 - p_{a_u}$, where $a_u$ is the item allocated to $u$. For unallocated bidder $v \in L$, let $\text{util}(v)$ be $0$.

Defn 3.2. ($\varepsilon$-happy) We say that a bidder $i$ is $\varepsilon$-happy if and only if $\text{util}(i) \ge 1 - p_j - \varepsilon$ for all $j \in \Gamma(i)$, i.e. changing the allocation of $i$ to any other item does not increase the utility of $i$ by more than $\varepsilon$.

Fact 3.3. In every iteration of the auction, allocated bidders as well as unallocated bidders with empty demand sets are $\varepsilon$-happy.

Proof. This fact holds as:

1. Each allocated bidder picked the minimum price item in its neighborhoods (and increased its price only by $\varepsilon$), and the price of items are monotonically increasing.
2. Every item in the neighborhoods of an unallocated bidder with empty demand set has price $1$ and thus picking that item cannot increase the utility of the bidder by more than. $\Box$

Let $M^*$ be a maximum matching of $G$ and $\text{OPT} \subset L$ be the set of bidders in $L$ that are matched by $M^*$. For any $i \in \text{OPT}$, we further use $b_i \in R$ to denote the item that is allocated to $i$ in $M^*$.

We first show that then most of the bidders in $\text{OPT}$ are $\varepsilon$-happy, then at the end of algorithm, we will get a $(1 + \varepsilon)$-approximate maximum matching.

Lemma 3.4. Suppose at the end of some iteration of the auction, at least $(1 - \varepsilon) \mu(G)$ bidders in $\text{OPT}$ are $\varepsilon$-happy.Then, the final matching $M$ has size at least $(1 - 2 \varepsilon) \mu(G)$.

Proof. Let $\text{Happy}$ be the collection of $\varepsilon$-happy bidders. First notice that:

$\begin{aligned} \sum_{i \in L} \text{util}(i) & \ge \sum_{i \in \text{Happy} \cap \text{OPT}} \text{util}(i) \\ & \ge \sum_{i \in \text{Happy} \cap \text{OPT}} (1 - p_{b_i} - \varepsilon) \\ & = |\text{Happy} \cap \text{OPT}| \cdot (1 - \varepsilon) - \sum_{i \in \text{Happy} \cap \text{OPT}} p_{b_i} \\ & \ge (1 - 2 \varepsilon) \mu(G) - \sum_{i \in \text{Happy} \cap \text{OPT}} p_{b_i} \end{aligned}$

where the second inequality holds since $i$ is $\varepsilon$-happy, and the last inequality holds since $|\text{Happy} \cap \text{OPT}|$ is at least $(1 - \varepsilon) \mu(G)$.

On the other hand, we have:

$\begin{aligned} \sum_{i \in L} \text{util}(i) & = \sum_{i \in \text{Happy \&\& }a_i \ne \bot} (1 - p_{a_i}) \\ & \le |M| - \sum_{i \in \text{Happy \&\& }a_i \ne \bot} p_{a_i} \\ & \le |M| - \sum_{j \in R} p_j \end{aligned}$

Thus:

$|M| \ge (1 - 2 \varepsilon) \mu(G) + \sum_{j \in R} p_j - \sum_{i \in \text{Happy} \cap \text{OPT}} p_{b_i} \ge (1 - 2 \varepsilon) \mu(G)$

as desired. $\Box$

Finally we prove that such iteration exists:

Lemma 3.5. There exists an iteration $r \le \lceil 2 / \varepsilon^2 \rceil$ wherein at least $(1 - \varepsilon) \mu(G)$ bidders in $\text{OPT}$ are $\varepsilon$-happy.

Proof. Consider the following two potential functions:

$\Phi_1 = \sum_{j \in R} p_j,\ \Phi_2 = \sum_{i \in L} \min_{j \in \Gamma(i)} p_j$

Since $j \in R$ is allocated iff $p_j > 0$, and $0 \le p_j \le 1$, then we can get that $0 \le \Phi_1, \Phi_2 \le \mu(G)$. And since the prices can only increase, $\Phi_1, \Phi_2$ are all monotone.

Assume that at the beginning of an iteration, there are at least $\varepsilon \mu(G)$ unhappy bidders in $\text{OPT}$. And then for these unhappy bidders, by Fact 3.3, algorithm will create a subgraph $G_r$ and try to find a maximal matching in this subgraph to allocate these bidders.

For each unhappy bidder $i$, after this iteration, there will be two cases: $i$ becomes allocated or still remains unallocated. Each of the former bidders contributes a value $\varepsilon$ of to $\Phi_1$ as $p_{a_i}$ increases $\varepsilon$. And each of the latter bidders contributes a value $\varepsilon$ to $\Phi_2$. This is because the matching is maximal, which implies that: $i$ still remains unallocated iff all of its neighbors becomes allocated, i.e. $\forall j \in \Gamma(i)$, $p_j$ increase $\varepsilon$. Thus $\min\limits_{j \in \Gamma(i)} p_j$ also increases $\varepsilon$.

Thus after this iteration, $\Phi_1 + \Phi_2$ increases $\varepsilon^2 \mu(G)$. Since $0 \le \Phi_1 + \Phi_2 \le 2 \mu(G)$, there will be at least $(1 - \varepsilon) \mu(G)$ happy bidders in $\text{OPT}$ after at most $\lceil 2 / \varepsilon^2 \rceil$ iterations. $\Box$

Application

Notice that each iteration in this algorithm can be easily simulated in $O(1)$ passes in semi-streaming model with memory $O(n)$ words. Thus we get a semi-streaming algorithm for $(1 + \varepsilon)$-approximate maximum matching with pass complexity $O(1 / \varepsilon^2)$.

And for massively parallel computation model, // TODO

Supplement

[DNO14] provides a strategy that every unallocated bidder reports the index of a uniformly at random minimum-price item (as opposed to an arbitrary one), and the items are reallocated arbitrarily among the bidders that reported them, then the entire auction converges in $O(\log n / \varepsilon^2)$ iterations.

Interestingly, the result of [DNO14] can be seen as almost a special case of [ALT21]'s algorithm.

References

[ALT21] Sepehr Assadi, S Cliff Liu, and Robert E Tarjan. An auction algorithm for bipartite matching in streaming and massively parallel computation models. In Symposium on Simplicity in Algorithms (SOSA), pages 165–171. SIAM, 2021.

[DNO14] Shahar Dobzinski, Noam Nisan, and Sigal Oren. Eco
nomic e ciency requires interaction. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31- June 03, 2014, pages 233242, 2014.