  Two-way online correlated selection (two-way OCS) is an online algorithm
that, at each timestep, takes a pair of elements from the ground set and
irrevocably chooses one of the two elements, while ensuring negative
correlation in the algorithm's choices. Whilst OCS was initially invented by
Fahrbach, Huang, Tao, and Zadimoghaddam to solve the edge-weighted online
bipartite matching problem, it is an interesting technique on its own due to
its capability of introducing a powerful algorithmic tool, namely negative
correlation, to online algorithms. As such, Fahrbach et al. posed two
tantalizing open questions in their paper, one of which was the following: Can
we obtain n-way OCS for n>2, in which the algorithm can be given n>2 elements
to choose from at each timestep?
  In this paper, we affirmatively answer this open question by presenting a
three-way OCS. Our algorithm uses two-way OCS as its building block and is
simple to describe; however, as it internally runs two instances of two-way
OCS, one of which is fed with the output of the other, the final output
probability distribution becomes highly elusive. We tackle this difficulty by
approximating the output distribution of OCS by a flat, less correlated
function and using it as a safe "surrogate" of the real distribution. Our
three-way OCS also yields a 0.5093-competitive algorithm for edge-weighted
online matching, demonstrating its usefulness.
