c xxxx Society for Industrial and Applied Mathematics

SIAM J. COMPUT.
Vol. xx, No. x, pp. x–x

ONLINE SUBMODULAR WELFARE MAXIMIZATION:
GREEDY BEATS 12 IN RANDOM ORDER∗

arXiv:1712.05450v1 [] 14 Dec 2017

NITISH KORULA† , VAHAB MIRROKNI‡ , AND MORTEZA ZADIMOGHADDAM§
Abstract. In the Submodular Welfare Maximization (SWM) problem, the input consists of a set
of n items, each of which must be allocated to one of m agents. Each agent ℓ has a valuation function
vℓ , where vℓ (S) denotes the welfare obtained by this agent if she receives the set of items S. The
functions vℓ are all submodular; as is standard, we assume that they are monotone and vℓ (∅) = 0.
The goal is to partition P
the items into m disjoint subsets S1 , S2 , . . . Sm in order to maximize the
social welfare, defined as m
ℓ=1 vℓ (Sℓ ). A simple greedy algorithm gives a 1/2-approximation to SWM
in the offline setting, and this was the best known until Vondrak’s recent (1 − 1/e)-approximation
algorithm [36].
In this paper, we consider the online version of SWM. Here, items arrive one at a time in an
online manner; when an item arrives, the algorithm must make an irrevocable decision about which
agent to assign it to before seeing any subsequent items. This problem is motivated by applications
to Internet advertising, where user ad impressions must be allocated to advertisers whose value is
a submodular function of the set of users / impressions they receive. There are two natural models
that differ in the order in which items arrive. In the fully adversarial setting, an adversary can
construct an arbitrary / worst-case instance, as well as pick the order in which items arrive in order
to minimize the algorithm’s performance. In this setting, the 1/2-competitive greedy algorithm is
the best possible. To improve on this, one must weaken the adversary slightly: In the random order
model, the adversary can construct a worst-case set of items and valuations, but does not control the
order in which the items arrive; instead, they are assumed to arrive in a random order. The random
order model has been well studied for online SWM and various special cases, but the best known
competitive ratio (even for several special cases) is 1/2 + 1/n [9, 10], barely better than the ratio for
the adversarial order. Obtaining a competitive ratio of 1/2 + Ω(1) for the random order model has
been an important open problem for several years. We solve this open problem by demonstrating that
the greedy algorithm has a competitive ratio of at least 0.505 for online SWM in the random order
model. This is the first result showing a competitive ratio bounded above 1/2 in the random order
model, even for special cases such as the weighted matching or budgeted allocation problems (without
the so-called ‘large capacity’ assumptions). For special cases of submodular functions including
weighted matching, weighted coverage functions and a broader class of “second-order supermodular”
functions, we provide a different analysis that gives a competitive ratio of 0.51. We analyze the
greedy algorithm using a factor-revealing linear program, bounding how the assignment of one item
can decrease potential welfare from assigning future items.
In addition to our new competitive ratios for online SWM, we make two further contributions:
First, we define the classes of second-order modular, supermodular, and submodular functions, which
are likely to be of independent interest in submodular optimization. Second, we obtain an improved
competitive ratio via a technique we refer to as gain linearizing, which may be useful in other
contexts (see [30]): Essentially, we linearize the submodular function by dividing the gain of an
optimal solution into gain from individual elements, compare the algorithm’s gain when it assigns an
element to the optimal solution’s gain from the element, and, crucially, bound the extent to which
assigning elements can affect the potential gain of other elements.
Key words. Submodular Welfare Maximization; Online algorithms; Online SWM; randomorder; submodular optimization; second-order submodular functions.
AMS subject classifications.

1. Introduction. As a general abstraction of many economic resource-allocation
problems, submodular welfare maximization (abbreviated as SWM) is a central optimization problem in combinatorial auctions and has attracted significant attention
∗ An extended abstract
(STOC)’ 2015.
† Google Research, New
‡ Google Research, New
§ Google Research, New

of this paper appeared at ACM Symposium on Theory of Computing
York. nitish@google.com
York. mirrokni@gmail.com
York. zadim@google.com
1

2

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

in the research area at the intersection of economics, game theory, and computer
science. In this problem, an auctioneer sells a set N of n items to a set M of m
agents. The value of agent ℓ ∈ M for any subset (bundle) of items is given by a
submodular valuation set function vℓ : 2N → R+ , where vℓ (S) represents i’s maximum willingness to pay for the bundle S. The two standard assumptions on each vℓ
(besides submodularity) are that if S ⊆ T then vℓ (S) ≤ vℓ (T ) (monotonicity), and
that vℓ (∅) = 0 (normalization). The objective is to partition N into m disjoint subsets
S1 , S2 , . . . , Sm , andP
give set Sℓ to agent ℓ in a way that maximizes the social welfare,
m
i.e. the expression ℓ=1 vℓ (Sℓ ).
In the online version of the problem (also known as online submodular welfare
maximization), referred to as online SWM, items in N arrive one by one online, and
upon arrival of an item, it must be assigned immediately and irrevocably to one of
the agents. That is, the assignment of an item must be made before any subsequent
items arrive, and it may not be changed later.
The online SWM problem is a natural generalization of the online matching [21,
18, 14, 1, 25], budgeted allocation [26, 4, 5, 16] and online weighted matching problems [1, 13], along with more general classes of online allocation / assignment problems [12, 35, 2, 6]. Besides being theoretically important, these problems have a
number of practical applications including Internet advertising, network routing, etc.
These online allocation problems have been studied in both worst-case / adversarial
and stochastic settings. In the adversarial arrival model, an adversary constructs a
worst-case instance, and can order the items arbitrarily in order to minimize the algorithm’s performance. In contrast, in the random order arrival model, the adversary
can construct an arbitrary instance, but the order in which items arrive is considered to be chosen uniformly at random. Here, the performance of the algorithm is
computed as the average over the random choice of the arrival order of the items.
The Submodular Welfare Maximization problem has been studied extensively as
both an offline and an online optimization problem: For the offline optimization problem, one can easily observe that SWM is a special case of the monotone submodular
maximization problem subject to a (partition) matroid constraint. As a result, an old
result of Nemhauser, Wolsey, and Fisher [32] implies that a simple greedy algorithm
achieves a 1/2-approximation. Improving this approximation factor for the offline
SWM was open until Vondrak [36] presented a new 1 − 1/e-approximation algorithm
for the problem; this is the best possible using a sub-exponential number of oracle
calls [29].
For the online SWM problem, a simple online greedy algorithm (assign each item
to the agent whose marginal valuation increases the most) achieves a competitive ratio
of 1/2 for the adversarial model [15, 23]. As online SWM and its special cases are of
considerable theoretical and practical interest, there has been a large body of work
trying to improve upon this competitive ratio in both the adversarial and random
arrival models. For example, in the adversarial model, 1 − 1/e-competitive algorithms
have been achieved for the special case of the online matching problem, as well as the
the budgeted allocation and online weighted matching problems under the so-called
large capacity assumption [21, 26, 13]. However, such a result is not possible for
the general online SWM problem in the adversarial setting, where the simple greedy
algorithm is the best possible: A recent result by Kapralov, Post, and Vondrak [19]
shows that this 1/2-approximation is tight for online SWM unless NP=RP. This
hardness result, however, does not rule out improving the approximation factor of
1/2 for the random order model. In fact, getting a 1/2 + Ω(1) approximation factor

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

3

remains an open problem even for special cases of online SWM such as the budgeted
allocation problem, and weighed matching with free disposal [13, 6].
Our Contributions and Techniques. In this paper, we resolve the open problem
of obtaining an improved competitive ratio for random order online SWM:
Theorem 1. The Greedy algorithm has competitive ratio at least 0.5052 for
online SWM in the random order model.
Prior to our work, the best known algorithm for this problem (even for special
cases such as weighted matching or budgeted allocation) gave a 21 + n1 -approximation [9,
10]. Thus, our result is also the first 1/2 + Ω(1)-competitive algorithm for the budgeted allocation and the online weighted matching problems under the random order
model. Beating the factor of 1/2 for the online weighted matching and budgeted allocation problems in either the adversarial or the random order model (without the
large capacity constraints) has remained a major open problem in the area.
Further, for a broad class of submodular functions, we can strengthen our analysis.
To do this, we introduce the concept of second-order supermodular functions; to the
best of our knowledge, this class of functions has not been explicitly studied before.
Definition 2. For a submodular function f , let M G(A, e) = f (A ∪ {e}) −
f (A) denote the marginal gain from adding element e to set A. For sets A, S, we
define GR(A, S, e) = M G(A, e) − M G(A ∪ S, e) as the amount by which S reduces the
marginal gain from adding e to A. (Here, GR stands for Gain Reduction.) Note that
by definition of submodularity, GR(A, S, e) is always non-negative.
• The function f is said to be second-order modular if, for all sets A, B, S such
that A ⊆ B, and S ∩ B = ∅, and all elements e, we have: GR(A, S, e) =
GR(B, S, e).
• The function f is second-order supermodular if, for all sets A, B, S such
that A ⊆ B, and S ∩ B = ∅, and all elements e, we have: GR(A, S, e) ≥
GR(B, S, e). Equivalently, M G(A, e) − M G(B, e) ≥ M G(A ∪ S, e) − M G(B ∪
S, e).
• The function f is said to be second-order submodular if, for all sets A, B, S
such that A ⊆ B, and S ∩ B = ∅, and all elements e, we have: GR(A, S, e) ≤
GR(B, S, e).
It is well known that when considering the multilinear extension of f , submodularity corresponds to a non-positive second-order derivative. Our definition of secondorder submodularity implies non-positive third-order derivatives, while the definition
of second-order supermodularity implies a non-negative third-order derivative.
We believe these classes are likely to be of independent interest, as they help
partition the space of submodular functions, and may refine our understanding of
submodular optimization. Several natural submodular functions can be classified in
this framework: For example, cut functions are second-order modular, while weighted
coverage functions and weighted matching functions are second-order supermodular.
Theorem 3. The Greedy algorithm has competitive ratio at least 0.5104 for online
SWM in the random order model if the valuation functions of agents are second-order
supermodular functions.
Note that our results also imply simple 1/2 + Ω(1) approximation algorithms for
the offline SWM problems: simply permute the items randomly and apply the online
Greedy algorithm.1 We focus on the Greedy algorithm for several reasons: It is
1 We note that improving on the ratio of 1/2 for the offline Submodular Welfare Maximization
Problem was an open problem for nearly 40 years until the result of Vondrak [36].

4

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

simple and natural, besides being easy to implement and likely to be used in practice.
Further, it is optimal in the adversarial setting. Algorithms that perform well in both
adversarial and stochastic settings (see, for instance, [28]) are of considerable practical
utility; by showing that the Greedy algorithm achieves a ratio better than 1/2 in the
random order model, we provide further justification for its practical importance.
Moreover, the Greedy algorithm for online SWM has been extensively studied in
strategic settings [24, 33, 34].
Our approach to analyzing the performance of the Greedy algorithm is to understand how item allocations interact via the technique we call gain linearizing: We
first formulate some basic inequalities about any greedy allocation which yield another proof that the Greedy algorithm achieves a competitive ratio of 1/2. To go
beyond this ratio, we note that the assignment of an item can reduce the expected
gains from future items, but this reduction in future gains is bounded, and the random
order ensures that it is ‘evenly spread out’ among future items. We formalize this
intuition in Section 2; once we can bound such interactions, we derive constraints for
a factor-revealing Linear Program, which we explicitly analyze to get a lower bound
on the competitive ratio of the Greedy algorithm.
1.1. Related Work. The online submodular welfare maximization problem is a
generalization of various well-studied online allocation problems, including problems
with practical applications to Internet advertising. These include online weighted
b-matching (with free disposal), also referred to as the Display Ads Allocation problem [13, 12, 2, 35], and budgeted allocation or the AdWords problem [26, 5]. In
both of these problems, a publisher must assign online impressions to a set of agents
corresponding to advertisers; the goal is to optimize efficiency or revenue of the allocation while respecting pre-specified contracts with advertisers. Both of these problems
have been studied in the competitive adversarial model [26, 13, 4] and the stochastic
random order model [5, 12, 2, 35].
In the online weighted b-matching problem with free disposal, motivated by display advertising, we are given a set of m advertisers; advertiser j has a set Sj of
eligible impressions and demand of at most N (j) impressions. The ad-serving algorithm must allocate the set of n impressions that arrive online. Each impression i
has value w(i, j) ≥ 0 for advertiser j. The goal of the algorithm is to assign each
impression to at most one advertiser, while maximizing the value of all the assigned
impressions and ensuring that advertiser j does not receive more than N (j) impressions. Expressed combinatorially, this corresponds to finding a maximum weight
b-matching online. This weighted b-matching problem is considered in [13], which
showed that the problem is inapproximable without exploiting free disposal. When
the demand of each advertiser is large, a (1 − 1e )-competitive algorithm exists [13],
and this is the best possible. In the budgeted allocation problem, motivated by sponsored search advertising, the ad-serving algorithm allocates impressions resulting from
search queries. Advertiser j has a budget B(j) on the total spend instead of a bound
N (j) on the number of impressions. Assigning impression i to advertiser j consumes
w(i, j) units of j’s budget instead of 1 of the N (j) slots, as in the weighted b-matching
problem. 1 − 1e -competitive algorithms have been designed for this problem under the
assumption of large budgets [26, 4].
The random order model has also been studied extensively for these problems. In
particular, a dual technique has been developed to solve problems in this setting: This
approach is based on computing an offline optimal dual solution based on the first ǫ
fraction of items / impressions, and using this solution online to assign the remaining

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

