The Taub Faculty of Computer Science Events and Talks

We consider the online Submodular Welfare problem. In this problem we are given n bidders each equipped with a submodular utility and m items that arrive online. The goal is to assign each item, once it arrives, to a bidder or discard it, while maximizing the sum of utilities. The case of monotone utilities has attracted much attention, however much less is known once utilities are general and not necessarily monotone. When an adversary determines the items' arrival order, we present an algorithm, inspired by the algorithm of [Dobzinski-Schapira SODA`06], that achieves a competitive ratio of (n/(8n-4)). For a single bidder, this ratio equals 1/4 and it gracefully degrades to 1/8 as the number of bidders increases. We note that for a single bidder, online Submodular Welfare is equivalent to online Unconstrained Submodular Maximization, for which a hardness of 1/4 is known alongside an algorithm with a matching competitive ratio. To the best of our knowledge, no competitive ratio was previously known except for the special case of a single bidder.