Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 − 1/e) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam [11] to 0.705; and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet and Lu [12] to 0.7299. We also consider two extensions, one is "known I.I.D." with non-integral arrival rate and stochastic rewards; the other is "known I.I.D." b-matching with non-integral arrival rate and stochastic rewards. We present a simple non-adaptive algorithm which works well simultaneously on the two extensions. One of the key ingredients of our improvement is the following (offline) approach to bipartitematching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution f; however, these give us less control over the structure of f. We next remove all these additional constraints and randomly move from f to a feasible point on the matching polytope with all coordinates being from the set {0, 1/k, 2/k, . . . , 1} for a chosen integer k. The structure of this solution is inspired by Jaillet and Lu (Mathematics of Operations Research, 2013) and is a tractable structure for algorithm design and analysis. The appropriate random move preserves many of the removed constraints (approximately [exactly] with high probability [in expectation]). This underlies some of our improvements, and, we hope, could be of independent interest.  ACM Subject Classification F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COM-PLEXITY Keywords and phrases Applications to Internet advertising have driven the study of online matching problems in recent years [19]. In these problems, we consider a bipartite graph G = (U, V, E) in which the set U is available offline while the vertices in V arrive online. Whenever some vertex v arrives, it must be matched immediately to at most one vertex in U . Each offline vertex u can be matched to at most one v or in the b-matching generalization, at most b vertices in V . In the context of Internet advertising, U is the set of advertisers, V is a set of impressions, and the edges E define the impressions that interest a particular advertiser. When v arrives, we must choose an available advertiser (if any) to match with it. Initially, we consider the case where v ∈ V can be matched at most once. We later relax this condition to it being matched up to b times. Since advertising forms the key source of revenue for many large Internet companies, finding good matching algorithms and obtaining even small performance gains can have high impact. In the stochastic known I.I.D. model of arrival, we are given the bipartite graph in advance and each arriving vertex v is drawn with replacement from a known distribution on the vertices in V . This captures the fact that we often have background data about the impressions and can predict the frequency with which each type of impression will arrive. Edge-weighted matching [8] is a general model in the context of advertising: every advertiser gains a given revenue for being matched to a particular type of impression. Here, a type of impression refers to a class of users (e.g., a demographic group) who are interested in the same subset of advertisements. A special case of this model is vertex-weighted matching [1], where weights are associated only with the advertisers. In other words, a given advertiser has the same revenue generated for matching any of the user types interested in it. In some modern business models, revenue is not generated upon matching advertisements, but only when a user clicks on the advertisement: this is the pay-per-click model. From background data, one can assign the probability of a particular advertisement being clicked by a type of user. Works including [20] , [21] capture this notion by assigning a probability to each edge. One unifying theme in most of our approaches is to use an LP benchmark with additional valid constraints that hold for the respective stochastic-arrival models, combined with some form of dependent rounding. For readers not familiar with these problems, they are encouraged to first read parts of section 2 for formal definitions before getting into the related work. The study of online matching began with the seminal work of Karp, Vazirani, Vazirani [14], where they gave an optimal online algorithm for a version of the unweighted bipartite matching problem in which vertices arrive in adversarial order. Following that, a series of works have studied various related models. The book by Mehta [19] gives a detailed overview. The vertex-weighted version of this problem was introduced by Aggarwal, Goel and Karande [1], where they give an optimal 1 − 1 e ratio for the adversarial arrival model. The edge-weighted setting has been studied in the adversarial model by Feldman, Korula, Mirrokni and Muthukrishnan [8], where they consider an additional relaxation of "free-disposal". Beyond the adversarial model, these problems are studied under the name stochastic matching, where the online vertices either arrive in random order or are drawn I.I.D. from a known B. Brubach, K. A. Sankararaman, A. Srinivasan and P. Xu 3 distribution. The works [5, 15, 16, 17] among others, study the random arrival order model; papers including [4, 6, 9, 11, 12, 18] [9] who were the first to beat 1 − 1/e with a competitive ratio of 0.67 for the unweighted problem. This was improved by Manshadi, Gharan, and Saberi [18] to 0.705 with an adaptive algorithm. In addition, they showed that even in the unweighted variant with integral arrival rates, no algorithm can achieve a ratio better than 1 − e −2 ≈ 0.86. Finally, Jaillet and Lu [12] presented an adaptive algorithm which used a clever LP to achieve 0.725 and 1 − 2e −2 ≈ 0.729 for the vertex-weighted and unweighted problems, respectively. Related Work in the Edge-Weighted Setting: For this model, Haeupler, Mirrokni, Zadimoghaddam [11] were the first to beat 1 − 1/e by achieving a competitive ratio of 0.667. They use a discounted LP with tighter constraints than the basic matching LP (a similar LP can be seen in 2.1) and they employ the power of two choices by constructing two matchings offline to guide their online algorithm. In the model of b-matching, we assume each vertex u has a uniform capacity of b, where b is a parameter which is generally a large integral value. The model of unweighted b-matching can be viewed as a special case of Adwords or Display Ads. There is extensive literature for Adwords or Display Ads under various settings (see the book by Mehta [19]). In particular, [13] shows that their algorithm BALANCE is optimal for online b-matching under the adversarial model, which achieves a ratio of 1 − 1 (1+1/b) b . In this paper, we consider edge-weighted b-matching with stochastic rewards under the known I.I.D. model with arbitrary arrival rates. To the best of our knowledge, we are the first to consider this very general model. Devanur et al [7] gave an algorithm which achieves a ratio of 1 − 1/ √ 2πk for the Adwords problem in the Unknown I.I.D. arrival model with knowledge of the optimal budget utilization and when the bid to budget ratios are at most 1/k. Notice that even the problem of general edge-weighted b-matching with deterministic rewards cannot be captured in the Adwords model. Alaei et al [2] consider the Prophet-Inequality Matching problem, in which v arrives from a distinct (known) distribution D t , in each round t. They gave a 1 − 1/ √ k + 3 competitive algorithm, where k is the minimum capacity of u. They assume deterministic rewards however, and it is non-trivial to extend their result to the stochastic reward setting. In this paper, we present a very simple algorithm which achieves a ratio of 2 /3 ) for any given > 0. It is worthwhile to see that our algorithm (10) can be trivially extended to the case where each vertex u has a distinct capacity b u . The value of b in the final ratio would be replaced by min u∈U b u . In the Unweighted Online Known I.I.D. Stochastic Bipartite Matching problem, we are given a bipartite graph G = (U, V, E). The set U is available offline while the vertices v arrive 4 New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching online and are drawn with replacement from an I.I.D. distribution on V . For each v ∈ V , we are given an arrival rate r v , which is the expected number of times v will arrive. With the exception of Sections 5 and 6, this paper will focus on the integral-arrival-rates setting where all r v ∈ Z + . As described in [11], WLOG we can assume in this setting that ∀v ∈ V, r v = 1. Let n = v∈V r v be the expected number of vertices arriving during the online phase. In the vertex-weighted variant, every vertex u ∈ U has a weight w u and we seek a maximum weight matching. In the edge-weighted variant, every edge e ∈ E has a weight w e and we seek a maximum weight matching. In the stochastic rewards variant 1 , additionally, each edge has a probability p e and we seek to maximize the expected weight of the matching. In the b-matching model, every vertex in U can be matched upto b times. Throughout, we will use "WS" to refer to the worst case for various algorithms. Asymptotic assumption and notation: We will always assume n is large and analyze algorithms as n goes to infinity: e.g., if n , we will just write this as "x ≤ 1 − 1/e 2 " instead of the more-accurate "x ≤ 1 − 1/e 2 + o(1)". These suppressed o(1) terms will subtract at most o(1) from our competitive ratios. Another fact to note is that the competitive ratio is defined slightly different than usual, for this set of problems (Similar to notation used in [19]). In particular, it is defined as . Algorithms can be adaptive or non-adaptive. When v arrives, an adaptive algorithm can check which neighbors are still available to be matched, but a non-adaptive algorithm cannot. We will use the following LP to upper bound the optimal offline solution and guide our algorithm. We will first show an LP for the unweighted variant, then describe changes for the vertex-weighted and edge-weighted settings. As usual, we have a variable f e for each edge. Let ∂(w) be the set of edges adjacent to a vertex w ∈ U ∪ V and let f w = e∈∂(w) f e . maximize e∈E f e (2.1) subject to Variants: The objective function is: maximize u∈U e∈∂(u) f e w u in the vertex-weighted variant and maximize e∈E f e w e in the edge-weighted variant. Constraint 2.2 is the matching constraint for vertices in U . Constraint 2.3 is valid because each vertex in V has an arrival rate of 1. Constraint 2.4 is used in [18] and [11]. It captures the fact that the expected number of matches for any edge is at most 1 − 1/e. This is 1 The edge realization process is independent from one another. At each step, the algorithm "probes" the edge. With probability pe the edge exists and with remaining probability it doesn't. Once realization of an edge is determined, it doesn't change for the rest of the algorithm valid for large n because the probability that a given vertex doesn't arrive after n rounds is 1/e. Constraint 2.5 is similar to the previous one, but for pairs of edges. For any two neighbors of a given u ∈ U , the probability that neither of them arrive is 1/e 2 . Therefore, the sum of variables for any two distinct edges in ∂(u) cannot exceed 1 − 1/e 2 . Notice that constraints 2.4 and 2.5 reduces the gap between the optimal LP solution and the performance of the optimal online algorithm. In fact, without constraint 2.4, we cannot in general achieve a competitive ratio better than 1 − 1/e. A key challenge encountered by [12] was that their special LP could lead to length four cycles of type C 1 shown in Figure 1 . In fact, they used this cycle to show that no algorithm could perform better than 1 − 2/e 2 ≈ 0.7293 using their LP. They mentioned that tighter LP constraints such as 2.4 and 2.5 in the LP from Section 2 could avoid this bottleneck, but they did not propose a technique to use them. Note that the {0, 1/3, 2/3} solution produced by their LP was an essential component of their Random List algorithm. We show a randomized rounding algorithm to construct a similar, simplified {0, 1/3, 2/3} vector from the solution of a stricter benchmark LP. This allows for the inclusion of additional constraints, most importantly constraint 2.5. Using this rounding algorithm combined with tighter constraints, we will upper bound the probability of a vertex appearing in the cycle C 1 from Figure 1 at 2−3/e ≈ 0.89. (See Lemma 8) Additionally, we show how to deterministically break all other length four cycles which are not of type C 1 without creating any new cycles of type C 1 . Finally, we describe an algorithm which utilizes these techniques to improve previous results in both the vertex-weighted and unweighted settings. For this algorithm, we first solve the LP in Section 2 on the input graph. In Section 4, we show how to use the technique in sub-section 2.6 to obtain a sparse fractional vector. We then present a randomized online algorithm (similar to the one in [12]) which uses the sparse fractional vector as a guide to achieve a competitive ratio of 0.7299. Previously, there was gap between the best unweighted algorithm with a ratio of 1 − 2e −2 due to [12] and the negative result of 1 − e −2 due to [18]. We take a step towards closing that gap by showing that an algorithm can achieve 0.7299 > 1 − 2e −2 for both the unweighted and vertex-weighted variants with integral arrival rates. A challenge that arises in applying the power of two choices to this setting is when the same edge (u, v) is included in both matchings M 1 and M 2 . In this case, the copy of (u, v)  New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching can offer no benefit and a second arrival of v is wasted. To use an example from related work, Haeupler et al. [11] choose two matchings in the following way. M 1 is attained by solving an LP with constraints 2.2, 2.3 and 2.4 and rounding to an integral solution. M 2 is constructed by finding a maximum weight matching and removing any edges which have already been included in M 1 . A key element of their proof is showing that the probability of an edge being removed from M 2 is at most 1 − 1/e ≈ 0.63. The approach in this paper is to construct two or three matchings together in a correlated manner to reduce the probability that some edge is included in all matchings. We will show a general technique to construct an ordered set of k matchings where k is an easily adjustable parameter. For k = 2, we show that the probability of an edge appearing in both M 1 and M 2 is at most 1 − 2/e ≈ 0.26. For the algorithms presented, we first solve an LP on the input graph. We then round the LP solution vector to a sparse integral vector and use this vector to construct a randomly ordered set of matchings which will guide our algorithm during the online phase. We begin Section 3 with a simple warm-up algorithm which uses a set of two matchings as a guide to achieve a 0.688 competitive ratio, improving the best known result for this problem. We follow it up with a slight variation that improves the ratio to 0.7 and a more complex 0.705-competitive algorithm which relies on a convex combination of a 3-matching algorithm and a separate pseudo-matching algorithm. This algorithm is presented in Section 5. We believe the known I.I.D. model with stochastic rewards is an interesting new direction motivated by the work of [20] and [21] in the adversarial model. We introduce a new, more general LP specifically for this setting and show that a simple algorithm using the LP solution directly can achieve a competitive ratio of 1 − 1/e. In [21] , it is shown that no randomized algorithm can achieve a ratio better than 0.62 < 1 − 1/e in the adversarial model. Hence, achieving a 1 − 1/e for the i.i.d. model shows that this lower bound does not extend to this model. In Section 6, we extend this simple algorithm 2 to the b-matching generalization of this problem where each offline vertex u can match with up to b arriving vertices. We show that our algorithm achieves a competitive ratio of at least 2 /3 ) for any given > 0. Note that this result makes progress on Open Question 14 in the online matching and ad allocation survey [19] which asks about stochastic rewards in non-adversarial models. Theorem 1. For vertex-weighted online stochastic matching with integral arrival rates, online algorithm VW achieves a competitive ratio of at least 0.7299. 2 Recently, we have come to know that the result in Section 6 can be obtained as a special case of [3]. Our approach gives an alternative, and a simpler algorithm for this special case.  2 /3 ) for any given > 0. For the algorithms presented, we will first solve the benchmark LP in sub-section 2.1 for the input instance to get a fractional solution vector f. We then round f to an integral solution F using a two step process we call DR [f, k]. The first step is to multiply f by k. The second step is to apply the dependent rounding techniques of Gandhi, Khuller, Parthasarathy and Srinivasan [10] to this new vector. In this paper, we will always choose k to be 2 or 3. This will help us handle the fact that a vertex in V may appear more than once, but probably not more than two or three times. While dependent rounding is typically applied to values between 0 and 1, the useful properties extend naturally to our case in which kf e may be greater than 1 for some edge e. To understand this process, it is easiest to imagine splitting each kf e into two edges with the integer value f e = kf e and fractional value f e = kf e − kf e . The former will remain unchanged by the dependent rounding since it is already an integer while the latter will be rounded to 1 with probability f e and 0 otherwise. Our final value F e would be the sum of those two rounded values. The two properties of dependent rounding we will use are:  For any vertex w ∈ U ∪ V , let its fractional degree kf w be e∈∂(w) kf e and integral degree be the random variable F w = e∈∂(w) F e . Then F w ∈ { kf w , kf w }. Edge-weighted matching with integral arrival rates 3.1 A simple 0.688-competitive algorithm As a warm-up, we will describe a simple algorithm which achieves a competitive ratio of 0.688 and introduces key ideas in our approach. We begin by solving the LP in sub-section 2.1 to get a fractional solution vector f and applying DR[f, 2] as described in Subsection 2.6 to get an integral vector F. We construct a bipartite graph G F with F e copies of each edge e. Note that G F will have max degree 2 since for all w ∈ U ∪ V , F w ≤ 2f w ≤ 2 and therefore we can decompose it into two matchings using Hall's Theorem.  when v arrives for the second time, try to assign v to some u 2 if (u 2 , v) ∈ M 2 . 6 When a vertex v arrives for the third time or more, do nothing in that step. We will show that EW 0 (Algorithm 1) achieves a competitive ratio of 0.688. Let [M 1 , M 2 ] be our randomly ordered pair of matchings. Note that there might exist some edge e which appears in both matchings if f e > 1/2. Therefore, we consider three types of edges. We say an edge e is of type ψ 1 , denoted by e ∈ ψ 1 , iff e appears only in M 1 . Similarly e ∈ ψ 2 , iff e appears only in M 2 and e ∈ ψ b , iff e appears in both M 1 and M 2 . Let P 1 , P 2 , P b be the probabilities of getting matched for e ∈ ψ 1 , e ∈ ψ 2 , and e ∈ ψ b respectively. According to the result in Haeupler et al. [11], the respective values are shown as follows. there can be at most one copy of e in G F and the probability of including e in G F is 2f e . Since an edge in G F can appear in either M 1 or M 2 with equal probability 1/2, we have Pr[e ∈ ψ 1 ] = Pr[e ∈ ψ 2 ] = f e . Thus, the ratio is (f e P 1 + f e P 2 )/f e = P 1 + P 2 = 0.729. (1/2)(1−(2f e −1)) = 1−f e . Thus, the ratio is ((1−f e )(P 1 +P 2 )+(2f e −1)P b )/f e ≥ 0.688, where the WS is for an edge e with f e = 1 − 1/e. 2. In this section, we describe an improvement upon the previous warm-up algorithm to get a competitive ratio of 0.7. We start by making an observation about the performance of the warm-up algorithm. After solving the LP, let edges with f e > 1/2 be called large and edges with f e ≤ 1/2 be called small. Let L and S, be the sets of large and small edges, respectively. Notice that in the previous analysis, small edges achieved a much higher competitive ratio of 0.729 versus 0.688 for large edges. This is primarily due to the fact that we may get two copies of a large edge in G F . In this case, the copy in M 1 has a better chance of being matched, since there is no edge which can block it, but the copy that is in M 2 has no chance of being matched. To correct this imbalance, we make an additional modification to the f e values before applying DR [f, k]. The rest of the algorithm is exactly the same. Let η be a parameter to be optimized later. For all large edges ∈ L such that f > 1/2, we set f = f + η. For all small edges s ∈ S which are adjacent to some large edge, let ∈ L be the largest edge adjacent to s such that f > 1/2. Note that it is possible for e to have two large neighbors, but we only care about the largest one. We set f s = f s In other words, we increase the values of large edges while ensuring that for all w ∈ U ∪ V , f w ≤ 1 by reducing the values of neighboring small edges proportional to their original values. Note that it is not possible for two large edges to be adjacent since they must both have f e > 1/2. For all other small edges which are not adjacent to any large edges, we leave their values unchanged. We then apply DR[f, 2] to this new vector, multiplying by 2 and applying dependent rounding as before. We can now prove Theorem 2. Proof. As in the warm-up analysis, we'll consider large and small edges separately Here we have two cases Case 1: s is not adjacent to any large edges. In this case, the analysis is the same as the warm-up algorithm and we still get a 0.729 competitive ratio for these edges. Case 2: s is adjacent to some large edge . For this case, let f be the value of the largest neighboring edge in the original LP solution. Then s achieves a ratio of New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching Note that for f ∈ [0, 1) this is a decreasing function with respect to f . So the worst case is f = 1 − 1/e and we have a ratio of 1 − (1 − 1/e + η) 1 − (1 − 1/e) (0.1484 + 0.5803) = 1/e − η 1/e (0.1484 + 0.5803) e : Here, the ratio is ((1 − (f + η))(P 1 + P 2 ) + (2(f + η) − 1)P b )/f , where the WS is for an edge e with f = 1 − 1/e since this is a decreasing function with respect to f . Choosing the optimal value of η = 0.0142, yields an overall competitive ratio of 0.7 for this new algorithm. In the next few sections, we will describe our final algorithm, with all the attenuation factors. To keep it modular we give the following guide to the reader. 3.3.1 describes the main algorithm which internally invokes two algorithms EW 1 and EW 2 which are described in sections 3.3.2 and 3.3.3 respectively. Theorem 2 proves the final competitive ratio. This proof depends on the performance guarantees of EW 1 and EW 2 , which are given by Lemmas 6 and 7 respectively. Proof of Lemma 6 depends on claims 15, 16 and 17 (Found in the Appendix). Each of those claims is a careful case-by-case analysis. Intuitively, 15 refers to the case where u has one large edge and one small edge(here analysis is for the large edge), 16 refers to the case where u is incident to three small edges and 17 refers to the case where u is incident to a small edge and large edge(here the analysis is for the small edge). Proof of Lemma 7 depends on claims 18 and 19 (Found in the Appendix). Again, both of those claims are proved by a careful case-by-case analysis. Since there are many cases, we have given a diagram of the cases when we prove them. In this section, we will describe an algorithm EW (Algorithm 2), that achieves a competitive ratio of 0.705. The algorithm first solves the benchmark LP in sub-section 2.1 and obtains a fractional optimal solution f. By invoking DR[f, 3], it obtains a random integral solution F. Notice that from LP constraint 2.4 we see f e ≤ 1 − 1/e ≤ 2/3. Therefore after DR[f, 3], each F e ∈ {0, 1, 2}. Consider the graph G F where each edge e is associated with the value of F e . We say an edge e is large if F e = 2 and small if F e = 1 (note that this differs from the definition of large and small in the previous sub-section). We design two non-adaptive algorithms, denoted by EW 1 and EW 2 , which take the sparse graph G F as input. The difference between the two algorithms EW 1 and EW 2 is that EW 1 favors the small edges while EW 2 favors the large edges. The final algorithm is to take a convex combination of EW 1 and EW 2 i.e. run EW 1 with probability q and EW 2 with probability 1 − q. B. Brubach, K. A. Sankararaman, A. Srinivasan and P. Xu 11 1 Solve the benchmark LP in sub-section 2.1 for the input. Let f be the optimal solution vector. 2 Invoke DR[f, 3] to obtain the vector F. 3 Independently run EW 1 and EW 2 with probabilities q and 1 − q respectively on G F . The details of algorithm EW 1 and EW 2 and the proof of Theorem 2 are presented in the following sections. In this section, we describe the randomized algorithm EW 1 (Algorithm 3). Suppose we view the graph of G F in another way where each edge has F e copies. Let PM [F, 3] refer to the process of constructing the graph G F with F e copies of each edge, decomposing it into three matchings, and randomly permuting the matchings. EW 1 first invokes PM[F, 3] to obtain a random ordered triple of matchings, say [M 1 , M 2 , M 3 ]. Notice that from the LP constraint 2.4 and the properties of DR[f, 3] and PM [F, 3], an edge will appear in at most two of the three matchings. For a small edge e = (u, v) in G F , we say e is of type Γ 1 if u has two other neighbors v 1 and v 2 in G F with F (u,v1) = F (u,v2) =1. We say e is of type Γ 2 if u has exactly one other neighbor v 1 with F (u,v1) = 2. WLOG we can assume that for every u, F u = e∈∂(u) F e = 3; otherwise, we can add a dummy node v to the neighborhood of u. Note, we use the terminology, assign v to u to denote that edge (u, v) is matched by the algorithm if u is not matched until that step. 1 Invoke PM[F, 3] to obtain a random ordered triple matchings, say [M 1 , M 2 , M 3 ]. 2 When a vertex v comes for the first time, assign v to some u 1 with (u 1 , v) ∈ M 1 . 3 When v comes for the second time, assign v to some u 2 with (u 2 , v) ∈ M 2 . 4 When v comes for the third time, if e is either a large edge or a small edge of type Γ 1 then assign v to some u 3 with e = (u 3 , v) ∈ M 3 . However, if e is a small edge of type Γ 2 then with probability h, assign v to some u 3 with e = (u 3 , v) ∈ M 3 ; otherwise, do nothing. 5 When v comes for the fourth or more time, do nothing in that step. Here, h is a parameter we will fix at the end of analysis. Let R[EW 1 , 1/3] and R[EW 1 , 2/3] be the competitive ratio for a small edge and large edge respectively. Proof. In case of the large edge e, we divide the analysis into three cases where each case corresponds to e being in one of the three matchings. And we combine these conditional probabilities using Bayes' theorem to get the final competitive ratio for e. For each of the two types of small edges, we similarly condition them based on the matching they can appear 12 New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching in, and combine them using Bayes' theorem. Complete proof can be found in section A.1.1 of Appendix. EW 2 (Algorithm 5) is a non-adaptive algorithm which takes G F as input and performs well on the large edges. Recall that the previous algorithm, EW 1 , first invokes PM[F, 3] to obtain a random ordered triple of matchings. In contrast, EW 2 will invoke a routine, denoted by PM * [F, 2] (Algorithm 4), to generate a (random ordered) pair of pseudo-matchings from F. Recall that F is an integral solution vector where ∀ e F e ∈ {0, 1, 2}. WLOG, we can assume that F v = 1 for every v in G F . Take a random permutation of ∂(v), say (π 1 , π 2 , π 3 ) ∈ Π(∂(v)). Add π 1 to M 1 with probability y 1 and π 2 to M 2 with probability y 2 . Here 0 ≤ y 1 , y 2 ≤ 1 are parameters which will be fixed after the analysis. Algorithm 5 describes EW 2 . Proof. We analyze this on a case-by-case basis by considering the local neighborhood of the edge. A large edge can have two possible cases in its neighborhood, while a small edge can have eight possible cases. Choosing the worst case among the two for large edge and the worst case among the eight for the small edge, we prove the claim. Complete details of the proof can be found in section A.1.2 of Appendix. In this section, we will prove theorem 2. Proof. Let (a 1 , b 1 ) be the competitive ratios achieved by EW 1 for large and small edges, respectively. Similarly, let (a 2 , b 2 ) denote the same for EW 2 . We will have the following two cases.  The competitive ratio of the convex combination is maximized at q = 0.149251 with a value of 0.70546. In this section, we will consider vertex-weighted online stochastic matching on a bipartite graph G under known I.I.D. model with integral arrival rates. We will present an algorithm in which each u has a competitive ratio of at least 0.72998. Recall that after invoking DR[f, 3], we can obtain a (random) integral vector F with F e ∈ {0, 1, 2}. Define H = F/3 and let G H be the graph induced by H and each edge takes the value H e ∈ {0, 1/3, 2/3}. In this section, we focus on the sparse graph G H . The main steps of the algorithm are: 1. Solve the vertex-weighted benchmark LP in sub-section 2.1. Let f be an optimal solution vector. Invoke DR[f, 3] to obtain an integral vector F and a fractional vector H with H = F/3. Apply a series of modifications to H and transform it to another solution H . See sub-section 4.1. Run the randomized list algorithm (RLA) [12] induced by H on the graph G H . Our goal is to generate a distribution over Π(∂(v)), which denotes the set of all permutations of nodes incident to u. Here we refer to a permutation of all nodes incident to u as a random list R v . Let H u = v∼u H (u,v) (u2,v) . Suppose v has three neighbors in G H . Then take a random permutation ( The resultant Random List Algorithm RLA [H], is shown in Algorithm 6. The WS for vertex-weighted case in [12] is shown in Figure 2 , which arrived at node u with a competitive ratio of 0.725. From their analysis, we find node u 1 has a competitive ratio of at least 0.736. Hence, we boost the performance of u at the cost of u 1 . In other words, we increase the value of H (u,v1) and decrease the value H (u1,v1) . Case (10) and (11) in Figure 4 illustrates this. After this modification, the new WS for vertex-weighted is now the C 1 cycle shown in Figure 1 . In fact, this is the WS for the unweighted case in [12]. However, Lemma 8 and the cycle breaking algorithm, implies that C 1 cycle can be avoided with probability at least 3/e − 1. This helps us improve the ratio even for the unweighted case in [12]. Lemma 8. For any given u ∈ U , u appears in a C 1 cycle after DR[f, 3] with probability at most 2 − 3/e. Proof. Consider the graph G H obtained after DR [f, 3]. Notice that for some vertex u to appear in a C 1 cycle, it must have a neighboring edge with H e = 2/3. Now we try to bound the probability of this event. It is easy to see that for some e ∈ ∂(u) with f e ≤ 1/3, F e ≤ 1 after DR [f, 3], and hence H e = F e /3 ≤ 1/3. Thus only those edges e ∈ ∂(u) with f e > 1/3 will possibly be rounded to H e = 2/3. Note that, there can be at most two such edges in ∂(u), since e∈∂(u) f e ≤ 1. Hence, we have the following two cases. ∂(u) contains only one edge e with f e > 1/3. Let Notice that q 1 + q 2 = 1 and hence q 2 = 3f e − 1. Since this is an increasing function of f e and f e ≤ 1 − 1/e from LP constraint 2.4, we have q 2 ≤ 3(1 − 1/e) − 1 = 2 − 3/e. contains two edges e 1 and e 2 with f e1 > 1/3 and f e2 > 1/3. Let q 2 be the probability that after DR[f, 3], either H e1 = 2/3 or H e2 = 2/3. Note that, these two events are mutually exclusive since H u ≤ 1. Using the analysis from case 1, it follows that q 2 = (3f e1 − 1) + (3f e2 − 1) = 3(f e1 + f e2 ) − 2. From LP constraint 2.5, we know that f e1 +f e2 ≤ 1−1/e 2 , and hence q 2 ≤ 3(1−1/e 2 )−2 < 2 − 3/e. Algorithm 7: [Cycle breaking algorithm] Offline Phase 1 While there is some cycle of type C 2 or C 3 , Do: 2 Break all cycles of type C 2 . 3 Break one cycle of type C 3 and return to the first step. The first modification is to break the cycles deterministically. There are three possible cycles of length 4 in the graph G H , denoted C 1 , C 2 , and C 3 . In [12], they give an efficient way to break C 2 and C 3 , as shown in Figure 2 . Cycle C 1 cannot be modified further and hence, is the bottleneck for their unweighted case. Notice that, while breaking the cycles of C 2 and C 3 , new cycles of C 1 can be created in the graph. Since our randomized construction of solution H gives us control on the probability of cycles C 1 occurring, we would like to break C 2 and C 3 in a controlled way, so as to not create any new C 1 cycles. This procedure is summarized in Algorithm 7. The proof of Lemma 12 follows from the following Claims: Claim 9. Breaking cycles will not change the value H w for any w ∈ U ∪ V . Claim 10. After breaking a cycle of type C 2 , the vertices u 1 , u 2 , v 1 , and v 2 can never be part of any length four cycle. Claim 11. When all length four cycles are of type C 1 or C 3 , breaking exactly one cycle of type C 3 cannot create a new cycle of type C 1 . New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching Proof. As shown in Figure 2 , we increase and decrease edge values f e in such a way that their sums H w at any vertex w will be preserved. Notice that C 2 cycles can be freely broken without creating new C 1 cycles. After removing all cycles of type C 2 , removing a single cycle of type C 3 cannot create any cycles of type C 1 . Hence, Algorithm 7 removes all C 2 and C 3 cycles without creating any new C 1 cycles. Proof. Consider the structure after breaking a cycle of type C 2 . Note that the edge (u 2 , v 2 ) has been permanently removed and hence, these four vertices together can never be part of a cycle of length four. The vertices u 1 and v 1 have H u1 = 1 and H v1 = 1 respectively. So they cannot have any other edges and therefore cannot appear in any length four cycle. The vertices u 2 and v 2 can each have one additional edge, but since the edge (u 2 , v 2 ) has been removed, they can never be part of any cycle with length less than six. Proof. First, we note that since no edges will be added during this process, we cannot create a new cycle of length four or join with a cycle of type C 1 . Therefore, the only cycles which could be affected are of type C 3 . However, every cycle c of type C 3 falls into one of two cases Case 1: c is the cycle we are breaking. In this case, c cannot become a cycle of type C 1 since we remove two of its edges and break the cycle. Case 2: c is not the cycle we are breaking. In this case, c can have at most one of its edges converted to a 2/3 edge. Let c be the length four cycle we are breaking. Note that c and c will differ by at least one vertex. When we break c , the two edges which are converted to 2/3 will cover all four vertices of c . Therefore, at most one of these edges can be in c. Note that breaking one cycle of type C 3 could create cycles of type C 2 , but these cycles are always broken in the next iteration, before breaking another cycle of type C 3 . Lemma 12. After applying Algorithm 7 to G H , we have (1) the value H w is preserved for each w ∈ U ∪ V ; (2)  Informally, this second modification decreases the rates of lists associated with those nodes u with H u = 1/3 or H u = 2/3 and increases the rates of lists associated with nodes u with H u = 1. We will illustrate this with the following example. Consider the graph G in Figure 3 . Let thin and thick edges represent H e = 1/3 and H e = 2/3 respectively. We will now calculate the competitive ratio after applying RLA on G. Let P u denote the probability that u gets matched after the algorithm. Let B u denote the event that among the n random lists, there exists a list starting with u and G v u denote the event that among the n lists, there exists successive lists such that (1) Each of those lists starts with a u = u and u ∈ ∂(v) and (2) The lists arrive in an order which ensures u will be matched by the algorithm. From lemma 4 and Corollary 1 in [12], the following lemma follows: Lemma 13. Suppose u is not a part of any cycle of length 4. We have For the node u, we have Pr [B u  u is the event that among the n lists, the random list R v1 = (u 1 , u) comes at least twice. Notice that the list R v1 = (u 1 , u) comes with probability Intuitively, one can improve the worst case ratio by increasing the arrival rate for R v1 = (u, u 1 ) while reducing that for R v1 = (u 1 , u). Suppose one modifies H (u1,v1) and H (u,v1) to H (u1,v1) = 0.1 and H (u,v1) = 0.9, the arrival rate for R v1 = (u, u 1 ) and R v1 = (u 1 , u) gets modified to 0.1/n and 0.9/n respectively. The resulting changes are Pr[B u ] = 1 − e −0.9−1/3 , Pr[G (11) and (12) help improve upon the WS described in Figure 2 .  Vertex-Weighted Algorithm VW The algorithm VW consists of two different random processes: sub-routine DR [f, 3] in the offline phase and RLA in the online phase. Consequently, the analysis consists of two parts. First, for a given graph G H , we analyze the ratio of RLA[H ] for each node u with H u = 1/3, H u = 2/3 and H u = 1. The analysis is similar to [12]. Second, we analyze the probability that DR[f, 3] transforms each u, with fractional f u values, into the three discrete cases seen in the first part. By combining the results from these two parts we get the final ratio. Let us first analyze the competitive ratio for RLA [H ]. For a given H and G H , let P u be the probability that u gets matched in RLA [H ]. Notice that the value P u is determined not just by the algorithm RLA itself, but also the modifications applied to H. We define the Proof. From Lemmas 8 and 12, we know that any u is present in cycle C 1 with probability at most (2 − 3/e). Consider a node u with 2/3 ≤ f u ≤ 1 and let q 1 , q 2 , q 3 be the probability that after DR[f, 3] and the first modification, H u = 1 and u is in the first cycle C 1 , H u = 1 and u is not in C 1 , H u = 2/3 respectively. From Lemma 14, we get that the final ratio for u should be at least Minimizing the above expression subject to (1) q 1 + q 2 + q 3 = 1; (2) 0 ≤ q i , 1 ≤ i ≤ 3; (3) q 1 ≤ 2 − 3/e, we get a minimum value of 0.729982 for q 1 = 2 − 3/e and q 2 = 3/e − 1. For any node u with 0 ≤ u ≤ 2/3, we know that the ratio is at least the min value of R[RLA, 2/3] and R[RLA, 1/3], which is 0.7622. This completes the proof of Theorem 1. Non-integral arrival rates with stochastic rewards The setting here is strictly generalized over the previous sections in the following ways. Firstly, it allows an arbitrary arrival rate (say r v ) which can be fractional for each stochastic vertex v. Notice that, v r v = n where n is the total number of rounds. Secondly, each e = (v, u) ∈ E is associated with a value p e , which indicates the probability that edge e = (u, v) is present when we assign v to u. We assume this process is independent of the stochastic arrival of each v. We will show that the simple non-adaptive algorithm introduced in [11] can be extended to this general case. This achieves a competitive ratio of (1 − 1 e ). Note that Manshadi et al. [18] show that no non-adaptive algorithm can possibly achieve a ratio better than (1 − 1/e) for the non-integral arrival rates, even for the case of all p e = 1. Thus, our algorithm is an optimal non-adaptive algorithm for this model. We use a similar LP as [12] for the case of non-integral arrival rates. For each e ∈ E, let f e be the probability that e gets matched in the offline optimal algorithm. Thus we have  Our algorithm is summarized in Algorithm 9. Notice that the last constraint ensures that step 2 in the algorithm is valid. Let us now prove theorem 3. Algorithm 9: SM 1 Construct and solve LP (5.1). WLOG assume {f e |e ∈ E} is an optimal solution. 2 When a vertex v arrives, assign v to each of its neighbor u with a probability f (u,v) rv . Proof. Let B(u, t) be the event that u is safe at beginning of round t and A(u, t) to be the event that vertex u is matched during the round t conditioned on B (u, t In this section, we further generalize the model in Section 5 to the case where each u in the offline set U has a uniform integral capacity b (i.e., each vertex u can be matched at most b times). Otherwise, we retain the same setting as Section 5; we allow non-integral arrival rates and stochastic rewards. We will generalize the simple algorithm used in the previous setting (i.e., Section 5) to this new setting. e∈∂ (u) f e p e ≤ b, ∀u ∈ U (6.2) e∈∂ (v) f e ≤ r v , ∀v ∈ V (6.3) (6.4) We modify Algorithm 9 for the b-matching problem as follows. Algorithm 10: SM b 1 Construct and solve LP (6.1). WLOG assume {f e |e ∈ E} is an optimal solution. 2 When a vertex v arrives, assign v to each of its neighbor u with a probability f (u,v) rv . Let us now prove Theorem 4. Proof. The proof is similar to that of Theorem 3. Let A t be the number of times u has been matched at the beginning of round t. Let B(u, t) be the event that u is safe at the beginning of round t, which is defined as A t ≤ b − 1. For any given edge e, let X e be the number of times that e gets matched over the n rounds. (u,v) r v p (u,v) ≤ b n It follows that for any t ≤ n(1 − τ ) with 0 < τ <  22 REFERENCES 7 In this paper, we gave improved algorithms for the Edge-Weighted and Vertex-Weighted models. Previously, there was a gap between the best unweighted algorithm with a ratio of 1 − 2e −2 due to [12] and the negative result of 1 − e −2 due to [18]. We took a step towards closing that gap by showing that an algorithm can achieve 0.7299 > 1 − 2e −2 for both the unweighted and vertex-weighted variants with integral arrival rates. In doing so, we made progess on Open Questions 3 and 4 in the online matching and ad allocation survey [19]. This was possible because our approach of rounding to a simpler fractional solution allowed us to employ a stricter LP. For the edge-weighted variant, we showed that one can significantly improve the power of two choices approach by generating two matchings from the same LP solution. For the variant with edge weights, non-integral arrival rates, and stochastic rewards, we presented a (1 − 1/e)-competitive algorithm. This showed that the 0.62 < 1 − 1/e bound given in [21] for the adversarial model with stochastic rewards does not extend to the known I.I.D. model. Furthermore, we considered the online edge-weighted b-matching problem with stochastic rewards under the known IID setting. We gave a very simple non-adaptive algorithm which achieves a ratio of 1 − b 2 /3 ) for any given > 0. A natural next step in the edge-weighted setting is to use an adaptive strategy. For the vertex-weighted problem, one can easily see that the stricter LP we use still has a gap. In addition, we only utilize fractional solutions {0, 1/3, 2/3}. However, dependent rounding gives solutions in {0, 1/k, 2/k, . . . , k(1 − 1/e) /k}; allowing for random lists of length greater than three. Stricter LPs and longer lists could both yield improved results. In the stochastic rewards model with non-integral arrival rates, an open question is to either improve upon the 1 − 1 e ratio or consider a simpler model with integral arrival rates and improve the ratio for this restricted model. Lastly, there is a gap between our result for b-matching with stochastic rewards and the results of [7] and [2] for similar problems with deterministic rewards. It would be nice to see a result for this problem that is 1 − O(k −1/2 ). Acknowledgements:
To date, the bestknown competitive ratio of 0.730 is due to Brubach et al REF .
New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching
ArXiv
ArXiv
Computer Science Mathematics