2019  OriginalPaper  Buchkapitel
Tipp
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Erschienen in:
Building Bridges II
We study the online bipartite matching problem, introduced by Karp, Vazirani and Vazirani [1990]. For bipartite graphs with matchings of size n, it is known that the Ranking randomized algorithm matches at least \((1  \frac{1}{e})n\) edges in expectation. It is also known that no online algorithm matches more than \((1  \frac{1}{e})n + O(1)\) edges in expectation, when the input is chosen from a certain distribution that we refer to as \(D_n\). This upper bound also applies to fractional matchings. We review the known proofs for this last statement. In passing we observe that the O(1) additive term (in the upper bound for fractional matching) is \(\frac{1}{2}  \frac{1}{2e} + O(\frac{1}{n})\), and that this term is tight: the online algorithm known as Balance indeed produces a fractional matching of this size. We provide a new proof that exactly characterizes the expected cardinality of the (integral) matching produced by Ranking when the input graph comes from the support of \(D_n\). This expectation turns out to be \((1  \frac{1}{e})n + 1  \frac{2}{e} + O(\frac{1}{n!})\), and serves as an upper bound on the performance ratio of any online (integral) matching algorithm.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Anzeige
For completeness, we review here a proof of Theorem
1.1. The proof that we present uses essentially the same mathematical expressions as the proof presented in [
2]. A simple presentation of the proof of [
2] appeared in a blog post of Claire Mathieu [
10] (with further slight simplifications made possible by a comment provided there by Pushkar Tripathi). We shall give an arguably even simpler presentation, due to Eden, Feldman, Fiat and Segal [
3]. The proofs in [
2,
10] make use of linear programming duality. The proof below is based on an economic interpretation, and a proof technique that splits
welfare into the sum of
utility and
revenue. These last two terms turn out to be scaled versions of the dual variables used in [
2,
10], but the proof does not need to make use of LP duality.
(
Theorem
1.1) Fix an arbitrary perfect matching
M in
G. Given a vertex
\(v \in V\), we use
M(
v) to denote the vertex in
U matched with
v under
M.
Recall that
Ranking chooses a random permutation
\(\pi \) over
V. Equivalently, we may assume that every vertex
\(v_i \in V\) chooses independently uniformly at random a real valued weight
\(w_i \in [0,1]\), and then the vertices of
V are sorted in order of increasing weight (lowest weight first). This gives a random permutation
\(\pi \). The same permutation
\(\pi \) is also obtained if each weight
\(w_i\) is replaced by a “price”
\(p_i = e^{w_i  1}\) and vertices are sorted by prices (because
\(e^{x1}\) is a monotonically increasing function in
x). Observe that
\(p_i \in [\frac{1}{e},1]\), though it is not uniformly distributed in that range. The expected price that
Ranking assigns to an item is:
It is convenient to think of the vertices of
U as
buyers and the vertices of
V as
items. Suppose that given
G(
U,
V;
E), each vertex (buyer)
\(u \in U\) desires only items
\(v \in V\) that are neighbors of
u (namely,
u desires
v iff
\((u,v) \in E\)), is willing to pay 1 for any such item, and wishes to buy exactly one item. The seller holding the items is offering to sell each item
\(v_i\) for a price of
\(p_i\). Then given
G, the matching produced by executing the
Ranking algorithm is the same as the one that would be produced in a setting in which each buyer
\(u_j\), upon arrival, buys its cheapest exposed desired item, if there is any. If
\(p_i\) is the price of the purchased item
\(v_i\), then the
revenue that the seller extracts from the sale of
\(v_i\) to
\(u_j\) is
\(r(v_i) = p_i\), whereas the
utility that the buyer extracts is
\(y(u_i) = 1  p_i\). Consequently, the revenue plus utility extracted from a sale is 1, and the total revenue extracted from all sales plus the total utility sum up to exactly the cardinality of the matching.
To lower bound the expected cardinality of the matching, we consider each edge
\((M(v_i),v_i) \in M\) separately, and consider the expectation
\(E[r(v_i) + y(M(v_i))]\), where expectation is taken over the choice of
\(\pi \). Using the linearity of the expectation, we will have that
\(\rho _n(Ranking,G) = \sum _{v_i \in V} E[r(v_i) + y(M(v_i))]\).
\(\square \)
For every
\(v_i \in V\) it holds that
\(E[r(v_i) + y(M(v_i))] \ge 1  \frac{1}{e}\). Moreover, this holds even if expectation is taken only over the choice of random weight
\(w_i\) (and hence of random price
\(p_i\)) of item
\(v_i\), without need to consider other aspects of the random permutation
\(\pi \).
\(\square \)
Fix an arbitrary graph
\(G(U,V;E)\in G_n\), an arbitrary perfect matching
M, and arbitrary prices
\(p_j \in [\frac{1}{e},1]\) for all items
\(v_j \not = v_i\). The price
\(p_i\) for item
\(v_i\) is set at random. Let
\(M'\) denote the greedy matching produced by this realization of the
Ranking algorithm (where each buyer upon its arrival is matched to the exposed vertex of lowest price among its neighbors, if there is any). Suppose as a thought experiment that item
\(v_i\) is removed from
V, and consider the greedy matching
\(M'_{i}\) that would have been produced in this setting. Let
p denote the price of the item in
V matched to
\(M(v_i)\) under
\(M'_{i}\), and set
\(p=1\) if
\(M(v_i)\) is left unmatched under
\(M'_{i}\). Now we make two easy claims.
If
\(p_i < p\),
then
\(v_i\)
is matched in
\(M'\). This follows because at the time that
\(M(v_i)\) arrived, either
\(v_i\) was already matched (as desired), or it was available for matching with
\(M(v_i)\) and preferable (in terms of price) over all other items that
\(M(v_i)\) desires (as all have price at least
\(p > p_i\)).
The utility of
\(M(v_i)\)
in
\(M'\)
satisfies
\(y(M(v_i)) \ge 1p\). This follows because under
\(M'_{i}\) the utility of
\(M(v_i)\) is
\(1  p\), and under the greedy algorithm considered, the introduction of an additional item (the item
\(v_i\) when considering
\(M'\)) cannot decrease the utility of any agent. (At every step of the arrival process, the set of exposed vertices under
\(M'\) contains the set of exposed vertices under
\(M'_{i}\), and one more vertex.)
Using the above two claims and taking
z to be the value satisfying
\(p = e^{z1}\), we have:
This completes the proof of Lemma
4.1.
\(\square \)
Using the linearity of the expectation, we have that
This completes the proof of Theorem
1.1.
\(\square \)
One can adapt the proof presented above to the special case in which the input graph is
MonotoneG (or more generally, comes from the distribution
\(D_n\)). In this case one can upper bound the slackness involved in the proof of Theorem
1.1, and infer the following theorem.
\(\square \)
For every
n it holds that
\(\rho _n(Ranking,MonotoneG) \le (1  \frac{1}{e})n + \frac{1}{e}\).
Recall the two properties mentioned in the beginning of the proof of Theorem
3.1. Recall also that the analysis of
Ranking in the proof of Theorem
1.1 (within Lemma
4.1) involved the matching
\(M'\) and other matchings
\(M'_{i}\), and two claims. Let us analyse the slackness involved in these claims when the input is the monotone graph. The claims are restated with
\(M(v_i)\) replaced by
\(u_i\), because for the monotone graph
\(M(v_i) = u_i\).
The first claim stated that
if
\(p_i < p\),
then
\(v_i\)
is matched in
\(M'\). When the input is the monotone graph, then a converse also holds: if
\(p_i > p\), then
\(v_i\) is not matched in
\(M'\). This follows because up to the time that
\(u_i\) arrives and is matched, only vertices of
V priced at most
p are matched, and thereafter, no other vertex in
U desires
\(v_i\). The event that
\(p_i = p\) has probability 0. Hence there is no slackness involved in the first claim—it is an
if and only if statement.
The second claim stated that
the utility of
\(u_i\)
in
\(M'\)
is
\(y(u_i) \ge 1p\). This inequality is not tight. Rather, the utility of
\(u_i\) in
\(M'_{i}\) is
\(1p\), and
\(y(u_i)\) is not smaller. Let us quantify the slackness involved in this inequality by introducing slackness variables
s(
u). For a vertex
\(u \in U\) we shall use the notation
y(
u) to denote the utility of
u under
Ranking, and
\(y_{v}(u)\) for the utility of
u when vertex
\(v \in V\) is removed. The
slackness
\(s(u_i)\) of vertex
\(u_i\) is defined as
\(s(u_i) = y(u_i)  y_{v_i}(u_i)\).
\(\square \)
For the monotone graph and an arbitrary vertex
\(u_j \in U\), the expected utility of
\(u_j\) (expectation taken over choices of
\(w_i\) for all
\(1 \le i \le n\) by the
Ranking algorithm) is identical in the following two settings: when
\(v_j\) is removed, and when
\(v_n\) is removed. Namely,
\(E[y_{v_j}(u_j)] = E[y_{v_n}(u_j)]\).
\(\square \)
Both
\(v_j\) and
\(v_n\) are neighbors of all vertices
\(u_k\) arriving up to
\(u_j\) (for
\(1 \le k \le j\)). Hence whichever of the two vertices,
\(v_j\) or
\(v_n\), is removed, the distributions of the outcomes of
Ranking on the first
j arriving vertices (including
\(u_j\)) are the same.
\(\square \)
As a consequence of Lemma
4.3 we deduce that for the monotone graph, the expected slackness of every vertex
\(u \in U\) satisfies
\(E[s(u)] = E[y(u)]  E[y_{v_n}(u)]\).
For the monotone graph and arbitrary setting of prices for the items (as chosen at random by
Ranking),
\(\sum _{u\in U} s(u) \le 1  p_{n}\). Consequently,
\(\sum _{u\in U} E[s(u)] \le \frac{1}{e}\), where expectation is taken over choice of weights
\(w_i\) for vertices in
V.
\(\square \)
Fix the prices
\(p_i\) (hence
\(\pi \)). Let
\(u_1, \ldots , u_k\) be the vertices of
U matched under
Ranking, and let
\(m(u_1), \ldots , m(u_k)\) be the vertices in
V to which they are matched. Observe that the prices
\(p(m(u_i))\) (where
\(1 \le i \le k\)) of these vertices form a monotonically increasing sequence. Necessarily,
\(v_{n}\) is one of the matched vertices, because it is a neighbor of all vertices in
U. Let
j be such that
\(v_{n} = m(u_j)\).
Consider now what happens when
\(v_{n}\) is removed. The vertices
\(u_1, \ldots , u_{j1}\) are matched to
\(m(u_1), \ldots , m(u_j1)\) as before. As to the vertices
\(u_j, \ldots , u_{k1}\), they can be matched to
\(m(u_{j+1}), \ldots , m(u_k)\), hence the algorithm will match them to vertices of no higher price. Specifically, for every
i in the range
\(j \le i \le k1\), vertex
\(u_i\) will be matched either to
\(m(u_{i+1})\) or to an earlier vertex, though not earlier than
\(m(u_i)\). The vertex
\(u_k\) may either be matched or be left unmatched. For simplicity of notation, we say that
\(u_k\) is matched to either
\(m(u_{k+1})\) or to an earlier vertex, where
\(m(u_{k+1})\) is an auxiliary vertex of price 1 than indicates that
\(u_{k}\) is left unmatched.
Note that:
and that:
Hence we have that:
Finally, noting that
\(p(m(u_{k+1})) \le 1\) and that
\(E[p(v_{n})] = 1  \frac{1}{e}\) (see Eq. (
5)), the lemma is proved.
\(\square \)
As in the proof of Theorem
1.1 we have:
Using the linearity of the expectation and Lemma
4.4 we have that:
This completes the proof of Theorem
4.2.
\(\square \)
$$\begin{aligned} E[p_i] = \int _0^1 e^{w_i  1} dw_i = \frac{1}{e}(e  1) = 1  \frac{1}{e} \;. \end{aligned}$$
(5)
1.
If
\(p_i < p\),
then
\(v_i\)
is matched in
\(M'\). This follows because at the time that
\(M(v_i)\) arrived, either
\(v_i\) was already matched (as desired), or it was available for matching with
\(M(v_i)\) and preferable (in terms of price) over all other items that
\(M(v_i)\) desires (as all have price at least
\(p > p_i\)).
2.
The utility of
\(M(v_i)\)
in
\(M'\)
satisfies
\(y(M(v_i)) \ge 1p\). This follows because under
\(M'_{i}\) the utility of
\(M(v_i)\) is
\(1  p\), and under the greedy algorithm considered, the introduction of an additional item (the item
\(v_i\) when considering
\(M'\)) cannot decrease the utility of any agent. (At every step of the arrival process, the set of exposed vertices under
\(M'\) contains the set of exposed vertices under
\(M'_{i}\), and one more vertex.)
$$\begin{aligned} E[y(M(v_i)) + r(v_i)]\ge & {} 1  p + Pr[p_i < p]p_i= 1  e^{z1} + \int _{w_i=0}^{z} e^{w_i1} dw_i \\= & {} 1  \frac{e^z}{e} + \frac{e^z  1}{e} = 1  \frac{1}{e} \;. \end{aligned}$$
$$\rho _n(Ranking,G) = \sum _{v_i \in V} E[r(v_i) + y(M(v_i))] \ge (1  \frac{1}{e})n \;.$$
$$\sum _{u \in U} y(u) = \sum _{i=1}^k y(u_i) = k  \sum _{i=1}^k p(m(u_i)) \;,$$
$$\sum _{u \in U} y_{v_{n}}(u) = \sum _{i=1}^k y_{v_{n}}(u_i) \ge k  \sum _{i=1}^{j1} p(m(u_i))  \sum _{i=j+1}^{k+1} p(m(u_i)) \;.$$
$$\sum _{u\in U} s(u) = \sum _{u \in U} y(u)  \sum _{u \in U} y_{v_{n}}(u) \le p(m(u_{k+1}))  p(v_{n}) \;.$$
$$E[y(u_i) + r(v_i)] = 1  p + s(u_i) + Pr[p_i < p]p_i = 1  \frac{1}{e} + s(u_i) \;.$$
$$\begin{aligned} \rho _n(Ranking,MonotoneG)= & {} \sum _{v_i \in V} E[r(v_i) + y(u_i)] \\= & {} (1  \frac{1}{e})n + \sum _{u \in U} E[s(u)] \le (1  \frac{1}{e})n + \frac{1}{e} \;. \end{aligned}$$
1.
Benjamin E. Birnbaum, Claire Mathieu: Online bipartite matching made simple. SIGACT News
39(1), 80–87 (2008)
CrossRef
2.
Nikhil R. Devanur, Kamal Jain, Robert D Kleinberg: Randomized PrimalDual analysis of RANKING for Online BiPartite Matching. SODA 2013: 101–107
3.
Alon Eden, Michal Feldman, Amos Fiat, Kineret Segal: An EconomicBased Analysis of RANKING for Online Bipartite Matching. Manuscripy, 2018.
http://cs.tau.ac.il/~mfeldman/papers/EFFS18.pdf
4.
Gagan Goel, Aranyak Mehta: Online budgeted matching in random input models with applications to Adwords. SODA 2008: 982–991.
5.
Bala Kalyanasundaram, Kirk Pruhs: An optimal deterministic algorithm for online bmatching. Theor. Comput. Sci. 233(12): 319–325 (2000).
MathSciNetCrossRef
6.
Anna Karlin. Online bipartite matching, lecture notes in course on Randomized Algorithms and Probabilistic Analysis, scribes Alex Polozav and Daryl Hansen, Spring 2013.
https://courses.cs.washington.edu/courses/cse525/13sp/scribe/lec6.pdf
7.
Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani: An Optimal Algorithm for Online Bipartite Matching. STOC 1990: 352–358.
8.
Robert D. Kleinberg. Online bipartite matching algorithms, lecture note in course on Analysis of Algorithms, Fall 2012.
http://www.cs.cornell.edu/courses/cs6820/2012fa/
9.
L. Lovasz, M. D. Plummer. Matching Theory. Elsevier 1986.
10.
Claire Mathieu. A CS’s Professor Blog: A primaldual analysis of the Ranking algorithm. June 25, 2011.
http://teachingintrotocs.blogspot.co.il/2011/06/primaldualanalysisofranking.html
11.
Aranyak Mehta. Online matching and ad allocation.
Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013.
MathSciNetCrossRef
12.
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani: AdWords and generalized online matching. J. ACM 54(5): 22 (2007).
MathSciNetCrossRef
13.
N. J. A. Sloane, editor, The OnLine Encyclopedia of Integer Sequences, published electronically at
https://oeis.org.
 Titel
 Tighter Bounds for Online Bipartite Matching
 DOI
 https://doi.org/10.1007/9783662592045_7
 Autor:

Uriel Feige
 Verlag
 Springer Berlin Heidelberg
 Sequenznummer
 7