In the stochastic weighted matching problem, the goal is to find a large-weight matching of a graph when we are uncertain about the existence of its edges. In particular, each edge $e$ has a known weight $w_e$ but is realized independently with some probability $p_e$. The algorithm may query an edge to see whether it is realized. We consider the well-studied query commit version of the problem, in which any queried edge that happens to be realized must be included in the solution.

Gamlath, Kale, and Svensson [SODA'19] showed that when the input graph is bipartite, the problem admits a  $(1-1/e)$-approximation. In this paper, we give an algorithm that for an absolute constant $\delta > \apximprove$ obtains a $(1-1/e+\delta)$-approximation, therefore breaking this prevalent bound.

§ INTRODUCTION

Matching under uncertainty is a well-studied topic in theoretical computer science, primarily due to applications in matching markets such as kidney exchange, labor markets, online advertising, etc. (See [24, 13, 5, 22] and the references within.)  In this paper, we study the max-weight stochastic matching problem on bipartite graphs in the query commit model. We are given a bipartite graph $G = (A\cup B, E)$ along with a weight $w_e$ and a parameter $p_e \in (0,1]$ for any edge $e\in E$. Each edge of this graph is realized (or exists) independently, with a known probability $p_e$ forming the realized subgraph  $G_p$. We are unaware of the realization of the edges but can access them via queries. Our goal is to find a large-weight matching of $G_p$ in the query commit model in which any edge joins the matching if and only if it is queried and realized. In other words, to add an edge to the matching, we have to ensure that it exists; thus, we have to query it. Moreover, if a queried edge is realized, we have to add it to our matching (i.e., commit to it). This also implies that if an edge has at least one matched end-point it cannot be queried.

In this paper, we focus on designing an approximation algorithm for the above problem, where the approximation ratio is defined with respect to the max-weight matching found by an algorithm that knows the realization of all the edges. For this problem, a $0.5$-approximation can be achieved via the greedy matching algorithm by simply iterating over the edges in the decreasing order of their weights and querying any edge with unmatched end-points. The first non-trivial algorithm for this problem designed by Gamlath, Kale, and Svensson [15] achieves a  $(1-1/e)$ approximation ratio, a very familiar bound that holds for many matching algorithms in various settings (e.g., [16, 9, 24, 23, 16]). It is also known that $(1-1/e)$ is the best approximation ratio achievable by Gamlath et al.'s algorithm [23], which remains to be the state of the art for this problem.  In this paper, we provide a novel algorithm, breaking this $(1-1/e)$ barrier.

Main Theorem. (See Theorem <ref>)
There exists a polynomial-time algorithm that, given any stochastic weighted bipartite graph, finds a matching with an approximation ratio of at least $1-1/e+\apximprove$ in the query commit model.

After Gamlath et al.'s $(1-1/e)$-approximation algorithm, Tang, Wu, and Zhang [24, 23][ [23] is an extension of [24] published separately by the same authors.

] showed that this approximation ratio can also be extended to the more general oblivious matching problem using a random greedy algorithm.
Unlike our problem, in which edges exist independently with known probabilities, in the oblivious matching problem, an oblivious adversary decides which edges exist[The adversary is called oblivious since they determine which edges exist, beforehand, oblivious to the randomization of the algorithm.].
A natural question here is whether there is a separation between the two models when it comes to weighted bipartite graphs. In this work, we take a step toward answering this question as we break the $(1-1/e)$ barrier for the stochastic matching problem while the best-known approximation ratio for the oblivious matching problem remains to be $(1-1/e)$.

§.§ Our Techniques

In this section, we will give a brief overview of our ideas and techniques which allow us to design an algorithm with an approximation factor larger than $(1-1/e)$. Our algorithm is LP-based. We start with an LP   which we borrow from Gamlath et al. [15]. This LP gives us an upper-bound for the optimal solution of the problem. We then design a rounding procedure that given the optimal solution of this LP, decides which edges to query and in which order. In this section, we first describe the LP. We then briefly explain how Gamlath et al. round the solution of this LP in order to find a $(1-1/e)$-approximate matching. Finally, we discuss our rounding procedure which results in beating the $(1-1/e)$-approximation.

The LP. We will use an LP designed by Gamlath et al. The LP has a variable $x_e$ for any edge, and its solution forms a fractional matching. Besides the natural matching constraints, the LP also has a special constraint for any subset of edges sharing an end-point to ensure that the probability of at least one of them being realized is not smaller than the total fraction of matching on them (Constraint (<ref>) below). The LP clearly has exponentially many constraints, but Gamlath et al. show that it is polynomially solvable using the ellipsoid method. Below we provide the formulation of this LP in which $E_u$ denotes the subset of edges that have $u$ as one of their end-points.

\begin{align}
\nonumber \max_{\mathbf{x}} \qquad &\b{x} \cdot \b{w}	\,& \\
\textrm{s.t.} \qquad & \sum_{e \in F} x_e \le \Pr[\text{an edge in $F$ exists}]& \forall u \in A \cup B,  \forall F \subseteq E_u  \label{cons:437489}\\
&x_e \ge 0& \forall e \in E
\end{align}

