  In this paper, we study online double auctions, where multiple sellers and
multiple buyers arrive and depart dynamically to exchange one commodity. We
show that there is no deterministic online double auction that is truthful and
competitive for maximising social welfare in an adversarial model. However,
given the prior information that sellers are patient and the demand is not more
than the supply, a deterministic and truthful greedy mechanism is actually
2-competitive, i.e. it guarantees that the social welfare of its allocation is
at least half of the optimal one achievable offline. Moreover, if the number of
incoming buyers is predictable, we demonstrate that an online double auction
can be reduced to an online one-sided auction, and the truthfulness and
competitiveness of the reduced online double auction follow that of the online
one-sided auction. Notably, by using the reduction, we find a truthful
mechanism that is almost 1-competitive, when buyers arrive randomly. Finally,
we argue that these mechanisms also have a promising applicability in more
general settings without assuming that sellers are patient, by decomposing a
market into multiple sub-markets.
