Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order

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ℓ(emptyset) = 0. The goal is to partition the items into m disjoint subsets S1, S2, ldots Sm in order to maximize the social welfare, defined as sumℓ = 1m vℓ(Sℓ). 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.