Now, let us briefly explain the $(1-1/e)$-approximation algorithm  of Gamlath et al. [15].  In the rest of the paper, we will refer to this algorithm as (The authors' initials).

Gamlath et al.'s rounding procedure. Based on the solution of the LP, they draw a random ordering over the edges satisfying some special properties. They then iterate over the edges in this order and decide whether to query them and subsequently add them to the matching or lose them forever.  The query decisions are made dynamically and they consist of each vertex in part $B$ of the graph running a prophet-secretary based algorithm [12] to decide which one of its edges should be queried. Due to making irrevocable query decisions, the algorithm may choose not to query some of the edges while both their end-points are unmatched at the end of the algorithm.

To prove that finds a a $(1-1/e)$-approximate matching, they show that the expected weight of the matching edge connected to any vertex in set $u\in B$ is at least $(1-1/e)$ fraction of the total contribution of its edges to the optimal solution of the LP. That is
$$\sum_{e\in E_u}\Pr[\GKS  \text{ adds } e \text{ to the matching}]\cdot w_e \geq (1-1/e) \sum_{e\in E_u} x_ew_e.$$

Later, Fu et al. [14] observe that replacing the prophet-secretary based approch with an OCRS algorithm makes it possible for each edge to join the matching with probability at least $(1-1/e)x_e$.

Our rounding procedure. Our rounding procedure consists of two steps. We first design a rounding procedure, which, given the optimal solution of the LP, returns a $(1-1/e)$-approximate matching and prove some new desirable properties for it. We call this procedure . We then use this as a subroutine in our final algorithm which beats $(1-1/e)$-approximation. Below are the four important properties.

*  For any vertex $u\in B$, let $\ubar_u$ denote the probability with which this vertex is matched in the optimal solution of the LP. That is $\ubar_u=\sum_{e\ni u} x_e$. One of the desirable properties of is that if $\ubar_u$ is smaller than one by a constant, then  its edges will have a higher chance of joining the matching in comparison to the case of $\ubar_u=1$ (by a constant fraction). As a result of this property, if $\ubar_u$ is small enough for all the vertices in $u\in B$, itself achieves an approximation ratio larger than $(1-1/e)$.

*  After running , any vertex of the graph remains unmatched with a constant probability. Similarly, any edge does not join the matching with a probability of at least $\Omega(x_e)$. We will later explain why this property is helpful.

*   For any edge $e=(v,u)$, we want to ensure that conditioned on that $e$ is not queried by , there is a constant probability of both its end-points being unmatched. Property <ref> already implies that $u$ and $v$ remain unmatched with a large probability.  This property, however, is about the correlation between these events and is the most challenging  one to prove.
We will use this property to show that for some instances of the problem running $\PAM$ for a second time on the remaining edges results in an improved approximation ratio.

In order to achieve these properties, takes the optimal solution of the LP, makes several changes to it and then feeds it to a modified version of (which assumes all the edges have the same weight). One of these changes relies on a transformation function. This function takes $\b{x}$, the optimal solution of the LP and outputs $\tilde{\b{x}}$ which is also a solution of the LP. For any edge $e$, we set $\tilde{x}_e=g(x_e, \ubar)$ where $\ubar$ is a (carefully picked) constant no smaller than $\max_{u\in B} \sum_{e\ni u} x_e$, and

$$g(x, \ubar) = \frac{(e^\ubar-1)(\ubar  -x) x}{\ubar (e^\ubar- e^x)}.$$

It is not hard to see that for any $x_e$, this transformation results in $x_e \geq \tilde{x}_e$, therefore $\tilde{\b{x}}$ will still be a valid solution of the LP.    See Appendix <ref> for more details about this function and the ideas behind choosing it.

We will use properties <ref> and <ref> to prove that after running , any edge $e$ with a small enough $\tilde{x}_e/p_e$ (smaller than a constant) remains available with a constant probability. We say an edge is available if it is not queried and its end-points are unmatched. Roughly speaking, for any edge $e$ satisfying this constraint, property <ref> of implies that the edge is not queried with a constant probability and any of its end-points are also unmatched with a constant probability. The challenging part, however, is to prove that despite potential correlations, the probability of all three events happening together is still a constant. Therefore, the edge remains available with a constant probability. We use this feature of in a crucial way in order to break the $(1-1/e)$ approximation ratio. The reason being that if edges with a small enough $\tilde{x}_e/p_e$ constitute a constant fraction of the optimal solution of the LP, then we can run for a second time on the remaining available edges and use its output to enhance the matching.

Beating $(1-1/e)$-approximation
Now, let us briefly explain how we use the aforementioned properties  of to design another algorithm with an improved approximation ratio. We claim that for any instance of the problem, rounding the optimal solution of the LP in at least one of the two following ways results in an improved approximation ratio. [label=(*)]

* simply run once on the whole graph and once on the remaining available edges.

* Prune the graph by deleting any edge with $\tilde{x}_e/p_e<\tau$   for a carefully picked threshold $\tau$ (which is a constant smaller than one), and then run on the remaining subgraph.

As we already discussed, we prove that edges with  $\tilde{x}_e/p_e<\tau$ will remain available with a constant probability after we run . Therefore, if at least a constant fraction of the optimal solution of the LP comes from these edges, then the first rounding achieves an improved approximation ratio. On the flip side, if these edges do not have a large contribution, by deleting them we are left with a solution of the LP which is close to optimal. We now claim that simply running on the remaining subgraph gives us a matching with an improved approximation ratio. Roughly speaking, we are able to take advantage of constraint (<ref>) of the LP, in order to show the following for any vertex $u$:  The sum of ${x}_e$ of edges connected to $u$ that satisfy  $\tilde{x}_e/p_e\geq \tau$ are upper-bounded by a small enough constant. This implies that in the remaining subgraph, $\sigma_u$ of all the vertices in bounded away from one by a constant. Invoking property <ref> of , implies that simply running it on this remaining subgraph results in an improved approximation ratio. Using  constraint (<ref>) of the LP in this way is a technically challenging part of the paper which we discuss in Section <ref>.

§.§ Further Related Work

The stochastic matching problem in the query commit model was first considered   by  Chen et al. [10], who study the problem under the additional constraint that for any vertex a limited number of its edges can be queried. In this setting, they provide a $0.25$-approximation algorithm for bipartite unweighted graphs. After a series of works [3, 4, 21], this approximation ratio was improved to $0.5$ for unweighted graphs [1], $0.39$ for bipartite weighted graphs [2], and $0.269$ for general wighted graphs [2]. (In all  these works, the approximation ratio is defined with respect to the online benchmark.)  Costello et al. [11] are the first to consider the query commit model without the above-mentioned extra constraint. In this setting, they provide a $0.573$-approximation algorithm for general unweighted graphs. Subsequently, the problem was studied for general wighted graphs with the best known approximation ratio being $0.567$ due to [14].

A problem, closely connected to the one studied in this paper, is the online bipartite matching problem first introduced by Karp, Vazirani, and Vazirani [18]. Here, vertices in one part of the graph are present from the beginning while vertices on the other part arrive online. Whenever an online vertex arrives, its edges are revealed, and the algorithm has to decide whether to match the vertex with an unmatched neighbor, irrevocably, or lose it forever. For this problem, Karp et al. present their celebrated ranking algorithm which achieves a tight $(1-1/e)$ approximation ratio in the standard adversarial model. Later, Mahdian and Yan [20] show that if the online vertices arrive in a random order, the ranking algorithm achieves an approximation ratio of at least $0.69$. On the other hand,  Karande et al. [17] provide an upper-bound of $0.727$ for the ranking algorithm in the random arrivals model. Since ranking is a random greedy algorithm, it can also be used for the problem studied in this paper achieving an approximation ratio of  $0.69$ for unweighted graphs.  This is indeed the best-known approximation ratio for the unweighted version of the bipartite stochastic matching problem in the query commit model (the unweighted version of our problem).

Our paper also relates to a line of work initiated by Blum et al. [8] which concerns the query complexity of the stochastic matching problem. In this model, the goal is to find a large matching of the graph while having only a constant number of queries per vertex. Here, the matching does not have to commit to the queried edges that are realized.  After a long line of work on this problem, (See [25, 7, 6] and the references within.)  Behnezhad et al. [5]   prove that it is possible to  achieve a $(1-\epsilon)$ approximation ratio for general weighted graphs.

Another model which is closely related to the one considered in this paper, is the price of information model (POI). It was first introduced by Singla [22] and subsequently studied in [14, 15].  In POI, (similar to  the query commit model), to know the edge weights one needs to query them, however, instead of having to commit to the realized edges, they need to pay a cost for each query. Moreover, edge weights come from discrete distributions. The best known approximation ratio for matching in the POI model is a $(1-1/e)$ by Gamlath et al.  [15]. Due to their similar nature,  the POI model and the query commit model are often studied together. In Appendix <ref> we have a discussion about extending our ideas to the POI model in order to improve over the  $(1-1/e)$ approximation ratio.

§ PRELIMINARIES

We consider the stochastic matching problem on weighted bipartite graphs in the query-commit model. Our input is a  bipartite graph $G=(A \cup B,E) $, a vector of weights $\b{x} = (x_e)_{e\in E}$, and vector of probabilities  $\b{p} = (p_e)_{e\in E}$. Each edge exists or is realized with probability $p_e$ forming subgraph $\gp$. We refer to $\gp$ as the realized subgraph.  We do not know which edges are realized but can access them via queries.  We can query any edges $e\in E$ to see whether it exists or not, and if it does, we must add it to the matching irrevocably. In other words, our matching must commit to the edge.  Our goal is to design a polynomial-time algorithm which finds a matching $\sol$ of $\gp$ with a large approximation ratio. The approximation ratio of the algorithm is defined as

where $\opt$ is the maximum weight matching of $\gp$ (i.e., the optimal solution) and  $\W{.}$ is a function outputting the weight of a given matching. The expectation here is taken over both the randomization in the algorithm and realization of edges.

General notations. For any $v\in A\cup B$ we will use $E_v$ to denote the subset of edges that have $v$ as one of their end-points. Unless otherwise stated, we will refer to vertices of $B$ using the letter $u$ and vertices of $A$ using the letter $v$. Moreover, we will write our edges as ordered pairs, meaning that for any edge $(v,u)\in  E$ we always have $v \in A$ and $u \in B$.

Organization of the paper. The rest of the paper is organized as follows. In Section <ref> we explain the LP which we borrow from Gamlath et al. This LP gives us an upper-bound on the optimal solution of the LP. In Section <ref>, we first design , a rounding procedure which given the optimal solution of the LP outputs a $(1-1/e)$-approximate matching. Later in the section, we design which uses to find a matching with an approximation ratio of $(1-1/e+\apximprove)$. In Section <ref>, we prove some desirable properties of our , and finally, in Section <ref> we use these properties to analyze the approximation ratio of our algorithm.

§.§ Our $(1-1/e)$-approximation Algorithm

Let us start by explaining the desirable properties that we are trying to achieve by designing a new $(1-1/e)$-approximate matching below. We call this algorithm .  We first define
$$\ubar=\max_{u\in B} \sum_{e\in E_u} x_e.$$
These properties as follows. (We have briefly discussed these properties in Section <ref>.)

*  The probability of any edge joining the matching is at least $(1-1/e)x_e$ and is also a  decreasing function of $\ubar$. In other words, if  $\ubar$ is smaller than one by a constant, we want to match any edge with probability at least $(1-1/e+c)x_e$, where $c$ is a constant. This implies that in this scenario, itself achieves an approximation ratio larger than $(1-1/e)$.

*  The algorithm ensures that any vertex of the graph remains unmatched with a constant probability. Similarly, any edge does not join the matching with probability at least $\Omega(x_e)$. does not satisfy this property as it may match some of the edges and vertices with probability one. This property allows us to show that for some instances of the problem, running twice gives us an improved algorithm. That is, we once run on $G$ and once on the edges that are not queried and have unmatched end-points after the first run.

*  For any edge $e=(v,u)$, we want to ensure that conditioned on any edge $e$ not being examined, there is a constant probability of both its end-points being unmatched. This, again is helpful in arguing that for instances of the problem running twice gives us an improved algorithm. Property <ref> already implies that all the vertices remain unmatched with a large probability. It can also be used to show that some particular edges remain unexamined with a constant probability. This property, however, is about the correlation between these  events.

Algorithm is very similar to with three  main differences. The first one which allows us to satisfy property <ref> is due to a transformation function. Given the optimal solution of the LP, we transform it to a different solution which still satisfies all the LP constraints. We then give this as an input to a modified version of .

To pick our transformation function we start by observing that if all the edges connected to a vertex $u\in B$ have the same $x_e$ and $x_e\rightarrow 0$, then in each edge joins the matching with a probability that satisfies this property. Since the algorithm draws a uniform permutation over vertices in $A$, all of $u$'s edges have the same probability of joining the matching and that is

\begin{align*}\frac{\Pr[u \text{ joins the matching}]}{|E_u|}=\frac{1-(1-x_e)^{|E_u|}}{|E_u|}=\frac{1-(1-x_e)^{x_u/x_e}}{x_u/x_e}= \frac{(1-e^{-x_u})}{x_u}\cdot x_e. \end{align*}

Note that here $\frac{(1-e^{-x_u})}{x_u}$ is a decreasing function of $x_u$ and for $x_u=1$ it is exactly equal to $(1-1/e)$. Therefore, it satisfies property <ref>. Roughly speaking, based on this observation, we aim to modify the solution of the LP in a way that each edge $e=(v,u)$ behaves as if instead of a single edge it was a collection of edges $e'_1\dots e'_k$ with $k \rightarrow \infty$ and $\sum_{i=1}^k x_{e'}=x_e$. Of course, we cannot simply replace $e$ with $k$ parallel edges between $v$ and $u$ and hope to achieve the desired bound since these edges all being representatives of a single edge cannot behave independently. However, we show that lowering $x_e$ to $\tilde{x}_e$ defined as follows gives us a similar effect.

Let us denote the modified solution by ${\tilde{\b x}}$. Assume that for every $u \in B$, we have $\sum_{e \ni u} x_e \le \ubar$. For any edge $e\in E$ we let  $\tilde{x}_e=g(x_e, \ubar)$ where,

$$g(x, \ubar) = \frac{(e^\ubar-1)(\ubar  -x) x}{\ubar (e^\ubar- e^x)}$$

for any $x\in [0,\ubar)$, and
$$g(\ubar, \ubar) = \lim_{x\rightarrow \ubar} g(x, \ubar) = 1-e^{-\ubar}.$$
We then set $\tilde{x}_e = g(x_e, \ubar)$. When value of $\ubar$ is clear from the context we will simply use $g(x_e)$ instead of $g(x_e, \ubar)$.  In Appendix <ref> we provide more details about this function and the ideas behind choosing it.

For any $x\in [0,\ubar]$ and $\ubar\in (0,1]$	we have $x\geq g(x,\ubar)$.

The proof of this claim is deferred to Appendix <ref>.

The modified solution ${\tilde{\b x}}$ defined above satisfies all the constraints of <ref> since for any $e\in E$, we have $\tilde{x}_e= g(x_e, \ubar) \le x_e.$

It is possible to show that this modification ensures that the simple algorithm matches each edge with probability $(1-1/e)x_e$. This is a corollary of Lemma <ref> which we prove later. Indeed, the lemma implies the following lower-bound for the probability of each edge $e$ being matched by $G, {\tilde{\b x}}$.

where $\ubar=\max_{u\in B}x_u$. Note that this is exactly what we were hoping to get.  That is the probability of the edges being matched if they all had the same $x_e$ and $x_e\rightarrow 0$, and it satisfies property <ref>.

Now, let us give some intuition about  the second difference between algorithms and . We need this to  satisfy property <ref>. Recall that due to this property we need any edge $e$ to remain unmated with probability at least a constant fraction of $x_e$.  For large values of $x_e$, the transformation function takes care of this property since $x_e-\tilde{x}_e$ will be large as well. However, consider an edge $e=(v,u)$ with a very small $x_e$ which results in  $\tilde{x}_e \approx x_e$. In this case, $v$ sends a proposal to $u$ with probability almost equal to $x_e$. If $e$ is the only edge connected to $u$, this proposal will always be accepted and $e$ joins the matching with probability almost equal to $x_e$ which contradicts property <ref>. On the other hand, if $u$ has many other edges, the probability of rejecting $v$'s proposal increases. Thus, our idea for satisfying this property is adding dummy edges to the graph to ensure that all the proposals have a constant probability of being rejected. Below we explain what these dummy edges are and how we use them.

Given a graph $G$ and an LP solution $\b{x}$, let $\ubar\in [0,1]$ be a constant number satisfying $\sum_{e\ni u} x_e \leq \ubar$ for any $u\in B$.
Dummy edges are edges with   $w_e=0$ and $p_e=1$ which we add to our graph in order to ensure $\sum_{e\ni u} x_e = \ubar$ for all $u\in B$. To achieve this for any vertex $u\in B$ we add a dummy edges $e$ with  $x_e=\ubar -\sum_{e\ni u} x_e$  between $u$ and a degree-one dummy vertex which we add to $A$.

It is clear that after adding these  dummy edges, $\b{x}$ is still an optimal solution of the LP. Since the dummy edges weigh zero, they do not change the weight of the matching.  Moreover, due to having $p_e=1$ they do not violate constraint (<ref>) of the LP either.

After adding dummy edges to the graph as described in Definition <ref>, $\b{x}$ is still an optimal solution of the <ref>.

We will talk about the third difference between and after stating   formally.

Our $(1-1/e)$-approximation algorithm with specific properties.

$A,B, E, \b x, \ubar$
For any vertex $u\in B$ ensure $\sum_{e\ni u} x_e=\ubar$ via adding dummy edges. (See Definition <ref>.)
${\tilde{\b x}} \gets g({\b x}, \ubar)$.
Let $\match=\emptyset$ be a matching of $E$.
Let $\pi$ be a permutation over vertices in $A$ chosen uniformly at random.
$v$ in the order of $\pi$
Let $\pi_v\sim \mathcal{D}^{\tilde{\b x}}_v$ as described by $v, \b{x}, \tilde{\b{x}}$.
$e=(v,u)$ permuted in the order of  $\pi_v$
Examine edge $e$.

$e$ is realized Vertex $v$ sends a proposal to $u$.

If $u$ is unmatched, it accepts the proposal and $e$ joins $\match$.

Terminate the loop.

As one can see, this algorithm has two additional lines compared to , Lines <ref> and Lines <ref>. As input, this algorithm gets a bipartite graph $G=(A,B,E)$, a solution of <ref>, $\b{x}$, and a parameter $\ubar$ which should satisfy $\sum_{e\ni u} x_e \leq \ubar$. In Lines <ref> we add dummy edges to vertices in $B$ to ensure that they all satisfy $\sum_{e\ni u} x_e = \ubar$, and in  Lines <ref> we transform  $\b{x}$ to another solution of the LP, $\tilde{\b x}$.

The only other difference between and is in the way we find distribution $\mathcal{D}^{\tilde{\b x}}_v$ in Line <ref>. Instead of simply using Lemma <ref> to find an arbitrary distribution $\mathcal{D}^{\tilde{\b x}}_v$  proportional to $\tilde{\b{x}}$, we need to construct one with particular features. The goal here is to satisfy property <ref>. Recall that due to this property, we want to ensure that conditioned on an edge $e=(v,u)$ being unexamined, its end-points are unmatched with a constant probability. Unfortunately, some proportional distributions result in $\Pr[ v \text{ is unmatched } \mid e \text{ is not examined}\ ]\approx 0$. Below we describe our special $\mathcal{D}^{\tilde{\b x}}_v$ by designing a polynomial time algorithm for drawing a permutation from it.

Drawing a permutation from $\mathcal{D}^{\tilde{\b x}}_v$
$v, \b{x}, \tilde{\b{x}}$
Let $\mathcal{D}^{\b x}_v$ be a distribution over permutations of subsets of $E_v$ from Definition <ref>.
Let $\pi_v\sim  \mathcal{D}^{\b x}_v$
Let $\pi'_v$ be an empty permutation.
$e$ in the order of $\pi_v$
Let $c$ be random number drawn uniformly from $[0,1]$.
$c\leq p_e(1-\frac{\tilde{x}_e}{x_e})$
End the loop.

$p_e(1-\frac{\tilde{x}_e}{x_e})< c\leq p_e(1-\frac{\tilde{x}_e}{x_e})+\frac{\tilde{x}_e}{x_e}$
Add  $e$ to the end of permutation $\pi'_v$.

We also need to prove that drawing a permutation from $\mathcal{D}^{\tilde{\b x}}_v$  using $v, \b{x}, \tilde{\b{x}}$ does not contradict with it being proportional to $\tilde{\b{x}}$. Let $\pi_v\gets $ $v, \b{x}, \tilde{\b{x}}$. By Definition <ref>, $\mathcal{D}^{\tilde{\b x}}_v$ is proportional to $\tilde{\b{x}}$, iff for any edge in $e\in E_v$ probability of $e$ being the first realized one in $\pi_v$ is equal to $\tilde{x}_e$.
Since in , the inner-loop ends when the first edge from $\pi_v$ is realized, the probability of an edge $e$ being proposed is equal to the probability of $e$ being the first realized edge in $\pi_v$. Therefore, the below lemma proves that $\mathcal{D}^{\tilde{\b x}}_v$  is proportional to $\tilde{x}_e$ as well.  We  defer the proof of the lemma to Appendix <ref>.

For any edge $e\in E_v$, the probability of $v$ sending a proposal to $u$ in  is equal to $\tilde{x}_{e}$.

§.§ Improving Over $(1-1/e)$ Approximation Ratio

Now we are ready to discuss how we use to design an algorithm with an improved approximation ratio. We call this algorithm and formally state it in Algorithm <ref>. Let us say an edge is available after running if it remains unexamined with its end-points unmatched. Note that these edges if realized can join the matching. Let us define

$$r=\sum_{e\in E}x_e w_e\Pr[e \text{ remains available}].$$

If we run for a second time on these remaining available edges, we find a matching of weight at least $(1-1/e)r$ which we can add  to the matching we found in the first run. Thus if $r$ is at least a constant fraction of the optimal solution of the LP, two runs of returns a matching with approximation ratio higher than $(1-1/e)$.

A crucial lemma that we will prove about  is Lemma <ref>.  Roughly speaking it states that after we run once, any edge $e\in E$ will remains available with probability at least $c\cdot(1-\tilde{x}_e/p_e)$ where $c$ is a constant.  (The proof of this lemma strongly relies on properties <ref> and <ref> of .) Now, let $E^{(\tau)}$ denote the subset of edges  for which $\tilde{x}_e/p_e$ is  no larger that a constant $\tau$. If the contribution of these edges to the optimal solution of the LP is larger than a constant fraction, then the algorithm mentioned above that is running twice returns a matching with approximation ratio higher than $(1-1/e)$. This is exactly what does for these graphs.

The inputs to algorithm are a graph $G$, the optimal solution of the LP, $\b{x}$, and three parameters $\tau,\ubar,\lambda\in (0,1)$.  As discussed above, given the threshold $\tau$, the algorithm constructs $E^{(\tau)}$ which is the subset of edges for which $\tilde{x}_e/p_e\leq\tau$. Then, it denotes their contribution to the optimal solution of the LP by $\omega$. If $\omega$ is larger than $\lambda$ fraction of the optimal solution, then it runs two rounds of . Once on the whole graph, and once on the remaining available edges.

Our algorithm with an approximation ratio larger than $(1-1/e)$.
$G, \b x, \tau, \ubar, \lambda$
Let $\match=\emptyset$ be a matching of $E$.
${\tilde{\b x}} \gets g({\b x}, 1)$.
$E^{(\tau)}\gets \{e\in E \mid \tilde{x}_e/p_e\leq \tau\}$.
$\omega\gets\sum_{e\in E^{(\tau)}} x_ew_e$.
$\omega\geq \lambda(\b{x}\cdot\b{w})$

$\match_1\gets$  $A, B, E, \b{x}, 1$.
Let $E_2$ be the set of edges in $E$ that are not examined and do not share any end-points with edges in $\match_1$.
$\match_2 \gets$ $A, B, E_2, \b{x}, 1$.
$\match\gets \match_1\cup \match_2$.

$\match\gets$ $A, B, E \setminus E^{(\tau)}, \b{x}, \ubar$

Now, if two runs of do not achieve an approximation ratio larger than $(1-1/e)$, roughly speaking, it implies that the contribution of edges of $E^{(\tau)}$ to the optimal solution of the LP is very small. Thus, if we remove edges of $E^{(\tau)}$ from the graph and accordingly adjust $\b{x}$, it does not make a significant change in $\b{x}\cdot\b{w}$. We will prove in Claim <ref> that if all the edges have a large $\tilde{x}_e/p_e$, then due to constraint (<ref>) of the <ref>, $\max_{u\in B} \sum_{e\in E_u} x_e$ is upper-bounded by a constant $\ubar<1$. In this case, the idea is to use property <ref> of , and show that running $A, B, E \setminus E^{(\tau)}, \b{x}, \ubar$ achieves an approximation ratio larger than $(1-1/e)$. This is exactly what Algorithm does in this scenario.

[Main Theorem]theoremmaint

§ PROPERTIES OF BASEMATCHING

In this section, we focus on proving some desirable properties  of (not only the ones discussed before), which we will later need in our analysis.

In the lemma stated below, we  provide upper and lower bounds for the probability of any edge joining the matching in  $G, \b{x}, \sigma$. This lemma directly implies the first two properties, <ref>, and <ref>. Later, we also prove property <ref> in Lemma <ref>.

For any edge $e$, we have the following.

\begin{align*}
\frac{(1-e^{-\ubar})x_e}{\ubar} \le \Pr[e \in \match_1] \le \frac{x_e(1+e^{-\ubar})}{2}, \end{align*}

where $\match_1=$$G, \b{x}, \sigma$.

Before starting the proof, let us mention that for ease of notation, throughout the proof, we will refer to $x_e$ of an edge by its contribution to the solution of the LP (instead of $x_ew_e$).
Note that in algorithm $\match_1=$$G, \b{x}, \ubar$, we use dummy edges to ensure that for any vertex $u\in B$, we have $x_u \gets \sum_{e \ni u} x_e =\ubar.$  Suppose that $e=(v,u)$.   We claim that $\Pr[e \in \match_1]$ is minimized when  except $e$, $u$ has a large number of edges (approaching $\infty$) with the total contribution of $\ubar-x_e$. On the other hand, it is maximized  when $u$ is only incident to one other edge with the contribution of $\ubar-x_e$. To prove our claim, we take an edge $e'=(v', u)\neq e$ and show that replacing it with two edges $e_1'$ and $e_2'$ with $x_{e_1'}=x_{e_2'}= x_e/2$ increases $\Pr[e \in \match_1]$.

Let $\pi$ be the permutation over vertices in $A$ chosen uniformly at random in the algorithm constructing $\match_1$. For any edge $(v'', u)\in E'$, let $s_{v''}$ be a Bernoulli random variable which is equal to one if $v''$ is the first vertex from set $B/\{v'\}$ to send a proposal to $u$. This implies that edge $e$ has a chance of joining the matching only if $s_v=1$. In addition to that, $v'$ should not send a proposal before $v$.  By Claim <ref>, we know that the probability of any edge $e'$ being proposed by the algorithm is equal to $\tilde{x}_{e'}$.  Thus, we have

\begin{align*}
\Pr[e \in \match_1] &=  \Pr\left[v' \text{ does not send a proposal to } u \text{ before } v \mid s_v=1\right]\Pr[s_v=1] \\
& = \left(1- \Pr\left[\pi(v') < \pi(v) \mid s_v=1\right]\Pr\left[v' \text{ sends a proposal to } u \mid s_v=1\right]\right)\Pr[s_v=1] \\
& \hspace{-6.3mm}\stackrel{(Claim~\ref{lemma:nierfj})}{=} (1- 0.5\cdot \tilde{x}_{e'})\Pr[s_v=1].
\end{align*}

Now if we replace $e'$ with $e_1'=(v'_1, u)$ and $e_2' = (v'_2, u)$ we get

\begin{align*}
\Pr[e \in \match_1] &=  \Pr\left[\text{neither } v_1'  \text{ nor }  v_2' \text{ send a proposal to } u \text{ before } v \mid s_v=1\right]\Pr[s_v=1] \\
& = (1- 0.5\cdot \tilde{x}_{e_1'} - 0.5\cdot \tilde{x}_{e_2'} + 0.25\cdot \tilde{x}_{e_1'}\tilde{x}_{e_2'})\Pr[s_v=1].
\end{align*}

To prove our claim, we need to show

\begin{align*}
(1- 0.5\cdot \tilde{x}_{e_1'} - 0.5\cdot \tilde{x}_{e_2'} + 0.25\cdot \tilde{x}_{e_1'}\tilde{x}_{e_2'})\Pr[s_v=1]- (1- 0.5\cdot \tilde{x}_{e'})\Pr[s_v=1] \leq 0.
\end{align*}

Since $\Pr[s_v=1]$ is a non-negative number, we can factor  $0.5\cdot\Pr[s_v=1]$ out and get

\begin{align*}
- \tilde{x}_{e_1'} -  \tilde{x}_{e_2'} + 0.5\cdot \tilde{x}_{e_1'}\tilde{x}_{e_2'} +  \tilde{x}_{e'} \leq 0.
\end{align*}

Now, plugging in the values of $\tilde{x}_{e'}$, $\tilde{x}_{e_1'}$, and $\tilde{x}_{e_2'}$, we need to prove that the following term is not positive for any $\ubar\in [0,1]$ and $x_e\in [0,\ubar]$.

\begin{align*}
-2\frac{(e^\ubar-1)(\ubar  -x_e/2) x_e/2}{\ubar (e^\ubar- e^{x_e/2}) }+ 0.5\left(\frac{(e^\ubar-1)(\ubar  -x_e/2) x_e/2}{\ubar (e^\ubar- e^{x_e/2}) }\right)^2 +\frac{(e^\ubar-1)(\ubar  -x_e) x_e}{\ubar (e^\ubar- e^{x_e})}.
\end{align*}

After factoring out $\frac{(e^\ubar-1) x_e}{8\ubar}$ (which is always positive) from all terms, it suffices to prove:

\begin{align*}
-\frac{8(\ubar  -x_e/2)}{ (e^\ubar- e^{x_e/2}) }+ \frac{(e^\ubar-1)(\ubar  -x_e/2)^2 x_e}{\ubar (e^\ubar- e^{x_e/2})^2 } +\frac{8(\ubar  -x_e)}{ (e^\ubar- e^{x_e})}\leq 0.
\end{align*}

We do so by plotting this function and observing that it is not positive for any $\ubar\in [0,1]$ and $x_e\in [0,\ubar]$.
This proves our claim that $\Pr[e \in \match_1]$ is minimized when except $e$, $u$ has a large number of edges (approaching $\infty$) with the total contribution of $\ubar-x_e$. On the other hand, it is maximized  when $u$ is only incident to one other edge with the contribution of $\ubar-x_e$. Now, we are ready to prove the desired lower and upper bounds for $\Pr[e \in \match_1]$. We start by proving the lower-bound.

Let $k$ denote the number of vertices adjacent to $u$ other than $v$ and define $\delta=\ubar-x_e$. We already proved that $\Pr[e \in \match_1]$ is minimized when $k\rightarrow \infty$ and $x_{e'} = \delta/k$  for any $e'\neq e$. Thus,

\begin{align*}\Pr[e \in \match_1] \\&= \Pr[e \text{ is proposed}]\sum_{i=0}^k\Pr[\text{There are } i \text{ edges before } e \text{ in  } \pi \wedge \text{none of them are proposed}]
\\&\geq g(x_e)\times \lim_{k\rightarrow \infty}\left(\sum_{i=0}^{k}\frac{1}{k+1} \left(1-g\left(\delta/k\right)\right)^i\right)
\\& = \frac{g(x_e)}{k}\times \lim_{k \rightarrow \infty} \left( \sum_{i=0}^{k} \left(1-\left( \delta/k \right)\right)^i \right)
\\&= g(x_e)\times  \lim_{ k \rightarrow \infty}\left(\sum_{i=0}^{k} \frac{e^{-i\delta/k}}{k}\right) , \end{align*}

where the third equality is due to $\lim_{x\rightarrow 0}g(x)= x$.
Since $k\rightarrow \infty$, we can replace the above summation with an integration as follows:

\begin{align}
\label{eq:integrate}
\sum_{i=0}^{k} \frac{e^{-i\delta/k}}{k}=\int_{0}^{1} e^{-y\delta} dy= \frac{1-e^{-\delta}}{\delta} = \frac{1-e^{-\ubar + x_e}}{\ubar - x_e}.
\end{align}

This gives us:

\begin{align*} \Pr[e \in \match_1]& \geq \frac{(e^\ubar-1)(\ubar  -x_e) x_e}{\ubar (e^\ubar- e^{x_e})}\times \frac{1-e^{-\ubar + x_e}}{\ubar - x_e}
\\ &= \frac{x_e}{\ubar}\times \frac{(e^\ubar-1)(1-e^{-\ubar + x_e})}{e^\ubar-e^{x_e}}
\\ &=\frac{x_e}{\ubar}\times \frac{e^\ubar  - e^{x_e}-1 +  e^{-\ubar + x_e}}{e^\ubar-e^{x_e}}
\\ &=\frac{x_e}{\ubar}\times \frac{(e^\ubar - e^{x_e}) (1-e^{-\ubar})}{e^\ubar-e^{x_e}}
\\ &=\frac{x_e(1-e^{-\ubar})}{\ubar}
\end{align*}

This completes the proof of our desired lower-bound.

Now, we proceed to prove the following upper-bound:

$$\Pr[e \in \match_1] \le \frac{1}{2}(1 + e^\ubar) x_e.$$

Recall that we have already proved that this probability is maximized  when $u$ is only incident to one other edge $e'$ with  $x_{e'}=\ubar-x_e$. Hence, we have

\begin{align*}\Pr\left[e \in \match_1\right] &= \Pr[e \text{ is proposed}]\left(\Pr[\pi(e) < \pi(e') ] + \Pr[\pi(e) > \pi(e')  \wedge e' \text{ is not proposed}]\right)
\\ & = g(x_e) \left( 0.5 + 0.5(1-g(x_{e'})\right)
\\& = g(x_e) \left( 1-0.5g(x_{e'})\right)
\end{align*}

Note that $g(x)/x=\frac{(e^\ubar-1)(\ubar  -x)}{\ubar (e^\ubar- e^x)}$ is a decreasing function of $x$. As such,

\begin{align*} g(x_e)/x_e\leq  \lim_{x\rightarrow 0}(g(x)/x) =  \lim_{x\rightarrow 0} \frac{(e^\ubar-1)(\ubar  -x)}{\ubar (e^\ubar- e^x)} = \frac{(e^\ubar-1)\ubar  }{\ubar (e^\ubar- 1)}= 1.\end{align*}

Moreover, combining this with the fact that $\lim_{x\rightarrow \ubar} (\ubar-x)/(e^\ubar-e^x) = e^{-\ubar},$ we get

$$g(x_{e'})/x_{e'}\geq \lim_{x\rightarrow \ubar}(g(x)/x) = \lim_{x\rightarrow \ubar} \frac{(e^\ubar-1)(\ubar  -x)}{\ubar (e^\ubar- e^x)} = \frac{(e^\ubar-1)e^{-\ubar}}{\ubar} = \frac{1 - e^{-\ubar}}{\ubar}.$$

As a result, we have

\begin{align*}\Pr\left[e \in \match_1\right] &= g(x_e) \left( 1-0.5g(x_{e'})\right)
\\&=x_e \frac{g(x_e)}{x_e}\left( 1-0.5x_{e'}\frac{g(\ubar-x_{e'})}{\ubar-x_{e'}}\right)
\\& \leq x_e (1-0.5x_{e'}\frac{1 - e^{-\ubar}}{\ubar})
\\& \leq x_e (1-0.5(\ubar - x_e)\frac{1 - e^{-\ubar}}{\ubar})
\\& \leq x_e (1-0.5(1 - e^{-\ubar}))
\\& \leq x_e (0.5+0.5e^{-\ubar})
\\& \leq \frac{x_e}{2}(1+e^{-\ubar}).
\end{align*}

This proves our desired upper-bound and completes the proof of this lemma.

[1]
Marek Adamczyk.
Improved analysis of the greedy algorithm for stochastic matching.
Inf. Process. Lett., 111(15):731–737, 2011.

[2]
Marek Adamczyk, Brian Brubach, Fabrizio Grandoni, Karthik Abinav Sankararaman,
Aravind Srinivasan, and Pan Xu.
Improved approximation algorithms for stochastic-matching problems.
CoRR, abs/2010.08142, 2020.

[3]
Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan,
and Atri Rudra.
When LP is the cure for your matching woes: Improved bounds for
stochastic matchings.
Algorithmica, 63(4):733–762, 2012.

[4]
Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu.
Improved bounds in stochastic matching and optimization.
Algorithmica, 80(11):3225–3252, 2018.

[5]
Soheil Behnezhad and Mahsa Derakhshan.
Stochastic weighted matching:(1-ϵ) approximation.
In Sandy Irani, editor, 61st IEEE Annual Symposium on
Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November
16-19, 2020, pages 1392–1403. IEEE, 2020.

[6]
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi.
Stochastic matching with few queries: (1-\(\epsilon\))
In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam
Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM
SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA,
June 22-26, 2020, pages 1111–1124. ACM, 2020.

[7]
Soheil Behnezhad and Nima Reyhani.
Almost optimal stochastic weighted matching with few queries.
In Éva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation,
Ithaca, NY, USA, June 18-22, 2018, pages 235–249. ACM, 2018.

[8]
Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas
Sandholm, and Ankit Sharma.
Ignorance is almost bliss: Near-optimal stochastic matching with few
Oper. Res., 68(1):16–34, 2020.

[9]
Mark Braverman, Mahsa Derakhshan, and Antonio Molina Lovett.
Max-weight online stochastic matching: Improved approximations
against the online benchmark.
In Proceedings of the 2022 ACM Conference on Economics and
Computation, 2022.

[10]
Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra.
Approximating matches made in heaven.
In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias,
Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, Automata,
Languages and Programming, 36th International Colloquium, ICALP 2009,
Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, volume 5555 of Lecture Notes in Computer Science, pages 266–278. Springer, 2009.

[11]
Kevin P. Costello, Prasad Tetali, and Pushkar Tripathi.
Stochastic matching with commitment.
In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger
Wattenhofer, editors, Automata, Languages, and Programming - 39th
International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012,
Proceedings, Part I, volume 7391 of Lecture Notes in Computer
Science, pages 822–833. Springer, 2012.

[12]
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla.
Prophet secretary for combinatorial auctions and matroids.
In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA,
USA, January 7-10, 2018, pages 700–714. SIAM, 2018.

[13]
Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, and S. Muthukrishnan.
Online stochastic matching: Beating 1-1/e.
In 50th Annual IEEE Symposium on Foundations of Computer
Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages
117–126. IEEE Computer Society, 2009.

[14]
Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang.
Random order vertex arrival contention resolution schemes for
matching, with applications.
In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming,
ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference),
volume 198 of LIPIcs, pages 68:1–68:20. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2021.

[15]
Buddhima Gamlath, Sagar Kale, and Ola Svensson.
Beating greedy for stochastic bipartite matching.
In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego,
California, USA, January 6-9, 2019, pages 2841–2854. SIAM, 2019.

[16]
Gagan Goel and Aranyak Mehta.
Online budgeted matching in random input models with applications to
In Shang-Hua Teng, editor, Proceedings of the Nineteenth
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San
Francisco, California, USA, January 20-22, 2008, pages 982–991. SIAM,

[17]
Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi.
Online bipartite matching with unknown distributions.
In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of
the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA,
USA, 6-8 June 2011, pages 587–596. ACM, 2011.

[18]
Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani.
An optimal algorithm for on-line bipartite matching.
In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM
Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland,
USA, pages 352–358. ACM, 1990.

[19]
Euiwoong Lee and Sahil Singla.
Optimal online contention resolution schemes via ex-ante prophet
In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th
Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018,
Helsinki, Finland, volume 112 of LIPIcs, pages 57:1–57:14. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2018.

[20]
Mohammad Mahdian and Qiqi Yan.
Online bipartite matching with random arrivals: an approach based on
strongly factor-revealing lps.
In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of
the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA,
USA, 6-8 June 2011, pages 597–606. ACM, 2011.

[21]
Marco Molinaro and R. Ravi.
The query-commit problem.
CoRR, abs/1110.0990, 2011.

[22]
Sahil Singla.
The price of information in combinatorial optimization.
In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA,
USA, January 7-10, 2018, pages 2523–2532. SIAM, 2018.

[23]
Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang.
A simple 1-1/e approximation for oblivious bipartite matching.
CoRR, abs/2002.06037, 2020.

[24]
Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang.
Towards a better understanding of randomized greedy matching.
In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam
Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM
SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA,
June 22-26, 2020, pages 1097–1110. ACM, 2020.

[25]
Yutaro Yamaguchi and Takanori Maehara.
Stochastic packing integer programs with few queries.
In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA,
USA, January 7-10, 2018, pages 293–310. SIAM, 2018.

§ OMITTED PROOFS

§.§ Omitted Proofs of Section 4

We show that $\frac{g(x,\ubar)}{x} \le 1$. We have the following.

\begin{align*}
\frac{g(x,\ubar)}{x} = \frac{(e^\ubar-1)(\ubar  -x)}{\ubar (e^\ubar- e^x)}
\end{align*}

Since $\frac{g(x,\ubar)}{x}$ is decreasing with respect to $x$ (see Claim <ref>), it gets maximized when $x$ approaches $0$ in which we have

\begin{align*}
\frac{g(x,\ubar)}{x} \le \lim_{x \rightarrow 0} \frac{g(x,\ubar)}{x} =  \frac{(e^\ubar-1)(\ubar )}{\ubar (e^\ubar- 1)} =1 \,.
\end{align*}

Vertex $v$ send a proposal by drawing a random permutation from $v, \b{x}, \tilde{\b{x}}$. It then examines the edges in the same order of the permutation and proposes the first realized edge. Therefore, instead of showing that $v$ sends a proposal to $u$ with the probability $\tilde{x}_e$, we can show that if we draw a random permutation $\pi'_v$ from , and examine the edges in the same order, then the edge $(v,u)$ would be the first realized edge with the probability of $\tilde{x}_e$.

If we draw a random permutation $\pi_v$ from $\mathcal{D}^{\b x}_v$, then for each $e \in E_v$ the probability that $e$ is the first edge that realizes in $\pi_v$ is $x_e$. Consider any fixed permutation $\bar{\pi}_v$, and let $\bar{\pi}'_v$ be a random permutation that returns when in Line 2 of $\pi_v=\bar{\pi}_v$. For any edge $e$ let $q_e$ be the probability that $e$ is the first edge that gets realized in $\bar{\pi}_v$, and $q'_e$ be the probability that $e$ is the first edge that gets realized in  $\bar{\pi}'_v$. We then show that $q'_e = q_e \cdot \frac{\tilde{x}_e}{x_e}$. Assuming that this holds for every permutation $\bar{\pi}_v$, it immediately implies the following and proves the claim.

\begin{align*}
\Pr[ \text{ $e$ is the first edge that is realized in $\pi'_v$}] &= \frac{\tilde{x}_e}{x_e} \cdot \Pr[ \text{ $e$ is the first edge that is realized in $\pi_v$}] \\
&= \frac{\tilde{x}_e}{x_e} \cdot x_e = \tilde{x}_e \,.
\end{align*}

We now have to show that for any fixed permutation $\bar{\pi}_v$, we have $q'_e = q_e \cdot \frac{\tilde{x}_e}{x_e}$. If $e \notin \bar{\pi}_v$, then $q_e=0$. In this case $e$ also does not appear in the permutation $\bar{\pi}'_v$, and we have $q'_e=0$ which clearly satisfies our claim. For an edge $e \in \bar{\pi}_v$, the probability that $e$ is the first realized edge is $q_e= p_e \cdot \prod_{e' \in \bar{\pi}_v : \bar{\pi}_v(e') < \bar{\pi}_v(e)} (1-p_{e'})$. This is because $e$ should get realized, however previous edges in the permutation should not get realized.

Now consider the permutation $\bar{\pi}'_v$. In order for an $e$ to be the first edge that gets realized in $\bar{\pi}'_v$, we should satisfy the following conditions.

* When reaches $e$, it should add $e$ to the permutation. This happens with probability $\frac{\tilde{x}_e}{x_e}$.

* When we query $e$ it should gets realized which happens with probability $p_e$.

* Consider an edge $e'$ such that  $\bar{\pi}_v(e') < \bar{\pi}_v(e)$. Then when reaches $e'$, either $e'$ is not added to the permutation and is not ended in Line 7, or either $e'$ is added to the permutation, but it does not get realized when we query it. Note that the probability that $e'$ gets added to the permutation and does not get realized is $(1-p_{e'}) \cdot \frac{\tilde{x}_{e'}}{x_{e'}}$. Also, the probability that $e'$ does not get added to the permutation, and does not get ended in Line 7 is $(1-p_{e'}) (1- \frac{\tilde{x}_{e'}}{x_{e'}})$. Thus, we satisfy this property for an edge $e'$ with probability

\begin{align*}
(1-p_{e'}) \cdot \frac{\tilde{x}_{e'}}{x_{e'}} + (1-p_{e'}) (1- \frac{\tilde{x}_{e'}}{x_{e'}}) = (1-p_{e'}) \,.
\end{align*}

According to the conditions that we discussed, $q'_e= p_e \cdot \frac{\tilde{x}_e}{x_e} \cdot \prod_{e' \in \bar{\pi}_v : \bar{\pi}_v(e') < \bar{\pi}_v(e)} (1-p_{e'})$. Thus, $q'_e = q_e \cdot \frac{\tilde{x}_e}{x_e}$, and it proves the claim.

§.§ Omitted Proofs of Section 5

Vertex $v$ first draws a random permutation $\pi'_v$ from . Recall that in we first draw a random permutation $\pi_v$ from $\mathcal{D}^{\b x}_v$, and then constructs another random permutation $\pi'_v$ based on it, and returns $\pi'_v$.  Consider any fixed permutation $\bar{\pi}_v$, and let $\bar{\pi}'_v$ be a random permutation that returns when in Line 2 of $\pi_v=\bar{\pi}_v$. Let $q$ be the probability that $v$ remains unmatched by when $e$ is not examined and also $\pi_v = \bar{\pi}_v$. Specifically,

\begin{align*}
q= \Pr [ v \notin \match_1 \ | \ \text{$e$ is not examined} \wedge \pi_v= \bar{\pi}_v ] \,.
\end{align*}

We then show that $q \ge \frac{1-1/e}{2}$. Since this holds for any fixed permutation $\bar{\pi}_v$, it immediately implies the claim. We first define the following definition.

Let $\bar{\pi}_v$ be a fixed permutation, and let $\bar{\pi}'_v$ be a random permutation that returns when in Line 2 of $\pi_v=\bar{\pi}_v$. Suppose that vertex $v$ queries the edges in $\bar{\pi}'_v$ in the same order until we find a realized edge. Then, we say that $\bar{\pi}_v$ “terminates”  when it reaches an edge $e$ if either $e$ is queried and got realized or if gets ended in Line 7 when it reaches $e$.

We now partition the event that $e$ is not examined and $\pi_v= \bar{\pi}_v$ into following disjoint events, and we show that for each of them the probability that $v$ remains unmatched is at least $\frac{1-1/e}{2}$ which shows that $q\ge \frac{1-1/e}{2}$ and proves the lemma.

* The first case that $e$ remains unexamined is when $ e \notin \bar{\pi}_v$. In this case if $\bar{\pi}_v$ does not terminate, then $v$ does not find any realized edge. Thus, it remains unmatched and we are done. Otherwise, we can assume that $\bar{\pi}_v$ terminates when it reaches one of the edges, let's say $e'$. When reaches $e'$, the probability that $e'$ gets added to the permutation and it gets realized is $p_{e'} \cdot \frac{\tilde{x}_{e'}}{x_{e'}}$. It also terminates with the probability $p_{e'}(1-\frac{\tilde{x}_{e'}}{x_{e'}})$ because ends in line 7. Thus, if we condition that $\bar{\pi}_v$ got terminated when it reached $e'$, the probability that $e'$ is proposed by $v$ is

\begin{align*}
\frac{p_{e'} \cdot \frac{\tilde{x}_{e'}}{x_{e'}}}{p_{e'} \cdot \frac{\tilde{x}_{e'}}{x_{e'}}+p_{e'}(1-\frac{\tilde{x}_{e'}}{x_{e'}})} = \frac{\tilde{x}_{e'}}{x_{e'}} \,.
\end{align*}

When $e'=(v,u')$ gets proposed, as we discussed in the proof of lemma <ref>, the probability that $e'$ joins the matching is maximized when $u'$ only has one other edge, let's say $e''$, and $x_{e''} = 1- x_{e'}$. In this case $e'$ joins the matching with the probability of at least $ \big (1/2 + 1/2 (1-g(x_{e''},1) \big)$.  Thus, the probability that $v$ gets matched when $\bar{\pi}_v$ gets terminated when it reaches $e'$ is at most

\begin{align*}
&\frac{\tilde{x}_{e'}}{x_{e'}} \big (1/2 + 1/2 (1-g(x_{e''},1) \big) \\
& = \frac{g(x_{e'},1)}{x_{e'}} \big (1/2 + 1/2 (1-g(1-x_{e'},1) \big)\,.
\end{align*}

It is easy to verify that function $g$ always guarantees that the inequality above is at most $1/2+1/(2e)$. Thus, $v$ remains unmatched with the probability of at least $1/2-1/(2e)$.

* The second case is when $e \in \bar{\pi}_v$, however $\bar{\pi}_v$ gets terminated before reaching $e$.  It is clear that in this case $e$ does not get examined. Let $T= \{e' \in \bar{\pi}_v : \bar{\pi}_v(e') \le \bar{\pi}_v(e) \}$ be the set of edges that are before $e$ in the permutation $\bar{\pi}_v$. Then, we can say that $\bar{\pi}_v$ got terminated reaching one of the edges in $T$. Similar to the previous case, for every edge $e' \in T$, the probability that $v$ remains unmatched when it terminates  reaching $e'$ is at least $1/2-1/(2e)$.

* The third case is when $\bar{\pi}_v$ gets terminated when it reaches $e$. Since we know that $e$ is not examined, then must be ended in Line 7 when it reaches $e$. In this case $v$ does not propose to any vertex, and always remains unmatched.

* The last case is when $\bar{\pi}_v$ does not get terminated before or when it reaches $e$, and also it does not add $e$ to the permutation. In this case all of the edges that are before $e$ in the permutation $\bar{\pi}_v$ should not get realized. Also, $v$ does not examine $e$ as it is not added to the permutation. Let $\bar{\pi}''_v$ be the suffix of $\bar{\pi}_v$ formed by the edges that are after $e$ in the permutation $\bar{\pi}_v$. It is then clear that if we condition on this case, proposals of $v$ have the same distribution as when it runs on $\pi_v = \bar{\pi}''_v$. This reduces this case to the first case, and shows $v$ remains unmatched with the probability of $1/2-1/(2e)$.

We showed that for all cases $v$ remains unmatched with the probability  $\frac{1-1/e}{2}$ which proves the lemma.

First if we $v'=v$, then $Pr[v' \not \curly u\ |\ \text{$e$ is not examined}]=1$ and the claim clearly holds. Thus, the remaining case is when $v' \neq v$. In this case since the proposal of vertices in $A$ are independent, the event $v' \not \curly u$ is independent from the event that $e$ is not examined. Therefore,

\begin{align*}
\Pr[ v' \not \curly u \ | \ X_{v,u'} \ \wedge \ \text{$e$ is not examined}] = \Pr[ v' \not \curly u \ | \ X_{v,u'}] \,.
\end{align*}

Recall that $X_{v,u'}$ is the event that at least one of the vertices in $\pi_{<v}$ proposes to $u'$. We similarly, use $\bar{X}_{v,u'}$ to denote the compliment of this event where none of vertices in $\pi_{<v}$ proposes to $u'$.  We show that $\Pr[ v' \not \curly u] \le \Pr[ v' \not \curly u \ | \ X_{v,u'}]$ by showing that $\Pr[ v' \not \curly u] \ge \Pr[ v' \not \curly u \ | \ \bar{X}_{v,u'}]$. Note that if $v' \in \pi_{<v}$, the event $\bar{X}_{v,u'}$ from the perspective of $v'$ is equivalent to say that $v'$ has not proposed to $u'$, i.e., $v' \not \curly u'$. On the other hand, if $v' \notin \pi_{<v}$ then the event $\bar{X}_{v,u'}$ does not tell us anything about the proposal of vertex $v'$. Thus, we can calculate the probability $\Pr[ v' \not \curly u \ | \ \bar{X}_{v,u'} \ ]$ as follows.

\begin{align}
\Pr[ v' \not \curly u \ | \ \bar{X}_{v,u'}] &= \Pr[ v' \not \curly u\ |\ v' \in \pi_{<v} \wedge \bar{X}_{v,u'}] \Pr[v' \in \pi_{<v} \ | \ \bar{X}_{v,u'}] \nonumber \\
&+ \Pr[ v' \not \curly u\ |\ v' \notin \pi_{<v} \wedge \bar{X}_{v,u'}] \Pr[v' \notin \pi_{<v} \ | \ \bar{X}_{v,u'}] \nonumber \\
&= \Pr[ v' \not \curly u\ |\ v' \not \curly u'] \Pr[v' \in \pi_{<v} \ | \ \bar{X}_{v,u'}] \nonumber\\
\label{eq:vnotubarx}
&+ \Pr[ v' \not \curly u] \Pr[v' \notin \pi_{<v} \ | \ \bar{X}_{v,u'}] \,.
\end{align}

Since vertex $v'$ proposes to at most one of the vertices in $B$, we have

\begin{align*}
\Pr[ v' \not \curly u\ |\ v' \not \curly u'] &= 1- \Pr[ v' \curly u\ |\ v' \not \curly u'] \\&= 1- \frac{\Pr[v' \curly u]}{\sum_{u'' \in B} \Pr [ v' \curly u'' ]- \Pr[v' \curly u']} \\&\ge  1- \Pr[v' \curly u] \\&= \Pr[v' \not \curly u]
\end{align*}

Using the inequality above and (<ref>), we have

\begin{align*}
\Pr[ v' \not \curly u \ | \ \bar{X}_{v,u'}] &= \Pr[ v' \not \curly u\ |\ v' \not \curly u'] \Pr[v' \in \pi_{<v} \ | \ \bar{X}_{v,u'}]\\
&+ \Pr[ v' \not \curly u] \Pr[v' \notin \pi_{<v} \ | \ \bar{X}_{v,u'}]  \\
&\ge \Pr[ v' \not \curly u] \Pr[v' \in \pi_{<v} \ | \ \bar{X}_{v,u'}]\\
&+ \Pr[ v' \not \curly u] \Pr[v' \notin \pi_{<v} \ | \ \bar{X}_{v,u'}] \\
& = \Pr[ v' \not \curly u] \,.
\end{align*}

This show that $\Pr[ v' \not \curly u] \ge \Pr[ v' \not \curly u \ | \ \bar{X}_{v,u'}]$. As a direct result, $\Pr[ v' \not \curly u] \le \Pr[ v' \not \curly u \ | \ X_{v,u'}]$ which proves the claim.

§.§ Omitted Proofs of Section 6

By taking the derivative of $\frac{g(x,\ubar)}{x}$ w.r.t. $x$ we get the following

\begin{align*}
\frac{\odv}{\odv x} \frac{g(x,\ubar)}{x} =
\frac{\odv}{\odv x} \frac{(e^\ubar-1)(\ubar  -x)}{\ubar (e^\ubar- e^x)}  = - \frac{(e^{\ubar}-1)(e^{\ubar}+ e^x (x-1-\ubar))}{\ubar (e^{\ubar}-e^{x})^2} \,.
\end{align*}

We show that the derivative above is negative for $0 \le x < \ubar$ which implies that the function is strictly decreasing. For an $0 \le x < \ubar$ we always have $e^{x}(x-1-\ubar) > -e^{\ubar}$. This implies that $(e^{\ubar}+ e^x (x-1-\ubar)) >0$ for $0 \le x < \ubar$, and the derivative taken above is negative $0 \le x < \ubar$.

We first show the following claim.

Let $a,b \in \mathbb{R}_+^2$ be real numbers such that $a+b \le 1$ and $a \ge b$. Also, let $\delta$ a any non-negative real number, i.e., $\delta \ge 0$. Then,

\begin{align*}
(1-(a+\delta)) (1- (b-\delta)) \le (1-a)(1-b) \,.
\end{align*}

By expanding the left hand side of the desired inequality we get

\begin{align*}
(1-(a+\delta)) (1- (b-\delta)) &= 1- a - b + (a+\delta) (b-\delta) \\
&= 1- a - b + a \cdot b +\delta( b-a - \delta) \,.
\end{align*}

Since $a \ge b$ and $\delta \ge 0$, we have $b-a-\delta \le 0$. Thus,

\begin{align*}
(1-(a+\delta)) (1- (b-\delta)) &= 1- a - b + a \cdot b +\delta( b-a - \delta) \\
&\le  1- a - b + a \cdot b = (1-a)(1-b) \,,
\end{align*}

which proves the claim.

Let $a_1, a_2, \cdots, a_k \in [0,c]^k$ be $k$ real numbers in $[0,c]^k$. Suppose that there are two numbers $a_i$ and $a_{i'}$ in this sequence such that $0<a_i \le a_{i'} <c$. Then we create  a new sequence $a'_1, a'_2, \cdots, a'_k$ where $a'_j = a_j$ if $j \notin \{i,i'\}$, $a'_i=\max\{0,a_i+ a_{i'}- c\}$ and $a'_{i'}=\min\{c, a_i+a_{i'} \}$. It is clear that $\sum_{i=1}^k a_i= \sum_{i=1}^k a'_i$. Then by the claim above we have  $\prod_{i=1}^k (1- a_i) \ge \prod_{i=1}^k (1- a'_i)$. Therefore the term $\prod_{i=1}^k (1- a_i)$ is minimized when at most one of the $a_i$'s are not equal to $c$ or $0$. In other words,

\begin{align*}
\prod_{i=1}^k (1- a_i) \ge (1-c)^{q} \cdot (1- (s- c \cdot q)) \,,
\end{align*}

where $q = \lfloor \frac{s}{c} \rfloor$. We then claim that $1-(s- c \cdot q) \ge (1-c)^{\frac{s}{c}-q}$. First we show how this completes the proof the lemma. Assuming that aforementioned inequality holds, we have

\begin{align*}
\prod_{i=1}^k (1- a_i) &\ge (1-c)^{q} \cdot (1- (s- c \cdot q)) \\
&\ge (1-c)^{q} \cdot (1-c)^{\frac{s}{c}-q} \\
&=(1-c)^{\frac{s}{c}} \,,
\end{align*}

which is the desired bound in the lemma. Therefore, it is remained to show that $1-(s- c \cdot q) \ge (1-c)^{\frac{s}{c}-q}$. To prove this we use the following inequality: For any $ 0 \le x \le 1$ and $0 \le p \le 1$, we have $(1-x)^p \le 1- p \cdot x$.  Note that $\frac{s}{c}-q = \frac{s}{c}- \lfloor \frac{s}{c} \rfloor  < c \le 1$. Therefore, using the mentioned inequality we can say that $(1-c)^{\frac{s}{c}-q} \le 1- (c \cdot (\frac{s}{c}-q)) = 1-(s- c \cdot q)$ which completes the proof.

We show that $\gm(\tau) < \tau$ for $3/4 \le \tau \le 1$ which immediately implies the claim. By the definition of $\gm (.)$ function,  $\gm(\tau)$ is the smallest real number $x$ such that $\frac{g(x',1)}{x'} \le \tau$ for any $x' \ge x$. Let $y=0.74$, we show that $\frac{g(y,1)}{y} \le 3/4$. This and the fact that $\frac{g(x,1)}{x}$ is a decreasing function implies that  $\gm(\tau) \le y < \tau$ for $3/4 \le \tau \le 1$ and proves the claim.

It is now remained to show that $\frac{g(y,1)}{y} \le 3/4$. By substituting function $g$ we get

\begin{align*}
\frac{g(y,1)}{y} &= \frac{(1-1/e)(1-y)}{1-e^{y-1}} \approx 0.718 \le 3/4 & \text{$y$=0.74}
\end{align*}

Recall that  $\rho(\tau)$ is the largest positive real value $x \in (0,1]$ such that $x \le 1-(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)}$. Thus, to show that $\rho(\tau) <1 $ it is enough to show that $1-(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{1}{\gm(\tau)}\big)} < 1$. For $3/4 \le \tau \le 1$, by Claim <ref> we have $\frac{\gm(\tau)}{\tau} <1$. Also, $\gm (\tau) >0 $ for $\tau <1$. Therefore, $(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{1}{\gm(\tau)}\big)} >0 $, and $1-(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{1}{\gm(\tau)}\big)} < 1$ which proves the claim.

First we claim that for $0.31719 \le \gm (\tau) \le 0.3172$ for $\tau=0.8723$. This can be easily verified as $\frac{g(0.3172,1)}{0.3172} \approx 0.872296 < \tau$ and $\frac{g(0.31719,1)}{0.31719} \approx 0.8723003 > \tau$. Recall that  $\rho(\tau)$ is the largest positive real value $x \in (0,1]$ such that $x \le 1-(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)}$. In other words, it is the largest $x$ such that $x - 1 +(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)} \le 0$. Using the lower and upper bounds that we derived for $\gm$, and by setting $x=0.5303$ we get

\begin{align*}
&x - 1 +(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)}\\
&\ge x-1+ (1-\frac{0.3172}{\tau})^{\big(\frac{x}{0.31719}\big)}\\
&\approx 6.3 \cdot 10^{-7} >0  \,. & \text{By setting $x=0.5303$ and $\tau=0.8723$}
\end{align*}

Therefore, for $x=0.5303$ we have $x - 1 +(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)} >0 $. We claim that for any $x'>x$ we also have $x' - 1 +(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x'}{\gm(\tau)}\big)} >0$ which immediately implies that $\rho(\tau) \le x =0.5303$ and proves the claim. To prove this we take the derivative of $x - 1 +(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)}$ and show it is always positive for $x \ge 0.5303$. By taking the derivative of the discussed function we get

\begin{align*}
&\frac{\odv}{\odv x} \bigg(x - 1 +(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)} \bigg) \\
& = 1+ \frac{(1-\frac{\gm(\tau)}{\tau})^{\big(\frac{x}{\gm(\tau)}\big)} \cdot \ln (1- \frac{\gm(\tau)}{\tau})}{\gm(\tau)} \\
& \ge 1+ \frac{(1-\frac{0.31719}{\tau})^{\big(\frac{x}{0.3172}\big)} \cdot \ln (1- \frac{0.31719}{\tau})}{0.31719} & \text{Since $0.31719 \le \gm (\tau) \le 0.3172$} \\
& \ge 1+ \frac{(1-\frac{0.31719}{\tau})^{\big(\frac{0.5303}{0.3172}\big)} \cdot \ln (1- \frac{0.31719}{\tau})}{0.31719} & \text{The second term is increasing w.r.t $x$ and $x \ge 0.5303$} \\
&\approx 1- 0.6693 >0 \,.
\end{align*}

This completes the proof of the claim.

§ THE TRANSFORMATION FUNCTION $G(X_E, \UBAR)$

In this section, we discuss how the transformation function $g$ has been derived. We show that function $g$ is the only function that satisfies the following two properties.

* Function $g$ should not change the $x_e$ when $x_e$ is arbitrary small, i.e., for every $\sigma \in [0,1]$, we should have $\lim_{x_e \rightarrow 0} g(x_e, \ubar) = x_e$.

* Consider an edge $e=(v,u)$, and let $e'_1, e'_2, \cdots, e'_k$ be other edges incident to $u$. As we discussed we always add dummy edges to the vertices $B$, such that $x_u = \ubar$ for every $u \in B$ where $x_u \leftarrow \sum_{e \ni u} x_e$. Another crucial property that we want to satisfy is that when $k$ approaches infinity and $x_{e'_i}$ is arbitrary small for each $e'_i$, then algorithm matches $e$ exactly with probability $\frac{(1-e^{-\ubar})x_e}{\ubar}$. Let $\match_1=$$G, \b{x}, \sigma$ and $x_{e'_i} = \frac{\ubar - x_e}{k}$, then we want to satisfy the following property.

\begin{align*}
\lim_{k \rightarrow \infty} \Pr [ e \in \match_1 ] = \frac{(1-e^{-\ubar})x_e}{\ubar} \,.
\end{align*}

Now we show that

$$g(x, \ubar) = \frac{(e^\ubar-1)(\ubar  -x) x}{\ubar (e^\ubar- e^x)}$$

is the unique function that satisfies these two properties.

Consider second desired property and an edge $e=(v,u)$. Then matches $e$ whenever it gets proposed and none of the edges $e'_i$ that are before $e$ in $\pi$ gets proposed. Let $\delta= \ubar - x_e$. Then in the second property for every other edge $e'_i$ incident to $u$ we have $x_{e'_i}= \frac{\delta}{k}$.  We then have,

\begin{align*}
\Pr[e \in \match_1] &= \Pr[e \text{ is proposed}]\sum_{i=0}^k\Pr[\text{There are } i \text{ edges before } e \text{ in  } \pi \wedge \text{none of them are proposed}]
\\&= g(x_e)\times \left(\sum_{i=0}^{k}\frac{1}{k+1} \left(1-g\left(\delta/k\right)\right)^i\right) \,.
\end{align*}

The probability of $e \in \match_1$ when $k \rightarrow \infty$ is then equal to

\begin{align*}
\lim_{k \rightarrow \infty} \Pr[e \in \match_1]= g(x_e, \ubar)\times \lim_{k\rightarrow \infty}\left(\sum_{i=0}^{k}\frac{1}{k+1} \left(1-g\left(\delta/k\right)\right)^i\right) \,.
\end{align*}

Note that when $k$ approaches infinity, $\delta/k$ approaches $0$. Therefore, by the first desired property of function $g$ we should have $\lim_{k \rightarrow \infty} g(\delta/k, \ubar) = \delta/k$. Thus,

\begin{align*}
&\lim_{k \rightarrow \infty} \Pr[e \in \match_1]= g(x_e,\ubar)\times \lim_{k\rightarrow \infty}\left(\sum_{i=0}^{k}\frac{1}{k+1} \left(1-\left(\delta/k\right)\right)^i\right)
\\& = \frac{g(x_e, \ubar)}{k}\times \lim_{k \rightarrow \infty}\left(\sum_{i=0}^{k} \left(1-\left( \delta/k \right)\right)^i\right)
\\&= g(x_e, \ubar)\times \lim_{k \rightarrow \infty} \left( \sum_{i=0}^{k} \frac{e^{-i\delta/k}}{k} \right)
\\ & =  g(x_e, \ubar)\times \frac{1-e^{-\delta}}{\delta} \,. & \text{By (\ref{eq:integrate})}
\end{align*}

Recall that the second desired property of function $g$ is $\lim_{k \rightarrow \infty} \Pr [ e \in \match_1 ] = \frac{(1-e^{-\ubar})x_e}{\ubar}$. According to the probability above, in order to satisfy this property we should have

\begin{align*}
&g(x_e, \ubar)= \frac{\delta (1- e^{-\sigma}) x_e}{\sigma (1-e^{-\delta})} \\
&=  \frac{(\ubar - x_e) (1- e^{-\sigma}) x_e}{\sigma (1-e^{x_e - \ubar})} \\
&=  \frac{(e^\ubar-1)(\ubar  -x_e) x_e}{\ubar (e^\ubar- e^{x_e})} \,.
\end{align*}

§ THE PRICE OF INFORMATION (POI)

In this section, we discuss how our techniques can be used to beat $(1-1/e)$ approximation for the matching constraints in the price of information (PoI) model. In this problem, we are given a set of edges $E$ and a feasibility system $\mathcal{F} \subseteq 2^E$. Here we assume that the feasibility set $\mathcal{F}$ is the set of all valid matchings in $E$. For each edge $e \in E$, we are also given a search cost $c_e \in \mathbb{R}^+$ and a distribution $F_e$ for the value of the edge. An algorithm can query an edge to realize its valuation $v_e$ from the distribution $F_e$, the algorithm then has to pay the cost $c_e$.  Let $S$ be the set of edges queried by the algorithm then the utility of an algorithm is equal to  $\max_{\match \in S: \match \in F} \sum_{e \in \match} v_e- \sum_{e \in S} c_e$. The goal is to maximize the expected utility.

In comparison to the query commit model, the POI problem has search costs, however it does not require commitment to the queried edges. Gamlath et al.  [15] provides a method to reduce the matchings in PoI to the stochastic matching problem with query commitment. Their method finds a threshold $\chi_e$ for each edge, and then changes the weight of every edge to $\kappa_e=\min\{v_e, \chi_e\}$.

Without loss of generality, assume that the $\kappa_e$ is discrete. Let $K_e$ be the set of all possible values of $\kappa_e$, their approach replaces every edge with an edge-value pair $(e,v)$ where $v \in K_e$, and they derive the LP below.

\begin{align}
\nonumber \max_{(e,v) \in E_{\text{all}}} x_{e,v} \cdot v	\,& \\
\nonumber \textrm{s.t.} \qquad & \sum_{(e,v) \in F} x_{e,v} \le f(F)& \forall u \in A \cup B,  \forall F \subseteq E_u  \\
\nonumber &x_{e,v} \ge 0& \forall (e,v) \in E_{\text{all}}
\end{align}

Where $f(F)$ is the probability that $\kappa_e = v$ for at least one edge-pair value $(e,v) \in F$.
They show that there is a distribution $\mathcal{D}$ for every vertex in $B$ such that it picks an edge $e$ that has the value $v$ with probability $x^*_{e,v}$.

Consider the analogous of our algorithm using their reduction. It can be verified that our approach beats the $(1-1/e)$ approximation by a constant if $|K_e|=O(1)$, i.e., when each discrete distribution takes constant number of possible values. Apply our transformation function to get modified solution $\tilde{x}_{e,v}= g(x_{e,v}, \sigma)$, and let $\tau$ be a constant very close to $1$. Consider running our two-round algorithm for this modified solution. It beats the $(1-1/e)$ approximation if at least a constant fraction of the optimal solution is available at the second round. As discussed the edges that do not proceed to the second round are the edges with almost $\tilde{x}_{e,v}/p_{e,v}=1$. Suppose that almost of the contribution of the optimal solution is among these edges. Now suppose that we run our one-round algorithm for only these edges. The algorithm beats $(1-1/e)$ approximation if for every vertex in $B$ the summation of its incident edges $\sum_{(e,v)} x_{e,v}$ is less than one. For the stochastic matching problem this was true because of the constraint (<ref>) of LP. The same fact holds if $|K_e|=O(1)$ beating the $(1-1/e)$ approximation. However, the same claim does not hold when $K_e$ is very large. For example suppose that we have a graph with a single edge $e$, and the $\kappa_{e}$ is uniform over $[0,c]$ where $c$ is a very large constant. Then, in the discretization of the distribution we get a lot of small discrete parts. Then, in the solution of LP $x_{e,v}$ would be small values bounded by $p_{e,v}$. Since $x_{e,v}$ is small for these edges, our transformation function almost does not change them and we have $\tilde{x}_{e,v} \approx x_{e,v}$. So the value of $\tilde{x}_{e,v}/p_{e,v}$ is larger than $\tau$ for these edges. However, the summation $\sum_{(e,v)} x_{e,v}$ can be also $1$, since in the distribution $\kappa_e$ it is guaranteed that one of the edge-value pairs gets realized.