5

vertices. Following the first such training-based dual algorithm of [5] for the budgeted
allocation problem, training-based (1−ǫ)-competitive algorithms have been developed
for the weighted matching problem and its generalization to various packing linear
programs [12, 35, 2, 31]. These papers develop (1−ǫ)-competitive algorithms for online
m log n
) and the
stochastic packing problems in the random order model, if OPT
wij ≥ O( ǫ2
demand of each advertiser / agent is large. Recently, Kesselheim et al. [22] have
weakened this condition using a primal -based technique. In a separate line of work,
improved approximation algorithms have been proposed for the unweighted online
bipartite matching problem (which is a special case of both the weighted matching
and budgeted allocation problems) in the random order model [20, 25], even without
the assumption that the demand of each agent is large.
i.i.d. Model. Other than the adversarial and random-order models studied in
this paper, online ad allocation problems have been studied extensively in the i.i.d.
stochastic models in which impressions arrive i.i.d. according to a known or an unknown distribution. A key technique in this area is the primal approach which is based
on solving an offline allocation problem on the instance that we expect to arrive according to the stochastic information, and then applying this offline solution online.
This technique has been applied to the online stochastic matching problem [21] and
in the i.i.d. model with known distributions [14, 27, 17, 3], and resulted in improved
competitive algorithms.
Interestingly, a new hybrid technique can be applied to obtain a 1−1/e-competitive
algorithm for the budgeted allocation problem in the i.i.d. model [7, 8], and a similar
ratio can be obtained for the more general online SWM problem [19]. However, all
results based on such techniques seem to only apply to the i.i.d. model [7, 19] and
not the random order model. Generalizing such results to the random order model
remains an interesting open problem in the area.
2. Preliminaries and Key Ideas. We study the following welfare maximization problem, referred to as online SWM: n items from a set N arrive sequentially
online, and when each item arrives, it should be irrevocably assigned to one of m
agents from the set M . Each agent 1 ≤ ℓ ≤ m has valuation function vℓ : 2[n] → R+ .
We assume that each agent’s valuation function vℓ is submodular, non-negative and
monotone. The goal
to assign the items to agents in order to maximize the social
Pis
m
welfare, defined as i=1 vℓ (Sℓ ) where Sℓ is the set of items assigned to ℓ. We assume
w.l.o.g. that all of the n items are distinct, but we sometimes consider the union of
two or more allocations, as a result of which there may exist multiple copies of items:
In this case, the set of items assigned to a single agent is the union of the sets assigned
to it under the allocations, so it does not actually receive multiple copies of the same
item. (Equivalently, one could extend the submodular function to multisets in the
natural way so that the marginal value of an agent for the second copy of an item is
0.)
Algorithms for maximizing welfare in combinatorial auctions and submodular
optimization are required to be polynomial in the natural parameters of the problem,
m and n. However, since the “input” (the valuation functions) is of exponential size,
one must specify how it can be accessed. Most works in this field have taken a “black
box” approach in which bidders’ valuation functions are accessed via oracles that can
answer specific type of queries. The most natural and popular oracle query model is
the value query model [9, 10, 23], which we also use: the query to a valuation function
vℓ is in the form of a bundle S ⊆ N , and the response is vℓ (S).
As discussed above, no online algorithm can achieve a competitive ratio greater

6

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

than 1/2 for online SWM in the adversarial setting, and hence we focus on the random
order model. We measure the competitive ratio of an algorithm as the ratio of the
expected social welfare achieved by the algorithm’s assigment (where the expectation
is taken over all n! permutations) to the optimum social welfare. Our main contribution is to demonstrate that the simple and natural Greedy algorithm achieves a
competitive ratio of 1/2 + Ω(1).
What is the main difficulty in proving that the Greedy algorithm achieves a
competitive ratio better than 1/2? It is obvious that the expected welfare that Greedy
obtains by allocating the first item is at least as much as the optimum algorithm
obtains by allocating this item. Of course, the disadvantage of the greedy allocation
is that by assigning one item, it may severely reduce the potential welfare gain from
items that arrive in the future. Our key insight is into how items interact and how
allocating one item can affect the welfare gain that can be obtained from allocating
other items.
2.1. Understanding Item Interactions and Gain. In order to study interactions between allocations, we need to introduce the following notation:
Definition 4. An allocation of items to agents, denoted by A, consists of m
subsets of items A = {Aℓ }m
ℓ=1 where Aℓ is the set of items allocated to agent ℓ, and
every item is assigned to at most one agent. We note that some items may remain
unallocated
Pmin an allocation. We denote the total welfare or value of allocation A by
V (A) = ℓ=1 vℓ (Aℓ ).
Pm
We let A∗ be the allocation that maximizes social welfare OP T = ℓ=1 vℓ (A∗ℓ )
where OP T is the maximum social welfare. Without loss of generality (by normalizing
all values), we assume that OP T is equal to 1. For an item j, we define optj to be
the agent that receives item j in the optimum allocation A∗ , i.e. j belongs to A∗optj .
For a permutation σ on the items [n], we define σ i to be the set of first i items in σ,
in other words {σ1 , σ2 , · · · , σi }. We note σ is defined to just fix an arbitrary ordering
of the items. It does not need to be a random shuffling and it is just for the purpose
of indexing the items.
We can now introduce a central concept in our analysis, used to provide a lower
bound on the welfare gains of Greedy. In standard analyses of greedy algorithms, a
common approach is to show that one good option available to the greedy algorithm
is the choice made by the optimal algorithm. In our setting, this would translate to
showing that Greedy can obtain a good increase in welfare by assigning item j to optj .
The other piece of this approach is to show that the greedy choice for allocating item
j does not reduce the welfare gain that can be obtained from future items by more
than the welfare increase from j. Together, these two ideas imply that Greedy is 1/2competitive in the worst case. In order to formally argue about this, we introduce the
following notation to describe the marginal gain of assigning item j to agent ℓ = optj
based on a current allocation and a (partial) optimum allocation:
Definition 5. Fix an arbitrary permutation σ (such as the identity permutation).
For any item j and any allocation A let ℓ = optj , and i + 1 denote the index of item
j in σ. We define Gain(j, A) as:


vℓ {j} ∪ Aℓ ∪ (A∗ℓ ∩ σ i ) − vℓ Aℓ ∪ (A∗ℓ ∩ σ i ) .
That is, Gain(j, A) denotes the marginal gain we get from assigning j to the
agent ℓ that receives it in the optimal solution, assuming that ℓ has already received

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

7

all items in Aℓ based on the allocation A, as well as those of the first i items (under
σ) that the optimal solution allocates to ℓ (i.e. A∗ℓ ∩ σ i ). It is important to note
that in the definition, the permutation σ is fixed and the same permutation is used
to define Gain(j, A) for all items j and allocations A.
Intuitively, Gain(j, A) captures the further marginal gain one can achieve from
item j, given allocation A. As a simple example, consider the case
Pn when A is an
empty allocation (no item is allocated in A). In this case, the sum j=1 Gain(j, A) is
Pn
equal to OP T because for any permutation σ, the sum j=1 Gain(j, A) of marginal
gains of the n items obtained by the optimal
P allocation is the definition of OP T . For
any set S, we use Gain(S, A) to denote j∈S Gain(j, A).
How is the concept of Gain useful? Let π denote the arrival order of the items.
We denote the allocation of Greedy on the first i items (that is, on the sequence π i )
by Ai . The following lemma captures the marginal welfare Greedy achieves at each
step by using the notion of Gain variables.
Lemma 6. If item j arrives at position i + 1 under permutation π, the increase
in welfare that Greedy achieves by allocating this item is at least Gain(j, Ai ).
Proof. Recall that Greedy’s allocation on the first i items is Ai . We now consider
how much Greedy gains by allocating item j in the next position. Since Greedy
allocates the item in order to maximize marginal gain, its gain on j is at least as much
as item j’s marginal gain on agent ℓ = optj which is equal to vℓ ({j} ∪ Aiℓ ) − vℓ (Aiℓ ).
(Recall that Aiℓ is the set of items assigned to agent ℓ in allocation Ai .)
Note that this lower bound is similar to the expression in the definition of Gain(j, Ai )
(it only lacks the A∗ℓ ∩ σ i parts). As a direct result of submodularity of the function
vℓ , we have:
vℓ ({j} ∪ Aiℓ ) − vℓ (Aiℓ ) ≥ vℓ ({j} ∪ Aiℓ ∪ (A∗ℓ ∩ σ i )) − vℓ (Aiℓ ∪ (A∗ℓ ∩ σ i ))
That is, vℓ (({j} ∪ Aiℓ ) − vℓ (Aiℓ ) ≥ Gain(j, Ai ) for any permutation σ.
What does this have to do with interactions between items? For a fixed item j,
the value Gain(j, Ai ) is non-increasing in i. In other words, when Greedy assigns a
new item πi , it may decrease the Gain values for some items. We now prove that the
total decrease in Gain values for all n items is at most the increase in welfare that
Greedy obtained by allocating item πi . This next lemma allows us to keep track of
changes in these Gain values throughout the algorithm.
P
Lemma 7. Greedy’s increase in welfare from item πi is at least j∈[n] Gain(j, Ai−1 )−
Gain(j, Ai ).
Proof. Suppose Greedy assigns item πi to agent ℓ. For each item j with optj 6= ℓ,
the Gain variable is intact after this allocation, i.e. Gain(j, Ai−1 ) = Gain(j, Ai ). For
those items j with optj = ℓ, for any permutation σ, the sum of Gain(j, Ai ) is equal
to vℓ (A∗ℓ ∪ Aiℓ ) − vℓ (Aiℓ ). A similar claim holds for i − 1. We conclude that:
X

i−1
∗
i
i
Gain(j, Ai−1 ) − Gain(j, Ai ) = vℓ (A∗ℓ ∪ Ai−1
ℓ ) − vℓ (Aℓ ) − vℓ (Aℓ ∪ Aℓ ) − vℓ (Aℓ )
j∈[n]

i−1
i−1
∗
i
i
∗
= vℓ (Aiℓ ) − vℓ (Ai−1
ℓ ) + vℓ (Aℓ ∪ Aℓ ) − vℓ (Aℓ ∪ Aℓ ) ≤ vℓ (Aℓ ) − vℓ (Aℓ ).

The final inequality follows from the fact that the difference of the two dropped
terms is negative due to the monotonicity of vℓ . The final expression is precisely the
marginal gain Greedy achieves on item πi , which completes the proof.
Lemmas 6 and 7 (note that neither uses the fact that we have a random permutation) use the concept of Gain to give an alternate proof of the simple fact that

8

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

the Greedy algorithm is 1/2-competitive in the adversarial model: We start with an
empty allocation A0 , and Greedy assigns items one by one. At the beginning, the
total Gain = Gain(N, A0 ) is equal to OP T . Let G denote the sum of the final
gains Gain(N, An ). Lemma 7 implies that the value of the allocation An is at least
OP T − G. On the other hand, Lemma 6 shows that if item j arrives at position i + 1,
the algorithm’s marginal increase in welfare is at least Gain(j, Ai ) ≥ Gain(j, An ).
Therefore, the total welfare obtained by the algorithm is at least G. Since the welfare
is at least max{G, OP T − G}, it must be at least OP T /2.
2.2. Going Beyond 1/2: Our Techniques. Of course, we wish to argue that
Greedy does better than half in the random order model. When we applied Lemma 6
in the previous paragraph, we could have lower bounded Greedy’s marginal increase
in welfare from allocating item j in position i + 1 by Gain(j, Ai ); instead, we used
the weaker lower bound Gain(j, An ) ≤ Gain(j, Ai ). When this inequality is not
tight (that is, if the gain of item j is reduced after it arrives by subsequent Greedy
allocations), we can obtain an improved competitive ratio. To make this formal, we
define β as the expected value of total amount by which the Greedy
allocation reduces
P
the gain of items which have already arrived. Formally β is j∈N E[Gain(j, Atj −1 ) −
Gain(j, An )] where 1 ≤ tj ≤ n is the arrival time of item j, and Atj −1 and An
respectively denote the allocation of algorithm Greedy right before j arrives and by
the end of algorithm.
Lemma 8. The competitive ratio of Greedy is at least 1/2 + β/2.
Proof. If item j arrives in position i + 1, define hj as the reduction in theP
gain of j
after it arrived; that is, hj = Gain(j, Ai ) − Gain(j, An ). By definition, β = nj=1 hj .
From Lemma 6, the increase in Greedy’s welfare from allocating item j is at least
Gain(j, Ai ) = Gain(j, An ) + hj . Denoting Gain(N, An ) as G, we conclude that the
total welfare of Greedy is at least G + β. Lemma 7 implies that the total welfare of
Greedy is at least 1 − G (recall that we normalized OP T to 1. Hence, Greedy’s total
welfare is at least max{G + β, 1 − G} ≥ 1/2 + β/2.
If the gains of items were consistently reduced by a substantial amount after they
arrived, we would have a proof that Greedy has competitive ratio 1/2 + Ω(1). But
perhaps in the worst-case instances, Greedy’s allocation of the ith item only reduces
Gain values for future items? By taking advantage of the random arrival order, we
can understand how the reduction in Gain is distributed among future items. In
particular, the second item to arrive is unlikely to have its Gain reduced significantly
(in expectation) by the first item, but when the last item arrives, it is quite likely
that it has a very small Gain value, because some previous (mis)-allocations of the
greedy algorithm mean that assigning it to its optimal agent produces little value.
A straightforward differential equation analysis based on Lemmas 6 and 7 (which
ultimately yields a competitive ratio of 1/2) shows that when items arrive in a random
order, the expected welfare from greedily assigning the first t fraction of items is at
2
least w(t) = t − t2 that of the optimal. Assuming this analysis is tight, the expected
rate at which welfare increases is w′ (t) = 1 − t which is essentially zero for the last
few items (as opposed to at least 1 for the first item). The key contribution we make,
then, is to go beyond such analyses: We derive new lower bounds on the welfare
obtained from items that arrive towards the end of the order. This allows us to show
that the total welfare obtained by the greedy algorithm is strictly better than 1/2 of
the optimal.
Proving such lower bounds is non-trivial, and the main technique we apply is
lower bounding the welfare obtained from a single item by both its own Gain when it

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

9

arrives (as in Lemma 6), and how it reduces the Gain of other items (as in Lemma 7).
In particular, we apply these lower bounds to items arriving at the end of the random
order, which allows us to show that Greedy obtains non-zero welfare even at the end.
In this paper, we take two distinct approaches to obtain the needed lower bounds
on Gain values from items that arrive at the end of the random order. Informally
speaking, we do the following:
• First, we consider the special case of second-order supermodular functions.
We show that Greedy gets good welfare from items that arrive towards the
end by proving that there exists an allocation of these items that significantly
reduces the Gains of the first n/2 items. (Recall from Lemma 7 that Greedy’s
welfare from allocating an item is at least as much as its ability to reduce the
Gains of other items.) Our proof proceeds in several steps: We first show
that there is an allocation of the first n/2 items that significantly reduces the
Gains of the last n/2 items; by symmetry, there must exist an allocation Â of
the last n/2 items that significantly reduces the Gains of the first n/2. Next,
we use second-order supermodularity to argue that a subset of the items that
arrive at the end will be able to reduce the Gains of the first n/2 items at
least in proportion to the size of this subset. More formally, we show that
for items that arrive at the end, the only way they might not significantly
reduce the Gains of the first n/2 items is if previous allocations among the
last n/2 items already reduced these Gains significantly. But in this case,
Greedy’s allocations reduced the gains of items that arrived previously, which
means that β is large, and Lemma 8 shows that Greedy must then have a
competitive ratio better than 1/2. We precisely quantify this improvement
over 1/2 by formulating a factor-revealing Linear Program, and analyzing it
explicitly.
• Second, we consider the general submodular valuation case. The previous approach no longer applies, as without the second-order supermodularity property, allocating a single random item might significantly affect the collective
gains of other items. Therefore, we consider the (simulated) effect of assigning the last quarter of items three times in succession, using three different
allocations. Intuitively, this can be understood as showing three distinct
allocations for these items and arguing that the (mis)-allocations of Greedy
cannot harm all of these simultaneously. Therefore, these allocations together
obtain large welfare, and the first time these items arrive (corresponding to
the ‘real’ arrival and allocation) is the best of these.
With these lower bounds on Gain values, we can prove Theorems 1 and 3 by
constructing factor-revealing linear programs; the fact that items arrive in a random
order allows us to constrain the values of the variables representing the interactions
in item Gains. We then formally analyze these linear programs, which requires some
intricate computations. Though these calculations are problem-specific, we believe
that our main technique of gain linearizing and bounding item interactions will be
generally useful to improve analyses of submodular allocations and greedy approaches
for random-order problems. (For one example, see [30].)
2.3. Formulating the Factor-Revealing LP. Recall from Lemmas 6 and 7
that when item j in position i arrives, Greedy has marginal welfare at least Gain(j, Ai−1 ).
Further, assigning this item j reduces the Gain values of other items (both those that
have already arrived, and those which will arrive after j), but the total reduction is

10

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

at most the marginal welfare of allocating item j.
Definition 9. For each index 1 ≤ i ≤ n, we define wi to be the expected increase
in welfare Greedy achieves by assigning the item in position i (that is, the ith item in
the arrival order). Formally, we have:
wi = E[V (AG (π i )) − V (AG (π i−1 ))]
where π is the permutation denoting the arrival order of items, and AG (S) denotes the
allocation of Greedy algorithm on the sequence of items S. Assigning item i possibly
reduces the Gain values of items. We partition this effect into two parts; for any item
i, we have two variables bi and ai defined as follows to capture the reduction in Gain
values of other items:
• bi (we use b to denote before) is the expected reduction in Gain of items j
that have already arrived. In formal notation, we define:
X
bi = E[
Gain(j, AG (π i−1 )) − Gain(j, AG (π i ))]
j∈π i

Pn
From our definition of β in Section 2.2, β = i=1 bi .
• ai (a denotes after) is the expected reduction in Gain of items j that are going
to arrive later:
X
ai = E[
Gain(j, AG (π i−1 )) − Gain(j, AG (π i ))]
j∈π n \π i

Clearly, allocating the item in position i reduces the total gain values of all items by
bi + ai in expectation.
Variables ai , bi , and wi (and similar variables defined later in the paper) are
all non-negative. In formulating the linear programs we do not mention these nonnegativity properties as extra constraints. We just
Pntreat them as boundary conditions.
By definition, Greedy’s performance is simply i=1 wi . Our factor-revealing linear
programs will consist of three separate lower bounds on wi . Two of these are common
to both the general submodular case as well as the case of second-order supermodular
functions.
For the first constraint of our LP, we use the notation of Definition 9 to express
Lemma 7 as wi ≥ bi + ai . (This follows because wi is the increase in welfare that
Greedy achieves from the ith item, and bi + ai is how much this segment reduces the
Gain values of all items.)
In the next lemma, we prove another lower bound on wi , yielding the next
constraint of our linear program. Recall that we normalized our instance so that
OP T = 1.
Pi−1 aj
Lemma 10. For any 1 ≤ i ≤ n, if OP T = 1, we have wi ≥ n1 − j=1 n−j
where
variables wi and aj are defined in Definition 9.
Proof. Let x be the item that arrives at time i. From Lemma 6, the increase in
welfare of the algorithm from x is at least its Gain value at the time of its arrival
(time i); this can be written as the difference of the original Gain value of x (before
the algorithm starts) and the reduction in its Gain value due to allocating items
that arrived previously. Its original Gain value is Gain(x, ∅), and
P since x is chosen
uniformly at random among all items, we have E[Gain(x, ∅)] = n1 y∈N Gain(y, ∅) =
OP T /n = 1/n because the sum of original Gain values is equal to OP T = 1.

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

11

Now it suffices to prove
the expected reduction in the Gain value of the ith
Pi−1 that
aj
item does not exceed j=1 n−j
. Since we are bounding the reduction in the Gain
value of an item before it arrives, we can ignore any reduction that occurs after it
arrives. If the Gain value of the ith item is reduced before it arrives, it must have
been reduced by the item in position j for some j < i, and hence this must have been
included in aj . However, the variable a1 , for instance, captures reductions in Gain
values for all items appearing after the first, not just the ith item. In general, for
some 1 ≤ j < i, aj accounts for reduction in Gain values of items which arrive in any
of the positions j + 1, j + 2, · · · , n. The probability that any of these items falls in
position i and hence the reduction of its Gain value becomes relevant in this lower
bound is 1/(n − j) because there are n − j future segments, and we have a random
aj
permutation of items. Therefore, for each 1 ≤ j < i, we should deduct n−j
in this
lower bound.
We now have two constraints that lower bound wi , but if we only use these two,
we will not be able to show that Greedy has a competitive ratio better than 1/2. As
described above, the further ingredient required is to show that Greedy obtains good
welfare from the items that arrive towards the end of the sequence. In Section 3, we do
this for the special case of second-order supermodular functions, proving Theorem 3.
Then, in Section 4, we apply a more general technique to obtain a slightly weaker
result for arbitrary submodular functions, proving Theorem 1.
3. Second-Order Supermodular Functions. In this section, we prove Theorem 3 which lower bounds the competitive ratio of the Greedy algorithm for online
SWM in the random order model if the valuation functions of agents are second-order
supermodular functions. We first introduce the factor-revealing linear program LPβ ,
and prove that its solution is a valid lower bound on the competitive ratio of the
Greedy algorithm. We note that β is defined in Subsection 2.2 as the expectation of
total amount by which the Greedy allocation reduces the gain of items which have
already arrived. We note that β is well defined for each weighted bipartite graph with
a set of items and agents as its two sides. In particular β does not depend on the
arrival order of items as this random permutation is incorporated in the expectation
that defines it. We also note that by normalizing OP T = 1, we can assume 0 ≤ β ≤ 1.
We treat β as a parameter in the following linear program, and not a variable.
We show in Corollary 19 of Subsection 3.1 that the value of the optimum solution
of linear program LPβ is at least 0.5312 − β. We also know the competitive ratio is
at least 21 + β2 using Lemma 8. So we conclude that on any instance of online SWM,
Greedy achieves a competitive ratio of at least max{ 21 + β2 , 0.5312−β} for some β > 0.
= 0.5104-competitive, which proves
Therefore, Greedy is always at least 12 + 0.0312
3
Theorem 3.
Let us start with describing LPβ .
β
Linear program
Pn LP
Minimize i=1 wi
Subject to:
wi ≥ bi + ai
Pi−1 aj
wi ≥ 1/n − j=1 n−j
Pn/2
j
−bj )
(aj n−j
− gi
wi ≥ j=1 n/2
Pn/2
Pn
β ≥ i=1 bi + i= n +1 gi
2

∀1 ≤ i ≤ n
∀1 ≤ i ≤ n

(1)
(2)

∀n/2 < i ≤ n

(3)
(4)

12

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

Linear program LPβ consists of 3n non-negative variables {ai , bi , wi }ni=1 and n/2
non-negative variables {gi }nn/2+1 where the non-negativity constraints are removed to
have a concise description. Following, we show that for any instance of online SWM
problem in random order model, based on the solution
Pn of Greedy algorithm, we can
find a feasible solution for LPβ with objective value i=1 wi equal to the competitive
ratio of Greedy algorithm. Consequently, we can say that competitive ratio of Greedy
is lower bounded by solution of LPβ .
Lemma 11. The solution of linear program LPβ lower bounds the competitive
ratio of Greedy algorithm for any instance of online SWM in random order model
with n online items. Parameter β is defined in Subsection 2.2.
Given an instance of online SWM and allocation of its items by Greedy algorithm,
we can set wi , ai and bi as defined in Section 2. Without loss of generality (by normalizing all values), we assume
that OPT is equal to 1. Therefore the competitive ratio
Pn
Pn
i=1 wi
of Greedy algorithm, OPT is equal to the objective function of LP β i.e.
i=1 wi .
As described in Section 2, the first two constraints of LPβ are direct implication of
Lemmas 7 and 10. In the rest, we present how to set variables gi to find a feasible
solution satisfying constraints (3) and (4). Before providing a formal proof of these
constraints, we give an intuition on how these constraints are proved and they help
us beat the 1/2 barrier.
As described in Section 2, the straightforward analysis that obtains a competitive
ratio of 1/2 shows that Greedy’s welfare from assigning the first t fraction of the items
is ≥ t − t2 /2. Therefore, at t = 0.8, we have already obtained welfare 0.48, and at
t = 0.9, we have welfare 0.495. That is, the remaining welfare from assigning the last
0.2 and 0.1 fraction of the items is 0.02 and 0.005 respectively. To improve on the
competitive ratio of 1/2, it is crucial to show that Greedy achieves a better welfare
from items that arrive at the end. The purpose of constraint (3) of LPβ is indeed
to lower bound Greedy’s welfare from assigning item i for any item that arrives in
the second half of the input, i.e. i > n/2. This lower bound is in terms of aj and
bj variables with some slack variable gi . Without putting any restriction on gi , one
could set gi to ∞ and make constraints (3) ineffective. Therefore, we prove constraint
(4) to upper bound the aggregate values of gi . We start by defining some notation to
formalize our proofs.
Definition 12. Let S1 be the sequence of items at position ≤ n/2, S2 the
sequence of items at position i such that n/2 < i ≤ 3n/4, and S3 the sequence of
items at position i > 3n/4. All of S1 , S2 , and S3 are random variables (sequences).
Let AG (S) be the allocation of items in sequence S of items by the Greedy algorithm, where we assume that no other item has arrived prior to S, and then Greedy
allocates items of sequence S one by one. We also define A∗ (S) to be the optimum
allocation of items in S.
We first intuitively show that Greedy’s allocation of items in S1 reduces the
Gains of items in S2 ∪ S3 by at least 1/4. In other words, the expected value of
Gain(S2 ∪ S3 , ∅) − Gain(S2 ∪ S3 , AG (S1 )) is at least 1/4. For the sake of providing
this intuition, we assume that the 1/2-competitive ratio analysis is tight. Therefore,
Greedy achieves a welfare of t − t2 /2 from the first 0 ≤ t ≤ 1 fraction of items. If
we simulate the arrival of items as a continuous process that happens at time interval
[0, 1] (every item arrival covering a time interval of length 1/n), we can say that items
that arrive at time t increase the welfare at the rate 1 − t. In particular, items that
arrive at small time interval [t, t+dt) approximately increase welfare by (1−t)dt. Since
the 1/2 competitive ratio analysis is tight, all this welfare increase should decrease the

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

13

Gain variables of other items and in fact only items that come in future. Knowing
1/2
(1 − t)dt = dt
the items arrive in random order, we imply that 1−t
2 is deducted from
Gain variables of items in S2 ∪ S3 for any t < 1/2. Aggregating these deductions for
R 1/2
1
all items in S1 , we have a total Gain reduction of 0 dt
2 = 4 from items in S2 ∪ S3
by Greedy allocation of items in S1 .
We note that S1 is the first half of items and S2 ∪ S3 is the second half of items.
Given the random arrival order assumption, these two sets are symmetric. Therefore,
there exists an allocation of S2 ∪S3 that reduces the Gains of S1 by 1/4 in expectation.
However, Greedy’s allocation of items in S1 may also reduce the Gains of other items
in S1 . We can compute this quantity similarly. For any t < 1/2, items in time interval
[t, t + dt) deduct the Gain of items in S1 by 1/2−t
1−t (1 − t)dt = (1/2 − t)dt. Aggregating
R 1/2
them yields the total reduction of 0 (1/2 − t)dt = 1/8. Hence, the further reduction
of Gains of S1 by allocating S2 ∪ S3 is at least 1/4 − 1/8 = 1/8. This amount of
further reduction is a concept that plays a major role in our analysis. We will capture
it by defining variable X in equation 3.1 and lower bounding it formally in Lemma 14.
We then take advantage of second-order supermodularity to argue that the ability
of a random subset of S2 ∪ S3 to reduce the Gains of items in S1 is proportional to
its size. That is, a subset of S2 ∪ S3 of size k will be able to reduce the Gain of S1 by
k 1
at least n/2
8 . In particular, the last 0.1 fraction of the items will be able to reduce
1
the Gain of S1 by at least 0.1
0.5 · 8 = 0.025; and hence there is an allocation of these
items which could obtain welfare at least 0.025. (Note that this is 5 times better than
the naive analysis of Greedy.) The only reason for Greedy to not get such a welfare
increase would be if previous allocations of items in S2 ∪ S3 already reduced the Gain
of S1 significantly. But in this case, we use Lemma 8 to show that Greedy has a
competitive ratio better than 1/2. More formally, instead of considering an explicit
fraction such as the last 0.1 fraction of the items, we quantify the improvement over
1/2 by applying this idea to write constraint (3) of LPβ for every i.
Setting variables gi . We are ready to set variables gi based on Greedy algorithm’s allocation. We need three main building blocks to be able to set variables
gi : a partial allocation Â, random variable X, and also random variables Yi for any
i > n/2.
Let Â denote the allocation of items in S2 ∪ S3 that maximizes the reduction in
Gain of items in S1 after Greedy’s assignment of items in S1 , that is:

Â :=
A

arg max
an allocation of items in

S2 ∪S3




Gain S1 , AG (S1 ) − Gain S1 , AG (S1 ) ∪ Â

Subsequently, we fix this allocation Â which is a random variable (allocation)
since S1 is a random sequence.
Recall that AG (S1 ) is the allocation of Greedy on the items in S1 . Let AG
i denote
Greedy’s allocation on the first i items from the total sequence of items (S1 , S2 , S3 );
G
therefore, we have AG
n/2 = A (S1 ). Let Âi+ denote the allocation of Â on items i
through n; that is, Â( n2 +1)+ = Â. For any n2 + 1 ≤ i ≤ n, AG
i−1 ∪ Âi+ denotes an
allocation of all n items.
Let X denote the further reduction in the Gain of items in S1 from allocating

14

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

items in S2 ∪ S3 according to Â.



X = Gain S1 , AG (S1 ) − Gain S1 , AG (S1 ) ∪ Â

(3.1)

We also define Yi for i > n/2 as the reduction in Gain of items in S1 by allocating
the items with indices i through n according to Âi+ , assuming that items with indices
1 through i − 1 were allocated according to AG
i−1 . Note that X = Yn/2+1 by definition,
but we use the shorter notation for easier reading. Formally,



G
−
Gain
S
,
A
∪
Â
Yi = Gain S1 , AG
1
i+
i−1
i−1
For each i > n/2, we let random variable Gi denote
E[X]
n/2

E[Yi ]
(n−i+1) .

X
n/2

−

Yi
(n−i+1) ,

and let gi

−
Next we show constraints (3) and (4) hold with this
denote E[Gi ] =
setting of variables gi . Constraint (3) is a direct implication of lower bounding wi in
terms of E[Yi ] (Proposition 13), and also lower bounding E[X] in terms of variables
aj and bj (Lemma 14).
By definition of Yi , we know there is a way to allocate the last remaining n − i + 1
items to reduce the Gain values of items in S1 by Yi (using allocation Âi+ ). Applying
Lemma 7 implies that the same allocation obtains welfare at least Yi . Note that the
fact that we are allocating these items greedily implies that the first of these items
obtains at least the ‘average’ welfare of any allocation. This lower bound is formalized
in the following proposition.
Proposition 13. For all i > n/2, wi ≥ E[Yi ]/(n − i + 1).
So to complete the proof of Constraint (3), it suffices to lower bound E[X] as
follows.

Pn/2 n/2 Pn/2  n/2−j
Lemma 14. E[X] ≥ j=1 aj n−j
− j=1 aj n−j + bj which can be simplified


P
j
.
−
b
to n/2
a
j
j
j=1
n−j
Proof. To prove the lemma, we first make two sub-claims:
Pn/2 n/2
Claim 1. E[Gain(S2 ∪ S3 , ∅) − Gain(S2 ∪ S3 , AG (S1 ))] = j=1 aj n−j
.


Pn/2
n/2−j
G
Claim 2. E[Gain(S1 , ∅) − Gain(S1 , A (S1 ))] = j=1 aj n−j + bj
Both these claims follow from the definitions of aj and bj , along similar lines to
the proof of Lemma 10. We recall that S1 is the first half of random permutation π
and S2 ∪ S3 is its second half, therefore the two sets S1 and S2 ∪ S3 are identically
distributed and symmetric. So it follows from Claim 1 that there exists an allocation
A′ of items in S2 ∪ S3 that reduces the Gain of items in S1 in expectation by the same
amount as Greedy’s assignment of S1 reduces the Gain of S2 ∪ S3 in expectation.
P
n/2
That is, E[Gain(S1 , ∅) − Gain(S1 , A′ )] = n/2
j=1 aj n−j .



X = Gain S1 , AG (S1 ) − Gain S1 , AG (S1 ) ∪ Â


≥ Gain S1 , AG (S1 ) − Gain S1 , AG (S1 ) ∪ A′


= Gain(S1 , ∅) − Gain S1 , AG (S1 ) ∪ A′ − Gain(S1 , ∅) − Gain S1 , AG (S1 )

≥ Gain(S1 , ∅) − Gain (S1 , A′ ) − Gain(S1 , ∅) − Gain S1 , AG (S1 )

where the first inequality follows from the definition of Â, which is the allocation
of S2 ∪ S3 that maximally reduces the Gain of S1 after Greedy’s assignment of S1 .

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

15

The last inequality follows from submodularity of valuation functions that implies
Gain(j, A) values to be monotone decreasing in set A for any item j. The lemma now
follows from taking the expectation of above equation and applying the two Claims 1
and 2.
So far we showed how to set variables gi such that constraints (3) is not violated.
We now show the same setting of
gi satisfies constraint (4) as well. We note
Pvariables
n
that by definition β is equal to i=1 bi , therefore proving constraint (4) is equivalent
of proving Lemma 15.
Pn
Pn
Lemma 15.
i=n/2+1 gi ≤
i=n/2+1 bi .
Proof. The proof of this lemma proceeds via two intermediate claims:
Claim 3. Let f be a monotone submodular function defined on a universe U .
For fixed sets S, Z ⊆ U , we define a set function R(A) for A ⊆ U \ (S ∪ Z) as follows:
R(A) = (f (S ∪ Z) − f (Z)) − (f (S ∪ Z ∪ A) − f (Z ∪ A)) .
Intuitively, R(A) captures the ability of A to reduce the marginal gain from S. If f is
a second-order supermodular function, then R is a submodular function.
We defer the proof of this claim temporarily, as it follows from the definition of
second-order supermodular functions in a straightforward way.
n−i
Claim 4. E[Yi+1 ] ≥ n−i+1
E[Yi ] − bi .
Proof. Claim 3 implies that if each agent’s valuation function is second-order
supermodular, then the reduction in Gain values of items in S1 by allocating a set of
items from S2 ∪ S3 is a submodular function of this set of items, keeping previously
G
assigned items fixed. Now, consider Yi = Gain(S1 , AG
i−1 ) − Gain(S1 , Ai−1 ∪ Âi+ ),
which is the reduction in Gain of items in S1 by allocating the last n − i + 1 items
according to Â, assuming Greedy allocated the first i − 1 items. We compare this to
G
Gain(S1 , AG
i−1 ) − Gain(S1 , Ai−1 ∪ Â(i+1)+ ), which is the reduction in Gain of items in
S1 by allocating the last n − i items according to Â, again assuming Greedy allocated
the same first i − 1 items. Keeping the first i − 1 items fixed, the last n − i items are
a random subset of the last n − i + 1 items, and since the Gain reduction function is
submodular, we have (see e.g. [11]):
h

i

G
E Gain S1 , AG
i−1 − Gain S1 , Ai−1 ∪ Â(i+1)+



n−i
n−i 
G
=
Gain S1 , AG
Yi
≥
i−1 − Gain S1 , Ai−1 ∪ Âi+
n−i+1
n−i+1
Now, it is easy to complete the proof of the claim:
h
i
n−i+1
G
· E Gain(S1 , AG
i−1 ) − Gain(S1 , Ai−1 ∪ Â(i+1)+ )
n−i
h
i
n−i+1
G
≤
· E Gain(S1 , AG
i−1 ) − Gain(S1 , Ai ∪ Â(i+1)+ )
n−i
h
i
n−i+1
G
· E bi + Gain(S1 , AG
)
−
Gain(S
,
A
∪
Â
)
≤
1
(i+1)+
i
i
n−i
n−i+1
(bi + E [Yi+1 ])
=
n−i

E[Yi ] ≤

16

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

Given this claim, the lemma follows via straightforward computations:
E[Yi+1 ] ≥

n−i
E[Yi+1 ]
E[Yi ]
bi
E[Yi ] − bi ⇒
≥
−
n−i+1
n−i
n−i+1 n−i
E[X]
bi
E[X]
− gi+1 ≥
− gi −
⇒
n/2
n/2
n−i
bi
⇒ gi+1 ≤ gi +
n−i
i
X
bj
⇒ gi+1 ≤
n−j
j=n/2+1

where the third inequality follows from the definition of gi , gi+1 , and the final
inequality comes from repeatedly applying the preceding inequality together with
gn/2+1 = 0. Therefore,
n
X

i=n/2+1

gi ≤

n
X

i−1
X

i=n/2+1 j=n/2+1

bj
=
n−j

n
X

j=n/2+1

bj

n
X

i=j+1

1
=
n−j

n
X

bj .

j=n/2+1

It now remains only to verify Claim 3:
Proof of Claim 3. To show that R is a submodular function, we define ∆R (e, A) to
be R(A ∪ {e}) − R(A), and then argue that for sets A, B such that A ⊆ B, we have
∆R (e, A) ≥ ∆R (e, B). By definition of ∆R , we have:
∆R (e, A) = (f (S ∪ Z) − f (S)) − (f (S ∪ Z ∪ A ∪ {e}) − f (Z ∪ A ∪ {e}))

− [(f (S ∪ Z) − f (S)) − (f (S ∪ Z ∪ A) − f (Z ∪ A))]
= (f (Z ∪ A ∪ {e} − f (Z ∪ A)) − (f (S ∪ Z ∪ A ∪ {e}) − f (S ∪ Z ∪ A))

= M G(Z ∪ A, e) − M G(S ∪ Z ∪ A, e)

where M G(S, e) denotes the marginal gain (under function f ) of adding e to S. If we
use A′ to denote Z ∪ A, we have:
∆R (e, A) = M G(A′ , e) − M G(S ∪ A′ , e).
Similarly, if B ′ denotes Z ∪ B, we have:
∆R (e, B) = M G(B ′ , e) − M G(S ∪ B ′ , e).
Now, obviously A′ ⊆ B ′ , and from the definition of second-order supermodularity
of f , we have ∆R (e, A) ≥ ∆R (e, B).

This completes the proof of Lemma
15.
Pn
Recall that β was defined as i=1 bi which concludes the proof of constraint (4):
Pn/2
Pn
Corollary 16. β ≥ i=1 bi + n/2+1 gi .

3.1. Analyzing the Factor-Revealing Linear Program. We want to lower
bound the solution of LP β in this subsection. To simplify the analysis, we will relax
some constraints of LPβ and analyze the relaxed linear program LPβ,λ for some λ ≥
1/2 that we set later. We note that LP β,λ is derived from LP β by removing two sets
of constraints:

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

• For any i > λn, the type (2) constraint for i is removed.
• For any n/2 < i ≤ λn, the type (3) constraint for i is removed.
β,λ
Linear program
Pn LP
Minimize i=1 wi
Subject to:
wi ≥ bi + ai
∀1 ≤ i ≤ n
(1)
Pi−1 aj
∀1 ≤ i ≤ λn (2)
wi ≥ 1/n − j=1 n−j
Pn/2
j
−bj )
(aj n−j
− gi ∀λn < i ≤ n (3)
wi ≥ j=1 n/2
Pn/2
Pn
β ≥ i=1 bi + i= n +1 gi
(4)

17

2

Proposition 17. For any λ ≥ 1/2, the solution of LPβ,λ is at most the solution
of LPβ .
Thus, a lower bound on LPβ,λ will give us the desired lower bound on LPβ . In the
following Theorem (proved at the end of this subsection), we lower bound the value
of the optimum solution of LPβ,λ .
2
+ 1−λ
Theorem 18. The solution of LPβ,λ is at least 12 − (1−λ)
2
4 − β for any
√
β ≥ 0, and λ > 1 − ( 68 − 8).
The following Corollary concludes the main goal of this subsection to lower bound
LPβ .
Corollary 19. The solution of LPβ is at least 0.5312 − β.
√
Proof. Using Proposition 17, Theorem 18, and setting λ = 0.754 > 1 − ( 68 − 8),
2
we achieve a lower bound of 12 − (0.246)
+ 0.246
− β > 0.5312 − β on the solution of
2
4
β
LP .
Before elaborating on the formal proof Theoem 18, we provide an overview of the
analysis. To lower bound the optimum solution of LPβ,λ , we take three main steps:
• We show there exists an optimum solution in which each bi is set to 0, and
therefore they all can be removed.
• We then show one can assume that in the optimum solution, constraint (2)
is tight for any i ≤ λn, and also constraint (3) is tight for any i > λn. We
also show that a choice of large enough λ implies tightness of constraint (1)
for any i.
• After taking the first two steps, we have a simplified linear program with
enough tight variables that the optimum solution can be explicitly computed.
In particular, given the tightness of constraint (2), one can inductively compute each wi as a function of i and n for any i ≤ λn. For higher values of
i, tightness of constraint 3 yields the exact value of wi + gi . Applying constraint (4) bounds the sum of variables gi and consequently gives the value
of optimum solution as a function of β.
We start by eliminating all variables {bi }ni=1 .
Lemma 20. There exists an optimum solution for LPβ,λ in which bi = 0 for all
1 ≤ i ≤ n.
Proof. Suppose bk > 0 for some k > n/2: Set bk to 0, and note that we still have a
feasible solution, since the first constraint still holds for wk , and all other constraints
bk
for
are unaffected. Now, suppose bk > 0 for some k ≤ n/2: Increase each gj by n/2
each j > n/2, and then set bk to 0. Constraints (1) and (2) still hold since their right
hand sides either remained unchanged or decreased. The right hand side of constraint
(3) for any i > λn is effected by the changes in variables bk and gi . Note that the
coefficient of bk in this constraint is −2/n and variable gi was increased by exactly

18

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

bk
n/2 .

Therefore these two changes cancel each other out and this lower bound on wi
is not raised. The constraint (4) is also unchanged because in its right hand side,
bk
and variable bk is decreased by this total
n/2 variables gi are each increased by n/2
amount. Since all constraints are still satisfied, we can repeat this process for each
bk > 0 without raising the value of the objective function.
We can now remove all variables bi ’s from LPβ,λ . We then prove that for all
i ≤ λn, constraint (2) is a tight lower bound for wi , while for i > λn, constraint (3)
is a tight lower bound.
Lemma 21. There exists an optimum solution to LPβ,λ in which constraints (2)
and (3) are tight, and also bi = 0 for all 1 ≤ i ≤ n.
Proof. Suppose this is not true; fix an optimal solution satisfying Lemma 20. Let
k be the smallest index such that the inequality is not tight for k, and let δ be how
much wk exceeds the lower bound from the relevant inequality. Decrease wk by δ,
and to ensure that we satisfy the constraint wk ≥ bk + ak , also decrease ak by δ. To
keep the rest of the constraints valid, for each j > k, we increase wj by δ/(n − k). To
see that these changes keep all the constraints satisfied, we note that variables wi do
not appear on the right hand side of the constraints, so they do not change the lower
bounds. The only change that effects the right hand sides is increment of ak which
becomes relevant in constraint (3) only for k ≤ n/2. In this case, the increment does
not exceed δ/(n − k), and the associated wi for this constraint is increased by this
amount to keep it satisfied. So after these updates, we still have a feasible solution.
Moreover, these updates do not increase the objective value. So far, we have argued
that the inequality for wk is now tight and we still have a feasible solution, but since
some other constraint may no longer be tight, we have to show that this process
terminates. To see this, note that we only affected constraints for j > k, so the
smallest index for which the inequality is not tight has increased. Therefore, in at
most n iterations, we find an optimum solution in which all inequalities are tight. We
also note that in this process variables bi are intact which means we can assume they
remain zero after all these updates given Lemma 20.
Up to this point, we have not used λ at all, and all our claims hold√for any
1/2 ≤ λ ≤ 1. Our next lemma shows that by choosing a large enough λ > 1−( 68−8),
one can assume that the constraints
wi ≥ ai are tight for all i.
√
Lemma 22. If λ > 1 − ( 68 − 8), any optimum point for LPβ,λ has wi = ai for
every i.
Proof. Suppose wk > ak for some k > n/2, simply set ak = wk . All constraints
still hold, since ak appears only on the right hand side of constraint (3) with a negative
coefficient; therefore, increasing it keeps the solution feasible. Please also note that
for k > n/2, ak does not appear on the right hand side of constraint (3). Therefore
we can assume ak = wk for any k > n/2.
Now we focus on the case k ≤ n/2. Suppose wk − ak = δ for some positive δ and
k ≤ n/2. Increase ak by δ. To maintain feasibility, we need to adjust all wi and ai
δ(n−i)
,
for i > k as follows. For each k < i ≤ λn, decrease both ai and wi by (n−k)(n−k−1)
δk
and for each λn < i ≤ n, increase ai and wi by (n−k)n/2 .
We first note that constraint (1) remains satisfied since the wi and ai changes are
synced. Constraint (4) is also unaffected since we did not change its variables. So to
see the other constraints (2) and (3) are still feasible, we track the changes in their
left and right hand sides. Clearly, these constraints are not affected for i ≤ k. For
δ(n−i)
, and we
k < i ≤ λn (associate with constraint (2)), wi is decreased by (n−k)(n−k−1)

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

19

show that the right hand side of constraint (2) is decreased accordingly. For i = k + 1,
δ
the decrease in both sides of the inequality is exactly n−k
; we prove it by induction
for other values of i. The total change on the right hand side is:

−

i−1
X
δ
δ(n − j)
1
δ
+
×
=
(−(n−k−1)+i−k−1)
n−k
(n − k)(n − k − 1) n − j
(n − k)(n − k − 1)
j=k+1

δ(n−i)
This sums up to a total decrease of (n−k)(n−k−1)
which matches the decrement
of the left hand side (variable wi ), and shows constraint (2) remains feasible, and
completes the claim for i ≤ λn.
For i > λn (associated with constraint (3)), it is clear that the rightmost side of
δk
constraint (3) is not increased by more than (n−k)n/2
because the only term which
increased in the right hand side of constraint (3) corresponds to ak , which increased
by exactly this quantity. (Note that values of ai for i > λn were increased, but
these either do not participate in the rightmost sides of constraints (2) and (3) or
have negative coefficients there.) We also note that the leftmost side of constraint (3)
which is wi increased exactly this amount, so all the constraints remained feasible.
To conclude, we
Pnjust need to show that all these changes did not increase the
objective function i=1 wi . From values of i ≤ λn, the total decrease in the objective
is equal to:

λn
X

i=k+1

δ[(n − k − 1)(n − k)/2 − (n − λn − 1)(n − λn)/2]
δ(n − i)
=
(n − k)(n − k − 1)
(n − k)(n − k − 1)

Since we are considering the case k ≤ n/2, the above term is minimized at k =
n/2, and is at least δ(1/2 − (1 − λ)2 /8) at that point.
On the other hand, the total increase in the objective due to values of i > λn is
δk
. This total is maximized at k = n/2, and is equal to 2(1 − λ)δ.
(1 − λ)n × (n−k)n/2
√
For λ > 1 − ( 68 − 8) ≈ 0.7538, the total increase in the objective is less than the
total decrease, which contradicts the optimality of the solution. So wi is indeed equal
to ai for all i.
Using the previous 3 lemmas, we can exactly compute the values of each wi , and
therefore lower bound the solutions of LPβ,λ and LPβ as follows:
Proof of Theorem 18. Using Lemma 20 and Lemma 21, we can eliminate all b variables,
and at the same time assume that constraints (2) and (3) of LPβ,λ are tight. To
simplify further, we can use Lemma 22 to set each ai equal to wi .
To compute wi for each i ≤ λn, we use the tightness of constraint (2) in LPβ,λ .
So we have:
wi = 1/n −

i−1
i−1
X
X
wj
aj
= 1/n −
n
−
j
n
−j
j=1
j=1

n−i
for any i ≤ λn.
We can inductively prove that wi is (n−1)n
Since we know wi for each i ≤ n/2, we can compute the lower bound in constraint

20

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

(3) of LPβ,λ . For each i > λn, we know constraint (3) is tight, giving:
wi =

Pn/2

=

j=1

j
aj n−j

n/2

− gi =

(n/2)(n/2+1)/2
(n−1)n

n/2

Pn/2

n−j
j=1 (n−1)n

− gi ≥

n/2

×

j
n−j

− gi =

Pn/2

j
j=1 (n−1)n

n/2

− gi

1
− gi
4n

Summing up these equations and applying constraint (4), we have the following
lower bound on the objective:
n
X

wi =

λn
X
i=1

i=1

≥

wi +

n
X

i=λn+1

wi ≥

n
X
n−i
1
+ (1 − λ)n( ) −
gi
(n − 1)n
4n

Pλn

i=1

i=λn+1

(n − 1)n/2 − (n − λn − 1)(n − λn)/2 1 − λ
1 (1 − λ)2
1−λ
+
−β ≥ −
+
−β
(n − 1)n
4
2
2
4


4. General Submodular Functions. In this section, we prove Theorem 1 that
lower bounds the competitive ratio of Greedy for general submodular functions. For
arbitrary submodular functions, we can no longer use the technique of the previous
section to argue that we obtain sufficient welfare from each of the itemsP
in S2 ∪ S3 .
Instead, here we use a different constraint that provides a lower bound on i>3n/4 wi ,
which is Greedy’s expected aggregate increase in welfare when assigning S3 , the last
quarter of items. We first need to set some notation for concatenation of multiple
subsets (sequences) of items.
Definition 23. We define hS1 , S2 , · · · , Sℓ i to be the concatenation of sequences
of items S1 , S2 , · · · , Sℓ . This definition can be similarly extended to any series of
sequences of items. For any sequence Sk , we abuse notation and use Sk to denote
both a sequence of items and the set of these items, but the meaning will always be
clear from context.
We consider the simulated sequence of items S ′ = hS1 , S2 , S3 , S2 , S3 , S2 i. In other
words, we will analyze how one could assign items if after the items in S1 arrive, items
in S2 and S3 arrive multiple times. We assign items of S ′ using the following allocation
A′ = AG (hS1 , S2 , S3 i) ∪ AG (hS2 , S3 i) ∪ A∗ (S2 ). That is, we first use Greedy to assign
the items of hS1 , S2 , S3 i; then, we use the different allocation given by Greedy on
hS2 , S3 i assuming nothing has been assigned so far (that is, ignoring the previous
allocation of Greedy on hS1 , S2 , S3 i). Finally we use the optimum allocation for S2 .
A′ is defined as the union of these three allocations.
To show that Greedy gets sufficient value from items in S3 , we will lower bound
the value of A′ on the last five segments hS2 , S3 , S2 , S3 , S2 i. This part of the value of
A′ can be formally written as V (A′ ) − V (AG (S1 ))2 . The rest of this section consists
of three major parts:
• Lower bounding the marginal value of A′ on the last five segments by:
n/2

E[V (A′ ) − V (AG (S1 ))] ≥

1 X
+
4 i=1




i − n/4
ai − b i +
n−i

3n/4

X

i=n/2+1

n/4
ai
n−i

(4.1)

2 Recall from Definition 4 that V (A) for some allocation A denotes the total welfare or value of
the allocation.

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

21

This part of the proof is implied by noting that marginal value of allocation A′
on the last five segments is at least how much it reduces the Gains of all items
(Lemma 7), and then investigating the Gain reductions of the sets S1 , S2 and S3
separately in Claims 5, 6 and 7.
P
• We then use Equation 4.1 and lower bound
i>3n/4 wi which is the Greedy’s
expected welfare increase from items in S3 . This part is formalized in Lemma 24.
It is interesting to note that the lower bound terms of both Equation 4.1 and
consequently the one in Lemma 24 are in terms of 9n/4 variables {ai , bi , wi } for
1 ≤ i ≤ 3n/4.
• Finally, we can combine the lower bound of Equation 4.1 with other Lemmas and
conclude that competitive ratio of Greedy is at least:

n/2 
1 X
i − n/4
5
(1 +
+
)ai + bi +
24 i=1
6(n − i)
6

3n/4

X

i=n/2+1



5
n/4
5
( +
)ai + bi
6 6(n − i)
6

3n/4

+

X 5
(wi − ai − bi )
6
i=1

(4.2)

which does not depend directly on the last quarter of items because their marginal
contributions in welfare has been already encoded in Equation 4.2. The rest of
the proof is analyzing Equation 4.2 and show that it is always at least 0.5052
which completes the proof of Theorem 1.
We now start by proving Equation 4.1 formally which is essentially lower bounding
E[V (A′ ) − V (AG (S1 ))].

Proof of Equation 4.1. Using Lemma 7, we know it suffices to measure how much this
allocation reduces the Gain values of all items. That is, E[V (A′ ) − V (AG (S1 ))] ≥
E[Gain(N, AG (S1 )) − Gain(N, A′ )]. Since N = S1 ∪ S2 ∪ S3 , we can lower bound the
desired quantity by separately lower bounding E[Gain(Sk , AG (Sk )) − Gain(Sk , A′ )]
for each of k = 1, 2, 3 which is done in Claims 5, 6 and 7.
Pn/2 n/2
Pn/2
Claim 5. E[Gain(S1 , AG (S1 )) − Gain(S1 , A′ )] ≥ i=1 n−i
ai − i=1 ( n/2−i
n−i ai +
bi ).
Proof. For any item j, Gain(j, AG (hS2 , S3 i)) is at least Gain(j, A′ ) by submodularity and the fact that AG (hS2 , S3 i) ⊆ A′ . So to lower bound E[Gain(S1 , AG (S1 )) −
Gain(S1 , A′ )], it suffices to lower bound:
E[Gain(S1 , AG (S1 )) − Gain(S1 , AG (hS2 , S3 i))] =
E[Gain(S1 , ∅) − Gain(S1 , AG (hS2 , S3 i))] − E[Gain(S1 , ∅) − Gain(S1 , AG (S1 ))]

Pn/2 n/2
ai
It follows that E[Gain(S1 , ∅) − Gain(S1 , AG (hS2 , S3 i))] is equal to i=1 n−i
from symmetry and the definition of ai variables. To see this, note that π ′ =
hS2 , S3 , S1 i is also a random permutation in which hS2 , S3 i is the first half of items,
and S1 is the second half. Now we want to lower bound how much Greedy’s allocation of first half items in the random permutation π ′ reduces the Gain variables of
second half items of π ′ . We know that for any i ≤ n/2, the ith item in π ′ reduces
the Gain variables of items that appear in positions greater than i in π ′ by ai , and
n/2
(as in Lemma 10), in expectation n−i
fraction of this reduction is associated with
items in positions greater than n/2. Similarly, we can consider the original random
permutation π = hS1 , S2 , S3 i, and see that the allocation of items in S1 reduces the

22

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

P
n/2−i
Gain variables of other items in S1 by a total of n/2
i=1 n−i ai + bi . This proves the
desired claim.
Pn/2 n/4
Claim 6. E[Gain(S2 , AG (S1 )) − Gain(S2 , A′ )] = 41 − i=1 n−i
ai .
Proof. Since S2 is a random quarter of all items, we have that E[Gain(S2 , ∅)] =
1
′
∗
4 , and since A concludes with the optimum allocation on items of S2 (A (S2 )),
1
′
G
′
Gain(S2 , A ) is zero. So E[Gain(S2 , A (S1 ))−Gain(S2 , A )] is equal to 4 −(E[Gain(S2 , ∅)−
Gain(S2 , AG (S1 ))]). The latter term can be exactly calculated from the fact that allocating the item in the ith position reduces the gains of subsequent items by ai , and n/4
of the n− i remaining items are in S2 ; therefore, E[Gain(S2 , ∅)− Gain(S2 , AG (S1 ))] =
Pn/2 n/4
i=1 n−i ai .
P3n/4
n/4
ai .
Claim 7. E[Gain(S3 , AG (S1 )) − Gain(S3 , A′ )] ≥ i=n/2+1 n−i
G
′
Proof. Since A (hS1 , S2 i) is a subset of A , it suffices to lower bound
E[Gain(S3 , AG (S1 )) − Gain(S3 , AG (hS1 , S2 i))].
Similarly to the proof of the previous claim, this reduction in Gain of items in S3
n/4
from allocating the ith item for any n/2 < i ≤ 3n/4 is n−i
ai . This shows how much
allocating items of S2 reduce Gain of items in S3 .
From the three preceding claims, we conclude Equation 4.1 which is:
E[V (A′ ) − V (AG (S1 ))] ≥ E[Gain(N, AG (S1 )) − Gain(N, A′ )]

n/2 
n/2
3n/4
n/2
X
X
X
1 X n/4
n/2 − i
n/2
ai −
ai + b i + −
ai +
≥
n−i
n−i
4 i=1 n − i
i=1
i=1

i=n/2+1

=

1
+
4

n/2

X
i=1

i − n/4
ai − b i
n−i



3n/4

+

X

i=n/2+1

n/4
ai
n−i

n/4
ai
n−i
(4.1)

where the first inequality holds because of Lemma 7 and the second is derived by
applying the three claims. This lower bound concludes the proof of Equation 4.1. 
Now that we have proved Equation 4.1, the first main part of proof of Theorem 1
is complete. As the second main step, we apply Equation 4.1 to achieve a lower bound
on the expected welfare gain of the last quarter of items.
Lemma 24. The expected increase in welfare that Greedy achieves for the last
Pn/2 i−n/4
P3n/4
P
n/4
1
+ i=1 ( 6(n−i)
ai − 61 bi ) + i=n/2+1 6(n−i)
ai −
quarter of items i>3n/4 wi is at least 24
P
3n/4
1
6
i=n/2+1 wi .
Proof. We use X to denote the lower bound obtained in Equation 4.1 on how much
A′ increases the welfare from the rest of S ′ after items in S1 have already arrived. In
other words, this
Pis how much it increases its welfare by allocating hS2 , S3 , S2 , S3 , S2 i.
We use W3 = i∈S3 wi to denote how much A′ increases its welfare by allocating
items in the first copy of S3 , and since items in the first copy are assigned greedily (in
A′ ), their total increase in the welfare is at least as much as the increase in welfare
A′ obtains by allocating the second copy S3 (this is easy to verify for each item). So
A′ in total increases its welfare from the two copies of S3 by at most 2W3 .
Let S2′ be the sequence hS2 , S2 , S2 i derived from S ′ by removing the initial copy
of S1 and the two copies of S3 . Let A′2 be the projection of allocation A′ on sequence
S2′ ; in other words, A′2 is an allocation of sequence S2′ , and it is consistent with A′
on this sequence. It is clear that after the allocation AG (S1 ), allocating the three

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

23

copies of S2 using A′2 increases the welfare by at least X − 2W3 since removing the
two copies of S3 will not reduce the welfare by more than 2W3 .
We now appeal to symmetry and switch the argument from S2 to S3 . Given set
S1 , S2 is a random sequence of half of the items in N \ S1 , and so is S3 ; that is, given
sequence S1 , the two sequences S2 and S3 have the same distribution. Suppose S1 is
allocated by Greedy; as argued above, we know that after this allocation it is possible
to allocate three consecutive copies of S2 using A′2 and increase the welfare by at least
X − 2W3 in expectation. Therefore we can claim that after allocation AG (S1 ), it is
possible to allocate three copies of S3 and increase the welfare by the same amount of
at least X −2W3 . Formally, there exists an allocation A′3 of sequence S3′ = hS3 , S3 , S3 i
such that E[V (AG (S1 ) ∪ A′3 ) − V (AG (S1 ))] is at least X − 2W3 .
Now consider the sequence hS1 , S2 , S3 , S3′ i, which begins with the original sequence S = hS1 , S2 , S3 i and then has three copies of S3 . For this sequence, consider
the allocation AF inal = AG (hS1 , S2 , S3 i) ∪ A′3 ; that is, we first assign the original sequence hS1 , S2 , S3 i according to Greedy, and then assign the three copies of S3 using
F inal
A′3 . The increase in welfare by allocating
is at
P the last three copies of S3 in A
least X − 2W3 − W2 − W3 where W2 = i∈S2 wi . Now there are four copies of S3 in
the sequence hS1 , S2 , S3 , S3′ i. Since the first copy of S3 is allocated greedily in AF inal ,
its increase in welfare which is W3 is at least as much as the increase in welfare of
any the other copies of S3 in AF inal , and hence also at least as much as the average
of increase in welfare by these three copies. We conclude that:

W3 ≥
which implies W3 ≥
W3 ≥

1
4

+

X−W2
.
6

Pn/2

X − 2W3 − W2 − W3
3

By definition of X and W2 , we have:

i−n/4
i=1 ( n−i ai

− bi ) +

P3n/4

n/4
i=n/2+1 n−i ai

6

−

P3n/4

i=n/2+1

wi

which concludes the proof.
We now have all the building blocks we need to conclude the last step of proof
of Theorem 1. We provide a lower bound on the total welfare obtained by Greedy
in terms of wi , ai , and bi associated with the first 3n/4 items. This lower bound is
strong enough that we can consequently prove Greedy achieves a competitive ratio
better than 12 .


P
i−n/4
5
1
+ n/2
Lemma 25. The expected welfare obtained by Greedy is at least 24
i=1 (1 + 6(n−i) )ai + 6 bi +

 P
P3n/4
3n/4 5
n/4
5
5
(
+
)a
+
b
i=1 6 (wi − ai − bi ).
i=n/2+1
6
6(n−i) i
6 i +
Pn/2
Proof. We can write the expected increase in welfare by Greedy as i=1 wi +
P3n/4
Pn
P
i>3n/4 wi ,
i=3n/4+1 wi . Using Lemma 24 to lower bound the last term
i=n/2+1 wi +
P
P
3n/4
n/2
i−n/4
n/4
1
+ i=1 ( 6(n−i) ai − 61 bi ) + i=n/2+1 6(n−i) ai +
we conclude that the welfare is at least 24
P
P
3n/4
n/2
5
i=1 wi .
i=n/2+1 wi +
6
Since the coefficient of each wi is positive (either 56 or 1) in this lower bound, we
P3n/4
can apply Lemma 7 to replace each wi with ai +bi , and add the sum i=1 65 (wi −ai −
bi ) while still having a valid lower bound. It suffices to merge the sums to conclude
the claim of this lemma.

24

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

Using Lemma 25, proving Theorem 1 is reduced to analyzing the minimum value
3n/4
expression 4.2 can take based on the 9n/4 variables {ai , bi , wi }i=1 . One can think
about it as a linear program that we analyze in the rest:
Proof of Theorem 1. Using Lemma 25, we know that for any instance the expected
gain of greedy is at least:

 3n/4
3n/4 
n/2 
X
X 5
5
i − n/4
5
n/4
5
1 X
( +
(1 +
+
)ai + bi +
)ai + bi +
(wi −ai −bi )
LB =
24 i=1
6(n − i)
6
6 6(n − i)
6
6
i=1
i=n/2+1
3n/4

for some set of 9n
7 and 10,
4 numbers {wi , ai , bi }i=1 all in [0, 1]. From Lemmas
Pi−1 aj
1
we know they satisfy the inequalities wi ≥ ai + bi , and wi ≥ n − j=1 n−j for any
1 ≤ i ≤ 3n
4 . The minimum value of LB among the feasible solutions of these linear
constraints lower bounds the competitive ratio of Greedy algorithm. We prove that to
minimize LB given these linear constraints, one can assume w.l.o.g. that wi = ai + bi
3n
for any i ≤ 3n
4 as follows. Suppose for some i ≤ 4 , the gap δ = wi − (ai + bi ) is
positive. We increase bi by δ. The value of LB is intact because on one hand 56 bi
appears in either the first or second summation in the lower bound, and − 56 bi appears
Pi=1 aj
in the third summation. The inequalities wi ≥ ai + bi and wi ≥ n1 − j=1 n−j
are
also still satisfied, and wi is now equal to ai + bi . Performing this update for every
constraint wi ≥ ai + bi that is not tight, we can assume that wi = ai + bi for any
′
i ≤ 3n
4 . Therefore it suffices to lower bound the following simplified expression LB :
LB ′ =


n/2 
X
i − n/4
1
5
(1 +
+
)ai + bi +
24 i=1
6(n − i)
6

3n/4

X

i=n/2+1



5
n/4
5
( +
)ai + bi
6 6(n − i)
6

3n/4



numbers {ai , bi }i=1 all in [0, 1] with linear constraints ai + bi ≥
for some set of 3n
Pi−1 aj 2
1
3n
j=1 n−j for any 1 ≤ i ≤ 4 .
n −
We find the minimum value of LB ′ among all feasible solutions of these linear constraints. Our analysis is somewhat similar to that in Subsection 3.1 for the
parametrized linear program. First, we prove that there exists an optimum
Pi−1 solution
aj
for
(minimizing LB ′ , and satisfying the constraints) in which ai + bi = n1 − j=1 n−j
3n
any 1 ≤ i ≤ 4 . In other words, the linear constraints should be tight. Second, we
show that there exists an optimal solution in which, furthermore, all bi values are 0.
This then allows us to explicitly find the values of ai in this optimal solution, and we
can evaluate LB ′ explicitly.
We begin by showing that all the linear constraints are tight, and bi values are 0;
3n/4
we prove this by contradiction. Let {a∗i , b∗i }i=1 be an optimum solution of this linear
program. Suppose i is the smallest index for which either this constraint is not tight
or b∗i is not zero. At first we consider
the case that the constraint is not tight. Define

Pi−1 a∗j 
1
∗
∗
δ > 0 to be the gap ai + bi − n − j=1 n−j . We change the solution as follows
and claim that the new solution is still feasible and the objective function LB ′ has
not increased.

anew
j


∗

 aj
= a∗j − δ

 a∗ +
δ(n−j)
j
(n−i)(n−i−1)

if j < i
if j = i
if j > i

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

25

We keep all b values intact, i.e. bnew
= b∗j for each 1 ≤ j ≤ 3n
j
4 . To prove
the
feasibility
of
solution
is
maintained,
we
should
show
that
constraint
aj + b j ≥

Pj−1 aj′ 
1
still holds. For j < i, all variables are intact, and therefore this
j ′ =1 n−j ′
n −

constraint still holds. For j = i, the constraint holds (and is tight now) by definition
δ(n−j)
, and the right hand
of δ. For j > i, the left hand side is increased by (n−i)(n−i−1)
′
P
Pj−1
j−1
δ(n−j )
1
δ
δ
δ
=
side is changed by n−i − j ′ =i+1 (n−i)(n−i−1) n−j ′ = n−i − j ′ =i+1 (n−i)(n−i−1)

δ(n−j)
− i − 1) − (j − 1 − i)) = (n−i)(n−i−1)
. Therefore both sides of the
constraint change in the same way which means the constraint still holds, and the
solution remains feasible. Now we prove that the objective function has not increased.
There are two cases: a) i ≤ n2 , and b) i > n2 . For i ≤ n2 , the change in the objective
function is equal to:
δ
(n−i)(n−i−1) ((n





n/2 
3n/4 
X
X
j − n/4
5
δ(n − j)
δ(n − j)
n/4
i − n/4
1+
δ+
+
+
− 1+
6(n − i)
6(n
−
j)
(n
−
i)(n
−
i
−
1)
6
6(n
−
j)
(n
−
i)(n − i − 1)
j=i+1
j=n/2+1






n/2 
3n/4 
X
X
23n
21n
δ
− 23n − 5i (n − i − 1) +
− 5j +
− 5j 
=
6(n − i)(n − i − 1)
4
4
4
j=i+1
j=n/2+1




3n/4
X
δ
− 23n − 5i (n − i − 1) + 23n (n/2 − i) + 21n (n/4) −
5j 
=
6(n − i)(n − i − 1)
4
4
4
j=i+1


δ
23n
21n
(3n/4)(3n/4 + 1)
i(i + 1)
=
5i(n − i − 1) −
(n/2 − 1) +
(n/4) − 5
+5
6(n − i)(n − i − 1)
4
4
2
2


δ
23n
21n
(3n/4)(3n/4 + 1)
=
5i(n − (i + 1)/2) −
(n/2 − 1) +
(n/4) − 5
6(n − i)(n − i − 1)
4
4
2
If the above expression is positive for some 1 ≤ i ≤ n2 , it should be positive
for i = n/2 that maximizes the term i(n − (i + 1)/2). We note that the coefficient
δ
n
6(n−i)(n−i−1) is positive for all values of i. For i = 2 , the above expression becomes:



n
23n
21n
(3n/4)(3n/4 + 1)
δ
5 (n − (n/2 + 1)/2) −
(n/2 − 1) +
(n/4) − 5
6(n − i)(n − i − 1)
2
4
4
2


δ
15 23 21 45 2
5 23 15
=
( −
+
− )n + (− +
− )n
6(n − i)(n − i − 1)
8
8
16 32
4
4
8


60 − 92 + 42 − 45 2
−10 + 46 − 15
δ
(
)n + (
)n
=
6(n − i)(n − i − 1)
32
8


δ
−35 2
21
=
(
)n + ( )n
6(n − i)(n − i − 1)
32
8
The above expression is negative for n > 2. Therefore these updates do not
increase the objective function for any i ≤ n2 . To prove the same claim for i > n2 , we
write down the changes in the objective function:

26

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM



3n/4


X 5
δ(n − j)
n/4
+
6 6(n − j) (n − i)(n − i − 1)
j=i+1





3n/4 
X 21n
δ
21n
−
=
− 5i (n − i − 1) +
− 5j 
6(n − i)(n − i − 1)
4
4
j=i+1
−

5
n/4
+
6 6(n − i)



δ+

It is not hard to see that the above expression is always non-positive. We note
21n
that 21n
4 − 5i is greater than 4 − 5j for each j > i, and the number of different j
indices in the sum is less than n − i − 1. Therefore the expression inside the large
δ
is positive. We conclude
parentheses is not positive, and its coefficient 6(n−i)(n−i−1)
that the updates do not increase the objective function for any value of i. Therefore
Pi−1 a∗j
.
we can assume that the constraints are tight: a∗i + b∗i = n1 − j=1 n−1
Now we show how to update the solution when b∗i is equal to some δ > 0. We
prove that without increasing the objective function we can set b∗i to zero. We change
the solution as follows:

anew
j


∗

 aj
= a∗j + δ

 a∗ −
δ(n−j)
j
(n−i)(n−i−1)

if j < i
if j = i
if j > i

We set bnew
= 0, and keep the rest of b values intact. Similar to the previous
i
updates, these changes maintain feasibility. We just need to prove that the objective
function has not increased. Again we have two cases. If i ≤ n2 , the change in the
objective function is:


3n/4 
n/2 
X
X
δ(n − j)
δ(n − j)
5
n/4
j − n/4
−
+
δ−
1+
6(n − j) (n − i)(n − i − 1)
6 6(n − j) (n − i)(n − i − 1)
j=i+1
j=n/2+1




n/2 
3n/4 
X
X
23n
21n
3n
δ
 (n − i − 1) −
− 5j −
− 5j 
6(n − i)(n − i − 1)
4
4
4
j=i+1
j=n/2+1


3n/4
X
δ
3n
23n
21n
 (n − i − 1) −
5j 
(n/2 − i) −
(n/4) +
6(n − i)(n − i − 1)
4
4
4
j=i+1


n
(3n/4)(3n/4 + 1)
i(i + 1)
δ
(3n − 5i − 5 − 23n/2 + 23i − 21n/4) + 5
−5
6(n − i)(n − i − 1) 4
2
2



δ
65
5
9n 5(i + 1)
− n2 + n + i
−
6(n − i)(n − i − 1)
32
8
2
2


=

=
=
=

i − n/4
1
+
6 6(n − i)



If the above expression is positive for some 1 ≤ i ≤ n2 , it should be positive
5(i+1)
for i = n/2 that maximizes the term i( 9n
). We note that the coefficient
2 −
2
δ
n
is
positive
for
all
values
of
i.
For
i
=
6(n−i)(n−i−1)
2 , the above expression becomes:
δ
6(n − i)(n − i − 1)




65 2 5
δ
n 9n 5(n/2 + 1)
13
5
− n + n+
=
−
(− n2 − n)
32
8
2 2
2
6(n/2)(n/2 − 1) 32
8

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

which is negative. So the updates do not increase the objective function for i ≤
For i > n2 , the total change in the objective function is:

27
n
2.


3n/4 
X 5
n/4
δ(n − j)
n/4
δ−
+
6(n − i)
6
6(n
−
j)
(n
−
i)(n − i − 1)
j=i+1



3n/4 
X
n
21n
δ
 (n − i − 1) −
− 5j 
=
6(n − i)(n − i − 1) 4
4
j=i+1




δ
n
n 21n 5 3n 3n
5
=
(n − i − 1) − ×
+ ×
+ 1 − i(i + 1)
6(n − i)(n − i − 1) 4
4
4
2
4
4
2


δ
1 21 45 2
1 15
n 5
=
( −
+ )n + (− + )n + −( + (i + 1))i
6(n − i)(n − i − 1)
4 16 32
4
8
4
2
If the above expression is positive for some i > n2 , it should be positive for i = n2 +1
). For i = n2 + 1, the above expression becomes:
that minimizes the term i( n4 − 5(i+1)
2


  n

δ
11 2 13
n 5 n
n + n−
+
+2
+1
6(n − n/2 − 1)(n − n/2 − 2) 32
8
4
2 2
2


δ
13 2 19
=
− n − n−5
6(n/2 − 1)(n/2 − 2)
32
8
which is negative for any value of n.
We note that these updates only change the variables with higher indices keeping
a∗j , and b∗j intact for j < i. Therefore after performing these update operations
iteratively for at most n times (i = 1, 2, · · · , n), we make sure that all constraints are
tight, and all b∗ values are zero. Now we can assume that there exists an optimum
3n/4
solution {a∗i , b∗i }i=1 of the linear program that lower bounds the competitive ratio
Pi−1 a∗j
(the constraints are
of Greedy in which b∗i is zero for any i, and a∗i = n1 − j=1 n−j
n−i
∗
tight). We can recursively find a values, and imply that ai is equal to (n−1)n
. The
objective function at this optimum point is equal to:
n/2

LB ′ =

X
1
+
24 i=1




i − n/4
5
1+
a∗i + b∗i +
6(n − i)
6

 
n/2 
X
1
i − n/4
=
1+
a∗i +
+
24 i=1
6(n − i)

3n/4

i=n/2+1

3n/4

X

X

i=n/2+1





5
n/4
+
6 6(n − i)

5
n/4
+
6 6(n − i)



a∗i



5
a∗i + b∗i
6




3n/4  21n
X
− 5i
n−i
n−i
4 − 5i
+
×
×
6(n − i)
(n − 1)n
6(n − i)
(n − 1)n
i=n/2+1


3n/4
89n2
89n
2
2
X
− 15n
1
1
1
1
8
 23n + 21n − 5
=
i =
+
+ 32
>
+ 32
24 6(n − 1)n
8
16
24
6(n − 1)n
24
6n
i=1
n/2

X  23n

1
+
=
24 i=1

=

4

89
1
+
≈ 0.5052
24 192





28

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

Therefore Greedy increases the welfare by at least 0.5052 fraction of the optimum
offline solution in expectation.

5. Conclusions and Open Problems. As we have seen, the Greedy algorithm,
which achieves an optimal competitive ratio of 1/2 for online SWM in the adversarial
setting, does strictly better in the random order setting. We showed that the competitive ratio of this algorithm is at least 0.5052, and defined the new and interesting class
of second-order supermodular functions (including weighted matching and weighted
coverage functions), for which the ratio is at least 0.5104. This work motivates several
open problems, which are interesting directions for future research:
• First, we believe it should be possible to improve on the competitive ratios
of both Theorems 1 and 3. Our work broke the barrier of 1/2, but further
improvements may be possible via a more careful analysis.
• A natural question is whether the Greedy algorithm does in fact achieve a
ratio of 1 − 1/e in the random order model. A hardness result showing that
this ratio is impossible would be extremely interesting, yielding one of the
first provable separations between the random order and i.i.d. models.
• Finally, the new classes of second-order modular, second-order supermodular and second-order submodular functions that we defined are likely to be
of independent interest. We may be able to refine our understanding of submodular optimization by determining which problems become more tractable
for submodular functions in these classes.
References.
[1] Gagan Agarwal, Gagan Goel, Chinmay Karande, and Aranyak
Mehta, Online vertex-weighted bipartite matching and single-bid budgeted allocation, in SODA, SIAM, 2011.
[2] Shipra Agrawal, Zizhuo Wang, and Yinyu Ye, A dynamic near-optimal algorithm for online linear programming, Computing Research Repository, (2009).
[3] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat, Online
prophet-inequality matching with applications to ad allocation, in Proceedings of
the 13th ACM Conference on Electronic Commerce, ACM, 2012, pp. 18–35.
[4] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor, Online primal-dual
algorithms for maximizing ad-auctions revenue, in ESA, Springer, 2007, pp. 253–
264.
[5] Nikhil Devanur and Thomas Hayes, The adwords problem: Online keyword
matching with budgeted bidders under random permutations, in EC, 2009, pp. 71–
78.
[6] Nikhil R. Devanur, Zhiyi Huang, Nitish Korula, Vahab S. Mirrokni,
and Qiqi Yan, Whole-page optimization and submodular welfare maximization
with online bidders, in ACM Conference on Electronic Commerce, 2013, pp. 305–
322.
[7] Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens, Near optimal online algorithms and fast approximation algorithms for resource allocation problems, in EC, ACM, 2011, pp. 29–38.
[8] Nikhil R Devanur, Balasubramanian Sivan, and Yossi Azar, Asymptotically optimal algorithm for stochastic adwords, in Proceedings of the 13th ACM
Conference on Electronic Commerce, ACM, 2012, pp. 388–404.
[9] Shahar Dobzinski, Noam Nisan, and Michael Schapira, Approximation
algorithms for combinatorial auctions with complement-free bidders, in STOC,
2005, pp. 610–618.

ONLINE SUBMODULAR WELFARE MAXIMIZATION IN RANDOM ORDER

29

[10] Shahar Dobzinski and Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, in SODA, 2006,
pp. 1064–1073.
[11] Uriel Feige, Vahab S Mirrokni, and Jan Vondrak, Maximizing nonmonotone submodular functions, SIAM Journal on Computing, 40 (2011),
pp. 1133–1153.
[12] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni,
and Cliff Stein, Online stochastic packing applied to display ad allocation, in
ESA, Springer, 2010, pp. 182–194.
[13] J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pal,
Online ad assignment with free disposal, in WINE, 2009.
[14] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan, Online stochastic matching: Beating 1 - 1/e, in FOCS, 2009, pp. 117–126.
[15] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, An analysis of the
approximations for maximizing submodular set functions II, Mathematical Programming Study, 8 (1978), pp. 73–87.
[16] Gagan Goel and Aranyak Mehta, Online budgeted matching in random
input models with applications to adwords, in SODA, 2008, pp. 982–991.
[17] B. Haeupler, V. Mirrokni, and M. ZadiMoghaddam, Online stochastic
weighted matching: Improved approximation algorithms, in WINE, 2011, pp. 170–
181.
[18] Bala Kalyanasundaram and Kirk R. Pruhs, An optimal deterministic algorithm for online b -matching, Theoretical Computer Science, 233 (2000), pp. 319–
325.
[19] Michael Kapralov, Ian Post, and Jan Vondrák, Online submodular welfare maximization: Greedy is optimal, in SODA, 2013, pp. 1216–1225.
[20] Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi, Online bipartite matching with unknown distributions, in STOC, 2011, pp. 587–596.
[21] R.M. Karp, U.V. Vazirani, and V.V. Vazirani, An optimal algorithm for
online bipartite matching, in STOC, 1990, pp. 352–358.
[22] Thomas Kesselheim, Andreas Tönnis, Klaus Radke, and Berthold
Vöcking, Primal beats dual on online packing lps in the random-order model,
in Proceedings of the 46th Annual ACM Symposium on Theory of Computing,
ACM, 2014, pp. 303–312.
[23] Lehman, Lehman, and N. Nisan, Combinatorial auctions with decreasing
marginal utilities, Games and Economic Behaviour, (2006), pp. 270–296.
[24] Renato Paes Leme, Vasilis Syrgkanis, and Éva Tardos, Sequential auctions and externalities, in Proceedings of the Twenty-Third Annual ACM-SIAM
Symposium on Discrete Algorithms, SIAM, 2012, pp. 869–886.
[25] Mohammad Mahdian and Qiqi Yan, Online bipartite matching with random
arrivals: A strongly factor revealing lp approach, in STOC, 2011, pp. 597–606.
[26] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani,
Adwords and generalized online matching, J. ACM, 54 (2007), p. 22.
[27] Vahideh H. Menshadi, Shayan Oveis Gharan, and A. Saberi, Online
stochastic matching: Online actions based on offline statistics, in SODA, 2011,
pp. 1285–1294.
[28] Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza ZadiMoghaddam, Simultaneous approximations of stochastic and adversarial budgeted allocation problems, in SODA, 2011, pp. 1690–1701.

30

NITISH KORULA, VAHAB MIRROKNI AND MORTEZA ZADIMOGHADDAM

[29] Vahab S. Mirrokni, Michael Schapira, and Jan Vondrák, Tight
information-theoretic lower bounds for welfare maximization in combinatorial
auctions, in ACM Conference on Electronic Commerce, 2008, pp. 70–77.
[30] Vahab S. Mirrokni and Morteza Zadimoghaddam, Randomized composable core-sets for distributed submodular maximization, in Proceedings of the
Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC
2015, Portland, OR, USA, June 14-17, 2015, 2015, pp. 153–162.
[31] Marco Molinaro and R Ravi, The geometry of online packing linear programs, Mathematics of Operations Research, (2013).
[32] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, An analysis of approximations for maximizing submodular set functions. I, Math. Programming,
14 (1978), pp. 265–294.
[33] Vasilis Syrgkanis and Eva Tardos, Bayesian sequential auctions, in Proceedings of the 13th ACM Conference on Electronic Commerce, ACM, 2012,
pp. 929–944.
[34]
, Composable and efficient mechanisms, in Proceedings of the 45th annual
ACM symposium on Symposium on theory of computing, ACM, 2013, pp. 211–
220.
[35] Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram, Optimal online assignment with forecasts, in EC, 2010, pp. 109–118.
[36] J. Vondrak, Optimal approximation for the submodular welfare problem in the
value oracle model, in STOC, 2008, pp. 67–74.

