Double Auctions with Two-sided Bandit Feedback
Authors: Soumya Basu
Abishek Sankararaman
Venue: NeurIPS 2023 poster (2023)
Keywords: Double Auction
Markets
Bandits
Regret
TL;DR: Our paper is the first to provide decentralized learning algorithms in a two-sided market where both sides have uncertain preference that need to be learned.

Abstract: 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.

Double Auctions with Two-sided Bandit Feedback
Soumya Basu Google Mountain View basusoumya@google. com
Abishek Sankararaman
AWS abishek. Mrisshak.90@maill com com
Abstract
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 both buyers' and sellers' side. We show with confidence bound based bidding, and 'Average Pricing' there is 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 (log(T)) (T) in T rounds, where A is the minimum price gap. Moreover, the buyers and sellers exchanging goods attain O(VT) regret, individually. The buyers and sellers who do not benefit from exchange in turn only experience Ollo T/A) regret individually T rounds. We augment our upper bound by showing that w( wVVT) individual regret, and w(log T) social regret unattainable in certain Double Auction markets. Our paper is the first to provide decentralized learning algorithms in two-sided market where both sides have uncertain preference that need to be learned.
Introduction
Online marketplaces, such as eBay, Craigslist, Task Rabbit, Doordash, Uber, enables allocation of resources between supply and demand side agents scale through market mechanisms, and dynamic pricing. In many of these markets, the valuation of the resources are often personalized across agents (both supply and demand side), and remain apriori unknown. The agents learn their own respective valuations through repeated interactions while competing in the marketplace. In turn, the learning influences the outcomes of the market mechanisms. In a recent line of research, this interplay between learning and competition in markets has been studied in multiple systems, such as bipartite matching markets [29, 30, 39, 7], centralized basic auctions [26, 22]. These works follow the 'protocol model' [2]. where multiple agents follow similar protocol/algorithm, while each agent executes her protocol using only her own snservations/woord-vviiii up to the point of execution.
In this paper, we initiate the study of the decentralized Double Auction market where multiple sellers and buyers, each with their own valuation, trades an indistinguishable good. In each round, the sellers and the buyers present bids for the goods. The auctioneer is then tasked with creating an allocation, and pricing for the goods. All sellers with bids smaller than the price set by the auctioneer sell that price, whereas all the buyers with higher bids buy at that price. Each buyer and seller, is oblivious to all the prices including her own. Only a buyer, or a seller participating in the market observes
"ork done when AS was affiliated with UC Berkeley. All opinions that of the authors and do not necessarily represent that the employers In some literature, the bids of the sellers is called 'asks', but we use bids for both sellers and buyers.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

