Bi-Objective Online Matching and Submodular Allocations
Abstract
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.
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.
Research Areas
