Bi-Objective Online Matching and Submodular Allocations
Online allocation problems have been widely studied due to their numerous practical applications (particularly to Internet advertising), as well as considerable theoretical interest. The main challenge in such problems is making assignment decisions in the face of uncertainty about future input; effective algorithms need to predict which constraints are most likely to bind, and learn the balance between short-term gain and the value of long-term resource availability. In many important applications, the algorithm designer is faced with multiple objectives to optimize. In particular, in online advertising it is fairly common to optimize multiple metrics, such as clicks, conversions, and impressions, as well as other metrics which may be largely uncorrelated such as 'share of voice', and 'buyer surplus'. While there has been considerable work on multi-objective offline optimization (when the entire input is known in advance), very little is known about the online case, particularly in the case of adversarial input. In this paper, we give the first results for bi-objective online submodular optimization, providing almost matching upper and lower bounds for allocating items to agents with two submodular value functions. We also study practically relevant special cases of this problem related to Internet advertising, and obtain improved results. All our algorithms are nearly best possible, as well as being efficient and easy to implement in practice.
The paper builds on the following problem.  There is a set of agents.  Each agent a is associated a submodular function f_a. Elements from the universe arrive over time.  When an element arrives, it is to be assigned to an agent. Let S_a be the set of elements assigned to agent a.  The goal is to assign the elements to agents as to maximum sum_a f(S_a).  This problem is known as online submodular welfare maximization.  For this problem, the greedy algorithm which greedily assigns elements to the agent that maximizes the objective is a 1/2 approximation and this is the best possible.  This paper considers a generalization of this problem where each agent has two different submodular functions.  These two functions represent two different objectives each agent may want to optimize.  The goal is to design an an allocation of elements so as to give a (a,b)-approximation where 'a' is the approximation ratio if only the first function is considered in the objective and similarly 'b' is for the second function.  The paper shows what is essentially a (1/3,1/3) approximation for the problem.  This is done simply by flipping a coin when an element arises and choosing to runt the greedy algorithm only considering one of the objectives.  Proving this result is straightforward.  What is nice about this work is they show that this is the best possible algorithm but giving a lower bound.  This I found interesting.  The paper goes on to show better results in some restricted cases.  I think this is a reasonable paper.  The downside of the work is that they did not motivate the two objective setting much and this leaves my feeling that it is a contrived.  On the other hard, I personally think the problem is reasonable despite the lack of motivation given.  I feel the authors add insight into this area.    I feel the paper is a weak accept.  
Please give more detailed motivation for the problem if available.