her own valuation of the good (with added noise). Notably, our work tackles two-sided uncertainty. whereas the previous works mainly focused on one-sided uncertainty in the market.
and peer-to-peee markets, bandwidth allocation [24, 23], power allocation [31]. We focus on the 'Average Mechanism' for double auction. Average mechanism guarantees that the auctioneer and the auction participants incur no losses in the trade. It also ensures that each commodity given to the participant that values it the highest, thus maximizing social welfare. Additionally, average mechanism can be implemented through simple transactions. These properties make average mechanism suitable choice in large social markets, such as energy markets [32], environmental markets [35], cloud- computing markets [38, 32], bidding on wireless spectrum [18]. Our objective to design a bandit average mechanism for double auction markets when the participants are a-prioiri unaware of their exact valuation.
Double auction is used in e-commerce [13]-including
Under average mechanism (detailed in Section 2.2) first an allocation is found, by maximizing K such that the K highest bidding buyers all bid higher than the K lowest bidding sellers. The price is set as the average of the K-th lowest bid among the buyers, and the K highest bid among the sellers for the chosen K. We have two-sided uncertainty in the market, as both buyers and sellers do not know their own valuation. The uncertainty in bids manifests in two ways. Firstly, each buyer needs to compete with others by bidding high enough to get allotted so that she can discover her own price. Similarly, the sellers compete by bidding lower for price discovery. The competition- -driven increase in buyers' bids, and decrease in the sellers' bids may decrease the utility that a buyer or seller generates. Secondly, as the valuation needs to be estimated, the price set in each round as function of these estimated valuations (communicated to the auctioneer in the form of bids) remains noisy. This noise in price also decreases the utility. However, when price discovery is slow the noise in price increases. Therefore, the main challenge in decentralized double auction with learning is to strike a balance between the competition-driver increase/decrease of bids, and controlling the noise in price.
1.1 Main Contributions
Our main contributions in this paper are as follows.
1. Our paper is the first to provide decentralized learning algorithms in a two-sided market where both sides have uncertain preference that need to be learned. Unlike in the setting with one sided uncertainity only. we identify that with two-sided uncertainty in double auction markets optimism in the face of uncertainty in learning (OFUL. from both sides causes information flow bottleneck and thus not good strategy. We introduce the notion of domination of information flow that increases the chance of trade and price discovery. The sellers bid the lower confidence bound (I.CB), and buyers bid the upper confidence bound (UCB) of their respective valuation. By using UCB bids the buyers, and using the LCB bids the sellers decrease their reward and facilitate price discovery. Formally, with the above bids under average mechanism
We show that the social welfare regret, i.e. the regret in the combined valuation of all the sellers and the buyers in the market is O(log(T)/A A) regret in T rounds with a minimum reward gap A. We also show a (2(log(T)/ A) lower bound on veeial-welfare regret and thus our upper bound is order-optimal.
For individual regret, we show that each of the the sellers and the buyers that do not participate under the true valuations incur O(log(T)/ A) regret, while the optimal participating buyers and sellers incur O(vTlog (T)) regret. Our upper bound holds for heterogeneous confidence widths, making it robust against the choices of the individual agents.
We complement the upper bounds by showing price discovery itself is 52( ((VT) hard in the minimax sense. Specifically, we consider relaxed system where (i) the price of the good is known to all, and (ii) an infinite pool of resource exists, and hence any buyer willing to pay the price gets to buy, and any seller willing to sell at the price does so. We show under this setup, for any buyer or seller, there exists system where that agent must incur regret of Q(VT). Similarly, we establish Q(log(T)) lower bound for the locial-welfar regret by showing that the centralized system can be reduced to combinatorial semi-bandit and using the results of [14].

---

2
System Model
The market consists of N 2 buyers and M 2 sellers, trading a single type of item which are indistinguishable across sellers. This set of M + . market participants, repeatedly participate in the market for T' rounds. Each buyer i E [N] has valuation B; 2 0, for the item and each seller E [M]] has valuation S; 2 0. No participant knows of their valuation apriori and learn it while repeatedly participating in the market over T rounds.
2.1 Interaction Protocol
The buyers and sellers interact through an auctioneer who implements a bilateral trade mechanism at each round. At each round 2 1, every buyer E [N] submits bids (t( and seller j E [M] submits asking price (t) simultaneously. Based on the bids and asking prices in round t, the auctioneer outputs (i) subsets Po(() S [N] and (t) S [M] of participating buyers and sellers with equal cardinality (1) S min(M, N). and (ūi) the trading price p(t) for the participating buyers and sellers in this round. Subsequently, every buyer i E [N] is (i) either part of the trade at time 4, in
which case she gets utility r: (8))() == B, + vs. (t) - p(t). or (ii) is not part the trade at time t and receives 0 utility along with signal that she did not participate. Similarly, each seller E [M]
either part of the trade and receives utility r (t) == p(t) S, - Va. (t), or is informed she is not part of the trade and receives 0 utility. The random variables (t) and Vag (t) for all i E [N],
j E [M] and t e [7] are i..dd,, mean, Ga--sasssian random variables."
2.2 Average price mechanism
Throughout the paper, we assume the auctioneer implements the average price mechanism in every round t. Under this mechanism, at each round t, the auctioneer orders the bids by the 'natural order', i.e., sorts the buyers bids in descending order and the seller's bids in ascend- ing order. Denote by the sorted bids from the buyer and seller as b, (t) Z ...b,y (t) and the sorted sellers bids by st,(t) (t) ...Sjar (t). Denote by the index ((t) to be the largest in- dex such that bixco (t) 2 Six (t). In words, ((t) is the 'break-even index' such that all buyers ".. ,((()) have placed bids offering buy at price strictly larger than the asking price submitted by sellers jı," ,jK())- The auctioneer then selects the participating buyers Po()) = {ir. ... (K(e), and participating sellers Pt(t) = -...... j.()). The price is set to
b o tenee) and thus the name of the mechanism is deemed as the average mechanism.
p(t) =
Partsipant
Partopani
B1
2.3 Regret definition
B2
B3
enienn
For the given bilateral trade mechanism, and true valuations (B.)ee[N) and ((])) denote by K* min( M, N) be the number of matches and by p" to be the price under the average mechanism when all the buyers and sellers bid their true val- uations. Let P to be set of the optimal participating buyers, and P. to be set of the optimal participating sellers. For any buyer [N]. we denote by (B, p²) be the true utility of the buyer. Similarly, for any seller j E [MV, we denote by (p" Sy) to be the true utility of seller j. From the description of the average mechanism, in the system with true valuations, all participating agents have non-negative true utilities.
S4
Buyer O
Salter A
Figure 1: Average Mechanism with Buyers and 5 Sellers
Recall from the protocol description in Section 2. that at any time t, if buyer i E [N] participates. then she receives mean utility of (B,- p(t)). For participating seller j E [M] her mean utility of (p(t)= Sz) in round f. If in any round t, if a buyer E [N] or seller j [M] does not participate, then she receives a deterministic utility 0. The expected individual regret of a buyer i, namely Rg, (T).
Throughout, we refer to sellers 'bids' as their asking price We study the system with 1-sub-Garne Gaussian to avoid clutter. Extension to general o-sub Sub-Gaussian is trivial when or upper bound to it is known.
3

---

and seller j. namely (T,)(T), are defined as
(B: - p(t)]] P.
Σ
TT" K*)
Σ
-5)
t:jEP.()
Auctioneer has no regret as average mechanism is hudget balanced, i.e. auctioneer does not gain or lose any utility during the process.
We also define the social welfare regret similar to gain from trade regret in [10]. The social welfare is defined as the total valuation of the goods after the transfer of goods from seller to buyer in each round. The expected (w.nt reward noise) total valuation after transfer is thus defined as
(iEP)()) Bi + EEEMMNVP S3). while the the expected total valuation under oracle average
mechanism is (Eiegg Bi + ESE(MINV; S)). . Therefore, the expected social welfare regret is defined as
Rew (T) = Σ B Σ S,) Σ
B (EP&(1)
Σ
s,)] JE(MITPA(0)
E
(1)
SEPE
JEMMNP
[=1
3 Decentralized Bidding for Domination of Information Flow
We consider the decentralized system where each market participant bids based on their own observa- tion, without any additional communication. The core idea is balancing domination of information flow and over/under bidding, i.e. ensuring the number of allocation is not less than K* in each round with high probability, and the bids converge to each agent's 's true valuation.
Each seller j E [M], with nay (t) participation upto round t, at time t + 1 bids the lower confidence bound (scaled by as.)), LCB(O,g) in short, of its own valuation of the item. Each buyer E [N], with (t) participation upto round f, at time t + 1, bids the upper confidence bound (scaled by a5,)), UCB(o8,;) in short, of its own valuation of the item. The bids are specified in Equation 2.
8j(1+ + =)=((()) - J..j log(t)
Olb log(1)
by(1+ b))())
(t)
7bb (1)
Here, 8,(1) ney(or EesejjeR (t)(t)) and (t() = TE, EeSHiEPLCY (t) are the observed empirical valuation of the item upto time I by seller j. and buyer i, respectively.
Our buyers and sellers follow the protocol model (which is ubiquitous in bandit learning for markets) and agree on UCB and LCB based bids, respectively. They are heterogeneous as they may use different 0b,5 and aa..j scaling parameters. The only restriction (as seen in Section 4) is min(as.. aej } 2 4 which they agree on as part of the protocol.
Key Insights: We now contrast our algorithm design from standard multi-armed armed-bandit (MAB) problems. In typical MAB problems, including other multi-agent settings, algorithm is designed based on optimism in the face of uncertainty in learning (OFUL) principle [1]. The UCB-type indices under OFUL arises as optimistic estimate of the rewards of arms/actions. However, such optimism used from both sides, i.e. both buyer and seller using UCB indices, may lead to standstill. The bids of the buyers with constant probability can remain below the sellers' bids. Instead, we emphasize information flow through trade. In our algorithm buyers' UCB bids and sellers' LCB bids ensure that the system increases the chance for buyer and seller to participate in each round as compared to using their true valuations. There is domination of information flow, and consequently they discover their own valuation in the market.
However, too aggressive over or under bidding can disrupt the price setting process. In particu- lar, if even one non-participating buyer bidding high enough (due to UCB bids) to exceed a non-participating seller's price, firstly she participates and accrues regret. More importantly, the participating sets deviates, resulting in deviation of the price of the good from p". Thus resulting in regret for all participating agents well. Similar problems arise if one or more pontpatiicipating

---

seller predicts lower. On the other hand, too low aggression is also harmful as the price discovery may not happen resulting deviation of participating set, deviation of price, and high regret. In the next section, we show the aggression remains within desired range, i.e. the regret of the agents remain low, even with heterogeneous UCBs and I.CSs.
Regret Upper Bound
In this section, derive the regret upper bound for all the buyers and sellers in the system. Without loss of generality, let us assume that the buyers are sorted in decreasing order valuation B1 > B2 > ... > Bx. The sellers are sorted in increasing order of valuation Si S2 < < SN- The the buyers = 1...., K are the optimal participating buyers, and, similarly, the sellers j 1....,K K are the optimal participating sellers. Let define mmiu min minn(os, Oz. h and Omax == max maxx(ass,s (vs,i, as.r I. We define the minimum distance of an agent's true valuation from the true price p² A miN]; J.MM {pp" Sy1. |B; - p" []. As item is sold only if the matched buyer bids strictly greater than the matched seller's bid we have > 0.
Our first main result, Theorem 1, proves (loo(())4 upper bound for the social welfare regret. Theorem 1. The expected social welfare regret of the Average mechanism with buyers bidding UCB(as), and sellers bidding LCB(c,.) of their estimated valuation, for Omin 2, is bounded as:
(Viimax + +2)3
(Vimmax + 2)
Rsw (T) S +Σ
(B: (By) log(1)+
Σ
(Sp -s,) log(T")
iSK" PSK'
JSK j>K-
( [lmax + 2)2
ΣΣ
log(T) + M MMM (Otmin/
(Sy Bτ)
アンス POK*
where ((x) is the Riemann-zett zeta function which is finite for x 1.
The following theorem provides the individual regret bounds for all sellers and buyers in T rounds. Theorem 2. The expected regret of the Average mechanism with buyers bidding UCB(o)), and sellers bidding LCB(o,,) of their estimated valuation, for Omin > bounded as:
for participating buyer E [K*] as Ra, (T) S (2+ (m v (T) + Cy., log(T").
for participating seller E [K*] as Rs. (T) S (2 + ((max) V T Tlog(T) (T) Cs' . log(T),
for non-participating buyer 2 (K* + +1 as Re, < -M Armax
log(T),
(Bx+-Ba)
for non-participating seller 2 (K* + 1) as (T) < Kt))++
amax
log(T").
(3,-8k*)
Here Ow and C are (IM- (M--'+ constants (see Theorem 16 in Appendix A).
We can summarize our main results (with lower bounds taken from Section 5) as
Non-participant
Regret
Social
Participant
Buyer
Seller
Upper
O MN log(T)) 2 M+N ITg(
O((VT+ + MN log(
O V log(T))
O V log(T))
Lower
Q(VT)"
Table I: Regret bounds derived this paper. The participant regret lower bound instance independent
indicated by (+). Rest are instance dependent. Lower bound of 0 indicates absence of non-trivial bound.
Several comments
main results are in order.
Social and Individual Regret: The social regret as well as the individual regret of the optimal non-participating buyers and sellers under the average mechanism with confidence bound bids grow as (log())). However, the individual regret of the optimal participating agents grow as The social regret, is determined by how many times a participant buyers fails to participate, and non participants end up participating. Also, the non-participants incur individual
5

---

regret through participation. The effect of price setting is not present in both the cases, and counting the number of bad events lead to (log((T) regret. For the participant agents the error in price-setting dominates their respective individual regret of ((VTlog(T))
Individually rational for A = (oo (T) /T): We observe that the non-participating buyers and sellers, are only having individual regret (loo((T)/)) And the participating buyers and sellers are having individual regret O (T)( This is reassuring as this does not discourage buyers and sellers from participation for a large range of system a-priori. Indeed, for the last participating buyer and seller the utility is (Bx /2, which is close to A. Hence, as long as (Tllog(T) or A = w( prefers entering the market then discovering her price and getting out, compared to not participating in the beginning. Also, participating buyer or seller is guaranteed return through participation.
AT = w (ooax((oo(())))
a non- pon-patticipaiing buyer or seller
We now discuss the incentives of individual users closely following the notion of symmetric equilibrium in double auction [42]. In this setting, a myopic agent who knows her true valuation, and greedily maximizes her reward in each round assuming all the non-strategic agents use confidence- based bidding. For average mechanism only the rettinsetting agents (i.e. the K buyer and the K"-tth seller) have incentive to deviate from their true valuation to increase their single-round reward. The non-pree cen--ricc-settiy agents are truthful. When the K*-th buyer deviates then each participating buyer has an average per round surplus of (Bx- max( Skr +1),2 and each participating seller has the same deficit. On the contrary, when the K -ttth seller deviates each participating seller has average per round surplus of (Sx* min( min(Bx-. SK--1) 1)/ surplus, and each participating buyer has the same average deficit in each round. See Appendix C for more discussions.
Incentives and Deviations:
Scaling of Regret with N, M, K" A:
Social regret: The social regret scales O(MNN- - (K*)) log( (og)))))()))) When participant buyers replaced by non-participant buyers the valuation decreases which leads to O(K O(K' K*) log(T) (T) A) regret. Similarly, participant seller getting replaced by non-partinn con-aatiicipant seller introduces O(K* *MM
K*) (T) / social regret. Finally, as goods move from non-participant buyers to non-participant
sellers we obtain O(MM- KNV K*) log(T)) /) regret.
Non-participant regret: The individual regret scales as O(v M log(T)/A) for non-participant buyer, whereas it scales as O(VN log(Z)) A) for non- con-participant seller. For any non-participant buyer once it has (log(T)) A²)) samples it no longer falls in top K buyer. However, it can keep participating until each non- participant seller collects enough samples, i.e. (llo(())/) 2 samples. Finally, regret shown to be Ovv #participation log(T)) which leads to the (VMM (Tg(T)/
Participants:
The leading (og))))) term in the regret for each optimal participating buyer and seller do not scale with the size of the system. This leading term depends mainly on the random fluctuation of the bid of the lowest bidding participating buyer and the highest bidding participating seller. The O MN log(T)) regret for the participating buyer and seller comes because each time A
non-participating buyer or seller ends up participating the price deviates.
Special Case K R N R M: We see that when the system the number of participants is very high, i.e. (N - K'), (M- - K*) = O(1), then the (log(T))AA) component, hence the regret, per buyer/seller does not scale with the system size. Furthermore, the social regret also scales as O(MMN - (K*)²) log(T)/A) A) & Olog(T)/AA) This indicates that there is rapid learning, as all the participants are discovering her own price almost every round.
4.1 Proof Outline of Regret Upper Bounds
We now present an outline to the proof of Theorem 2. The full proof is given in Appendix A. A salient challenge in our proof comes from two-sided uncertainty. In Double auction, the outcomes of the buyers' and sellers' sides are inherently coupled. Hence error in buyers' side propagates to the sellers' side, and vice versa, under two-sided uncertainty. For example. if the buyers are bidding lower than their true valuation then the optimal non-participating sellers, even with perfect wedge of their own valuation, ends up participating. We show that optimal participants (both buyers and sellers) get decoupled, whereas in optimal non-partisipants regret leads to new information both buyer and seller side. This breaks the two-sided uncertainty obstacle.

---

Our proof leverages monotonicity of the average mechanism, which means if the bid of each buyer is equal or higher, and simultaneously bid of each seller is equal or lower, then the number of participants increases (Proposition 7). Additionally, UCB ensures each buyer w.h.p. bids higher than its true value, and LCB ensures each seller w.h.p. bids lower than its true value. Therefore, we have domination of the information flow: (() 2 K w.h.p. for all 2 1.
Monotonicity and Information Flow:
Social Regret Decomposition: For any sample path with (t) 2 K* the social regret, namely Tsw (T), under average mechanism can be bounded as
T
Psw(T)
Σ isk*<t <V
(B,
(B-BB))
(((PP((),
T
T
E (S SSK
Σ 10FP.(0).EEPP.))++
(Sy (S Bv) Σ ((EEP((0)
The first term corresponds to a con-participant buyer replacing a participant buyer. The second term is the same for sellers, whereas the final term corresponds to two non-participant buyer and seller getting matched.
Individual Regret Decomposition: We now turn to the individual regrets. Regret of a non- participant buyer i, can be bounded by
Σ (p(() B.) S (.)))(())
Σ (b,(1) (B)
Σ
obo log
V ab, (T) log(T).
(SEP)())
(NEP)(()
We have p(f) lesser than (t) because i-th buyer participates in round By UCB property w.h.p. b, (t) most V cru. log(t)
Ns,.(f) away from B,. A similar argument shows for a non non-participating seller the regret is roughly / (T) log(T).
For participating buyer i, we have the regret bounded as
Σ
(B: D--)")+ +
Σ (v(() - -0) = (T mn,, -B)) +
Σ (v(1) -p)) MEP)))
(1)
HEP)))
Similarly, a participating seller j has regret bound (T' Tee (T))(" -, (p- p(t)).
Decoupling Participants: In Lemma 10 in Appendix A, show that learning is decoupled for the optimal participating buyers, and optimal participating sellers. lower bounds the number of participation for optimal participating buyers and sellers
Lemma 3 (Informal statement of Lemma 10). For amin > 4, w.h.p., for every i, E [K*,, and "',"" K
(T (T)
ay log(T)) (B.-BoJ.. (T n (T))
B log(T)
1"2K++1
J"2K*+1
T Σ 1((EP(0)
2 a log(T) B, and 10EEP.(0,JEP.(()) a log(T))
-,)=
argues after a optimal non- portpaaiiiiaant 1" gets O (B. - B.n )2 samples it can not participate while i does not participate the bid of is higher than the bid of i" with high probability. Similarly seller side result follow.
Tog(T)
Non-Participant regret leads to two-sided Learning: Unlike optimal participating agents, the effect of uncertainties on the optimal non- participating buyers and sellers cannot be decoupled directly. With at least one non- con-paaiiiiptinn buyer with large estimation error in her valuation present, the pon-participating sellers can keep participating even with perfect knowledge. However, this does not ensure directly that the estimation error of this non-participating buyer decreases. Next, in Lemma 12 in Appendix A, we upper bound the number of times non-participant can participate. Informally we have
7

---

Lemma 4 (Informal), For Onain > 4, with high probability for any i,j 2 (K* + 1),
1b. (T)
2 [Bx B.
06. log [T)
Do (T)
(8 B. nay (T)
[3, 5k.
log(T)
(B (1(
Σ
2 2,.r log(7)
+2(((+1)
and Di= 10' EP. (
Gmay log(T)
(8,--By)*
A non-participant buyer i after obtaining O (Bx--B., B,y samples does not belong to top K* w.h.p.
log(
Hence, she participates with non-negligible probability only if seller j' (K* 1) participates. However, this implies that with each new match of buyer i, additionally at least one non non-participating seller is matched, decreasing both their uncertainties. For this buyer i, we argue such spurious log(T)
participation happens a total of E)²(k++1) O( (Sp--BB) B.)² times. After that all the non-participating sellers (K* 1) will have enough samples that their LCBB bids will separate from the i-th buyer's UCB bid. Reversing sellers' and buyers' roles does the rest.
Bounding Price Difference: The final part of the proof establishes bound on the cumulative differ- ence price from the true price p" (see, Lemma 15 in Appendix A).
Lemma 5. (Informal statement of Lemma 15) For amin 4, w.h.p. E lp(t) pp'1= Cllo(TT) Vamaa T log))), where C = - (M-K K K-N---- (N-KK))
A
Let us focus on the first upper bound, i.e. of the cumulative value of (n(1) - p²). The proof breaks down the difference into terms, 2(p(t) - p²) (mingep,()) bi(1) Bx-) (Sx- maxxep.()) (1) sy(t)). For rounds when the buyer K is present (which happens all but O O( rounds) we can replace min.eP,(0) bt(t) with bg. Finally noticing that E, (t) - Bx-) E Vamar / T (T) takes care of the first term. For the second term, we need to study the process max,eP,(t)) 8y (t). First we bound the number of times sellers to (K* - 1) crosses the seller K*. Next we eliminate all the rounds where at least one seller j 2 (K* * + 1) are participating. Such an elimination comes at a cost of O (M-K") For any seller j 2 (K* + 1) this happens O (og(T) times for some appropriate Aj, and gives A, regret in each round. This A
final step gives us the dominating 0 (M-K" term. The bound for the cumulative value of A
(p" p(t) follows analogously.
5
Lower Bounds
5.1 ((vT) minimax lower bound on individual regret
We show a minimax regret lower bound of (((TT) in Lemma 21 by considering a simpler system that decouples learning and competition. In this system, the seller assumed to (i) know her exact valuation, and (ii) always ask her true valuation as the selling price, i.e., is truthful in her asking price in all the rounds. Furthermore, the pricing at every round is fixed to the average pa = B.-S. in the event that B, 2 S. We show in Corollary 19 through coupling argument that any algorithm for the classical two armed bandit problem can be converted to an algorithm for this special case. Then we use well known lower bounds for the bandit problem to give the 2(VT) lower bound in Lemma 21. All technical details are in Appendix B.
5.2 ((lo(TT) instance dependent lower bound on Social Welfare Regret
The key observation is that social- regret in Equation (1) is independent of the pricing mechanism and only depends on the participating buyers (t(t) and sellers (t( at each time t. We will establish a lower bound on a centralized decision maker (DM), who at each time, observes all the rewards obtained by all agents thus far, and decides Pt(()) and P.(() for each l. In Appendix B.7, we show that the actions of the DM can be coupled to that of a combinatorial semi-bandit model [14], where the base set of arms are the set of all buyers and sellers, the valid subset of arms are those subsets having an equal number of buyers and sellers and the mean reward of any valid subset
8

---

A 2 is the difference between the sum of all valuations of buyers in A and of sellers in A. In Appendix B we exploit this connection to aami-bandits to give a [[(log(T) regret lower bound for the centralized DM. Thus our upper bound of (log(()) social welfare regret under the decentralized setting is order optimal since even a centralized system must incur (T(log(T) regret.
6 Simulation Study
We perform synthetic studies augment our theoretical guarantees. For a fixed system of N buyers, M sellers, K* participants, and A gap, the rewards are Bernoulli, with means themselves chosen uniformly random. We vary the confidence width of the buyers, og, and seller, Ogg. in [2] Next we simulate the performance of the UCB(as) and LCB(a,, over 100 independent sample paths with T 50k. We report the mean, 25% and 75% value of the trajectories. We plot the cumulative regret of the buyers, it, and the sellers, R (t), the number of matches in the system K (t), and the price difference (p(t) p²). In Figure 2, we have a
system with K 5. We see that ((t) converges to 5, where as (p(t) p') converges to O. The social regret grows as (T). The participant and non- con-patticipant individual regret of this instance is presented in the appendix in Figure 3. We defer the simulation of other systems used to study behavior of heterogeneous o, varying gaps, and different system sizes to Appendix D.
Social Regret
Match Size
Price Diff
13655
30:00
11000
20i00
time
time
(a) Social Regret
(b) Convergence of match size K(t). price difference (p(1) - -p")
Figure 2: Double Auction N = 8, M 8, K 5, A 0.2, 01 4, and a2 8
7
Related Work
Classical mechanism design in double auctions: There is a large body of work on mechanism design for double auctions, following Myerson et al. [36]. The average-mechanism, which the subject of focus in this paper achieves all the above desiderata except for being incentive compatible. The VCG mechanism was developed in a series of works [40]. [12] and [20] achieves all desiderata except being budget balanced. This mechanism requires the auctioneer to subsidize the trade. More sophisticated trade mechanisms known as the McAfee mechanism [33], trade reduction, and the probabilistic mechanism [5] all trade-off some of the desiderata for others. However, the key assumption in all of these lines of work was that all participants know their own valuations, and do not need to learn through repeated interactions.
Bandit learning in matching markets: recent times, online learning for the two-sided matching markets have been extensively studied in [29], [30]. [39], [7], [16]. This line of work studies two sided markets when one of the side does not know of their preferences apriori and learn through interactions. However, unlike the price-discovery aspect of the present paper, the space of preferences that each participant has to Iearn is discrete and finite, while the valuations that agents need to learn form continuum. This model was improved upon by [9] that added notions of price and transfer. The paper of [25] studied a contextual version of the two-sided markets where the agents preferences depend on the reveled context through an unknown function that is learnt through interactions.
Learning in auctions: Online learning in simple auctions has a rich history - [6]. [13], [34]. [8]. [15], [41], [22], [17] to name a few, each of which study separate angle towards learning from repeated samples auctions. However, unlike the our setting, one side of the market knows of their true valuations apriori. The work of [26] is the closest to ours, where the participants apriori do not know their true valuations. However, they consider the VCG mechanism in the centralized setting, i..., all participants can observe the utilities of all participants in every round.

---

One of the first studies on learning in bilateral trade is [10]. The work of [10] considers the single buyer and seller model under a weaker ordinal feedback model, while in the present work we consider the multi-agent model under stronger bandit feedback model. The feedback model in [10] more restrictive since the gain from the trade cannot be estimated by the agents based on ordinal feedback while in our model, the gain from the trade can be estimated by each agent. However, our work considers the impact of multi-agent competition on regret minimization, which is not studied in [10]. In each round a buyer and a seller draw her own valuation i.i.d. from their respective distributions. Then an arbiter sets the price, with trade happening if the price is between the seller's 's and buyer's 's price. They show with full-information follow-the-ledd leader type algorithm achieves O(vT) regret, where as with realistic (bandit-like) feedback by learning the two distributions approximately ((T2/$) regret can be achieved.
Learning in bi-lateral trade:
Protocol Model: The 'protocol model' alludes to multiple agents following similar proto- col/algorithm with each agent executing protocol with private information (e.g. Platform-as Sasimm-as----eveeee -ervicc (PAAS) [2I]). In the works on learning and markets mentioned here, although the decentralized systems can be modeled as games, the protocol model is studied tractable way to capture the essence of the problem [4, 3]. The technical basis for this assumption is that, the limit when the number of participants are large, and the impact of any single participant is small, a protocol based algorithm is the limit in a precise sense of any equilibrium solution to the multi-agent game [19].
Conclusion and Future Work
We study the Double auction with Average mechanism where the buyers and sellers need to know their own valuation from her own feedback. Using confidence based bounds- - UCB for the buyers and LCB for the sellers, we show that it is possible to obtain O(v Togg(T) individual regret for the true participant buyers and sellers in T rounds. Whereas, the true non non-participant buyers and sellers obtain a O(log(7) (7) A) individual regret where A is the smallest gap. The social regret of the proposed algorithm also admits Olog(( / A) bound. We show that there are simpler systems where each buyer and seller must obtain a S2 (VVT) individual regret in the minimax sense. Moreover, in our setting we show even a centralized controller obtains ((log(T)) social regret. Obtaining minimax matching O(VT) regret remains open, Another important future avenue is, developing framework and bidding strategy with provable 'good' regret for general Double auction mechanisms. Alleviating drawbacks of protocol model, such as collusion among participants, and platform disintermediation are important directions to explore.
References
[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304 2007.
[3] Nick Arnosti, Ramesh Johari, and Yash Kanoria. Managing congestion in decentralized match- ing markets. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 451 151-451,22 2014.
[4] Itai Ashlagi, Mark Braverman, Yash Kanoria, and Peng Shi. Communication requirements and informative signaling in matching markets. In EC, page 263, 2017.
[5] Moshe Babaioff and Noam Nisan. Concurrent auctions across the supply chain. Journal of Artificial Intelligence Research, 21:595-629, 2004.
[6] Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. Single price mechanisms for revenue maximization in unlimited supply combinatorial auctions. Technical report, Technical Report CMU-CS-07-111, Carnegie Mellon University, 2007. 3, 2007.
[7] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond (l) regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pages 705-715. PMLR, 2021.
10

---

[8] Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu. Online learning in online auctions. Theoretical Computer Science, 324(2-3)1177146, 2004.
[9] Sarah H Cen and Devavrat Shah. Regret, stability & fairness in matching markets with bandit learners. In International Conference on Artificial Intelligence and Stafistics, pages 8938-8968 PMLR, 2022.
[10] Nicolò Cesa- Bisa-B,, Tommaso R Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. A regret analysis of bilateral trade. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 289-309, 2021.
[11]
Nicolo Besa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404 1422, 2012.
[12] Edward Clarke. Multipart pricing of public goods. Public choice, pages 17-33, 1971.
[13] Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 252-252, 2014.
[14] Richard Combes, Mohammad Sadegh Talebi Mazrach Shahi, Alexandre Proutiere, al. Com- binatorial bandits revisited. Advances in neural information processing systems, 28, 2015.
[15] Lorenzo Croissant, Marc Abeille, and Clément Calauzènes. Real-time optimisation for online learning in auctions. In International Conference on Machine Learning, pages 2217-2226. PMLR, 2020.
[16] Xiaowu Dai and Michael Jordan. Learning in multi-stage decentralized matching markets. Advances in Neural Information Processing Systems, 34, 2021.
[17] Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. Games and Economic Behavior, 2022.
[18] Xiaojun Feng, Yanjiao Chen, Jin Zhang, Qian Zhang, and Bo Li. Tahes: truthful double auc- tion mechanism for heterogeneous spectrums. IEEE Transactions on Wireless Communications, 11(11):4038 4047, 2012.
[19] Markus Fischer. On the connection between symmetric n-player games and mean field games. The Annals of Applied Probability, 27:757-810, 2017.
[20] Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617-631, 1973.
[21] Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. Learning mean-field games. Advances in Neural Information Processing Systems, 32, 2019.
[22] Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman. Optimal no-regret learning in repeated first-price auctions. arXiv preprint arXiv:2003.09775,, 2020.
[23] George Iosifidis, Lin Gao, Jianwei Huang, and Leandros Tassiulas. A double-auction mechanism for mobile data-offloading markets. IEEE/ACM Transactions On Networking, 2365)
2014.
[24] George losifidis and lordanis Koutsopoulos. Double auction mechanisms for resource allocation in autonomous networks. IEEE Journal Selected Areas in Communications, 28(1):95-102, 2009.
[25] Meena Jagadecsan, Alexander Wei, Yixin Wang, Michael Jordan, and Jacob Steinhardt. Leam- ing equilibria matching markets from bandit feedback. Advances in Neural Information Processing Systems, 34, 2021.
(26) Kirthevasan Kandasamy, Joseph E Gonzalez, Michael I Jordan, and Ion Stoica. Mechanism design with bandit feedback. arXiv preprint arXiv:2004.0892. 2020.
11

---

[27] Elon Kohlberg, Shmuel Zamir, et al. Repeated games of incomplete information: The symmetric case. Annals of Statistics, 205):1040-0041 1974.
[28] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020,
[29] Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020.
[30] Lydia Liu, Feng Ruan, Horia Mania, and Michael Jordan, Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1-34, 2021.
[31] Bodhisattwa P Majumder, M Nazif Faqiry, Sanjoy Das, and Anil Pahwa. An efficient iterative double auction for energy trading in microgrids. In 2014 IEEE Symposium on Computational Intelligence Applications Smart Grid (CIASG), pages 1-7. IEFE, 2014.
[32] Sweta Malik, Subhasis Thakur, Maeve Duffy, and John Breslin. Double auction mechanisms for peer-to-pese energy trading: A comparative analysis. In 2022 IEEE 7th International Energy Conference (ENERGYCON), pages 1-6. IEEE, 2022.
[33] Preston McAfee. A dominant strategy double auction. Journal of economic Theory, 56(2):434-
450, 1992.
[34] Mchryar Mohri and Andres Munoz Medina. Learning theory and algorithms for revenue optimization in second price auctions with reserve. In International conference on machine learning, pages 262-270. PMLR, 2014.
[35] Andrew Muller, Stuart Mestelman, John Spraggon, and Rob Godby. Can double auctions con- trol monopoly and monopsony power in emissions trading markets? Journal of environmental economics and management, 44(1):70-92, 2002.
[36] Roger B Myerson and Mark Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2):65--281, 1983.
[37] Jean-Pierre Ponssard and Shmuel Zamir. Zero-sum sequential games with incomplete informa- tion. International Journal of Game Theory, 2(1):99-107, 1973.
[38] SM Reza Dibaj, Ali Miri, and SeyedAkbar Mostafavi. A cloud priority-based dynamic online double auction mechanism (pb-dodam). Journal of Cloud Computing, 9:1-26, 2020.
[39] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pages 1252-1260. PMLR, 2021.
[40] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
[41] Jonathan Weed, Vianney Perchet, and Philippe Rigollet. Online learning in repeated auctions. In Conference on Learning Theory, pages 1562-1583. PMLR, 2016
[42] Robert Wilson. Incentive efficiency of double auctions. Econometrica: Journal of the Econo- metric Society, pages 1101-1115, 1985.
[43] Peter R Wurman, William E Walsh, and Michael P Wellman. Flexible double auctions for electronic commerce: Theory and implementation. Decision Support Systems, 24(1):17-27, 1998.
12


Reviews:
[{"review_id": "EbL4L6hH1M", "reviewer": "Reviewer_51dr", "summary": "This work considers learning in a two-sided double auction setting in which both sides must confront uncertainty over their valuations (which are realized upon winning in the auction) and choose to adhere to the same protocol in order to perform that learning. The work shows that buyers and sellers bidding less aggressively - e.g., buyers bidding higher than they otherwise might, and sellers bidding lower than they otherwise might - leads to faster learning than the usual alternative (Optimism in the Face of Uncertainty). One note is that strategic behavior and any Nash equilibrium will be a change in the other direction, and involve bidders bidding more aggressively (buyers lower / sellers higher).\n\nUsing this strategy, the paper develops bounds on social welfare and individual participant regret. \n\nIt is mentioned in the appendix that individuals may have incentives to deviate, but in the context of robustness of results, strategic behavior is not considered.", "questions": "Double auctions are ubiquitous as mentioned in the discussion. Which many-to-many double auction bandit settings do you view as the right motivation for this work?", "limitations": "No - discussions of collusion or platform disintermediation would be beneficial for the work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The work makes an interesting connection between double auctions and bandit learning, and would seem to be the first to tackle learning on both sides of the market.", "weaknesses": "The recommended strategy is quite simple - bidding higher for buyers or lower for sellers, which results in more trade happening than e.g. bidding at expectation or bidding more aggressively, and it is this encouragement of trade that drives results. The authors note that if both sides bid too aggressively then it can slow down trade and hence slow down learning. Incentives from best responding however will push buyers and sellers in the other direction. \n\nThe protocol model assumes coordination between buyers and sellers on the algorithm to use in order to bid, which could in a real world setting encourage collusion among participants and/or platform disintermediation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. \n\n**Which many-to-many double auction bandit settings is the motivation?** \nOnline learning in economic markets is an active area of research evident from the abundance of research works in the past few years. This is also acknowledged by *Reviewer BEVv*. Our work contributes to this area by initiating the study of double auction.\nWe draw motivation from multiple practical applications, e-commerce, bidding in wireless spectrum, cloud computing markets to name a few. Please see line 38 - line 47 for details.  Our objective here is not to model one particular application in detail, but to develop a framework to study repeated double auctions under bandit learning. \n\nAs a stylized example consider a specific task, say *image labeling*, in a *decentralized crowdsourcing marketplace*. There are multiple *labelers (sell-side)*, each having her own valuation of labeling a batch of images determined by the time taken to label. Here time taken for labeling is unknown, stochastic, and different for each labeler. The labeling task is accomplished with comparable accuracy by each labeler. There are multiple *companies (buy-side)* that want to get a batch of images labeled in each interaction. Each company has its own valuation of a batch of labeled images at the accuracy of the pool of labeler under consideration. However, the accuracy and hence the valuation of each company is a-priori unknown. The companies and labelers can transact -- labelers are paid by the companies for a batch of labeled images -- through a repeated double auction market. The accuracy of labeled images by a company, and time taken for labeling by a labeler can be learned only through *image-labeling (bandit feedback)*. Our work captures this scenario.\n\n\n**We view the simplicity of our algorithm as a strength:** We note that our algorithm (sellers bid LCB, and buyers bid UCB) attains optimal social regret, and sub-linear individual regrets. Our key contribution is to show under the presence of two-sided uncertainty of double auction markets, simple UCB-LCB based algorithm can succeed. The fact that a simple algorithm can attain this performance is a strength and contribution of the paper. Thus, we respectfully push-back on the opinion that simplicity is a weakness. \n\n**Incentives from best responding however will push buyers and sellers in the other direction:**  We note that indiscriminately reducing the bids for a buyer, and increasing the bid for a seller is not always best. Indeed, too low a bid from buyer or too high a bid from seller can leave them unmatched leading to high regret. Note that for the true-participant sellers and buyers who benefit from trade the UCB and LCB decays roughly as $O(1/\\sqrt{t})$ at time $t$. So for these buyers and sellers, the bids converge to their true valuation. For true-non-participating buyers and sellers there is no gain from trade. UCB-LCB based bidding happens in the vicinity of true valuation while ensuring their participation in trade is vanishing (only $O(\\log(T))$ in $T$ rounds). Therefore, UCB-LCB bidding is as incentivized as bidding their respective true valuation for all agents (quantified by the individual regrets). We discuss the incentives of deviation from true valuation in detail in Appendix C along with a summary in our main paper (see line 212 - 221).\n\n\n**Collusion among participants and/or Platform disintermediation:** Thank you for bringing up the possibility of collusion and platform disintermediation within the protocol model. We acknowledge these drawbacks of protocol model, and will mention them in our revised *Conclusion and Future Work* section. However, going beyond the protocol model where the agents are taking part in a repeated game with unknown valuation is out of scope for this paper. In fact, to the best of our knowledge,  this limitation is shared by almost all works on Bandit learning in Markets with stochastic rewards as these works also adopt a protocol model (see line 25 - line 29). \n"}, {"review_id": "gj7NVyj0fF", "reviewer": "Reviewer_bD4t", "summary": "The paper studies an online learning  problem related to double auctions. In particular, the paper assumes that the auctioneer uses a average price mechanism. The goal is to study the online learning problem faced by sellers and buyers that do not know they own valuations. The authors design a algorithm based on upper confidence bounds that if applied by all the sellers and buyers guarantees low regret both for each individual and socially. In particular, they show that the social regret is upperbounded by $O(log T/\\Delta)$, where $\\Delta$ is the minimum price gap, while the individual regret is at most $O(\\sqrt T)$.", "questions": "Please clarify why your are using both instance dependent and instance independent regret bounds. Why do you handle individual regret and social regret in different ways?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The setting is interesting and of practical relevance. The proposed algorithm is easy to implement and guarantees good regret bounds.", "weaknesses": "The algorithmic approach is straghtforward and does not introduce substantial new ideas.\n\nI am confused by your choice to use instance dependent regret bound in some cases (depending on $\\Delta$) and some instance independent regret bounds $\\sqrt T$. I don’t see any conceptual difference between the case in which you apply instance dependent and instance independent bound. For instance, your Lemma 21 (that proves the instance dependent bound) employs arbitrary small difference between the buyer and seller valuations. Hence, it does not rule out logarithm instance dependent bound depending on $\\Delta$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Regarding instance dependent versus instance independent bounds**\n\n***All our upper bounds in Theorems 1 and 2 are instance dependent***, including the $\\sqrt{T}$ for participating agents. Theorem 1 bounds the social-welfare regret as a function of $\\Delta$ and is thus instance dependent. In theorem 2, the regret upper bounds for both the participating buyers(sellers) and the non-participating buyers(sellers) depend on instance dependent terms such as $K^*$ and $\\Delta$. Observe the $\\Delta$ dependence in the second order $\\log(T)$ term for the participating buyers and sellers’ regret. Thus, our regret upper bounds are instance dependent bounds. \n\n*We propose to add a statement and highlight that all our upper bounds are instance dependent in the revised version.*\n\n\n\n***$\\sqrt{T}$ Instance dependent Individual Regret:*** Among the instance dependent upper bounds, the regret for the participating buyers and sellers is the non-standard term of $\\sqrt{T}$. This is unlike $\\log(T)$ instance dependent bounds in typical multi-armed-bandits. At a high-level, a $\\sqrt{T}$ term for the regret shows up for participating agents because of having to do *price-discovery* which is a continuous variable. To solidify this intuition, consider estimating the mean of a continuous random variable using $t$ i.i.d. Samples. It is known (for ex. Using Central Limit Theorem arguments)  that the estimated mean will be about $\\mathcal{O}\\left(\\frac{1}{\\sqrt{t}}\\right)$ away from the true mean. In the price-discovery setting, this error in estimating the true valuation will accumulate over time to a $\\sum_{t=1}^T\\mathcal{O} \\left(\\frac{1}{\\sqrt{t}}\\right) = \\mathcal{O} \\left(\\sqrt{T}\\right)$ regret term.  Moreover, the system needs to eliminate suboptimal *matching* by playing them $O(log(T))$ times. This reflects in the $O(log(T))$ components of the individual regrets.\n\n***$O(\\log(T))$ Instance dependent Social Regret:*** In the social welfare regret, the *price discovery* does not play any role, because in each round the prices cancel out in the social welfare. Only sub-optimal *matching* used in each round contributes to the regret leading to decomposition in line 258. $O(log(T))$ number of play of each of the finite sub-optimal matchings suffices to separate the optimal matching, creating $O(log(T))$ social welfare regret.\n\n***Our lower bound on social welfare regret is instance dependent:*** The lower bound given in Appendix B.7 on the social welfare is instance dependent and order-wise captures the upper bound. We are able to give instance dependent lower bounds by establishing a coupling between our system and a combinatorial semi-bandit system in Proposition 22.\n\n***Our Lower bound for individual regret (Lemma 21) is instance independent:*** As the reviewer correctly notices, our lower bound for price-discovery in Lemma 21 is instance independent. Note we already mention this as a *minimax bound*. We do not have an instance dependent lower bound for price discovery in our work. Establishing an instance dependent lower bound is a challenging open problem as it requires us to formalize the mean-estimation intuition to obtain a $\\sqrt{T}$ type instance dependent lower bound. Doing so requires circumventing several technical challenges such as estimation from adaptively collected samples through a bandit policy. The correlations among the samples are  further complicated by the impact of market competition where a sample for the valuation is received only when an agent is matched which in turn is dependent on the other agents’ perceived valuation. These technical challenges render an instance dependent lower bound for the pricing beyond the scope of the present work.\n\n*We propose to make this explanation clearer in the revision and will highlight that the only instance independent regret bound is the individual regret. We will also pose as an open problem/future work of obtaining a $\\sqrt{T}$ type instance dependent lower bound on individual regret.* \n\n\n**2. Regarding algorithmic simplicity and technical contributions**\n\n***We view the simplicity of our algorithm as a strength:*** We note that our algorithm (sellers bid LCB, and buyers bid UCB) attains optimal social regret, and sub-linear individual regrets. Our key contribution is to show under the presence of two-sided uncertainty of double auction markets, simple UCB-LCB based algorithm can succeed. The fact that a simple algorithm can attain this performance is a strength and contribution of the paper. Thus, we respectfully push-back on the opinion that simplicity is a weakness. \n\n***Technical Challenges and contributions in the analysis:*** We want to remark that despite the algorithm being simple, its analysis is novel and does not follow existing works in multi-armed bandits. The key challenge in the analysis is that the information across agents are different resulting in heterogeneity, as we explain in Section 4.1. Thus, even though the algorithm appears simple, *new ideas are needed for the multi-agent analysis.*\n"}, {"review_id": "gUO6OkPH7r", "reviewer": "Reviewer_XUqU", "summary": "This paper studies double auction markets where both buyers and sellers receive bandit feedback. There are $N$ buyers and $M$ sellers trading a single type of item in the market during a time horizon $T$. They don't know their own valuations so they need to learn through repeated interactions. The auctioneer implements the average price mechanism at each round. All buyers use UCB algorithms while all seller use LCB algorithms. The benchmark is defined to be the ideal market where true valuations are known and all players bid truthfully. The authors derive regret upper bounds for social welfare and individual utility. They also give regret lower bounds in the minimax sense. ", "questions": "1. Line 148, $n_{s,j}(t)$ -> $n_{b,i}(t)$.\n\n2. How to understand these regret bounds if there are ties. For instance, if $B_{K^*} = B_{K^*+1}$, will the regret on social welfare be arbitrarily bad? What if $\\Delta=0$?\n\n3. I personally suggest making the proof outline more concise, so that the main body of the paper can have space to put some results of simulation experiments.\n\n4. Line 615. Does it mean $\\beta\\geq 2$ is enough for proving Regret=$O(\\log T)$?", "limitations": "The authors acknowledge that the study of incentive compatibility is out of scope for this paper. However, they have given enough discussion on incentives in Appendix C.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. To the best of my knowledge, this is the first paper that considers repeated double auctions with unknown valuations. Unlike in the standard repeated-auction setting, one need to deal with two-sided uncertainty in repeated double auctions. The regret analysis requires non-trivial techniques.\n\n2. The analysis in the paper is limited to a specific variant of double auction mechanism, but the authors have discussed incentives and deviations, and have complemented the theoretical results with simulation study for completeness. I believe these results can inspire future work on a more general setting.\n\n3. The paper is well written and organized. I particularly like the comments after the main results, which contribute to helping readers better perceive the regret bounds in theorems. The proof flow in the appendix is also very good.", "weaknesses": "1. The proof techniques may not be easily applied to more general settings, i.e., when agents don't follow UCB-type algorithms, when the auctioneer don't use the average price mechanism, or where true valuations are time-variant, sampled from some distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments, and highlighting insightful future directions. Please find our response below.\n\n**General Applicability of Proof Techniques:**  In bandit literature, handling stochastic reward and time-variant reward requires different algorithmic and technical ideas. We acknowledge this, and leave handling time-variant ture valuation open. We will add this to our future work discussions.\n\nOur proof techniques of Social regret relies only on convergence to the correct set of buyers and sellers, and can be adapted to other mechanisms with a reasonable effort. However, our techniques require substantive modifications to handle individual regret in other mechanisms as price discovery changes drastically with mechanism.  We leave studying general double auction mechanisms with bandit feedback as a future work (see line 389-390 in the paper).\n\n**Adding Plots in the Main Body:** Thank you for this suggestion. If accepted, we will utilize the additional page in the camera ready to add simulation plots in the main paper. \n\n**$\\Delta = 0$ is not feasible:**  $\\Delta = 0$ (where $\\Delta$ is defined in line 182) implies $p^* = S_{K^*} = B_{K^*}$. However, Double auction only matches a buyer with bid higher than a  seller. So if $K^*$-th buyer and $K^*$-th seller participate we must have $S_{K^*} < B_{K^*}$. Therefore, we always have $\\Delta > 0$.\n\n**Ties in Valuation:** $B_{K^*} = B_{K^*+1}$ is an interesting setting. Understanding this behavior formally is out of scope. We provide an informal discussion here.  In the case where $B_{K^*} = B_{K^*+1}$ and $S_{K^* + 1} > B_{K^*}$, i.e. there are $(K+1)$ buyers and $K$ sellers. A tie-breaking needs to be employed. We assume the tie-breaking happens randomly with equal probability.  Under bandit feedback the UCB of $(K^*+1)$-th and $K^*$-th buyer will both be higher than LCB bid from the $K^*$-th seller with high probability. As exactly one of the two buyers match every round the social regret will remain mostly unchanged orderwise in N, M, K and T.  The individual regret analysis is more complicated. We conjecture the number of times  $K^*$-th and $(K^* + 1)$-th buyer match satisfy,  $1/polylog(T) \\leq  n_{K^*+1}(T) / n_{K^*}(T) \\leq polylog(T)$. Otherwise, the less matched buyer will have a higher UCB whp. Thus due to fluctuations in the UCB of these two buyers they will incur $polylog(T)$ regret. However, this is orderwise negligible to the $\\sqrt{T}$ individual regret from the price estimation error for these two buyers.  A formal treatment requires considering *all possible ties*, specifying *tie-breaking rules*, and utilizing arguments similar to the above to give regret guarantees. Therefore, we will leave studying *'Ties in valuation'* open, and add it to our *Conclusion and Future Work* section. \n\n\n**$\\beta > 2$ suffices:** Thank you for pointing this out. Yes $\\beta > 2$ suffices for our regret upper bounds, with increased constant term. E.g. Theorem 1 will hold with $MNb_{max} \\zeta(\\beta / 2)$ instead of $MNb_{max} \\pi^2/6$, where $\\zeta(x)$ is the Riemann zeta function which is finite for $x > 1$.  We will update this in the final version.\n\n"}, {"review_id": "glpJ3JtV42", "reviewer": "Reviewer_BEVv", "summary": "This paper studies double auctions, where a set of $N$ buyers interacts with a set of $M$ sellers to trade some goods. This is a fundamental problem in economics that has been studied extensively. The specific mechanism that is studied in this paper is the average mechanism; it sorts the bids of the sellers and the buyers, identifies the best $k$ so that exactly $k$ trades can happen, and then posts as price the average of the bids of the kth seller and the kth buyer. \n\nFormally, the authors study the following repeated setting: at each time $t$, each agent submits a bid, the average mechanism is implemented, and all the agents participating in a trade are revealed a noisy sample of their valuation. This paper aims to design a learning protocol that exhibits a sublinear regret with respect to the outcome of the average mechanism when all the agents declare their actual valuations. Note that in the model studied, the agents do not know their valuations but only learn it by participating in the auction and receiving bandit feedback.  \n\nThe learning protocol proposed by the authors is simple: each agent maintains a (scaled) confidence interval of their valuation, the sellers bid according to LCB, and the buyers to UCB. This protocol yields $O(\\log T /\\Delta)$ regret regarding social welfare, which is tight. From the agent's perspective, the protocol exhibits an $O(\\sqrt T)$ regret for agents belonging to the optimal solution and an $O(\\log T/\\Delta) $ regret for the others. These results are shown to be tight up to poly-log T terms. \n", "questions": "None", "limitations": "See above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The study of economic problems from an online learning perspective is an active and fruitful line of research, and many works have appeared at NeuriPS and ICML\n- The regret results are tight, and the algorithm is natural and elegant. \n- The fact that the authors studied social welfare (i.e., total happiness) and individual utility (i.e., individual happiness) offers a compelling argument for implementing this mechanism in real life. \n- Given the space constraints, the authors did a good job in presenting and motivating the problem and highlighting the crucial steps of the analysis\n", "weaknesses": "Minor comments: \n- I do not find that surprising the fact that sellers want to bid according to their LCB\n- Please spend some extra words on the definition of social welfare used in the paper. In the economic literature, social welfare is defined as the sum of the agents' utilities at the end of the trade. Thus, it also contains the sellers' valuations that retain their goods. The authors call social welfare the gain from trade, i.e., the variation in social welfare after and before the trade. As pointed out by [10], these two notions are equivalent when minimizing regret (due to its additive nature). Please clarify this point. \n- It makes little sense to have an experimental paragraph in the main body and all the experimental results in the appendix. Either add some plots in the main body or defer everything to the appendix. \n- The feedback in [10] is not bandit-like: they receive only ordinal information about the price posted and the agents' valuations. This is not enough to reconstruct the gain from trade (so it is strongly less informative than bandit feedback).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Social welfare definition:** We thank the reviewer for this pointer and will add the distinction from the classical definition of social welfare and what we consider. Further while defining social welfare, we will write a sentence crediting [10] for establishing the equivalence of the classical definition and what we consider while studying for regret minimization. \n\n**Weaker feedback in [10]:** We thank the reviewer for identifying this gap in our related work attribution. We will update the revision in Line 366 by adding a statement that – \n\n“*The work of [10] considers the single buyer and seller model under a much weaker ordinal feedback model, while in the present work we consider the multi-agent model under a stronger bandit feedback model. The feedback model in [10] is more restrictive since the gain from the trade cannot be estimated by the agents based on ordinal feedback while in our model, the gain from the trade can be estimated by each agent. However, our work considers the impact of multi-agent competition on regret minimization, which is not studied in [10].*”\n\n**Experimental plots in the main body:** We will follow the reviewer’s suggestion and use the extra page for the camera ready to move regret plots from the Appendix to the main body of the paper.\n"}]

Author rebuttal:

Meta-review: This paper looks at a double auction where multiple buyers and sellers both compete; the paper builds on the two-sided bandit feedback setting that has been fleshed out over the last few years in the NeurIPS/ICML/COLT communities, where buyers/sellers learn about their valuation in a round after bidding and receiving their outcome.  Reviewers appreciated the novelty of the setting (this AC also believes this is the first paper considering a double auction + unknown vals), the breadth of results, and the exposition/presentation of the work.  We’d ask the authors to pay special attention to their comprehension rebuttals and reviewers’ discussion responses; reviewers brought up some great points that would make this paper much stronger should it appear at NeurIPS or elsewhere.
Decision: Accept (poster)