Beating Greedy for Stochastic Bipartite Matching
Buddhima Gamlath Sagar Kale Ola Svensson



 


Beating Greedy for Stochastic Bipartite Matching
    
   Buddhima Gamlath 

   EPFL

  
     Sagar Kale 

  EPFL

   
     Ola Svensson 

  EPFL

   
 
    
======================================================================================================




  We consider the maximum bipartite matching problem in stochastic settings,
  namely the query-commit and price-of-information models.    In the
  query-commit model, an edge e independently exists with probability p_e.
  We can query whether an edge exists or not, but if it does exist, then we
  have to take it into our solution.  In the unweighted case, one can
  query edges in the order given by the classical online algorithm of Karp,
  Vazirani, and Vazirani <cit.> to get a (1-1/e)-approximation.
  In contrast, the previously best known algorithm in the weighted case
  is the (1/2)-approximation achieved by the greedy algorithm that sorts the
  edges according to their weights and queries in that order.  
  
  Improving upon the basic greedy, we give a (1-1/e)-approximation algorithm
  in the weighted query-commit model.  We use a linear program (LP) to upper
  bound the optimum achieved by any strategy. The proposed LP admits several
  structural properties that play a crucial role in the design and analysis of
  our algorithm.  We also extend these techniques to get
  a (1-1/e)-approximation algorithm for maximum bipartite matching in the
  price-of-information model introduced by Singla <cit.>, who also
  used the basic greedy algorithm to give a (1/2)-approximation. 




§ INTRODUCTION


Maximum matching is an important problem in theoretical computer science.  We
consider it in the query-commit and price-of-information models.  These settings
model the situation where the input is random, but we can know a specific part
of the input by incurring some cost, which is explicit in the
price-of-information setting, i.e., pay π_e to know the weight of the edge
e, and implicit in the query-commit, i.e., the algorithm queries existence of
e, and if e exists, the algorithm has to take e into its solution.  We
formalize this now.  In the query-commit model, an edge e independently exists
with probability p_e.  We can query whether an edge exists or not, but if it
does exist, then we have to take it into our solution (hence the name
query-commit).  So, specifically, for the matching problem, if M is our
current matching, then we cannot query an edge e if it intersects with M.
In the price-of-information model introduced by Singla <cit.>, edge
weights are random variables and we can query for the weight W_e of an edge
e by paying a (fixed) cost π_e.  We want to query a set Q of edges and
output a matching M ⊆ Q such that W(M) - ∑_e∈ Qπ_e is
maximized. 

In the query-commit model, for bipartite graphs, one can query edges
in the order given by the classical algorithm of Karp, Vazirani, and
Vazirani <cit.> to get a (1-1/e) approximation.  However, in the more
general weighted query-commit setting where an edge e exists with weight
w_e with probability p_e and does not exist with probability 1-p_e, it is
not clear how to use such a strategy. In fact, prior to our work, the best algorithm for the weighted setting was the basic greedy that sorts the edges by
weight w_e and then queries in that order to get a (1/2)-approximate matching.  Similarly, in
the price-of-information setting, Singla gave a (1/2)-approximation algorithm
based on the greedy approach. 
In this work, we beat the greedy algorithm using
new techniques and give clean algorithms that achieve an approximation ratio of
1-1/e (improving from 1/2) in the settings of weighted query-commit as well
as price-of-information. A key component of our approach is to upper bound the optimum achieved by any strategy using a linear program (LP), and exploit several structural properties of this LP in the design of our algorithms. We now give a high level description of these techniques.



 §.§ Techniques

We first solve the weighted query-commit version, and this part of the paper
contains the essential ideas.  We then expand on these ideas to solve the
price-of-information version[Actually, we implicitly use
  “multiple-weight query-commit” as an intermediate step, where an edge has
  nonnegative random weight, and an algorithm can ask queries of the form “is
  weight of e greater than c,” and if it is, then the algorithm has to add
  e to its solution.  Then we use a reduction by Singla to reduce from
  price-of-information.].  Let us first focus on the weighted query-commit
setting.  Here, the input is a bipartite graph G = (A, B, E), and for each
e ∈ E, its existence probability p_e and weight w_e.  Our goal is to
design a polynomial-time algorithm that gives a sequence of edges to query such
that after the last query, we end up with a matching of large weight.  First, to
get a handle on the expected value of an optimum strategy (), consider the
linear program (LP) below.  For a vertex u, let E_u be the set of edges
incident to u.

    Maximize       ∑_e ∈ E x_e · w_e, 
       subject to       ∑_e ∈ F x_e       -60mu≤[an edge
                                                    in F exists] ,
                                 for all  u ∈ A ∪ B  and for all  F ⊆ E_u ,
             35mux_e       -60mu≥ 0  ,       for all  e ∈ E .

