Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Online Submodular Welfare Maximization with General Utilities
event speaker icon
Amit Ganz (M.Sc. Thesis Seminar)
event date icon
Thursday, 05.01.2023, 14:30
event location icon
Zoom Lecture: 94984580239
event speaker icon
Advisor: Prof. Roy Schwartz
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.