  This paper combines two key ingredients for online algorithms - competitive
analysis (e.g. the competitive ratio) and advice complexity (e.g. the number of
advice bits needed to improve online decisions) - in the context of a simple
online fair division model where items arrive one by one and are allocated to
agents via some mechanism. We consider four such online mechanisms: the popular
Ranking matching mechanism adapted from online bipartite matching and the Like,
Balanced Like and Maximum Like allocation mechanisms firstly introduced for
online fair division problems. Our first contribution is that we perform a
competitive analysis of these mechanisms with respect to the expected size of
the matching, the utilitarian welfare, and the egalitarian welfare. We also
suppose that an oracle can give a number of advice bits to the mechanisms. Our
second contribution is to give several impossibility results; e.g. no mechanism
can achieve the egalitarian outcome of the optimal offline mechanism supposing
they receive partial advice from the oracle. Our third contribution is that we
quantify the competitive performance of these four mechanisms w.r.t. the number
of oracle requests they can make. We thus present a most-competitive mechanism
for each objective.