Let x'_e be the probability that  solution contains e.  Since 
can have at most one edge incident to u, for any F⊆ E_u, the events
in {contains e : e∈ F } are disjoint.  Hence,
∑_e ∈ F x'_e is the probability that  contains an edge in F,
which must be at most the probability that at least one edge in F exists.
Therefore, (x'_e)_e∈ E has to satisfy the above LP.  We can solve this LP
in polynomial time using a subdmodular-function-minimization algorithm as a
separation oracle for the ellipsoid algorithm.  Let 𝐱^∗ be the
solution.  For a u ∈ A, if we restrict 𝐱^∗ to E_u to get,
say, 𝐱^∗_u, we can write 𝐱^∗_u as a convex
combination of extreme points of the polytope

    {x ∈^E_u_+ :  ∑_e∈ F x_e ≤[
      an edge in F exists]   ∀ F⊆ E_u} .


 
A key part of our approach is the nice structural properties of extreme points: 
the subsets corresponding to the tight constraints for an
extreme point  of the above polytope form a chain over a subset of E_u,
because the right hand side of the constraints is strictly submodular.  For a
, if we query the edges in the order given by its chain 
then it can be proved that we commit to an edge e ∈ E_u with probability
_e.  Since 𝐱^∗_u can be written as a convex combination of
such extreme points, if we select an extreme point with probability equal to its
coefficient in the convex combination and query the edges in the order given by
its chain, we commit to an edge e ∈ E_u with probability
𝐱^∗_e.  See <Ref>.  But if we do this independently
for each vertex in A, then we end up with collisions on B, so we have to do
contention resolution there.  Effectively, for each vertex in v∈ B, its
neighbor u arrives independently with probability 𝐱^∗_uv and
weight w_uv, and it has to pick one neighbor so that its expected utility is
close to ∑_uv𝐱^∗_uv· w_uv.  This setting is similar
to the prophet secretary problem, and we extend the ideas of Ehsani et
al. <cit.> to achieve this.

To generalize this from two-point distributions to multi-point distributions, we
think of an edge e to have as many copies as the values its weight can take.
But now instead of being independent, the existence of these copies is correlated.
To handle this, we write a more general LP with constraints corresponding to
sets that are from a lattice family.  We can solve
submodular-function-minimization over a lattice family in polynomial
time <cit.>, which gives us a separation oracle for this LP.
Also, the extreme points of the polytope defined by constraints for a
left-hand-side vertex correspond to a chain with properties similar to the
two-point-distribution case (see <Ref>).

Once we have a query-commit algorithm for multi-point distributions, we can basically get
a price-of-information algorithm by a clean reduction <cit.>: for each edge
e with weight given by the random variable X_e and probing cost π_e, let
τ_e be the solution to the equation [max{(X_e - τ_e),0}] = π_e,
and let Y_e = min(X_e, τ_e) be a new random variable.  Now run the
query-commit algorithm with Y_e, and whenever the algorithm queries any copy
of the edge e, we probe e, and  we only pay π_e the first time we probe that edge. 



  §.§.§ Organization of the Paper


Next, we review the related work.  In <Ref>, we see the weighted
query-commit algorithm; we then extend it to the price-of-information setting
in <Ref>.



 §.§ Related Work



As mentioned earlier, the algorithm of Karp et al. gives a (1 - 1/e) = 0.632
approximation in the unweighted query-commit model for bipartite graphs.
Costello et al. <cit.> give a 0.573-approximation for general
graphs and show that no algorithm can give an approximation better than 0.898 compared to the optimal offline algorithm (that knows all the outcomes before selecting the matching).

Motivated by applications in kidney exchange and online dating, Chen et
al. <cit.> consider the matching problem in the query-commit model
with further constraint that for each vertex v, the algorithm can query at
most t_v edges incident to it (t_v is a part of the input) and give a
(1/4)-approximation algorithm.  Bansal et al. <cit.> improve it to
(1/3) for bipartite graphs and to (1/3.46) for general graphs, and also give
a (1/4)-approximation in the weighted query-commit (for general graphs); both
of these ratios for the unweighted case are further improved by Adamczyk et
al. <cit.>, who give a (1/3.709)-approximation for general graphs.
Baveja et al. <cit.> improve this to 1/3.224.  We mention that this
setting is more general than the setting we consider, because t_v = (v)
for us, i.e., we do not put any restriction on the number of edges incident to a
vertex that we can query.

Molinaro and Ravi <cit.> give an optimal algorithm for a very
special class of sparse graphs in the unweighted query-commit setting.

Blum et al. <cit.> consider the maximum matching problem, where, in the
input graph, an edge e exists with probability p_e, the algorithm can query
the existence of an edge and does not have to commit, but needs to minimize the
number of queries subject to outputting a good approximation.  This model is considered in several follow-up
works <cit.>.



  §.§.§ Further Related Work in Other Stochastic Models

Feldman et al. <cit.> consider an online variant of stochastic
matching where the algorithm gets as input a bipartite graph G=(A,B,E), and a
distribution 𝒟 over B, and n elements are drawn i.i.d from B
according to 𝒟 (so there may be repetitions) that the algorithm
accesses online.  When a copy v ∼𝒟 arrives online, we have to
match it to an unmatched vertex u in A such that {u,v}∈ E.  Note that
here the existence of an edge is not random in itself but that of a vertex is.
Again, Karp et al.'s algorithm gives a (1 - 1/e)-approximation, and Feldman et
al. give a 0.67-approximation.  Significant amount of work has been done on this variant as well <cit.>.

We would like to mention the works of Dean et al. <cit.>, where they consider
stochastic problems where cost of an input unit is only known as a probability
distribution that is instantiated after the algorithm commits to including the
item in the solution.  Charikar et al. <cit.> and Katriel et
al. <cit.> consider two stage optimization problems, where the first
stage is stochastic with a lower cost for decisions, and in the second stage,
with an increase in the decision cost, the actual input is known.










§ A WEIGHTED QUERY-COMMIT ALGORITHM



In this section, we present a (1 - 1/e)-approximation algorithm for the 
maximum weight bipartite matching problem () in the model. 

Let G=(A, B, E, w) be a weighted bipartite graph with |A| = |B| = n,
where each edge e ∈ E has weight w(e) and exists independently with 
probability[Alternatively, one may think of the weight of an 
edge e as an independent random variable that takes value w(e) with 
probability p_e and value zero with probability 1 - p_e. 
We consider a more general distribution of edge weights in 
Section <ref>.] p_e.
Let _e be the indicator variable for the event that edge e exists 
(i.e., _e = 1 if and only if edge e exists).
The actual value of _e can only be determined by querying edge e to 
check whether it exists or not. 
Given such a graph G, a algorithm for (adaptively) 
queries a sequence of edges Q = (e_q_1, …, e_q_m) and outputs a 
valid matching M ⊆ Q.
Since a algorithm is committed to add any queried edge 
that exists to its output, M = { e ∈ Q: _e = 1}.  

Let 𝒜 be a algorithm for and let 
M(𝒜) denote its output on input G.
We define the expected utility of 𝒜,
(𝒜) :=  [ ∑_e ∈ M(𝒜) w(e) ]
to be the expected weight of its output matching, where the expectation is 
over the randomness of the existence of edges and any internal randomness 
of the algorithm.
Let = max_𝒜(𝒜), where the maximum is 
taken over all algorithms[We remark that our approximation guarantee in the query-commit model also works with respect to the stronger offline adversary that knows all outcomes before selecting the matching. We have presented it in this way as the guarantees in the price-of-information model are of this type.], be the optimal expected utility.
We give a algorithm whose expected utility
() is at least (1 - 1/e).

As described in the introduction, our approach consists of two stages. 
First, we solve a linear program to bound the optimal expected utility .
For each edge e ∈ E we associate a variable x_e, which we think of as 
the probability that an optimal algorithm adds edge e to its output. 
We set our LP constraints on x_e variables to be those that must be 
satisfied by any algorithm that outputs a valid matching formed only 
of edges that exist.
Then the optimal expected utility is upper bounded by the maximum of the 
weighted sum ∑_e ∈ E x_e · w(e) subject to our LP constraints.

Then, we use the structural properties of our LP polytope to define
a distribution over the permutations of edges and use this distribution
to set the query order in our algorithm.
For this, we first define distributions a over the permutations 
of neighboring edges for each vertex a ∈ A such that the following holds:
If we draw a random permutation σ_a 
from a for each a ∈ A, query edges in the order of σ_a, and finally 
add to our output the first edge in σ_a that exists, then the expected 
utility is optimal.
However, the output is not guaranteed to be a matching, because it might have
more than one edge incident to a vertex in B (i.e., collisions).

To deal with the issue of collisions in B, we view the problem as 
a collection of prophet secretary problem instances that has an 
instance for each vertex b ∈ B. 
In the prophet secretary problem, we have one item to sell (position to 
be filled) and a set of buyers (secretaries) arrive in a random order.
Each buyer makes a take it or leave it offer to buy the item at some 
random price (or each secretary has some random skill level) whose 
distribution we know beforehand, and we are interested in maximizing the 
profit (or hiring the best secretary).

In their recent work,
Ehsani et al. <cit.> gave a (1 - 1/e)-competitive algorithm 
for the prophet secretary problem. 
Inspired by this result, we design our algorithm so that for each b ∈ B, 
it recovers at least (1 - 1/e)-fraction of the expected weight of the edge
incident to b in an optimal algorithm's output. 
To elaborate, we pick a uniformly random permutation of the vertices in A 
and treat them as buyers arriving at uniformly random times. 
Then, as seen from the perspective of a fixed vertex (i.e. an item) b ∈ B, 
buyers make a one-time offer with random values (corresponding to weights of edges incident to b), and
our algorithm uses dynamic thresholds that depend on arrival times to
make the decision of whether to sell the item at the offered price or not. 
One may view our algorithm as running the (1 - 1/e)-competitive 
prophet secretary algorithm in parallel for each of the vertices in B, but the
way we set the dynamic thresholds is different.

The rest of this section is organized as follows:
In Section <ref>, we describe how to upper bound  using an LP.
In Section <ref>, we analyze the structure of 
the LP polytope  and show how to construct the distributions a 
for each a ∈ A.
Finally in Section <ref>, we present our proposed 
algorithm and adapt the ideas of 
Ehsani et al. <cit.> to analyze its approximation guarantee.



 §.§ Upper-bounding the optimal expected utility



For each vertex u ∈ A ∪ B, let u denote the set of edges 
incident to u.
For a subset of edges F⊆ E, let f(F) be the probability that at 
least one edge in F exists, 
then f(F) = 1 - ∏_e ∈ F(1 - p_e), because each edge e exists
independently with probability p_e.

Fix any algorithm 𝒜.
For each edge e ∈ E, let x_e be the probability that 𝒜 
outputs e. 
Consider a vertex u ∈ A ∪ B and a subset F ⊆u.
Since 𝒜 outputs a valid matching, the events that edge e being 
added to the output of 𝒜 for each e ∈ F are disjoint, and 
hence the probability that 𝒜 adds one of the edges in F to its 
output is ∑_e ∈ F x_e. 
But, for an edge to be added to the output, it must exist in the first place,
and thus it must be the case that ∑_e ∈ F x_e ≤ f(F) (because 
f(F) is the probability that at least one edge in F exists). 
Therefore, 𝐱 = (x_e)_e ∈ E is a feasible solution to 
the following linear program, which we call .  So, the expected utility
(A) of 𝒜 is at most the value of , which implies
Lemma <ref> below.

    Maximize       ∑_e ∈ E x_e · w(e), 
       subject to       ∑_e ∈ F x_e       -100mu ≤ f(F)  ,
                        	       for all  u ∈ A ∪ B  and for all  
                        			F ⊆u , 
             35mux_e  	      -100mu ≥ 0  , 
    	 									       for all  e ∈ E .


 
The optimal expected utility, , is upper bounded by the 
value of .




 §.§ Structure of the LP and its implications



Although  has exponentially many constraints, we can solve it in
polynomial time.

 
The linear program  is polynomial-time solvable.



Observe that for a fixed vertex u ∈ A ∪ B, the constraints 
∑_e ∈ F x_e ≤ f(F) for all F ⊆u, can be 
re-written as 0 ≤ g_u(F) for all F ⊆u, where 
g_u(F) = f(F) - ∑_e ∈ Fx_e is a submodular function (notice that 
f is submodular because it is a coverage function while ∑_e ∈ Fx_e 
is clearly modular).
Thus we can minimize g_u over all subsets of u for all 
u ∈ A ∪ B in polynomial time using O(n) submodular minimizations 
to find a violating constraint.
If none of the minimizations gives a negative value and if x_e ≥ 0 
for all e ∈ E, then the solution is feasible.
Thus we can solve  in polynomial-time using the ellipsoid method.


For the rest of this section, we assume that 0 < p_e < 1 for all e ∈ E.
We can safely ignore those edges e ∈ E for which p_e = 0, 
and for those with p_e = 1, we can scale down the probabilities (at a small
loss in the objective value) due to the following lemma.

 
Let p̃_e = (1 - γ) p_e for all e ∈ E, and for 
a subset F ⊆ E, let f̃(F) = 1 - ∏_e ∈ F(1 - 
p̃_e)  be the probability that at least one edge in F exists 
under the scaled down probabilities p̃_e.
If we replace f(F) in  by f̃(F), the value of the resulting 
LP is at least (1 - γ) times the value of .



Fix a set F ⊆ E and label the edges in F from 1 through |F|. For i = 1, …, |F|, let Q_i = 1 - ∏_e = 1^i(1 - p_e) and let Q̃_i = 1 - ∏_e = 1^i(1 - p̃_e). Then, for i > 1 we have that
Q_i = Q_i-1 + p_i(1 - Q_i-1), and similarly, Q̃_i = Q̃_i-1 + p̃_i(1 - Q̃_i-1). By definition, we have f(F) = Q_|F| and f̃(F) = Q̃_|F|.
We now prove that Q̃_i≥ (1 - γ) Q_i for i = 1, …, |F| by induction. 

For the base case, we have Q̃_1 = (1 - γ)Q_1. Notice that, by the definition of p̃_i's, we have Q_i ≥Q̃_i. Thus, for i > 1 we have that

    Q̃_i    = Q̃_i-1 + p̃_i(1 - Q̃_i-1)  
       ≥ (1 - γ) Q_i-1 + (1 - γ)p_i(1 - Q̃_i-1)          (by inductive hypothesis)
       ≥(1 - γ) Q_i-1 + (1 - γ)p_i(1 - Q_i-1)          (because Q_i-1≥Q̃_i-1)
       = (1 - γ)(Q_i-1 + p_i(1 - Q_i-1)) = (1 - γ) Q_i.

	
Thus if we scale down the polytope defined by the constraints of 
 by a factor of (1 - γ), the resulting polytope is contained 
inside the polytope defined by f̃(F) constraints. 
Moreover, all extreme points of both the polytopes have non-negative 
coordinates and the objective function has non-negative coefficients.
Hence the claim of Lemma <ref> follows.



The expected utility of our proposed algorithm is 
(1 - 1/e) ·^∗≥ (1 - 1/e) ·, where ^∗ 
is the optimal LP value of .
Thus, in the cases where the assumption p_e < 1 for all e ∈ E does 
not hold, we can scale the probabilities down by (1 - γ), and 
consequently the guarantee on expected utility will at least be 
(1 - γ)(1 - 1/e) · due to Lemma <ref>. 
We can choose γ to be arbitrarily small.
To implement the scaling down operation, we can simply replace
each query made by an algorithm with a function that only queries with 
probability (1 - γ).


The assumption that 0< p_e < 1 for all e ∈ E yields the following lemma 
on the function f.

 
Fix a vertex u ∈ A ∪ B, and suppose that 0< p_e < 1 for all 
e ∈u. 
Then the function f is strictly submodular 
and strictly increasing on subsets of u.
That is:


  *  For all subsets A, B ⊆u 
such that A ∖ B ≠∅ and B ∖ A ≠∅, 
f(A) + f(B) > f(A ∪ B) + f(A ∩ B).

  *  For all A ⊊ B ⊆u, f(A) < f(B).




Let g(F) = 1 - f(F) = ∏_e ∈ F(1 - p_e) (note that 
g(∅) = 1).
Notice that for F_1, F_2 ⊆ F such that F_1 ∩ F_2 = ∅ 
and F_1 ∪ F_2 = F, it holds that g(F) = g(F_1) · g(F_2).
Let A, B ⊆u be two sets such that A ∖ B ≠∅ and B ∖ A ≠∅.
It is sufficient to show that g(A) + g(B) < g(A ∪ B) + g(A ∩ B).
We have 

    g(A) + g(B)    = g(A ∩ B)( g(A ∖ B)_a + 
    g(B ∖ A)_b), and 
    g(A ∪ B) + g(A ∩ B)    = g(A ∩ B) ( g(A ∖ B) 
    · g(B ∖ A)_a · b + 1 ).

Since A ∖ B ≠∅ and B ∖ A ≠∅, 
and 0 < p_e < 1 for all e ∈ E, we have g(A ∩ B) > 0 and both 
a, b < 1. 
Thus a + b < 1 + a · b, because (1 - a)(1 - b) > 0. 
This combined with Equations (<ref>) and (<ref>) yields 
Property <ref>.

Now consider A ⊊u and any edge e ∈u∖ A. 
To prove Property <ref>, it is sufficient to show that
f(A ∪{ e }) > f(A), or equivalently, g(A ∪{ e }) < g(A).
This is straightforward since g(A ∪{e})/g(A) = 1 - p_e < 1,
because p_e > 0.


Let 𝐱^∗ = (x^∗_e)_e ∈ E be an optimal solution to 
.  
Fix a vertex a ∈ A.  
Then, 𝐱_a = (x^∗_e)_e ∈a, which is 
𝐱^∗ restricted only to those coordinates that correspond to 
edges in a, satisfy the following constraints:

    ∑_e ∈ Fx_e    ≤ f(F) ,       for all  F ⊆a , 
    
    
    x_e    ≥ 0 ,       for all  e ∈a .

Notice that these constraints are only a subset of the constraints of 
.

Let a denote the polytope defined by the above constrains.  The extreme
points of a have a nice structure that becomes crucial when designing
the probability distribution a over permutations of edges.  Namely,
for any extreme point, the sets for which Constraint (<ref>) is tight
form a chain. Moreover, each set in the chain has exactly one more element than
its predecessor and this element is non-zero coordinate of the extreme point.
Formally, we have Lemma <ref> below.

 
Let 𝐲 = (y_e)_e ∈a be an extreme point of a 
and let Y = {e ∈a : y_e > 0} be the set of edges that correspond 
to the non-zero coordinates of 𝐲.  
Then there exist |Y| subsets S_1, …, S_|Y| of a such that
S_1 ⊊ S_2 ⊊…⊊ S_|Y| with the following 
properties:


  * Constraint (<ref>) is tight for all S_1, S_2, 
… S_|Y|. 
That is ∑_e∈ S_i y_e = f(S_i) for all i = 1, …, |Y|.

  * For each i = 1, …, |Y|, the set S_i ∖ 
S_i-1 contains exactly one element e_i, and y_e_i is non-zero
(i.e., e_i ∈ Y).




It is clear that at least |Y| constraints in (<ref>) are tight.
If |Y| = 1, the claim of the lemma is obviously true. 
Suppose that |Y| > 1.
Now let A, B ⊆a be two different sets for which 
Constraint (<ref>) is tight. 
Then we have 

    f(A) + f(B) = ∑_e ∈ A y_e + ∑_e ∈ B y_e 
    	= ∑_e ∈ A ∪ B y_e+ ∑_e ∈ A ∩ B y_e 
    	≤ f(A ∪ B) + f (A ∩ B),

where the last inequality follows because 𝐲 satisfies 
Constraint (<ref>). 

Observe that, if A ⊈ B and B ⊈ A, then by 
Lemma <ref>, f(A) + f(B) > f(A ∪ B) + f(A ∩ B). 
Thus, it must be the case that either A ⊊ B or B ⊊ A, 
and consequently there exist |Y| sets S_1, S_2, …, S_|Y| such that 
S_1 ⊊ S_2 ⊊…⊊ S_|Y|, for which 
Constraint (<ref>) is tight. 

For each i = 1, 2, …, |Y|, we thus have that ∑_e ∈ S_i 
∖ S_i-1y_e = f(S_i) - f(S_i-1) > 0, where the 
inequality is due to the strictly increasing property of f. 
This implies that each S_i ∖ S_i-1 must contain at least one 
edge e_i such that y_e_i >  0, and since there are only |Y| 
non-zero coordinates in 𝐲, each S_i ∖ S_i-1 must
contain exactly one such e_i.  Now, suppose that some S_i ∖ S_i-1
contains some e'_i such that y_e'_i = 0. 
Then f(S_i) = ∑_e ∈ S_i y_e = ∑_e ∈ S_i ∖{e'_i} 
y_e ≤ f(S_i ∖{e'_i}) < f(S_i) yields a contradiction. 
Here, the first inequality is due to Constraint (<ref>) whereas
the last inequality is due the strictly increasing property of f.


Now fix a vertex a ∈ A and consider the simple query algorithm given in 
Algorithm <ref>, which outputs at most one edge adjacent to 
vertex a.
In Algorithm <ref>, a is a distribution over
the permutations of edges in some subsets of a that,
by <Ref>, can be found in polynomial time.
We have the following lemma considering Algorithm <ref>.



 
	Let 𝐱^∗ be an optimal solution to  and let 
	𝐱^∗_a = (x^∗_e)_e ∈a be its restriction to 
	the coordinates that corresponds to edges in a.
	Then there exists a distribution a over the permutations of 	
	subsets of a with the following property:
	When the permutation σ is drawn from a in 
	Algorithm <ref>, the probability 
that the algorithm outputs the edge e is x^∗_e, hence the expected	weight of the edge output by 
	Algorithm <ref> is ∑_e ∈ E_ax^∗_e w(e).
	Moreover, a permutation of edges from a can be sampled in 
	polynomial time.




Let 𝐲 = (y_e)_e ∈a be an extreme point of 
a and let |Y| be set of non-zero coordinates of 𝐲.
Let ∅ = S_0 ⊊ S_1 ⊊…⊊ S_|Y|
be the chain of sets (for which Constraint (<ref>) is tight) 
guaranteed by Lemma <ref> for the extreme point 𝐲. 
We can efficiently find the chain by first setting S_Y = Y, and 
iteratively recovering S_i-1 from S_i by trying all possible S_i∖{e } for e ∈ S_i to check whether 
Constraint (<ref>) is tight.
For each i = 1, …, |Y|, let e_i be the unique element in 
S_i∖ S_i-1 and let σ_y = (e_1, …, e_|Y|). 
Notice that S_i = {e_1, …, e_i}, and hence y_e_i = 
∑_e ∈ S_iy_e - ∑_e ∈ S_i-1 y_e = f(S_i) - f(S_i-1).
Thus if we select σ_y as the permutation in 
Algorithm <ref> and query according to that order, the 
probability that it outputs the edge e_i is exactly 

    [some edge in S_i appears] - [some edge in S_i-1
      appears] =f(S_i) - f(S_i-1) = y_e_i.


Note that the point 𝐱^∗_a is contained in polytope a.
Thus, using the constructive version of Caratheodary's theorem,  we can 
efficiently find a convex combination 𝐱^∗_a = ∑_i ∈ [k]a_i 
·𝐲^(i), where a_i ≥ 0 for all i ∈ [k], 
𝐲^(i) is an extreme points of a for all i ∈ [k], 
∑_i ∈ [k] a_i = 1, and k = (|E_a|). 
This is because we can optimize a linear function over a in 
polynomial time using submodular minimization as a separation oracle,
and for such polytopes, the constructive version of Caratheodary's
theorem holds (See Theorem 6.5.11 of <cit.>). 

Define the distribution a such that it gives permutation 
σ_𝐲^(i)  with probability a_i. 
If follows that, if we sample according to this distribution in 
Algorithm <ref>, then for any fixed edge e, the probability 
that the algorithm outputs the edge e is ∑_i ∈ [k]a_i · y^(i)_e  
= x^∗_e. 
Consequently, the expected weight of the output of 
Algorithm <ref> is ∑_e ∈ E_a x^∗_e · w(e).




 §.§ Proposed algorithm and analysis



Suppose that we run Algorithm <ref> for all vertices 
a ∈ A and let M' be the set of all output edges.
Then we have 
    [∑_e ∈ M' w(e) ] = ∑_a ∈ A∑_e ∈a x^∗_e · w(e) = ∑_e ∈ E x^∗_e · w(e) 
    ≥.

Furthermore, M' contains at most one adjacent edge per each vertex 
a ∈ A.
However M' may contain more than one adjacent edge for some vertices 
b ∈ B, and hence it may not be valid matching.

Now again suppose that we run Algorithm <ref> as described 
above for all vertices a ∈ A in some arbitrary order. 
Consider some fixed vertex b ∈ B.
By <Ref>, from the perspective of b, an edge e ∈b appears with probability 
x^∗_e (when we say an edge e = (a,b) appears, it means that 
Algorithm <ref>, when run on vertex a, outputs the edge e).
Viewing the vertices in A as buyers, we think of the appearance of an
edge e = (a, b) as a buyer a making a take-it or leave-it offer of 
value w_e for item b.
Thus if we use a uniformly random order of vertices in A, picking an 
edge adjacent to the fixed vertex b can be viewed as an instance of the 
prophet secretary problem.

The (1 - 1/e)-competitive algorithm algorithm given by 
Ehsani et al. <cit.> for the prophet secretary problem first sets 
a base price for the item. 
If some buyer comes at time t ∈ [0, 1], and if the item is not already
sold, then the algorithm sells the item to this buyer if the offered price
is at least (1 - e^t - 1) times the base price.
Since the prophet secretary problem deals with a single item,
the goal is to choose the buyer with highest offer, and hence
they set base price of the item as the expected value of the maximum
offer.

However, rather than picking the maximum weighted edge adjacent to each b,
we want to maximize the total weight of the matching constructed. 
Thus, we set the base price c_b for each b, not as the the expectation
of the offline secretary problem, but as the expected weight of the
edge adjacent to b in some optimal offline maximum-weight bipartite 
matching.
To be concrete, we set c_b = ∑_e ∈bx^∗_e · w(e) 
(recall that we can think of x^∗_e as the probability that some fixed 
optimal algorithm for maximum weighted bipartite matching in model adds edge e to its output).



We present the pseudo-code of our algorithm in
Algorithm <ref>.
We start by independently assigning each a ∈ A a uniformly random
arrival time t_a ∈ [0,1], and then for each vertex a ∈ A in 
the order of the arrival time, we run a slightly modified version of the 
query algorithm given in Algorithm <ref>.
For each b ∈ B, we pick an edge e = (a,b) if it appears and if its
weight exceeds the threshold (1 - e^t_a - 1) · c_b.
Since a algorithm is committed to adding any queried edge that
exists, we query an edge e only if e ∩ B is not already assigned to 
some other vertex a ∈ A and its weight w(e) exceeds the threshold.
But we still need to make sure that, for a fixed b, edges 
e ∈b appears (in the sense that if we run 
Algorithm <ref>, it outputs the edge e) with probability 
x^∗_e.
Hence we have the else clause of the conditional in 
Algorithm <ref> that simulates the behavior of 
Algorithm <ref> in the cases we decide not to actually query 
an edge.

We conclude this section with Theorem <ref> which shows that
our algorithm is (1 - 1/e)-approximate.
The proof follows exactly the same lines (except for the definition of
base price c_b) as in Ehsani et al. <cit.> to show that the 
expected weight of the edge adjacent to a fixed vertex b ∈ B in the
output of is at least (1 - 1/e) · c_b.
Then by the linearity of expectation, the expected utility of is
at least (1 - 1/e)  ·∑_b ∈ B c_b = (1 - 1/e) ·∑_e ∈ E
x^∗_e · w(e) ≥ (recall that c_b = ∑_e ∈b x^
∗_e · w(e)). 

 
The expected utility () of the algorithm is at 
least (1 - 1/e) ·.



For the sake of completeness, we reproduce the analysis of Ehsani et al. <cit.> in 
Section <ref> for our more general algorithm in the price of information model (see Theorem <ref>).




§ EXTENSION TO THE PRICE OF INFORMATION MODEL



In this section, we present a (1 - 1/e)-approximation algorithm for the 
maximum weight bipartite matching problem () in the price of information 
(PoI) model introduced by Singla <cit.>.
Our strategy is essentially the same as that used in Section <ref> 
for the model except for a few enhancements.

Let G = (A ∪ B, E) be a bipartite graph where each edge e ∈ E 
independently takes some random weight X_e from a known probability
distribution. 
The weight distributions can be different for different edges and are independent.
To find the realization of X_e (i.e., the actual weight of the edge e), we 
have to query the edge e at a cost of π_e.  
Consider an algorithm 𝒜 that queries a subset Q of edges E and
outputs a valid matching M ⊆ Q. 
We call such an algorithm a PoI algorithm for .
We define the expected PoI utility of Algorithm 𝒜 as

    () := [∑_e ∈ M X_e - ∑_e ∈ Qπ_e],

where the expectation is taken over the randomness of X_e's and any
internal randomness of the algorithm.
The goal is to design a polynomial-time PoI algorithm  for such that its expected PoI utility () is maximized. 
Let = max (𝒜) denote the optimal expected
PoI utility, where the maximization is over all PoI algorithms.

Let E={e_1, …, e_m}, and let 𝐗 = (X_e_1, …, X_e_m).
Let  be the collection of all valid bipartite matchings in G.  
The following lemma is due to Singla <cit.>.

 
For each edge e ∈ E, let τ_e be the solution to the equation
[max{(X_e - τ_e),0}] = π_e and let Y_e = min(X_e, τ_e).
Then the optimal expected PoI utility  is upper bounded by
_𝐗[ max_M ∈∑_e ∈ MY_e ].


To derive our algorithm, we go through the same two stages as in 
Section <ref>.
We first construct a linear program (LP), this times defining the constraints
using the probability distributions of Y_e's (that were defined in 
Lemma <ref>), and use its value together with 
Lemma <ref> to upper bound .
For this, we discretize the distributions of Y_e's, and in contrast to the 
setting, we now define variables x_e,v for each edge-value pair 
(e,v); 
We think of x_e,v as the joint probability that Y_e = v and some fixed 
optimal PoI algorithm includes edge e in its output.
The objective value of this LP upper bounds the quantity
_𝐗[ max_M ∈∑_e ∈ MY_e ], which
in turn is an upper bound of the optimal expected PoI utility as stated in
Lemma <ref>.
We describe the construction of our LP in Section <ref>.
Next, in Section <ref>, we analyze the structure of our new 
LP as we did in the previous section and use it to define analogous 
probability distributions over subsets of edge-value pairs. 
Finally, in Section <ref> we put everything together to construct 
our (1 - 1/e)-approximate PoI algorithm for .



 §.§ Upper-bounding the optimal expected utility.



Assume that the distributions of Y_e are discrete[We can e.g.
  achieve this by geometric grouping into polynomially many classes.].  
For each e ∈ E, let V_e denote the set of possible values of Y_e.  
For each vertex u ∈ A ∪ B, let u = {(e, v) : e ∈δ(u), 
v ∈ V_e} be the set of all edge-value pairs for all edges incident to u. 
Let = ∪_u ∈ Au be the set of all edge-value pairs.  
For each edge e ∈ E and value v ∈ V_e, let p_e,v be the 
probability that Y_e = v, and for a set F ⊆, let f(F) 
be the probability that Y_e = v for at least one edge-value pair 
(e,v) ∈ F.





Fix any PoI algorithm  for .
For each edge-value pair (e,v) ∈, let A_e,v be the event 
that Y_e = v and  includes edge e in its output, and let 
x_e,v = [A_e,v].  
Now fix a vertex u ∈ A ∪ B and a set F ⊆u.  
Then [ ∪_(e,v) ∈ F A_e,v] ≤[ Y_e = v  for some  
(e,v) ∈ F] = f(F).  
But since all events A_e,v for (e,v) ∈u are mutually disjoint
(as with the setting, the algorithm 𝒜 outputs a valid 
matching and thus the output has at most one edge incident to vertex u),
[∪_(e,v) ∈ F A_e,v] = ∑_(e,v) ∈ F[A_e,v] = 
∑_(e,v)  ∈ F x_e,v.  
Thus we have ∑_(e,v) ∈ F x_e,v≤ f(F), and this must be true 
for all u ∈ A ∪ B and F ⊆u.


Now consider the following LP, which we call .

    Maximize    ∑_(e,v) ∈ x_e,v· v,           
       subject to    ∑_(e,v) ∈ F x_e,v   ≤ f(F)     for all  F ⊆u for all  u ∈ A ∪ B,     
           x_e,v   ≥ 0    for all  (u,v) ∈.


We have the following lemma concerning .

 
The optimal expected PoI utility  is upper bounded by the value 
of .



By Lemma <ref>, we have that ≤_𝐗
[max_M ∈ℳ∑_e ∈ MY_e].
Now consider an algorithm 𝒜 that queries Y_e for all edges 
e ∈ E and outputs a maximum weighted bipartite matching M of G.
Setting x_e,v to be the joint probability that Y_e = v and 
e ∈ M for each edge-value pair (e,v) ∈ gives a feasible 
solution to . 
Hence (𝒜) =  _𝐗[max_M ∈ℳ∑_e ∈ MY_e] ≤∑_(e,v) ∈ x^∗_e,v· v, 
where 𝐱^∗ = (x^∗_e,v)_(e,v) ∈ is an optimal
solution of .




 §.§ Structure of the LP and its implications.



Now we analyze the structure of . 
Our analysis closely follows that of Section <ref>.

As usual, f is a coverage function and hence it is submodular.
Thus, for each vertex u ∈ A ∪ B, we can use submodular minimization 
to check whether any constraint of the form ∑_(e,v) ∈ F x_e,v≤ 
f(F) is violated for any subset F ⊆u. 
This yields Lemma <ref> below.

 
The linear program  is solvable in polynomial-time.


We proceed as follows.
Consider the query strategy given in Algorithm <ref> that
queries edges incident to a fixed vertex a ∈ A in some random order.
This is the PoI version of the Algorithm <ref> given for the
setting.
Following (almost) the  same procedure as in 
Section <ref>, we find distributions a 
that makes Algorithm <ref> pick an edge e that has value v 
with probability x^∗_e,v, and then use those to construct a PoI 
algorithm  for that gives (1 - 1/e) approximation guarantee.
But the issue here is that Algorithm <ref> considers 
the distributions of Y_e's and does not pay query costs whereas our final
approximate PoI algorithm needs to consider the distributions of X_e's and 
has to pay query costs.



Now consider the way we defined τ_e (which we used to define 
Y_e's), and observe that the values of X_e above the threshold 
τ_e, on expectation, covers the cost π_e of querying it.
Thus, if we can make sure that the first time we query an edge e (i.e.,
the time where we pay the price π_e) in 
Algorithm <ref> is for the value τ_e, then
we can still use it to construct our final PoI matching algorithm
(where we actually query X_e values, and when an edge e is queried 
for the first time for value τ_e, in expectation we actually get
a net value of τ_e with probability x^∗_e, τ_e after paying 
π_e).
Using a careful construction, we make sure that distributions a 
only gives those permutations where for any edge e, 
the pair (e, τ_e) appears before any other pair (e, v).

For such a construction, we consider a slightly different polytope a 
(as opposed to how we defined a) for each a ∈ A.
Fix a vertex a ∈ A, and consider the family a of subsets of 
a defined as follows:

    a := {F ⊆a: (e,v) ∈ F ⇒ (e,v') ∈ F 
     for all  v' ≥ v  such that  (e,v') ∈a}.
 
I.e., a is a family of subsets of a that satisfy the 
following: If a set F of edge-value pairs is in a and an edge-value 
pair (e,v) is in F, then F also contains all edge-value pairs for the 
same edge e having values greater than v.  
It is easy to verify that if A, B ∈a then both A ∪ B ∈a and A ∩ B ∈a, which makes a a lattice family.
(I.e., the sets in a forms a lattice where intersection and union 
serve as meet and join operations respectively.) 

We define below the polytope a using a constraint for each set in the
family a. 

    ∑_(e,v) ∈ F x_e,v   ≤ f(F)      for all  F ∈a
    
    x_e,v   ≥ 0    for all  (e,v) ∈a.
  


Analogous to our assumption 0 < p_e < 1 for all e ∈ E for the 
setting, we now assume that each p_e,v > 0 and
for each edge e, ∑_v ∈ V_e p_e,v < 1. 
(I.e., we can assume that with some small probability p_e,⋆ the 
edge e does not exist or equivalently, we can also assume p_e,0 > 0 
and 0 ∉ V_e.
We omit the details, but one can use the same argument of re-scaling the 
probabilities to justify this assumption.)
Under these assumptions on p_e,v's, we have the following lemma.
The proof resembles that of Lemma <ref> from
Section <ref>, and we defer it to 
Appendix <ref>.

 
Fix a vertex a ∈ A.
If p_e,v > 0 for all (e,v) ∈a and
∑_v ∈ V_e p_e,v < 1 for all e ∈a, the function f 
is strictly submodular and strictly increasing on the lattice family 
a.
Formally,


  *  For any A, B ∈a such that A ∖ B 
≠∅ and B ∖ A ≠∅, f(A) + f(B) > f(A ∩ B) 
+ f(A ∪ B), and

  *  For any A ⊊ B ⊆a, 
f(B) > f(A).



Similarly to the setting, we now analyze the structure of the 
extreme points of polytope a.
We have the following lemma, which is a slightly different version of 
Lemma <ref> from Section <ref>.


 
Let 𝐲=(y_e,v)_(e,v) ∈a be an extreme point of 
a and let Y = {e ∈a : y_e,v > 0} be the set of 
non-zero coordinates of 𝐲.
Then there exist |Y| subsets S_1, …, S_|Y| of a  such that
S_1 ⊊ S_2 ⊊…⊊ S_|Y| with the following 
properties:


  *  Constraint (<ref>) is tight for all 
S_1, S_2, … S_|Y|. That is ∑_(e,v) ∈ S_i y_e,v = f(S_i) 
for all i = 1, …, |Y|.

  *  For each i = 1, …, |Y|, the set
(S_i ∖ S_i-1) ∩ Y contains exactly one element (e_i, v_i).
Moreover, for any other (e, w) ∈ S_i ∖ S_i-1, we have e = e_i
and w ≥ v_i.
 



Property <ref> and the fact that each (S_i∖ S_i-1) 
∩ Y contains exactly one pair (e_i, v_i) follows from the proof of 
Lemma <ref>.
It remains to show that each S_i∖ S_i-1 additionally contains
only those edge-value pairs (e_i, w) for which w ≥ v_i.

Suppose to the contrary that there is some S_i ∖ S_i-1 that 
contains at least one other pair (e',v') that violates this property.
Let S'_i = S_i-1∪{(e_i, w): w ≥ v_i}.
Then S_i-1⊊ S'_i⊊ S_i and S'_i is also in 
the family a.
Thus we have that f(S'_i) ≥∑_(e,v) ∈ S'_iy_e,v = ∑_(e,v) 
∈ S_iy_e,v = f(S_i), which is a contradiction because f is strictly 
increasing and S'_i ⊊ S_i.
Here the first inequality holds because 𝐲 is in a 
and the first equality holds because S'_i contains all coordinates in S_i
for which 𝐲 is non-zero. 
The last equality is true because S_i corresponds to a tight constraint for 
the extreme point 𝐲.


As in the previous section, we are now ready to construct the distribution
a.
We present this explicit construction in the proof of 
Lemma <ref> stated below, which is the counterpart of 
Lemma <ref>. 

 
Let 𝐱^∗ be an optimal solution of .
For each vertex a ∈ A, there exist a distribution a over the
permutations of (subsets of) edge-value pairs in a that 
satisfies the following properties:


  * 
  For each permutation σ drawn from a, if edge-value 
  pair (e,v) appears in σ, then the edge-value pair (e, w) 
  appears before (e,v) in σ for all w ∈ V_e 
  such that w ≥ v,

  * 
  [Algorithm <ref> outputs e] = 
  ∑_v ∈ V_e x^∗_e,v for all e ∈a, and

  * 
  ∑_v ∈ V_e: v ≥ w[Algorithm <ref> 
  	outputs e with value v]· v ≥∑_v ∈ V_e: v ≥ w 
  	x^∗_e,v· v for all e ∈a and w ∈^+.

Moreover, a permutation  of edge-value pairs from a can be sampled 
in polynomial time.




As with the case of Lemma <ref>, we first associate a
permutation of edge-value pairs with each extreme point of a.

For an extreme point 𝐲, let Y and S_1,…,S_|Y| be as defined
in <Ref>.  Consider the permutation σ_y of elements in S_|Y| that is defined
as follows: Start with σ_y = [ ] and for each i = 1, …, |Y|,
append to it the edge-value pairs in S_i∖ S_i-1 in the 
decreasing order of value. 
Recall that for all i = 1, …, |Y|, all edge-value pairs in S_i∖ S_i-1 corresponds to a single edge.
Let (e,v) ∈ S_i. 
Then, by the definition of the family u, (e, v') ∈ S_i for all
v' ∈ V_e such that v' ≥ v.  
Thus none of the sets S_i+1∖ S_i, S_i+2∖ S_i+1,
…, S_|Y|∖ S_|Y| - 1 can contain an edge-value pair (e, v') 
such that v' > v.  
Also, since the elements in S_i∖ S_i-1 are appended to 
σ_y in decreasing order of values, σ_y has the following 
property: If at any point the edge-value pair (e,v) appears in σ_y, 
then (e,w) appears in σ_y before (e,v) for all w ∈ V_e such 
that w > v.

Let σ_y = (e_1, v_1), …, (e_ℓ, v_ℓ) be the permutation of 
edge value pairs associated with the extreme-point 𝐲.  
Let T_i := {(e_1, v_1), …, (e_i, v_i) } denote the set of first i
edge-value pairs in σ_y.  
If we select permutation σ_y in 
Line <ref> in Algorithm <ref>, 
the probability of it picking edge e_i with value v_i is exactly
f(T_i) - f(T_i-1).  
Now define a new vector 𝐲' with the same indices as 𝐲 
as follows: For each (e_j, v_j) ∈σ_y, y'_e_j,v_j 
= f(T_j) - f(T_j-1), and all the other coordinates of 𝐲' 
are 0.
Notice that 𝐲' and 𝐲 satisfy the following:


  *  ∑_v ∈ V_e y'_e,v = ∑_v ∈ V_e y_e,v 
for all e ∈a, and 

  *  ∑_v ∈ V_e: v ≥ w y'_e,v· v ≥∑_v ∈ V_e: v ≥ w y_e,v· v for all e ∈a and 
w ∈^+. 

To see this fix some set S_i and let (e_j,v_j), (e_j+1, v_j+1), 
…, (e_k, v_k) be all the edge-value pairs in S_i - S_i-1.  
Then we know that e_j = e_j+1 = … = e_k, v_j > v_j+1 > ⋯ 
> v_k, and y_e_k, v_k≠ 0.  
We thus have that ∑_j' = j^k y'_e_k,v_j = f(T_k) - f(T_j-1) 
= f(S_i) - f(S_i-1) = y_e_k, v_k (recall that (e_k, v_k) is the 
unique element in S_i ∖ S_i-1 for which y_e_k, v_k is 
non-zero).  
This holds for elements in S_i ∖ S_i-1 in all i = 1, …, |Y|, 
and yields the Property <ref> above.  
To see Property <ref>, notice that within each S_i ∖ 
S_i-1, the weight of the non-zero coordinate y_e_k,v_k is 
re-distributed among y_e_j,v_j, …, y_e_k,v_k, and that 
v_j'≥ v_k for j' = j, j+1, …, k.

Let σ be the random variable that denotes the permutation picked by
Algorithm <ref>. 
Then we have that, for all e ∈δ(u),

    [ Algorithm <ref> picks e | σ = σ_y] 
    = ∑_v ∈ V_e y'_e,v = ∑_v ∈ V_e y_e,v,
 and for all
(e,w) ∈u,

    ∑_e, v ∈ V_e: v ≥ w[Algorithm <ref> 
    picks e with value v | σ = σ_y] ·
    v = ∑_e, v ∈ V_e: v ≥ w y'_e,v· v ≥∑_e, v ∈ V_e: v
    ≥ w y_e,v· v.

 
Now let 𝐱^∗_a be the restriction of the optimal solution the 
coordinates in a.
Since the constraints that define a are only a subset of the
constraints of , 𝐱^∗_a lies in a.
If we can optimize a linear function of a in polynomial time,
then we can follow the same lines of the proof of 
Lemma <ref> and use the constructive version of 
Caratheodary's theorem to find a convex combination 𝐱^∗_a = 
∑_i ∈ [k] a_i ·𝐲^(i), where k = (|a])
and for each i ∈ [k], 𝐲^(i) is an extreme point of 
a.
However, unlike in the case, the polytope a only has 
constraints for sets of a lattice family, and as a result, we cannot 
use the usual submodular minimization as a separation oracle for .
But luckily, Grötschel et al. <cit.> showed that we can 
minimize any submodular function over a lattice family in polynomial time.
Thus we can efficiently find such a convex combination.

Once we have the convex combination, the rest is exactly the same as
the setting. The distribution a returns the permutation
σ_y^(i) with probability a_i for all i ∈ [k].
One can easily verify that Properties <ref>-<ref> hold for 
this distribution.




 §.§ Proposed algorithm and analysis.



We now present a (1 - 1/e)-approximate PoI algorithm for .

The algorithm closely resembles the algorithm we presented
for the model, but has two key differences.
First, we now have to pay a price for querying edges. 
But, as we prove later, this price is already taken care of by the way we
defined Y_e variables.
The second difference is that for each edge e ∈ E, we now have multiple 
values to consider, but regardless, with respect to a fixed vertex 
(i.e. an item) b ∈ B, the vertices a ∈ A can still be viewed as 
buyers; The appearance of multiple edge-value pairs for the same edge can be 
interpreted as a distribution over values that the buyer a offers for the 
item b.

The outline of our algorithm is given in Algorithm <ref>.
Note that, we again have the else clause in the conditional to make sure 
that we do not change the probability distributions of the appearances of
edge-value pairs even if we decide not to query some edges for certain values.



The analysis of the expected PoI utility of consists of two parts.
First we use the same technique used by Singla <cit.> to show that
we can analyze the expected utility using Y_e variables and no query
costs instead of using X_e variables with query costs. 
Next we reproduce almost the same analyis by Ehsani et al. <cit.> 
to prove the approximation guarantee.

Let Z be the value we get from Algorithm <ref>.  
Then Z = ∑_e ∈ E( e X_e - eπ_e ),
where e and e are the indicator variables for the
events that edge e is picked in Line <ref> and it is 
queried in Line <ref> respectively.

Now suppose that we run an identical copy of Algorithm <ref>
in parallel but we do not pay for querying in Line <ref>, 
but instead of gaining X_e, we only get Y_e = min(X_e, τ_e).  
We say that this latter execution in the “free-information” world whereas 
the original algorithm runs in the “price-of-information” world or PoI 
world. 
Let Z' be the value we get in the free information world.  
We have the following lemma.

 
The expected utility [Z] of (which is the PoI world) is equal 
to the expected utility of its counterpart in the free information world.



Consider a case where the algorithm picks an edge that is already queried 
before.
In this case, both algorithms get the same value, so the expected increase to
Z and Z' are the same.

Now consider the case where both algorithms query for some edge e. 
Notice that if an edge e is queried at any point, it is queried for the 
edge-value pair (e, τ_e).  
This is because τ_e is the maximum possible value for an edge e, and 
as a result, (e, τ_e) appears before any other (e,v) for v < τ_e 
(if it appears at all) in the permutations chosen in 
Line <ref> of Algorithm <ref>.  
In this case, the expected increase to Z' in the free information world is
τ_e ·[X_e ≥τ_e].  
The expected increase to Z in the PoI world is

    - π_e + ∫_τ_e^∞ t · p_e(t) dt
       = -π_e + ∫_τ_e^∞ (t - τ_e) · p_e(t)  dt +
      ∫_τ_e^∞τ_e· p_e(t)   dt 
       = - π_e + [ (X_e - τ_e)^+]_0 + τ_e ·[X_e ≥τ_e].



To conclude our analysis, we now present following theorem on the
approximation guarantee.

 
  
The expected PoI utility () of is at least 
(1 - 1/e) ·.



By Lemma <ref>, we have () = [Z] = 
[Z'].
Since the optimal value of  is an upper bound on the 
optimal value  (by Lemma <ref>), it is sufficient to 
show that

    [Z'] ≥ (1 - 1/e) ·∑_(e,v) ∈ x^∗_e,v v = 
    (1 - 1/e) ·∑_b ∈ B c_b.
 
(Recall that c_b = ∑_(e,v) ∈b x^∗_u,v· v as defined
on <Ref> in <Ref>.)
Let Z'_b = ∑_a ∈ba,b Y_a,b so that
Z' = ∑_b ∈ B Z'_b.  
We show that for any b ∈ B, [Z'_b] ≥ (1 - 1/e) · c_b.  
Then the theorem follows from the linearity of expectation. The following calculations now follow the analysis in <cit.> and are included for completeness.

We proceed by splitting Z'_a,b into two parts:

    Z'_a,b = a,b (Y_a,b - 
    (1 - e^t_a-1) · c_b)_M_a,b + a,b 
    (1 - e^t_a-1) · c_b_N_a,b.
 
Define r(t) := [no edge incident to b is picked before time 
t] and α(t):= 1 - e^t-1. 
Notice that r(t) is decreasing, and since our t_a's are from a continuous 
distribution, r(t) is a differentiable function. 
Thus we have

    [∑_a ∈b N_a,b]
       =  - ∫_0^1 r'(t) · (1 - 1/e^t-1)  · c_b   dt = -  c_b 
      ∫_0^1 r'(t) ·α(t) dt. 
    By applying integration by parts,[∑_a ∈b N_a,b]
       = - c_b ( [ r(t) ·α(t)  ]_0^1 - ∫_0^1 r(t) 
    	·α'(t) dt )
       = c_b ( (1 - 1/e) + ∫_0^1 r(t) ·α'(t) dt ). 
    equation1

Now we consider the expectation of M_a,b.  
Note that the inequality below is due to the third property of the  
distributions a of edge-value pairs we used in the algorithm
(see Lemma <ref>).

    [M_a,b | t_a = t]    ≥[no edge incident to b is picked 
    before t | t_a = t] 
    ∑_v ∈ V_a,b
     v ≥α(t) · c_b 
    x^∗_(a,b),v 
    (v - α(t) · c_b ).

 
If t_a = t, this means that t_a could not have arrived before t.  
Hence
[no edge incident to b is picked before t | t_a = t] ≥[no edge incident to b is picked before t ],
and thus we have

    ∑_a ∈δ(b)   [M_a,b |t_a = t] 
       ≥[no edge incident to b is picked before t | t_a = t] 
    	∑_a ∈b∑_v ∈ V_a,b
     v ≥α(t) 
    	· c_b 
    	x^∗_(a,b),v (v - α(t) · c_b ) 
       ≥[no edge incident to b is picked before t] 
     	∑_a ∈b∑_v ∈ V_a,b
     v ≥α(t) 
     	· c_b 
      x^∗_(a,b),v (v - α(t) · c_b ) 
       ≥ r(t) ∑_a ∈b∑_v ∈ V_a,b x^∗_(a,b),v 
        (v - α(t) · c_b ) 
       = r(t) (c_b -  α(t) · c_b ∑_a ∈b∑_v ∈ 
    V_a,b   x^∗_(a,b),v) 
       ≥  r(t) (1 - α(t)) · c_b.

Since t_a is uniformly distributed over [0,1] for each a ∈ A, 
it follows that

    [∑_a ∈b M_a,b]
        = ∫_0^1 ∑_a ∈b[ M_a,b | t_a = t]   dt ≥  
      c_b ∫_0^1 r(t) ( 1 - α(t) )  dt. 
      equation1

Now (<ref>) + (<ref>) yields

    [ ∑_a ∈b Z'_a,b]
       = [∑_a ∈b N_a,b] + [ 
    	∑_a ∈b M_ij] 
       ≥ c_b ((1 - 1/e) + ∫_0^1 r(t) ·α'(t) dt ) 
    	+ c_b ∫_0^1 r(t) ( 1 - α(t) )     dt 
       = c_b  (1 - 1/e) +  c_b  ∫_0^1 r(t) (1 - α(t) +
      α'(t) )_0  dt 
       = (1 - 1/e) · c_b.







§ ACKNOWLEDGEMENTS
 We are grateful to Anupam Gupta and Amit Kumar
for influential discussions at an early stage of this work.


alpha




§ PROOFS OF SOME SUPPLEMENTARY RESULTS



 

Fix a vertex a ∈ A.
If p_e,v > 0 for all (e,v) ∈a and
∑_v ∈ V_e p_e,v < 1 for all e ∈a, the function f 
is strictly submodular and strictly increasing on the lattice family 
a.
Formally,


  *  For any A, B ∈a such that A ∖ B 
≠∅ and B ∖ A ≠∅, f(A) + f(B) > f(A ∩ B) 
+ f(A ∪ B), and

  *  For any A ⊊ B ⊆a, 
f(B) > f(A).




It is easy to see that  f(F) = 1 - ∏_e ∈ E (1 - ∑_v ∈ V_e : 
(e,v) ∈ F p_e,v).
Consider two sets A, B ∈a such that A ∖ B ≠∅
and B ∖ A ≠∅.
Fore each e ∈ E, let a_e = 1 - ∑_v ∈ V_e: (e,v) ∈ A p_e,v
and b_e = 1 - ∑_v ∈ V_e: (e,v) ∈ B p_e,v.
Thus we have that f(A) = 1 - ∏_e ∈ Ea_e, 
f(B) = 1 - ∏_e ∈ E b_e, f(A ∪ B) = 1 - ∏_e ∈ Emin(a_e, b_e), and f(A ∩ B) = 1 - ∏_e ∈ Emax(a_e, b_e).
The last two equations follow from the definition of the family a.

Now we have

    f(A) + f(B) - f(A ∪ B) - f(A ∩ B) 
       = ∏_e ∈ Emin(a_e, b_e) + ∏_e ∈ Emax(a_e, b_e)  - 
    ∏_e ∈ E a_e - ∏_e ∈ E b_e.

Thus to prove Property <ref>, it is sufficient to prove that the 
right hand side of (<ref>) is strictly greater than zero,
which is equivalent to showing that
∏_e ∈ Emin(a_e, b_e) + ∏_e ∈ Emax(a_e, b_e)  > 
∏_e ∈ E a_e + ∏_e ∈ E b_e.

Since A ∖ B ≠∅, we have a_e < b_e for at least one 
edge e_1 ∈ E.
To see this, let (e,v) ∈ A ∖ B.
Then for such edge e, it follows from the definition of set family
a that the set A_e = A ∩{(e,w): w ∈ V_e} contains all the 
elements in the set B_e = B ∩{(e,w): w ∈ V_e}, and in addition, 
it also contains at least one more element, namely (e,v). 
Since p_e,v > 0, a_e < b_e.
Similarly, we have a_e > b_e for at least one edge e_2 ∈ E 
(since we assumed that p_e,v > 0 for all (e,v) ∈a).
Let E_1 be the (nonempty) set of edges for which a_e < b_e, and let E_2 
be the (nonempty) set of edges for which a_e > b_e.
Without loss of generality we assume that E_1 ∪ E_2 = E
(if a_e = b_e for some e, then we can divide (<ref>) by a_e
since ∑_v ∈ V_e p_e,v < 1, a_e > 0).
We then have

    ∏_e ∈ Emin(a_e, b_e) + ∏_e ∈ Emax(a_e, b_e) 
       =  ∏_e ∈ E_2 b_e ∏_e ∈ E_1 a_e + 
    		∏_e ∈ E_2 a_e ∏_e ∈ E_1 b_e 
       > ∏_e ∈ E_2 a_e ∏_e ∈ E_1 a_e + 
    	 ∏_e ∈ E_2 b_e ∏_e ∈ E_1 b_e 
       = ∏_e ∈ E a_e + ∏_e ∈ E b_e

as required. 
The inequality above follows from the rearrangement inequality as 
∏_e ∈ E_1 b_e > ∏_e ∈ E_1 a_e and 
∏_e ∈ E_2 a_e > ∏_e ∈ E_2 b_e.

As for Property <ref>, suppose that A ⊊ B.
Then for all e ∈ E, a_e ≥ b_e, and for at least one e ∈ E,
a_e > b_e. 
Hence  f(B) - f(A) =  ∏_e ∈ E a_e - ∏_e ∈ E b_e > 0.



