  Double Auction enables decentralized transfer of goods between multiple
buyers and sellers, thus underpinning functioning of many online marketplaces.
Buyers and sellers compete in these markets through bidding, but do not often
know their own valuation a-priori. As the allocation and pricing happens
through bids, the profitability of participants, hence sustainability of such
markets, depends crucially on learning respective valuations through repeated
interactions. We initiate the study of Double Auction markets under bandit
feedback on both buyers' and sellers' side. We show with confidence bound based
bidding, and `Average Pricing' there is an efficient price discovery among the
participants. In particular, the regret on combined valuation of the buyers and
the sellers -- a.k.a. the social regret -- is $O(\log(T)/\Delta)$ in $T$
rounds, where $\Delta$ is the minimum price gap. Moreover, the buyers and
sellers exchanging goods attain $O(\sqrt{T})$ regret, individually. The buyers
and sellers who do not benefit from exchange in turn only experience
$O(\log{T}/ \Delta)$ regret individually in $T$ rounds. We augment our upper
bound by showing that $\omega(\sqrt{T})$ individual regret, and
$\omega(\log{T})$ social regret is unattainable in certain Double Auction
markets. Our paper is the first to provide decentralized learning algorithms in
a two-sided market where \emph{both sides have uncertain preference} that need
to be learned.

Machine Learning;Computer Science and Game Theory