  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 $\ell$ has a valuation function $v_\ell$, where $v_\ell(S)$ denotes the
welfare obtained by this agent if she receives the set of items $S$. The
functions $v_\ell$ are all submodular; as is standard, we assume that they are
monotone and $v_\ell(\emptyset) = 0$. The goal is to partition the items into
$m$ disjoint subsets $S_1, S_2, \ldots S_m$ in order to maximize the social
welfare, defined as $\sum_{\ell = 1}^m v_\ell(S_\ell)$.
  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.
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. Obtaining a competitive
ratio of $1/2 + \Omega(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 the
Online Submodular Welfare Maximization problem in the random order model. 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$.
