Online Pricing for Multi-User Multi-Item Markets
Authors: Yigit Efe Erginbas
Thomas Courtade
Kannan Ramchandran
Soham Rajesh Phade
Venue: NeurIPS 2023 poster (2023)
Keywords: revenue
price
offer
online
TL;DR: We consider the problem of a provider seeking to accumulate revenue from the sale of multiple items to multiple users in a repeated interaction setting.

Abstract: Online pricing has been the focus of extensive research in recent years, particularly in the context of selling an item to sequentially arriving users. However, what if a provider wants to maximize revenue by selling multiple items to multiple users in each round? This presents a complex problem, as the provider must intelligently offer the items to those users who value them the most without exceeding their highest acceptable prices. In this study, we tackle this challenge by designing online algorithms that can efficiently offer and price items while learning user valuations from accept/reject feedback. We focus on three user valuation models (fixed valuations, random experiences, and random valuations) and provide algorithms with nearly-optimal revenue regret guarantees. In particular, for any market setting with $N$ users, $M$ items, and load $L$ (which roughly corresponds to the maximum number of simultaneous allocations possible), our algorithms achieve regret of order $O(NM\log\log(LT))$ under fixed valuations model, $\widetilde{O}(\sqrt{NMLT})$ under random experiences model and $\widetilde{O}(\sqrt{NMLT})$ under random valuations model in $T$ rounds.

Online Pricing for Multi-User Multi-Item Markets
Yigit Efe Erginbas'
Thomas Courtade'
Kannan Ramchandran'
Soham Phade?
University of California, Berkeley
Wayve Technologies
Abstract
Online pricing has been the focus extensive research recent years, particularly in the context of selling an item to sequentially arriving users. However, what if provider wants to maximize revenue by selling multiple items multiple users each round? This presents complex problem, as the provider must intelligently offer the items those users who value them the most without exceeding their highest acceptable prices. In this study, we tackle this challenge by designing online algorithms that can efficiently offer and price items while learning user valuations from accept/reject feedback. We focus on three user valuation models (fixed valuations, random experiences, and random valuations) and provide algorithms with nearly-optimal revenue regret guarantees. In particular, for any market setting with N users, M items, and load (which roughly corresponds to the maximum number of simultancous allocations possible), algorithms achieve regret of order ( log log( LT)) under fixed valuations model, O(vN LT) under random experiences model and O(VNMLT) under random valuations model in T rounds.
Introduction
The ability to design algorithms that can achieve the optimal sale of goods to multiple users having vare-ig valuations for each of the goods is both timely and relevant, given the explosion in the use of data large-scale systems. This problem is commonly encountered in various contexts, such as in the e-commerce (Amazon, eBay), ride-share (Uber, Lyft), airline, and hotel (Airbnb, Booking.com) industries. Since the provider's goal maximizing revenue can only be achieved through delicate balance of considering prior transactions and adjusting offers and prices, it presents a unique opportunity to advance our understanding of dynamic pricing.
We presently consider the problem of designing algorithms that aim to optimize the sale of multiple goods to multiple users having maryingying valuations over the course of repeated rounds. At each round, the provider offers each item to a user at a chosen price, and users decide whether or not to buy, by comparing the offered price their private valuation for the good. The provider may decide offers and prices based on outcomes of prior transactions, but each individual user accepts or rejects their offer based only their valuation for the current round. The provider's 's goal is maximize the revenue accumulated in multiple rounds by judiciously selecting the offers and associated prices.
The provider, who is endowed with multiple items at each round, repeatedly offers these items to multiple users well-chosen prices. In response, the provider obtains feedback regarding the acceptance or rejection decisions of the users and receives revenue for the accepted items. The provider's goal is to maximize the accumulated revenue over time by making offers that respect the endowment constraints and user demands. In the process of identifying the best way of offering the items target users, the provider encounters challenges regarding two separate aspects of the problem; such challenges are addressed in our work. As depicted in Figure T] the first challenge is learn user preferences from interactive feedback; the second is find offers and prices that will result in maximal revenue.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The challenge of learning arises from the fact that the provider does not have knowledge of the user valuations ahead of time and hence has to learn them while continually taking action. On the other hand, the challenge of offering and pricing stems from both of the facts that (a) avail- able items are scarce and (b) user demands are limited. Therefore, to achieve better outcomes, the provider needs to make careful decisions which items to offer to which user within the limits of these constraints. However, since the valuations of the users are unknown, the offering and pricing decisions involve trade-off between learning individual customer preferences in or- der to increase long-term revenues and earning short-term revenues by leveraging the informa- tion acquired far.
Provider
Learning user valuations
Offers & pricing
Payment Feedback
S
Users
Items
In this study, we focus algorithms that offer each item to only one user during each round. This assumption eliminates the risk of multiple users requesting the same item and removes the need for the provider decide who should ceive it. Relaxing this assumption could possi- bly offer more flexibility and revenue potential during the earlier phases while learning the val- uations. However, it does not result in a loss in the maximum achievable revenue under known valuations, and hence our algorithms can still achieve no-regret guarantees. Additionally, offering limited number of items simplifies the process for users by reducing the number of choices they need to consider. As the provider gains insights into user valuations over time, the offers become more tailored and relevant, enabling users to focus on evaluating items that the provider believes will of the highest interest to them. This saves time and reduces the effort required to make decision.
Figure 1: The provider's goal is to maximize the revenue obtained from sales over multiple rounds. The provider decides offers and prices while interactively learning the user valuations from the accept/reject feedback. At each round, only subset of items may be available for sale and only subset of users may be active.
1.1 Our contributions
To the best of our knowledge, are the first address the problem of dynamic pricing for the sale of multiple items to multiple users with unknown valuations. Our contributions are as follows.
We consider three user valuation models: fixed valuations, random experiences, and random valuations. While the fixed valuation and random valuation models are standard models explored extensively in prior work on dynamic pricing (Bubeck et al. (209),, we also propose and analyze the random experiences model as a more realistic representation of user behavior.
We introduce problem-dependent load parameter L that roughly corresponds to the maximum number of simultaneous allocations possible (see Def. 2). We uncover its crucial role in character- izing problem classes for which we establish matching upper and lower regret bounds.
We design regret-optimal (up to smaller order terms) algorithms for each setting. For any market setting with N users, M items, and maximum load T., our algorithms achieve regret ONNM log log( (LT)) under fixed valuations model, O(VNML. under random experiences model and O(VN under random valuations model in T rounds.
All proposed algorithms have computational complexity (L per round in the worst case. The algorithms for fixed valuations and random experiences models have space complexity O O(N M) while the algorithm for random valuations has space complexity (LT)//))
2 Related work
Bandits for dynamic posted-pricing. The problem of dynamic pricing has been typically modeled as a variant of the multi-armed bandit problem starting with Rothschild (1974). In their seminal work, Kleinbere and Leighton (2003) developed more general and widely-appreciated framework to maximize revenue from selling copies of a single good sequentially arriving users. In the following years, there has been growing body of work on multi-period
dynamic

---

pricing problems under different user valuation models including non- parametric models (Besbes)
and Zeevi 2009 Keskin and Zeevi 2014, Bianchi al., 2019 Bubeck et al. 2019), contextual
(feature-basedl models (Paes Leme and Schneider 2018 Cohen et al. 2020 Xu and Wang 2021 I. and other parametric models (Araman and [ Broder and Rusmevichientong 2012
Harrison et al.) 2012 Chen and Farias 20s3/ Besbes and Zeevi 2015 Ferreira et al. 2018). However, all of these works address the posted price problem for selling a single item in each round. Our contribution stands out by considering the combinatorial aspect of the allocation problem faced in simultaneously selling multiple items, a factor that was not taken into account in prior literature.
Combinatorial multi-armed bandits. The semi-bandits framework of Audiberrt et al. (2011) and the combinatorial multi-armed bandits frameworks offChen et al. (2015) and oveton et al. (2015) model problems where a player selects a combination of arms in each round and observes random rewards from the played arms. Therefore, the selection of the offers in setting shows parallelism with these frameworks. However, their algorithmic solutions cannot be directly applied to our problem because the feedback and reward mechanisms in dynamic pricing models considered in this literature. It is mainly because the feedback (acceptance/rejeccion)) and reward (revenue) are not only affected by the offers but also by the accompanying prices.
crucially different than the
Bandits in matching markets. One recent line of related literature in computational economics studies algorithms for learning socially-optimal matching in two-sided markets (Liu et al. 2020 Johari et al. 2017 Jagadeesan al. 2021). These frameworks can be used to model the problem of allocating multiple items to multiple users with unknown valuations with the goal of maximizing social welfare. However, these works only consider scenarios where all the users accept their matchings (i.e. offers) without being affected by prices and send the provider real-valued random feedback representing the welfare they achieve from this matching. In their recent work, Erginbas iet al. (2023) also analyze a similar problem of optimal and stable allocations and further allow users to accept or reject their recommendations based on the prices. However, their framework also requires random feedback to be sent to the provider regarding their valuation for each accepted matching, whereas our problem setting limits the provider to only observe acceptance or rejection decisions.
Learning in repeated auctions. The learning literature on auctions considers both offline (Morgen- stern and Roughgarden, 2016 Cai and Daskalakis 2017) and online approaches (Bar- Yossef et al. 2002] and Nisan| 2000) to maximize the provider's revenue from selling multiple items to multi- ple users. Nonetheless, the implementation of these auctions often presents significant difficulties due to the inherent complexities in obtaining precise valuations from human participants for all the items. As result, there is growing interest in designing mechanisms that are accessible, simple to use, and can easily elicit the valuations of the buyers while maximizing the revenue of the provider. In this direction, our approach in this study follows the main premise of posted-price mechanisms (Feldman et al. [0155] Einav et al. 2018), in which the provider sets a fixed price for each item, and buyers decide whether not to purchase the item at that price.
3 Problem setting
Notation: We use bold font for vectors x and matrices X, and calligraphic font X for sets. For vector x, we denote i-th entry by x; and for matrix X, we denote its (i.h) entry by zij- For any positive integer n. we use [n] to denote the set [1, ........, .n). For real numbers a and b, we use A to denote their minimum and a b to denote their maximum.
Suppose the market consists of a set of users N of size N and a set of items I of size M. At each round & E [T] over some fixed time horizon T, provider is endowed with a subset of the items denoted by 8 C I and tries to sell these items to users with the goal of obtaining revenue. D We assume that endowed items E are only available for sale at time interval t. That is, the items that are not sold at a round cannot be stored to be sold in future rounds.
Each user u E W has an unknown and possibly time vare-ig valuation of for each item at round t. In this work, we consider that each user u has a time-varying request for at most d', items and has an additive utility model over items. Thus, the provider decides on a price vector p E RR and offers each user u E N subset of the available items denoted by St, C El of size at most [S S d' Then, users decide to accept a subset of their offered items At, C St based on their valuations and the prices of the items in order to maximize their surplus given by Eiers (vi, pt).
'Our framework readily extends to scenarios where the provider is endowed with multiple copies of each type of item. However, for simplicity in our analysis and presentation, we do not consider this generalization.
3

---

Due to the additive utility assumption, when user u is offered S it accepts all items i E St that give positive surplus (i.e. of 2 pt) while rejecting all other items. Hence, the of accepted items can be written
A" = (i SiESS St vh 2 p.).
For future reference, also denote the collections of offered and accepted items time by S' = (S lu E W and AA' = {At, ju E N, respectively. To eliminate the possibility of an item getting accepted by multiple users, we consider posted-price offer mechanisms that offer each item to at most one user. Therefore, the offered sets of items are disjoint, i.e. St n.S = 0 for u * u'.
Whenever a user accepts the offer item at round t, this sale generates pt revenue for the provider. Therefore, the cumulative revenue obtained over T rounds equals
T ΣΣΣN=EN
T
Σ BES! pt 1 2 p/}.
(I)
WEN
After the provider decides the price vector p' and the offers S (S E M the report their set of accepted items A' = {AAi .V. We denote by H2 the history (S" .p" ,A of observations available the provider when choosing the next set of offers S along with the next price vector p'. The provider employs a policy π = (n'lt it E NJ. which is a sequence of functions, each mapping the history Hg to an action (S*, ,p').
The task of the provider to repeatedly offer the items to users and choose the prices such that can achieve maximal revenue. To evaluate policies in achieving this objective, we define regret metrics that measure the gap between the expected revenue policy æ and an optimal algorithm. Definition 1. For a policy n, its revenue regret in T rounds is defined as
R(T, mt) OPT -E pt ( 2 p/),
LEE iES!
where OPT denotes the revenue of the optimal algorithm which will be defined separately for each different valuation model in Section f
We can also represent the offers S = (S) E . using binary variables x/. = [ E St that indicate whether item is member of each of the sets S. With this definition, each variable o equal to user
offered item matrix X E {0, 1 JNN called the offer matrix. Due to endowment and demand constraints, the offer matrix X at each time t needs to belong to the set
time and otherwise. We collect these variables into a
x²
x (0,
NXM
ΣS' S d',, Vu E N and Σ Jui S c Vi Se WEN
(3)
VEI
where each endowment quantity et life E`} is equal to I when item is available to be offered at time f, and 0 otherwise. Using this notation, we can write the cumulative revenue as
ΣΣΣ Am WEN VEN
shan Ho 211).
(4)
Lastly, we define the maximum load parameter which refers to the maximum amount of simultancous demand and supply in the market. Formally, Definition For a problem with endowment sequence (ESST and demand sequences (d))) of all users E N, the maximum load is defined as
I = max (Dr A Ft). 1<tTT
(5)
where D, := EnEE d' and E, := | are the total demand and endowment at time t, respectively.
Note that the maximum load parameter L is an upper bound for the number of offers that can be made any round t. This parameter is central our analysis since the problem becomes more complex as the maximum load increases.
In this definition, assume that all tie bie-brekk are resolved in favor of the provider.

---

3.1 Summary of results
Our goal in this work is to provide insights into how to strategize multi-round posted-pric offers when the provider does not have prior knowledge of user valuations. In particular, we consider the problem under three different valuation models as described below.
1. Fixed valuations:
The valuations of users do not change time. Formally, there exist values Oui such that o = Cui for all E (T].
2. Random experiences: The valuations of users are given as their average historical experience where each experience is independently drawn from distributions specific to each user and each item. Formally, we consider the experience of user u with item i to be given as the random variable z independently drawn from some distribution with cumulative distribution function Fui for all rounds at which user u has accepted item i. Then, each valuation uys is given as the average the past experiences, i.e., the average of values { T t, E A.)
3. Random valuations: The valuations of users at different rounds are independently drawn from distributions specific to each user and each item. Formally, there exist cumulative distribution functions Fu: for all (u, E N x I such that each v is independently drawn from a distribution with edf Fus.
For each of the models described above, we derive upper and lower bounds for revenue regret, matching up logarithmic factors. We summarize our results in Table
Table Upper and lower bounds for revenue regret under different valuation models.
Model
Upper Bound
Lower Bound
Fixed Valuations (Section 4.1
O (NM log loggoo((1) (LT)
Ω (NM loglog(LL (N)))
Random Experiences (Section 4.2
δ (NNMTT)
s (VNMLT
Random Valuations (Section 4.3)
Ö (VNMLT
Ω VNMLT
Remark. The frameworks of fixed valuations and random valuations can also be used to model settings where each interacting user is associated with a type that determines their valuations. In this case, the set N corresponds to the set of all user types and each demand parameter d' represents the total demand of users of type u in round t. Under the fixed valuations model, all users type u have valuation vn, Vui for item i at all rounds t. Under the random valuations model, each user of type u has a random valuation with distribution Fus for item independently for each user at each time t. Since most user receives any item in any round, it is sufficient consider single random valuation uy for each type u and item i at time L.
Methodology
We provide algorithms for achieving sub-linear revenue regret under different user valuation models described in Section 3.1, While the strategies for the selection of offers are similar under different models, we use different pricing strategies for different models depicted in Figure
if accepted aui
if rejected
if accceeeed
blog muai
if rejected bui
if accepted oe if rejected
bui
aud
Bus
else
if n for some jeIN
0
K
2
(a) Fixed valuations
(b) Random experiences
(c) Random valuations
Figure 2: The selection of prices for different valuation models. (a) If the offer is accepted (rejected),
we set the new value of aus (bus) as the offered price pç. (b) If nus = 2 for some j E and the offer is accepted (rejected), After offering an item at price k/ K, update the 8th confidence interval based whether the offer is accepted or rejected.
set the new value of aui (bus) number smaller (larger) than pI. (c)
5

---

Algorithm Offerings with incremental search prices
aui f 0, bus + 1 and Suc + 0.5 for all u E N.
for t= 1, ..2,...,7 do
Calculate X by solving problem @ using bui values.
for (u,t) {(u, 1): I
1) do
offer item i P set the price
P < Out + Puc 1 (b Qui rrr Offer item to user u price př and observe 1f de 2 p.}. if u 2 pi then Gus +- aue V pi else bus bus A if bus Ous I Pur then But + Pui
update the interval > update the search step size
end for
end for
4.1 Revenue maximization under fixed valuations
In this section, we focus the scenario where the provider makes posted-price offers to users whose valuations are fixed over time. We formalize this condition in the following assumption.
Assumption 1. The valuation of any user E for any item i I is given by vh Vua for some Vai E [0, 1] at all rounds E [T].
In the case of fixed valuations, we define the optimum strategy as the one that maximizes the revenue under complete information on user valuations. Therefore, the optimum offers X and prices p', for all rounds are given by maximizing the cumulative revenue given in (4). That is, we define the optimum objective value as
OPT = Σ max max
ΣΣ X D'ERY WEN IET
xe p foor 2 p1]
(6)
and let X and pt be the solutions that maximize term t. Note that for any allocation X E X have Σ Eusv ot S ef < 1. Therefore, whenever an item i is offered to a user u, the optimum price of item equal to the user's valuation tui. In other words, the optimum price for item is given by pf EvEN "r Vni- Based on this observation, the evenue-maximinn
offer can be found as
X = arg max X NEN TET
Σ
x Vai.
We note that the integer program in (7) can be written instance of maximum weight bipartite matching. Then, using a variant of the Hungarian algorithm for unbalanced bipartite graphs (Ramshaw and Tarjan 2012). this problem can be solved in space ((NM) and time O(N M in the worst case. (See Appendix A for details.)
Since there is no randomness user responses, every response from a user u about item i gives the provider complete information about lower upper bound Vais depending user response was to accept or reject the offered price for the item i. For this reason, the algorithm operates by keeping track of intervals [aus. buel that contain Uns value for each E A,, E I at all rounds. At each time t, the algorithm chooses which items to offer to each user using these intervals and then determines price for each offered item. The selection of the allocations is done according to the OFU principle (Dani et al., 2008 Abbasi- Yadkori, (011 in order to ensure low regret. In particular, the offers are chosen by replacing each Vas in problem with byg to obtain
whether the
X max
ΣV
(8)
X'EX"
REN KE
Having decided on the offers, the next step is to decide on the price of the offered items. Similar to the challenge we encountered in selecting the offers, the selection of prices should also serve two different goals that are in tension with each other. On one hand, learning new information about users' valuations requires us to set prices to values from (aui. bus). On the other hand, to ensure the offers are accepted and generate revenue, we would need to select prices lower than or equal to aui- The crucial property that enables us to obtain D(NM log log(T)) regret is that the function p - Uns pl (p S Vay) asymmetric and decreases more slowly on the left than on the right as discussed in Kleinberg and Leighton (2003). Based on this observation, we design a pricing algorithm

---

that operates by offering item i to user prices increasing with increments of Bus. When the width of the interval [aw. bux] becomes smaller than the precision parameter Puis we the new precision parameter as & and continue exploration with this smaller step size. However, we show in the proof of Theorem [ continuing to explore indefinitely would result in a regret linear in T. To avoid this issue, the algorithm should stop exploration after achieving a certain level of precision and offer item to user u at the maximum price that is certainly acceptable, namely Oui-
We provide a summary of this algorithm Algorithm I and provide an upper bound for its regret in Theorem [ As the lower bound provided in Theorem shows, the regret of this algorithm is order-optimal up to smaller terms.
Theorem 1 (Upper bound for Fixed valuations). Assuming fixed valuations in market with N users, M items, and maximum load L; the regret of Algorithm 7 i rounds satisfies
R(T, T) 2 log log LT)) + +1
Proof. See Appendix B.1
Theorem (Lower bound for Fixed valuations). IfN M, and L S. M are given parameters and is any randomized policy; there exist randomly generated market instances of N users with fixed valuations for M items and maximum load L such that the expected regret of πI in 2 4NM rounds is S2NN M log log( (LTT/NN))
Proof. See Appendix B.2
4.2 Revenue maximization under random experiences
This section focuses the where the valuations of the users given as the average of their past experience. We assume that each user obtains independent experiences about the items that they accept at every round. Then, the users form their valuation at each time the average of their experiences so far. Formally, we make the following assumption.
Assumption 2. Whenever a user u E N accepts an item i < I round e [T], obtains an independent random experience zus with unknown edf Fus over [0, 1] with mean Vus- Then, the valuation of any user N for any item
round E [Z'] is given as
Σ
(9)
T
uui
TET..
where T < b is the set of rounds before round t at which user u has accepted and experienced item i, and m Tud denotes the size of this set.
Under the random experiences model, define the optimum strategy as the that maximizes the revenue with complete information on possible user experiences > and hence user valuations vi at all times. Therefore, the optimum revenue that can be obtained in rounds is given by
ΣΣΣ''. max X'EX"nEIT p' P'ERN
OPT
2 p.).
(10)
1=1 NEN FET
which is a random variable due to the randomness in 2i, and hence the randomness in v Next, we note that for any fixed sequence of offers {X* [T]}, the objective is maximized prices that satisfy pf EnEx di Vui at all t. Therefore, we can write the optimum value for the objective as
T ΣΣΣ
OPT
max XEE
(11)
1=1
NEN TET
Note that in problem [1]. we need to globally maximize over X all rounds / E [7] because the values of oy depend on selections of X at previous rounds. In order to deal with this dependency between the selections of X in Lemma 9 we show that OPT is not likely be much larger than the sum of the mean valuations of the best offers at all rounds.
7

---

Algorithm 2 Offerings with scheduled learning
Gui f 0, bus + 1, Bus f- O, and Mui + for all E ENiiEZ for t= 1, ..,, do
Calculate X by solving problem (8) using bui values
for (u, t) {(u,t) I' 1] do
offer item i b set the price
if āj E IN s.t. Aui = 2 then p + (asi + bua) 2 else p\ +- Oui
Offer item to user u price P and observe I { 2 pi].
7 4- 1--VVllo(( (8llo((NMT)
D set the confidence level update the interval
if u 2 P. then tus < aus V (pl - 7) else bus Uue A (pt + 7)
if vh 2 p¹ then Mas Mas
Aha f Rui +
end for end for
Next, we describe our algorithm in Algorithm 2 As the users accept and experience the items, their valuations converge the mean of their experience distribution. Therefore, before extracting the mean valuation information from the users, the provider must ensure that users accept and sufficiently experience the items. Then, to extract this information, the algorithm occasionally asks for higher prices while taking the risk of rejected offers. However, since there are most log(T" such learning rounds per user-item pair, it does not cause any significant loss in revenue.
Based on these observations, we establish an upper bound for our algorithm's regret in Theorem Furthermore, as indicated by the regret lower bound presented in Theorem 4 our algorithm's 's regret is order-optimal up to smaller terms.
Theorem 3 (Upper bound for random experiences). In any market of N users satisfying the random for M items and maximum load L, with probability 28,
experience model given in Assumption 2
the revenue regret of Algorithm 2 satisfies
R(T, = O (VNMLTlog(NM/)) + NM T)
Proof. See Appendix C.2
Theorem 4 (Lower bound for random experiences). If N, M, and L. S M are given parameters and π is any randomized policy; there exist randomly generated market instances of N users satisfying the random experience model given in Assumption for M items and maximum load L such that the expected regret of in T N rounds Q(VNMLT).
Proof. See Appendix
C.3
4.3 Revenue maximization under random valuations
In this section, we consider the case where the valuations of the users are given as independent random variables drawn from distributions specific to each user and item. Formally,
Assumption 3. The valuation any user E N for any item i I round E [T] is given as an independent random variable v with unknown cdf Fus over [0, 1].
Given foreknowledge of the distribution of valuations, but not of the individual valuations different rounds, it is easy to see what the optimal pricing strategy would be. The expected revenue obtained from offering item to user u at price p is given as (pu(p)) = p(1 - F., (p)), which we call to be the revenue function. Since valuations are independent over time and their distribution is known, individual responses provide no useful information about future realizations of the valuations. Therefore, the best price for offering item to user u is given by
Pus arg max p(1 (p)).
(12)
PER_
Thus, letting vh = v (P.)) denote the maximum expected revenue that can obtained by offering item to user an optimum policy that knows the distribution of valuations can obtain revenue
OPT Σ t=1
max XEX*
Σ> WEN NET
(13)
8

---

Algorithm 3 Offerings with quantized pricing
= (LT/ (N log(L))))) for = 1, 1.,....; T do
Thask O, and thisk < for all a e N.
for (u, 1) E x I do
Dask + (Dusk + / log (og(NNMT))//ad AA1 [K]
D compute UCB
huc f- arg m buek and bus f- max; buck
compute best price levels
end for
Calculate X by solving problem ( using bas values.
for (u, i) {(u, i) xiu 1) do
make offers
Offer item user u price Pui kuss/ K and observe Zui 11 (ris pui)
Pusk + (Musk Paik (ut
for kus
Buck <- Thusk for kui
end for end for
However, without the knowledge of the distributions, we are required to learn the expected revenue (i.e. rewards) at different prices via exploration. As previously done the literature on pricing under random valuation models (Kleinberg and Leighton| (003), we apply techniques from the literature on the multi-armed bandit problem to develop an algorithm with low regret guarantees. To so, we quantize the set of possible prices by limiting the provider to strategies that only offer prices belonging to the set (1/K, 2/K, ...1} for suitably chosen K. This brings us into setting where each at price k/ K yields revenue which is random variable taking values
offer of item to a in 00, 1]. whose distribution depends on (u, i, k). but the rewards for a given action are i.i.d. across the rounds. Therefore, offering item to user and 4 price level can be represented as pulling an arm that generates revenue with expectation thikk (k/ K). In total, the expected revenue of any offering and pricing is
K ΣΣΣΣ
miik Vusk:
(14)
WEN VET.
where zits are binary variables that denote whether user is offered item i at ktth price level at round Due to endowment and demand constraints, these variables at time must satisfy conditions (I)
Eier Ex= Tuik I d', (2) EvEN Σk= Tusk S e/, and (3) Ek Jusk S 1 for all u E N, I. In the literature on combinatorial multi-armen bandits, the standard regret bounds for UCB-based algorithms have inverse dependency on the gap between the rewards of optimal and suboptimal arms (Kveton et al. 2015). To use similar techniques in proving regret bounds for our algorithm, we make the following hypothesis the distributions of valuations, which translates directly into bounds on price sub-optimality gaps max; Duik Pusk-
Assumption 4. The revenue function vui(p) has a unique global maximum pu: E (0, 1), and V (Pt.) is defined and strictly negative.
Next, we show that our algorithm can attain the regret upper bound stated in Theorem 5 as illustrated in Theorem 6 our algorithm's regret order-optimal up to smaller terms.
Moreover,
Theorem (Upper bound for random valuations). In any market of N users satisfying the random valuation model given Assumptions 3 Aor M items and maximum load L, with probability 1 - 8, the revenue regret of Algorithm 3 satisfies
R(T, n) O ( NNMLTlog(LTy) Log (T
Proof. See Appendix D.2
Theorem 6 (Lower bound for random valuations). If N, M, and L < M are given parameters and is any randomized policy; there exist randomly generated market instances of N users satisfying the random valuation model given in Assumptions 3 And M items and maximum load L such that the expected regret of π is Q( (LL) in T rounds.
Proof. See Appendix D.3

---

Numerical experiments
In this section, we demonstrate the efficacy of our proposed algorithms through a numerical study. We provide our results in FiguresBaadd3 At each round E [T]. the provider is endowed with each item E I (i.e. i E 89) independently with probability 0.5. On the other hand, each user v E V has random demand dy with uniform probability over {0, 1, For the case of fixed valuations, we choose each Uni independently from (eta , 2). For other two models, we set each Fui as the cdf of (eta Bux) where Oui and Bui are uniformly and independently chosen over 5].
Fixed Valuations
Random Experiences
Random Valuations
Instantineus Regred
00
Iostantanengs Regret
Instontamena Regret
-0
40
40
30
30-
20
15)
10
Co
250
500
750
1000
750
1500
2250
3000
12500
2500
3750
5000
Itcratiinn
lteration
Figure 3: Instantaneous regret under different valuation models. The darker lines correspond to the mean across 20 experiments with N 150 users and M 100 items. The shaded areas indicate the region of error spanning two standard deviations. Results demonstrate the efficacy of our algorithms in achieving diminishing regret our theoretical results predict.
1of
Fixed Valuations
1ef
Random Experiences
lof
Random Valuations
2-
7.5
Roget
Regret
Regret
2.5
1000
2000
3000
1000
2000
3000
Time Horizon (
Time Harizon (
Time Herizon (T)
Figure 4: Regret as a function of time horizon under different valuation models. The darker lines correspond to the mean across 5 experiments with N 150 users and M = 100 items. The shaded areas indicate the region of error spanning two standard deviations. Note that the horizontal axis is logarithmic in the plot for fixed valuations and linear in the plots for the other two cases. Results verify that our algorithms can achieve mub-logarithmic regret under the fixed valuations model, sub-linear regret under random experiences model, and sub-linear regret under random valuations model.
6 Conclusion
Our study presents comprehensive solution to maximizing expected revenue in repeated interaction setting, where a provider seeks to sell multiple items to multiple users. By focusing on different valuation models, we design online learning algorithms that can infer user valuations and offer items to those who value them most to ensure approximately optimal revenue regret. The results this study have important implications for online marketplaces and can help providers optimize pricing strategics and maximize revenue a dynamic and uncertain environment.
Acknowledgements
This work was supported in part by NSF grants CIF-2007669 and CIF-1937357.
References
Abbasi- Yadkori, Y. (2011). Improved algorithms for linear stochastic bandits. Proceedings of
Twenty-Fifth Conference Neural Information Processing Systems (NeurIPS), pages 2312-2320
Araman, V. F. and Caldentey, R. (2009). Dynamic pricing for nonperishable products with demand learning. Operations Research, 57(5):1
Audibert, J.-Y., Bubeck, S., and Lugasi, G. (2011). Minimax policies for combinatorial prediction games. In Proceedings of the Twenty-Fourth Annual Conference on Learning Theory (COLT), volume 19, pages 107-132.
10

---

Bar- Yossef, Z., Hildrum, K., and Wu, F. (2002). mncetive-compatiie online auctions for digital goods. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 964-970.
Besbes, O. and Zeevi, A. (2009). Dynamic pricing without knowing the demand function: Risk bounds and near near-optimal algorithms. Operations Research, 5766):1407-1420.
Besbes, O. and Zeevi, A. (2015), On the surprising sufficiency of linear models for dynamic pricing with demand learning. Management Science, (44:7233-73
Broder, J. and Rusmevichientong. (2012). Dynamic pricing under general parametric choice model. Operations Research, 60(4):965-980.
Bubeck, S., Devanur, N. R., Huang, Z.,, and Niazadeh, R. (2019). Multi-scale online learning: Theory and applications to online auctions and pricing. Journal of Machine Learning Research, 20(62):1-37.
Cai. Y. and Daskalakis. C. (2017). Learning multi-item auctions with (or without) samples. In Proceedings of the Fifty-Fighth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 516-527.
Bssa-Bianchi, N., Cesari, T., and Perchet, V. (2019). Dynamic pricing with finitely many unknown valuations. In Proceedings of the Thirtieth International Conference on Algorithmic Learning Theeory pages 247-273.
Chen, W., Wang, Y., and Yuan, Y. (2013). Combinatorial multi aamti--rmedd bandit: General framework and applications. In Proceedings of the Thirtieth International Conference on Machine Learning (ICML), volume 28, pages 151-159.
Chen, Y. and Farias, V. F. (2013). Simple policies for dynamic pricing with imperfect forecasts. Operations Research, 63:66612-6
Cohen, M. C., Lobel, I., and Paes Leme, R. (2020). Feature-basse dynamic pricing. Management Science, 66(1 19:491144933
Dani, V., Hayes, T., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. Proceedings of the Twenty-First Annual Conference on Learning Theeory (COLT), pages 355-366.
Einav, L., Farronato, C., Levin, J., and Sundaresan, N. (2018). Auctions versus posted prices in online markets. Journal of Political Economy, 126(1):178-215.
Erginbas, Y. E., Phade, S., and Ramchandran, K. (2023). Interactive learning with pricing for optimal and stable allocations in markets. In Proceedings of the Twenty- Sixth International Conference on Artificial Intelligence and Statistics (AISTATS), pages 9773-9806.
Feldman, M., Gravin, N., and Lucier, B. (2015). Combinatorial auctions via posted prices. In Proceedings of the Twenty-Sixth Annual ACM-SEA -SAM Symposium on Discrete Algorithms (SODA), pages 123-135.
Ferreira, K. J., Simchi-Levi, D., and Wang, H. (2018). Online network revenue management using thompson sampling. Operations Research, 66(6):1586-166)
Harrison, J. M., Keskin, N. B., and Zeevi, A. (2012). Bayesian dynamic pricing policies: Learning and earning under binary prior distribution. Management Science, 58(3):570-586
Jagadeesan, M., Wei, A., Wang. Y., Jordan, M. I., and Steinhardt, J. (2021). Learning equilibria in matching markets from bandit feedback. Proceedings of Thity-Fifth Conference Neural Information Processing Systems (NeurIPS), pages 1323-3333..
Johari, R., Kamble, V., and Kanoria, Y. (2017). Matching while learning. In Proceedings of the ACM Conference on Economics and Computation, pages 119-119.
Keskin, N. and Zeevi, A. (2014). Dynamic pricing with an unknown demand model: Asymptoti- cally optimal semi-myopic policies. Operations Research, 62:1 1667
11

---

Kleinberg, R. and Leighton, T. (2003). The value of knowing a demand curve: bounds on regret for online posted-pric auctions. In Proceedings of the Forty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 594-60446 605.
Kveton, B., Wen, Z. Ashkan, A., and Szepesvari, C. (2015). Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits, In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics (AISTATS), volume 38, pages 535-543.
Lavi, R. and Nisan, N. (2000). Competitive analysis of incentive compatible on-line auctions. In Proceedings of the Second ACM Conference on Electronic Commerce.
Liu, L. T., Mania, H., and Jordan, M. I. (2020). Competing bandits in matching markets. In Proceedings of the Twenty-Third International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1618-1628.
Morgenstern, J. and Roughgarden, T. (2016). Learning simple auctions. In Proceedings of the 29th Annual Conference on Learning Theory (COLT), pages 1298-1318.
Paes Leme, R. and Schneider, (2018). Contextual search via intrinsic volumes. In Proceedings of the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 268-282.
Ramshaw, L. and Tarjan, R. E. (2012). On minimum-cost assignments in unbalanced bipartite graphs. HP Labs, Palo Alto, CA, USA, Tech. Rep. HHP1-2012-40R), 20.
Rothschild, M. (1974). A two-armed bandit theory of market pricing. Journal of Economic Theory, 9(2):185-202
Xu, J. and Wang, Y.-X. (2021). Logarithmic regret in feature-based dynamic pricing. In Proceedings of Thitty-Fifth Conference on Neural Information Processing Systems (NeurIPS), volume 34, pages 13898-13910.
12

---

A Algorithmic Details for Solving the Integer Program
The integer linear program in (7) can be written as an instance of maximum weight bipartite matching. In this graph, we represent each user u with d' left nodes and we represent each endowed item with right node. Then, we construct the complete weighted bipartite graph where the weight of an edge between node for user u and a node for item given as Uut- In total, this graph has D; left vertices, E, right vertices, and D,Er Et weighted edges where D, and E, correspond to total demand and endowment at time t (as given in Definition 2
Then, using variant of the Hungarian algorithm for unbalanced bipartite graphs (Ramshaw and Tarjan 2012), this problem can be solved in space (DD, F&) and time O(D, Eg min Dr, Ex)).
Since we can upper bound D; S N. E, S M, and min D,, ( runs in space (NN and time O(NML) in the worst case.
< L, we conclude that the algorithm
B Proofs for Revenue Maximization with Fixed Valuations
B.1 Proof of Theorem !
Letting OPT, denote the optimum revenue at each time I. and Rg denote the regret at round L
R₂ OPT, ΣΣ
s (uus 2 pt}
NEN FEI
Σ MEN FEI
E
suipl 1 {iri 2 pi}
max XEX
Tuatiui
WEN EE
S max XEX
Σ
Σ
Trable ui
ΣΣ
Bui (rri 2 p-t
WEN EEI
WEN iEI
ΣΣ Blu
ΣΣ
I (Wai 2 p
WEN IEI
UEN VEI
ΣΣ
Tu (bir - I 2 p(1))
NEN iEZ
Then, sum over all < T to have
R(T. TT
Σ Ri
t=1
Σ
dlelllivee 2 ptf
WEN IET
Σ Σ
Σ (Bi, ( 2 p()),
"EA VEI TET.:
where Tai = (t::
1} denotes the time indices where (u, i) is offered. Now, we let
Rui
Σ (b... a's (was 2 v())
TE
be an upper bound for the total regret incurred from offering the pair (u, i) such that we have R(T, < EnEN Eiez Rui- Now, let kth learning epoch for pair (u, i) correspond the time indices which Bi, = (1/2)* and the pair (u, i) offered. That is,
T = {1 E Tai : = (1/2)*}.
Note that we have bys a Bts (1/2)* for each E T During the learning phase, each epoch Th ends either when the offer (u,, i) is rejected the offer (u. i) is accepted 2 -1 times in row. Therefore, in epoch k, there are at most one rejection and 2* 1 acceptances. As a result, the regret incurred by offers (u, i) during each T.k is upper bounded as
Σ (bh. a 1 1v 2 p!)) S 1 + (2* ()(1/2)* $2 2. TET
(15)
13

---

Note that a learning epoch Tyd can last for anywhere between 1 to 2 rounds in total. Therefore, if we were continue exploration indefinitely, the number of learning epochs could be as large as 'T' in the worst case. Consequently, continuing to explore indefinitely would result in linear regret. To avoid this issue, the algorithm should stop exploration after achieving a certain level of precision and offer item i to user at the maximum price that is certainly acceptable, namely Oui- We let this precision level be e and make the algorithm choose price Oui when b' dui S e. Based on this stopping rule, Kui [log log (1/e)] becomes the last epoch for (u, i) and therefore we run at most Kui learning epochs before the last epoch.
Since the offers are always accepted this last epoch, we incur at most regret at each round of Consequently, we have
Rui S 2log (1/c) + <TTl
< 2og log(1/t) + e/Tuil
Since X includes most L offers, also have ΣnEN Eier Iaail S LT. Thus,
R(T S 2 log eLT.
(16)
Letting = I/LT), we obtain
R(T, .T) 2N log log LT) + 1.
(17)
B.2
Proof of Theorem 2
Consider market with users N [N] where the demands of users given
L, t= (u (u-1) mod N
d = 0, otherwise.
so that only one user has nonzero demand in each round. Next, let M' be the smallest prime number larger than or equal M. If N M'. let M' be the next smallest prime number. By the prime number theorem, we always have M' < 4.M, and N and M' are always co-prime. Then, consider a set of items = [M'] such that the valuation all users for the first M items are uniformly and independently chosen over [0, 1] while the last M' - M items are artificial items that have zero valuation for all users. Next, assume that the set available items E at each time given according to
i g
i-t+1e E (1,2, L} mod M'
such that at most L of the items are available each round, and hence the maximum load parameter in this market is equal to L. By construction, the optimum offering pattern at each time is to offer all available items to a single user that has non-zero demand. Hence, the problem of the provider reduces to only learning the price at which it should offer each item. There are NM actual user-item pairs and each item E [M] is offered to user u E [N] for at least [LT/NM'] Z pricing optimization, each pricing problem is known to have (log log (T.)) regret T, rounds (Kleinberg and Leighton 2003). Therefore, any policy must have Q2 N M log log( L.T CLTT////NOOO M)) regret in total.
LLT//NNM > rounds. In the literature
C Proofs for Revenue Maximization with Random Experiences
C.1 Preliminary Lemmas
Lemma 7, With probability 6,
8 Slog(M (N M/ m
10 Vuil <
for all (u, E N x I and for all t I.
Proof. Let H4-1 be the o-algebra generated by (H, p') and let Ho = =000, Fix some (u, and define et, = 2th Vui for all t E N. By previous assumptions, Eje,, 74-11 0 and (et, I exp (2²/2) for all t IN.
14

---

Define d. = [( vei)² 2 - (z 21 = 1}. Then, we have
6x [-(v M/s ) 2c ue (v rue]] {> = 1}.
Therefore, the conditional mean and conditional cumulant generating function satisfy pus El [4-1]]+ - (vis vui)² 1 =1}
(An(A) log Li(ep (e(xpp((011 - ((a1))
log Wilepp ( [us)) 13
(2X(v vua)) )2
11 {arne =1.
Applying Lemma
14
we have, for all and 0,
T
(ou - (2x 1) [> =1 MMEN) 21 21-64
Therefore.
Σ 12 Uui)2 2- (2 v1 S + Σ TET.
(v 12x) 11) E 21-ca.
TET..
Noting that uh 1 ΣTETs. z we have ΣreTi [( Uni)² (2 ) 2 0 for all t.
miu
Then, choosing \ 1 and log 2 gives
P
(v'e vna)² S (log(1/0)
E
IN 21-6,
(t)
which implies
8 (lg((1)))
Iobe vasl S
vt
21-5.
m
By applying a union bound over all (u, i) pairs, we have
8log(NMM0)
P
|ute Vuel S
M((ii) EN 21
m
Lemma 8. With probability 6,
Uui E [a byul
for all (w, 1) E N x I and for all t IN.
Proof. From Lemma 7 have Jui Vusl S /8 ( / for all (u, N x I and for all t E [T) with probability - 5. Assume that this condition holds true.
We prove the statement of the lemma by induction. Assume Voi E =aa bb,ll as the inductive hypothesis. Then, if user accepts item at price př, then we have by 2 pÝ. Therefore, pf Vui S v Uni S / log M/O) So, a++1 a', V (pf / 88 log((N (og((NM/))/mmi S Vni Similarly, we can also show b++1 bi, A (pl + /8log(NM/8))mm) 2 Vas- Therefore, ..+ E [a 64t J.
Lemma 9, With probability 5, the value of OPT satisfies
OPT
max X
ΣΣ
Ius Uui s S (VNMITTog(NN/8))
(18)
uEN
iEi
15

---

Proof. Let us define
T
OPT
max XeX* "EN
Σ
Σee IEI
DueVus
(19)
Then, using the definition of OPT and OPT together with Lemma 7 we have
T
ΣΣΣ
OPT
max X [TE
1=1 NEN RE
2 Uus Σ
ΣΣΣ
xt (o Vus)
1=1 WEN IET
1=1 MEN FET
max
ΣΣΣ MEN IET.
Tut Uus
+
max
ΣΣΣ
D Pu Bus)
X
XIE
CEENEEE IET
OPT
max XIE
ΣEΣ
Fle vui)
MEN TET
ΣΣΣ
(NN
max < ОPT
(T
m
WEN iEZ
S ОPT V (N8
max (T
ΣΣΣ s'u V 1/mm
Recall that n counts the number of times user u is offered item i and vn counts the number of corresponding acceptances. Since item can be rejected only when n',, 2 for some j N, can write
T ΣΣΣ
E
I
Fui
mi
m
1= NENEN EET
MEN 1ET
tix!
ΣΣ WEN TEI
Σ
Σ
m
m
tixt tirh-1 AJEN:n
AjENmn =22
m
ΣΣ REN EEI
I k
+
2/ + log
REN SEI
where we upper bound the first term inside the parentheses using Σx= VR S So = 2 and we upper bound the second term by noting that it can have at most log T terms. Also note that the total number of offers over all time intervals upper bounded by LT, and therefore EnEx Eiez my S L.T Then, using the Cauchy-Schwar inequality, we can write
v
T
ΣΣΣ
V ml 2 NM Σ
Σ m + NMllg
EI WEW IET
NEN TET
SOWVNMLT NM N Iog
Putting all together, conclude the proof of the lemma.
16

---

C.2 Proof of Theorem
By Lemma 8 the confidence bounds include the mean, i.c., Uui E [a bysl with probability 1 1 8. Assume that this condition holds.
Then, the offered items are accepted whenever there does not exist j E IN such that n - 2², So, we have that m 2 nui/2 2 because ni counts the number of times item is offered to user and m counts the number of times item is accepted by user u.
Furthermore, we recall that intervals are only updated at time step if x = and n' 2 for some E IN. Therefore, we can show upper bound for the width of the intervals [ale bud Define the width Put = Uy - ays- When the update happens, the interval's size gia becomes at most -ui² /2 + (N/66/ m I f-1 /2 (16log(N MM/ Therefore,
K
K-j
16log(NM/6)
Iu S
2
2
j=1
where K =loga nu is the number of times the interval is updated before time t. Then,
v 16 M//
(2) 1
2K
16 log N M/8)
(2
1)(1 V2)
2
144 logglogNNN (NM/5)
2k
144 log (N
210g n
288 log NM/6)) n
Now, let T. a 1, N, n 20 denote the learning event for pair (u, round t.
Also note that x = 1 at some t, then p = 1 Ld-Lindo Jo's + HLLiaaaa + b/./22 Next, we recall
the definition of OPT in (9) and let
Y
arg max
ΣΣ
Fuiluss
(20)
XEX
WEN
IEZ
with entries v Then, the regret with respect to OPT is given as the difference
T
TT = :
Σ ΣΣΣ
a 2p4
[=1 WEIEEN EEI
Σ
ΣΣ
1 2 ps}
1=1
REN iET
NEN
Recalling that the confidence bounds include the mean, i.e., Vai E (af Br,sb
R(T
Vus Σ Σ
a a ui -b
Aml
WEN TET
WEN FET
Vuu Dui
ΣΣ
ΣΣ
It of 1(L
WEN GET
MEN TET
NEN İET
T
ΣΣ
ΣE
t=1
LEEN TET
NEN TE
EEN IEI
17

---

Since X' is selected according to
X
arg max XEX
ΣΣ
Bushias 103
(21)
WEN TE
we can upper bound the first term as
Σ
Σ
Wyin Bui
x a()
- ΣE E
Whebbe - al))
NEN FEI
uEN iEI
(ee - slualle)
uEN VEI
ΣΣ
uEN iEI
On the other hand, the second term is upper bounded as
ΣΣΣnEh
S NM log
t= LINENiE iez
Therefore, we can upper bound Re(T, πT) as
R(T, π S ΣΣΣ
F'ugus
NM log T.
1=1 WEN iE
Then, we can show
ΣΣΣ
T
2 Fui S
Σ ΣΣΣ
T
Fuel
288 log NN M/
n
1=1 iEE Fer
1=1 WEN PEI
T ΣΣ J'e 1/n
288 (N
288
where the proof of the last step is similar to the proof of Lemma 9 Therefore, with probability 1 8,
Ř(T, TT S O NoV (N/ + NM log T).
Then, we use Lemma 9 which holds with probability 1 - 8. Therefore, by applying a union bound, we can show that
R(T,T) OPT OPT O RTT, S 0( NOL/NNLTTgggNMMM + NM T),
with probability 28.
C.3 Proof of Theorem
Recall that our observations are limited to accept-reject signals given by indicator variables 1 2 }a} for all (u, i) such that o 1. Furthermore, the valuations are given by
1
Σ
2
TETH
where 2 are i.i.d. random variables with mean Vut and Tu: (1) = {T < <l: = =1} Hence, signal lfrs 2 p.) is function of = in Tax((). As result, the problem of learning revenue- maximizing offers by observing 2(, for all (u, i) such that xt = no harder than that of learning revenue- evenue-maximizing offers by observing 1 v 2 p.) signals for all (u, such that xt; 1.
18

---

On top of observing < if we further assume that an oracle sets the prices pi = v whenever ry 1 (such that all the offers are accepted by achieving revenue o v' the corresponding problem becomes an online linear optimization problem with semi-bandit feedback. In this problem, at each round I, the algorithm chooses an offering X from the set of feasible offers X', observes zyg for all (u, i) such that zy = 1, and aims to maximize the total revenue (note that the revenue at time t is equal to the sum of valuations for all (u, i) such that z = 1). Since this problem is also no harder than our original problem, any lower bound for this problem also applies to our setting.
A = [N] and I = [M] be the set of users and items respectively. Then, consider a market setting where the demands of users are given as
if 1= (u mod N dy = 0, otherwise
L,
so that only user has nonzero demand in each round and each user is active for (TT/N) rounds. Let & = for all rounds and note that the maximum load in this market is I. as needed. Consequently, have N independent sub-problems where each sub-prot sub-problem corresponds to offering the best T. items I to a single user. In the literature on online linear optimization with semi-bandit feedhack, this problem is known the L-sets problem and it is known that for any algorithm there exists an instance such that expected regret 12( LMM,) in To rounds Kleinberg and Leighton (2003). Therefore, for any algorithm, each of N sub- booo-roobems has 22( 22(LLMT/N regret which corresponds to (LVNMLT regret in total for the whole problem.
D Proofs for Revenue Maximization with Random Valuations
D.1 Preliminary Lemmas
Lemma 10. For any E N and i I. there exists constants C1 and C2 such that Ci(p- - p (ue(PTa) th (p) C2(p Pux))
(22)
for all p E [0, 1].
Proof. Since vhg (pts) is strictly negative, there exists constants A1, A2. > 0 such that A
Pu.) 2 uha (P..)) ] (p)(p) < A2 piz)2 for all p E (pus - E, Pu; + +).. Since the set S = {p
[0, 1] Ip- Puil 2 }) compact and vni(PTs) - (p)(p) > 0 for all E S, there exists constants
B1, B2 such that (p - p= ) (Pr((Pt) - (p) < B2(p pta)2 for all p E S. Hence, if we
set C1 = A A B1 and C2 = A2 B2, we obtain the statement of the lemma.
Lemma 11. For any u E N and i I, define Dusk = max; Duik - thank- If An S Aun S < -ui(K-1) are the elements of the set (Auil..... Ausk sorted in ascending order, then Ausk 2 a (k/2K)²
Proof. Applying Lemma 10 and using the definition of Ausk. we can show that Ausk 2 Ci k/ t/K)2. Then, lower bound on Aus follows upon observing that at most j elements of the set 1} lie within distance j/2K K of pi.-
Lemma 12. For any u E N and i E I, we have eh
maxa Daik S C2/K2.
Proof. Applying Lemma 10 and noting that at least one of the prices (1/K, 1} lies within distance 1/K of pi.. we obtain the statement of the lemma.
D.2 Proof of Theorem 5
Let π² be the algorithm that chooses the optimum choice of offers and prices. Let T be the algorithm that chooses the optimum choice of offers, but chooses the prices as the best price from the set (1/K,2) 2/ 2/K, K,..., 1}. Let denote our algorithm described in Algorithm 3 Furthermore, let p(-) represent the expected revenue obtained by an algorithm. Then, the regret of policy π satisfies
R(T, TT) p(TT') p(TT) (p(TT)) ) p(Trk)) + (p(Tk) p(T)))
19

---

We begin with upper bounding p( p(T)). Recall that we can represent the expected revenue of any offering and pricing (that is constrained to set the set {1/K, 2/K......... ..). as
ΣEΣN
Fiis Puiks
NEN km
where zis are binary variables that denote whether to the endowment, demand constraints, and the constraint that requires the prices to be from the set (1/ K, 2/,, 1), the uisk variables each time need to belong the set
is offered item i at k price level. Due
k
X = (0,1) N
Kuik S d' Vu EN
s=
and
Σ
Luik S Vi, VIEI
WEN k=1
K
Buik S LLIuEN,ieet and Σ
1=1
Similar to the proof of Lemma 7 we have 1 Duik S 8 log( (oog(NM//O)/// for all u E N,,
i I and t [T]. For ease of notation, let us define B == 8 log( N MK/0) and w v VI/n'ukk Assuming that this condition holds, we can show that
p(TTk) p(T))=
max ΣΣΣ
Buik Week
ΣΣΣ
Fust Pask
XEX!
WEN
k=
WEN iEI k=1
K
K
max XEX!
ΣΣΣ
Trenk
Pusk
+
B
Fues Vrssk
w
WEN SEI 1=1
WEN 1EI k=1
K
B
ΣΣΣ
Wisk
Fuik
Jeek Wirk
wi usk
LuEN
k=1
uEN k=1
K
Pusk - Drick +
T uik
w
wakk
1=
uEN
FET
k=1
Hence, with probability
5, we have
((Tk) - ((T)) 2B
Σ
wiik
(23)
wf uike
At each time step 4, consider the list consisting w for all (u, i, E O. {(u,i, - = 1}. Let's now consider the overall list consisting of the concatenation of all of these lists over all rounds. Let's order this list in decreasing order to obtain a list (Wi, ......, wy) where = Σ 10 < LT. Using this notation, we have
p(Tx)) p(T)) S
2B
Tj--
1=1
First, for any (u, k) pair, the list wt can contain most 1 + 1/c² elements that are associated with (u,i,k) and larger than or equal to c. Secondly, note that x max; Vusk - Paak Ausk- As result, size of (t x = 1] is at most B² / Therefore, the number of times (u, i, k) pair can appear in the list is also upper bounded by B2/ Therefore, summing over all & [K]. we upper bound the number of elements that associated
only if B B/w(,u Z
20

---

with (u, i) and larger than or equal to c by
K
1
B
K
B²
min
1 +
min
1
1+
c²
A2
2
A
km0
uik
1
1
B
2K
11+
Σ
2
c
Cf
B
K-1
2K 2
Σ
+
1+
C1
c²
k
k=1
= =0 (1 2
/
1
+
BK2
2
where the second step uses Lemma
Thus, the total number of times that any confidence can
have size at least üūj is upper bounded by O NM (1+ 13) NMBK2
/
Using this
result, we can write woj = 0 min
Hence,
VGIENMKYY- VI/NM11
0
Σ min
VG/BNMK3R-1 VJ/NM-
j=1
LT
=0
min
1.
VG/BNMK2R--
VJINM-1
= 0 BBNK log(LT)+ (og + VNMLT)
Therefore,
p(T - p(T)= (BBNNKK log(LT) VNMLT
(24)
Next, we bound p(TT)) p(TTk)) Note that for each (u, i), at least one of the numbers {1/Ks K, 2/.,..,, }} lies within 1/K of p", i). Then, by Lemma 12 vo. max, Dusk I C2/K² for some absolute constant Cz. Therefore, the gap p(Tr") - p(T k upper bounded as
p( - p(( < C2LT
(25)
K²
Combining equations 24 and 25 we have
Bd B2N log(LT) log + VNMLT LT K2
R(T, π = O
Lastly, we choose K =
LT
to obtain
NM (oR(L))
R(T, 0 (B² NMLT (og(T))(LT)
=0
(VNNNNA log(T) l
=0 (o
where the last step uses 0 < K T and T > 1.
21

---

D.3 Proof of Theorem
Consider the same market setting (demands and endowments) in Appendix Section B but assume that the valuations are i.i.d. random instead of being fixed. By construction, the optimum offering pattern at each time is to offer all available items to single user that has non-zero demand. Hence, the problem the provider reduces to only learning the price at which should offer each item. There are N. actual user-item pairs and each item i E [M] is offered to user [N] for O (LT/NNM' rounds. In the literature on pricing optimization with i.i.d. valuations, each pricing problem is known to have Q oT) regret in To rounds (Kleinberg and Leighton 2003). Therefore, any policy must have ((VNMLT) regret in total.
E Martingale Exponential Inequalities
Consider a sequence of random variables (ZN)NEN adapted to the filtration (Hr WenneN. Assume Elexp(AZ.)) finite for all Define the conditional mean 14 = |2 [Hi-1]. and define the conditional cumulant generating function of the centered random variable [Z /4] by (A) == log Fleex(A[ZZ [1]) Then, for a process (M,())) defined as
(A) = exp Σ AlZ; - pel - s2(aas. }
we can prove the following properties.
Lemma 13. (A) is martingale with respect to the filtration (Hu) and E[M, for any X.
Proof. By definition, we have
(A) E[exp(M[Z -m1] (11()))1
Then, for any 2,
EEM, exp (1 [n]] - (A)31/77 Mn (1 - pn]] th (n)())HHmmm1]]
MA-1(A),,
since M, Mn-1(A) is a measurable function of the filtration Hn- Lemma 14. For all x 2 0 and À 2 0,
P
XZ < x + Σ
Duu + (x(a
EVNN 21-62.
1=1
Proof. For any X, (A) is martingale with respect (Hn)eN and [XM, = by Lemma 13 For arbitrary æ 2 0, define T2 = in 2 Mn (A) 2 2} and note that To is stopping time corresponding to the first time M, crosses the boundary Since 7 is stopping time with respect to (Hn)EEN, we have E[M = 1. Then, by Markov's inequality
rP(M Am (2) 2 2) S REMM,AAn(M =1
Noting that the event (M, An (A) 2 x = UK (Ma(A) 2 I}, we have
P ((M())2)) s
_
1
Taking the limit as n co, and applying monotone convergence theorem shows that
x P
(IM(
22

---

Consequently, we can write
8 U(MA(N)2 sea
Then, by definition of M&(A), conclude
A|z 41] 22(2)2 20) 2) 50²
P
U
Σ
1=
23


Reviews:
[{"review_id": "1NanBixu67", "reviewer": "Reviewer_ABaL", "summary": "This paper addresses the problem of online pricing in multi-user multi-item markets. The main objective is to maximize revenue by selling multiple items to multiple users in each round. The paper proposes algorithms that efficiently offer and price items while learning user valuations from accept/reject feedback. It considers three user valuation models and provides algorithms with nearly-optimal revenue regret guarantees. Additionally, the paper introduces a problem-dependent load parameter and designs regret-optimal algorithms for different market settings. Overall, the paper makes contributions in terms of user valuation models, load parameter analysis, and algorithm design, being the first to address this problem.", "questions": "Please refer to weaknesses 1, 2, and 3", "limitations": "The paper presents several limitations that could be addressed in future work. Firstly, the assumption that each item is offered to only one user during each round may not reflect realistic settings where multiple users may have overlapping preferences for the same item. Secondly, the paper does not address practical considerations such as privacy concerns, fairness considerations, or strategic user behavior. Lastly, the exploration of different market settings is limited, and it would be interesting to analyze the performance of the proposed algorithms in diverse market scenarios. Addressing these limitations would provide a more comprehensive understanding of the applicability and robustness of the algorithms.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper introduces a novel problem of online pricing in multi-user multi-item markets and addresses the specific challenge of maximizing revenue by selling multiple items to multiple users in each round. The quality of the paper is commendable, with a comprehensive analysis of different user valuation models, well-explained methodology, and rigorously analyzed algorithms. The paper is also clearly written and well-structured, making it easy for readers to follow the flow of ideas. Overall, the paper demonstrates originality in problem formulation, high-quality research methodology, clear presentation of ideas, and significant contributions to the field.", "weaknesses": "1.\tThe paper makes a simplifying assumption that each item is offered to only one user during each round. However, this assumption may not capture the realistic settings in which multiple users may have overlapping preferences for the same item and providers may have incentives to offer the same item to multiple users to increase their revenue.\n2.\tThe paper does not investigate the scalability of the proposed algorithms. It would be important to evaluate how the algorithms scale with respect to the number of users, items, and rounds. This evaluation would reveal the computational complexity and resource requirements of the algorithms in large-scale multi-user multi-item markets.\n3.\tThe paper does not discuss practical considerations that may arise in real-world implementations, such as privacy concerns, fairness considerations, or strategic user behavior. It would be beneficial to address these practical considerations and discuss how the proposed algorithms can cope with such challenges or potential extensions to handle them.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and questions. Please find our responses to the questions below:\n\n* Our framework can be readily extended to capture settings in which multiple users are offered the same item. We could achieve this by replicating each item according to its number of available copies. Note that this would correspond to an increase in the number of items as we will need to count each copy as a separate item. For all three valuation models, the corresponding algorithms would achieve regret upper bounds that hold with this modification to the number of items. To not complicate the market model and its analysis in this work, we only consider the case we are given a single copy of each item. \\\nOn the other hand, another possibility is to offer an item to more users than the number of copies we have. However, this also brings with it the risk of demand exceeding capacity. If we want to allow algorithms that take such risks, we would need to (1) estimate the chances of overselling and (2) make quantifying assumptions about the consequences of not being able to satisfy users' requests. We agree that relaxing this assumption is an intriguing and important area for future work, and we believe that the current work serves as a foundation for exploring this topic.\n\n* Based on your comments, we agree to include a discussion on the computational complexity and resource requirements of the algorithms. The integer linear program in (7) can be written as an instance of maximum weight bipartite matching. Then, using a variant of the Hungarian algorithm for unbalanced bipartite graphs (Ramshaw and Tarjan, 2012), this problem can be solved in space $O(NM)$ and time $O(NML)$ in the worst case. As this result shows, for a fixed number of items, space and time complexities both have a linear dependency on the number of users. \\\n**Details of the construction:** In this graph, we represent each user $u$ with $d_u^t$ left nodes and we represent each endowed item $i$ with a right node. Then, we construct the complete weighted bipartite graph where the weight of an edge between a node for user $u$ and a node for item $i$ is given as $v_{ui}$. In total, this graph has $D_t$ left vertices, $E_t$ right vertices, and $D_t E_t$ weighted edges where $D_t$ and $E_t$ correspond to total demand and endowment at time $t$ (as given in Definition 2). Since we can upper bound $D_t \\leq N$, $E_t \\leq M$, and $\\min{D_t, E_t} \\leq L$, the results in the previous paragraph follow. \\\n**Reference:** Ramshaw, L., & Tarjan, R. E. (2012). On Minimum-Cost Assignments in Unbalanced Bipartite Graphs.\n\n* We recognize the importance of the practical considerations you've emphasized, such as privacy concerns, fairness, and strategic user behavior, within real-world applications. While these aspects extend beyond the paper's present focus, we intend to highlight their significance in our revised manuscript. There is an opportunity to delve into these areas more extensively in subsequent research, building on the groundwork we've established. \\\nTo further address the inquiry regarding strategic user behavior, we wish to offer the following insight: If each user interacts with the system only once, it would be in their best interest to behave myopically. In particular, our frameworks of fixed valuations and random valuations can be used to model settings where each user interacts with the system only once (at a single time step) if each user is associated with a type that determines their valuations. In this case, the set $\\mathcal{N}$ corresponds to the set of all user types and each demand parameter $d^t_u$ represents the total demand of users of type $u$ in round $t$. Under the fixed valuations model, all users of type $u$ have valuation $v_{ui}^t = v_{ui}$ for item $i$ at all rounds $t$. Under the random valuations model, each user of type $u$ has a random valuation with distribution $F_{ui}$ for item $i$ independently for each user at each time $t$. Since at most one user receives any item $i$ in any round, it is sufficient to consider a single random valuation $v_{ui}^t$ for each type $u$ and item $i$ at time $t$. Crucially, since each user interacts with the system only once, it is in each user’s best interest to behave myopically."}, {"review_id": "nM5zpABvYv", "reviewer": "Reviewer_Hkdu", "summary": "The paper proposes algorithms for optimizing the sale of multiple goods to multiple users, taking into account their time-varying valuations throughout repeated rounds. These algorithms efficiently learn from users' accept or reject feedback and utilize this information to make optimal offers and prices based on three user valuations: fixed valuation, random experience, and random valuation. To evaluate the effectiveness of the proposed algorithms, the paper provides revenue regret guarantees. Notably, the significant contribution of this paper lies in the introduction of the concept of user's random experience as a crucial valuation to consider in dynamic pricing algorithms.", "questions": "In line 56, why are the algorithms focused on offering each item to only one user during each round? The framework of \"multi-user multi-item\" proposed in the paper suggests that interactions happen between multiple users and multiple items over repeated rounds, indicating a dynamic market setting. While the constraint of offering one item to one user during each round simplifies the problem, it may not fully reflect the dynamic market. Therefore, I would like to see that the algorithms can be focused on more items to one user, one item to more users, or more items to more users, which aligns better with the multi-user multi-item market framework proposed in the paper. \nIn Section 5, why are two different datasets used for numerical experiments? Figure 3 is based on 20 sets of experiments with N=150 users and M=100 items, while Figure 4 is based on 5 sets of experiments with N=30 users and M=20 items.\n", "limitations": "No", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses the problem of revenue maximization in a dynamic market with time-varying valuations. Specifically, the paper introduces the concept of \"random experience\", which is a novel and unexplored idea in prior literature.\nThe paper offers a rigorous theoretical analysis of the proposed algorithms and assesses their effectiveness and efficiency in practice by evaluating nearly-optimal revenue regret guarantees for each algorithm.\nThe paper exhibits a well-organized structure, presenting the problem formulation, proposed algorithms, theoretical analysis, and experimental results in a clear and coherent manner.\n", "weaknesses": "Some statements are general and lack support or explicit example, such as in line 17, which states, “The ability to design algorithms that can achieve the optimal sale of goods to multiple users having time-varying valuations for each of the goods is both timely and relevant, given the explosion in the use of data in large-scale systems.” How does the author come to this statement? I would suggest briefly citing more literature to support the argument.\nFigure 1 is unclear, and it is challenging to understand how the provider learns user valuation from the current depiction. Additionally, the meaning of the gray user representative is not apparent. To improve the figure's clarity, I recommend providing a more detailed description.\nThe paper may lack comparisons with relevant literature. The author mentions that fixed valuation and random valuation have been used as standard models for dynamic pricing in previous research. Therefore, I would suggest that the author could further elaborate on and compare this paper’s results with previous work. In comparison with previous works, the author can emphasize the advantages and differences of their proposed method, such as differences in experimental design or interpretation of results. This will help clarify the innovation and contribution of the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and questions. Please find our responses to the questions below:\n\n* As discussed in our related works section, dynamic pricing literature has only considered settings where a single user interacts with the provider per time step. Therefore, even if their valuation models are similar, those algorithms and theoretical results are not directly comparable with ours. To best position our work within the literature, the related works section includes bodies of works that are most relevant to the framework that we are proposing. Throughout that section, we explain the similarities and differences between our work and cited papers. \\\nThough it’s not a direct comparison, it is possible to compare our work with Kleinberg and Leighton [3] since our results can be interpreted as a generalization of their theoretical findings. This is because their market model is a special case of ours where the number of users is $N=1$, the number of items is $M=1$, and the load is $L=1$. For fixed valuations, we achieve almost optimal regret of order $O(NM\\log\\log(LT))$ which reduces to $O(\\log \\log T)$ in the single-user single-item case. Similarly, for the random valuations model, we achieve regret of order $O(\\sqrt{NMLT})$ which reduces to $O(\\sqrt{T})$ in the single-user single-item case. For both cases, these results match the results of Kleinberg and Leighton [3].\n\n* We do have multiple active users in each round and we allocate multiple items across them simultaneously. Our assumption is only about not assigning the same item to multiple users in any round. Nevertheless, our framework can also be readily extended to capture settings in which multiple users are offered the same item. We could achieve this by replicating each item according to its number of available copies. Note that this would correspond to an increase in the number of items as we will need to count each copy as a separate item. For all three valuation models, the corresponding algorithms would achieve regret upper bounds that hold with this modification to the number of items. To not complicate the market model and its analysis in this work, we only consider the case we are given a single copy of each item.\n\n* We chose relatively large numbers of users and items for experiments in Figure 3 to show that our algorithms can achieve diminishing regret over time for larger-scale problems. On the other hand, for the experiments in Figure 4, we opted for a smaller problem because we needed to run many more experiments corresponding to each different time horizon. For instance, we run 20 experiments with $T=2^{10}$ for the first plot in Figure 3 while we run 50 experiments with up to $T=2^{14}$ for the first plot in Figure 4. \\\nNevertheless, we have improved the time complexity of our simulations using a maximum weight matching algorithm instead of an LP solver as suggested by reviewers 2rbX and ABaL. Therefore, we are now able to run the experiments in a shorter time and generate a figure showing “regret as a function of time horizon T under different valuation models with N = 150 users and M = 100 items”. (Please see the pdf document in our global response for this figure.) In our revised manuscript, we are committed to repeating this experiment across multiple runs and replacing Figure 4 with those results.\n\n* We appreciate your feedback regarding the motivating statements and their need for explicit support. We are fully committed to addressing this concern by incorporating relevant citations that strengthen the rationale behind these statements. This effort will significantly enhance the credibility and context of our arguments.\n\n* In relation to Figure 1, we recognize your observation regarding its clarity. We deeply value your input and are committed to incorporating your feedback as we revise the figure. This will involve providing a more detailed description that better elucidates the process and ensures a clearer understanding for our readers.\n"}, {"review_id": "liTkpAaE71", "reviewer": "Reviewer_PhX7", "summary": "The paper studies the problem of dynamic pricing in which multiple items are offered to multiple users at each round. Authors propose a novel algorithm for maximizing revenue under three user valuation models: fixed valuations,  random experiences and random valuations. Authors provide theoretical guarantees and provide simulation results supporting the theoretical claims.", "questions": "1.) Authors assume that items that are not sold in one round can not be stored to be sold in future rounds. What are technical challenges associated with relaxing this assumption?\n\n2.) Can this results be extended to the case where users only accept an item if its price is lower than the valuation by some ", "limitations": "The paper does not discuss the limitations of the method and potential societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Strengths**\n\n1.) The paper is well written and easy to follow. Authors motivate the problem formulation well.\n\n2.) Authors provide a detailed related work section and contributions well positioned in the relevant literature.\n\n3.) The theoretical results appear to be sound and the paper also provide novel algorithmic contributions.\n", "weaknesses": "**Weaknesses**\n\n1.) The main weakness of the paper is lack of comparison with existing methods. Authors do not provide a discussion comparing their theoretical or simulation results with existing work.\n\n2.) Including a proof sketch in the main paper will improve the quality of the paper.\n\n3.) Including additional simulation results will improve the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and questions. Please find our responses to the questions below:\n\n* As discussed in our related works section, dynamic pricing literature has only considered settings where a single user interacts with the provider per time step. Therefore, even if their valuation models are similar, those theoretical or empirical results are not directly comparable with ours. To best position our work within the literature, in our related works section, we include bodies of works that are most relevant to the framework that we are proposing. Throughout that section, we explain the similarities and differences between our work and cited papers. \\\nThough it’s not a direct comparison, it is possible to compare our work with Kleinberg and Leighton [3] since our results can be interpreted as a generalization of their theoretical findings. This is because their market model is a special case of ours where the number of users is $N=1$, the number of items is $M=1$, and the load is $L=1$. For fixed valuations, we achieve almost optimal regret of order $O(NM\\log\\log(LT))$ which reduces to $O(\\log \\log T)$ in the single-user single-item case. Similarly, for the random valuations model, we achieve regret of order $O(\\sqrt{NMLT})$ which reduces to $O(\\sqrt{T})$ in the single-user single-item case. For both cases, these results match the results of Kleinberg and Leighton [3].\n\n* We provide discussions on the reasoning behind our allocation and pricing mechanisms throughout Sections 4.1, 4.2, and 4.3 within the limitations of space constraints. Based on your comment, we will extend these discussions to speak about the high-level details of the proof as well.\n\n* In our current framework, the demand and endowment information for time $t$ is only made available to the provider at time $t$. However, if the provider can store the items to sell in future rounds, it also needs to have some idea about the demand for future rounds to be able to determine how much it needs to store. To formulate a no-regret algorithm under this scenario, one would need to analyze the tradeoff between offering available items to learn user valuations faster and storing the items to sell in future rounds at possibly higher prices. We believe that the combination of learning user preferences and estimating future demand/endowment is an important direction and we believe that the current work serves as a foundation for exploring this topic. \n\n* If we were to consider a case where users only accept an item if its price is lower than the valuation by some fixed (but unknown) amount $c_{ui}$, then our results would be still valid for all valuation models. Letting $b_{ui}^t = v_{ui}^t - c_{ui}$ to be the acceptance/rejection threshold and replacing $v_{ui}^t$ with $b_{ui}^t$ in the definitions of optimality and regret, all three algorithms would achieve the same order of regret without any modification. "}, {"review_id": "9QyGEz5aaD", "reviewer": "Reviewer_2rbX", "summary": "The paper considers the online pricing problem where there are several users and items. Each user has a (private) valuation for each item and a (public) upper bound for the number of items desired, both of which could vary at different rounds. The provider has an available item set at each round, and the goal is to distribute them to the users such that the total revenue is maximized. The paper considers three settings for the uses' valuation functions: (1) fixed valuations, (2) random experiences, and (3) random valuations. For each setting, the corresponding algorithm is proposed and analyzed, along the theoretical lower bound. For the first two settings, the basic algorithmic idea is trying to learn an accurate valuation interval for each item-user pair, and then computing the assignment and the prices according to the estimated intervals; while for the last setting, the authors quantize the set of possible prices and then borrow the idea from the multi-armed bandit problem to give an algorithm. Finally, the proposed algorithms are evaluated empirically.", "questions": "Minor comments:\n\n- It might be better to point out that $\\lor$ and $\\land$ represent \"taking max\" and \"taking min\" respectively in the paper.\n\n- In the statement of algorithm 3, $n_{uik}$ is initialized by 0, but in the first iteration, we compute the term $\\sqrt{8\\log (NMKT) / n_{uik}}$.", "limitations": "I didn't see any negative societal impact of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper makes theoretical contributions. The multi-user multi-item online pricing problem introduced makes sense. The authors consider different valuation settings of this problem, and obtain small gaps between the upper bounds and the lower bounds. The analysis is non-trival.\n\n- The paper is well-written. For each algorithm, the authors always provide the basic algorithmic intuition, which can help the reader understand the algorithm. ", "weaknesses": "- The discussion of the algorithms' running time is missing. Further, in the current statement, the algorithms need to solve linear programs at each round, but essentially, this can be formulated into a bipartite matching instance and thus, the classical matching algorithm can be applied and help to improve the running time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and questions. Please find our responses to the questions below:\n\n* Based on your comments, we agree to include a discussion on the computational complexity and resource requirements of the algorithms. As you noted, the integer linear program in (7) can be written as an instance of maximum weight bipartite matching. Then, using a variant of the Hungarian algorithm for unbalanced bipartite graphs (Ramshaw and Tarjan, 2012), this problem can be solved in space $O(NM)$ and time $O(NML)$ in the worst case. As this result shows, for a fixed number of items, space and time complexities both have a linear dependency on the number of users.\\\n**Details of the construction:** In this graph, we represent each user $u$ with $d_u^t$ left nodes and we represent each endowed item $i$ with a right node. Then, we construct the complete weighted bipartite graph where the weight of an edge between a node for user $u$ and a node for item $i$ is given as $v_{ui}$. In total, this graph has $D_t$ left vertices, $E_t$ right vertices, and $D_t E_t$ weighted edges where $D_t$ and $E_t$ correspond to total demand and endowment at time $t$ (as given in Definition 2). Since we can upper bound $D_t \\leq N$, $E_t \\leq M$, and $\\min \\\\{D_t, E_t\\\\} \\leq L$, the results in the previous paragraph follow.\\\n**Reference:** Ramshaw, L., & Tarjan, R. E. (2012). On Minimum-Cost Assignments in Unbalanced Bipartite Graphs.\n* We agree that it will be better to clearly define notations for “taking min” and “taking max” in our notation section at line 120.\n* The division by zero in Algorithm 3 can be interpreted as resulting in infinity. Since we set $b_{uik}$ as the minimum of $( \\psi_{uik} + \\sqrt{8 \\log (NMKT)/n_{uik}} )$ and $1$, we always set $b_{uik} = 1$ when $n_{uik} = 0$. For clarity, we will include a footnote that briefly explains how to interpret $\\sqrt{8 \\log (NMKT)/n_{uik}}$ when $n_{uik} = 0$.\n"}, {"review_id": "3Hu0JOm7x8", "reviewer": "Reviewer_bZxp", "summary": "The paper proposes online pricing and allocation strategies for multi-user multi-markets model under three different valuation models.\n\nThe main contribution is to extend dynamic pricing strategies from the literature to the case of more than one item and more than one user.\n\nThe setting goes as follows:\n- At every iteration, each user $u$ presents a maximum demand for items $d_u^t$, that is observed.\n- the algorithm allocates items and prices.\n- a user accepts the items for which his valuation is higher than the offered price, accepting at most $d_u^t$ items.\n\nThe study the fixed valuation model in which the valuation of users for each item is fixed and deterministic, the random experience model, where a user's valuation for an item is the mean of his past experiences, and the random valuation model where the valuations are drawn from fixed but unknown distributions.\n\nPresented algorithms construct confidence intervals for the user-item valuations. At every iteration, the items are allocated according to the so-called optimism principle, meaning the optimal allocation for the upper bounds on the user-item valuations is chosen.\n\nThe price set for the item depends on the valuation model.", "questions": "Overall, the paper has interesting elements, but a good discussion on the dependence of the problem in the parameter L, M and N is missing, as this is the main contribution of the paper. \n\nPrecise references to where previously existing methods were used are missing. Adding this would help the reader understand the contribution of the paper better.\n\nOn a side note, the assumption that $d_u^t$ is observed seems rather strong, if the authors have a good argument as to why it is necessary (or not), it would be interesting to add.\n", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper is clear and the algorithms well presented for the most part. The study of larger markets than one item/one user certainly is interesting and relevant for applications.", "weaknesses": "My main criticism concerns the way the paper is written. A lot of emphasis is put on the pricing strategies. However, at least two of the method for pricing, for the fixed valuation model and the random valuation model, already exist in the literature (reference 3) and this is not discussed in the paper.\nMore precisely, the methods of geometrically decreasing intervals and discretization of the price interval are exactly the methods used in ref 3.\n\nThere are some unclarities in the proofs, as listed below.\n\n1. The proof of Theorem 1 is not clear at all. Parameter $\\epsilon$ is set to $1/LT$ without explanation. This can only be done because exploration stops when the interval for the valuation becomes small enough. But although it appears in the pseudo-code of the algorithm, it is not evoked in the main text nor in the proof. However, this feature of stopping exploration after some time is crucial in avoiding linear regret. This is clear for a reader familiar with ref 3, but I do not believe it would be otherwise.\n\n2. In Appendix C, $y_ui$ is used without introduction. In figure 2, notations are also used before they are introduced.\n\n3. Line 494, the lists are defined too informally.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback and thoughtful questions.\n\nIn this paper, our main contribution is the analysis of revenue-maximizing algorithms that allocate and price multiple items to multiple users. As stated in our related work section, Kleinberg and Leighton [3] developed a widely-appreciated framework to maximize revenue from selling copies of a single good to sequentially arriving users. Their scenario corresponds to a special case of our problem where the provider interacts with only one user at each round and sells a single type of item. In contrast to this setting, a provider that simultaneously interacts with multiple users faces additional challenges in offering and pricing the items; such challenges are addressed in our work. \n\nThe hardest challenge is to decide on simultaneous allocation and pricing actions that can balance exploration with exploitation. At a high level, we tackle this challenge by combining ideas from the dynamic pricing and combinatorial bandits literature. The offers are chosen using the OFU principle as it is often done in combinatorial bandits literature. On the other hand, our solutions for pricing the items are based on the foundational techniques presented in [3]. Regarding related comments, we will provide more precise references to [3] in Sections 4.1 and 4.3 with the goal of improving clarity.\n\nPlease find our responses to your other questions below:\n* In Section 1.1 and in lines 166-168, we already have some discussion relating to the problem's dependency on the parameters $N$, $M$, and $L$. However, in response to related comments, we want to expand on that discussion by including the following paragraphs. \\\nUnder all three valuation models, we observe that optimal regret rates depend on two central quantities: $NM$ and $LT$. The $NM$ term in these expressions corresponds to the number of user-item pairs for which we need to learn the valuations. On the other hand, the $LT$ factor in the optimal regret rate corresponds to the maximum total number of offers that we make. \\\nFor the specific case of the random valuations model, it is possible to draw further conclusions about the complexity of the problem. Recall that we achieve an almost optimal regret rate of $\\widetilde{O}(\\sqrt{NMLT})$. In comparison, consider a social-welfare maximization problem where we can make real-valued observations of the random valuations $v_{ui}^t$ for each allocated user-item pair and our goal is to maximize the sum of expected valuations for our allocations. As this problem can be easily modeled as a semi-bandit problem with $NM$ arms of which at most $L$ can be chosen simultaneously at each of the $T$ rounds, the optimum regret rate would be $O(\\sqrt{NMLT})$ (Kveton et al., 2015). Hence, we can conclude that our revenue maximization problem with accept/reject feedback is no harder than the social welfare maximization problem with real-valued random reward feedback.\n* Our focus is on the problem of allocation and pricing to maximize long-term revenue when user preferences are unknown. Applications relevant to our study include online delivery, hotel bookings, ride-shares, etc., where users come to the platform in search of products or services. In these examples, we can readily consider that users demand only one item ($d^t_u = 1$) when they are active and they have no demand ($d^t_u = 0$) when inactive. While this assumption might be too strong for some applications, our work serves as a valuable starting point for investigation.\nPlease find our responses regarding other unclarities below:\n* We will include the following paragraph after line 227 to elaborate on the need to stop exploration.\\\nDue to this update rule for $\\beta_{ui}$, the length of the corresponding search interval $b_{ui} - a_{ui}$ is at most $\\sqrt{\\beta_{ui}}$ at any given time. Let an epoch for a user-item pair $(u, i)$ refer to the set of all time steps in which user $u$ is offered item $i$ using the same price increment $\\beta_{ui}$. Since the algorithm operates by offering item $i$ to user $u$ at prices increasing by $\\beta_{ui}$, the number of queries in an epoch can be anywhere between 1 and $1/\\sqrt{\\beta_{ui}}$. In the proof of Theorem 1, we show that the regret we incur over a single epoch for a user-item pair $(u, i)$ is $O(1)$, and the number of exploratory epochs can be as large as $T$ in the worst case. Therefore, continuing to explore indefinitely would result in linear regret. To avoid this issue, the algorithm should stop exploration after achieving a certain level of precision and offer item $i$ to user $u$ at the maximum price that is certainly acceptable, namely $a_{ui}$.\n\n* To address the weakness (2), we will use $v_{ui}^t$ instead of $y_{ui}$ throughout the proof. \n\n* Regarding weakness (3), we will revise the rest of the proof after line 494 as follows. \\\n\\begin{align}\n\\sum_{u\\in\\mathcal{N}}\\sum_{i \\in \\mathcal{I}}\\sum_{t:x_{ui}^t = 1}\\sqrt{\\frac{1}{m_{ui}^t}}\\leq \\sum_{u\\in\\mathcal{N}}\\sum_{i\\in\\mathcal{I}}\\left(\\sum_{t:x_{ui}^t=1\\text{ and }\\nexists j\\in\\mathbb{N}:n_{ui}^t=2^j}\\sqrt{\\frac{1}{m_{ui}^t}}+\\sum_{t:x_{ui}^t=1\\text{ and }\\exists j\\in\\mathbb{N}:n_{ui}^t=2^j}\\sqrt{\\frac{1}{m_{ui}^t}}\\right)\\leq\\sum_{u\\in\\mathcal{N}}\\sum_{i\\in\\mathcal{I}}\\left(2\\sqrt{m_{ui}^T}+\\log T\\right)\\end{align}\nwhere we upper bound the first term using $\\sum_{k=1}^{n}\\frac{1}{\\sqrt{k}}\\leq\\int_{0}^{n}\\frac{\\mathrm{d}x}{\\sqrt{x}}=2\\sqrt{n}$ and the second term by noting that it can have at most $\\log T$ terms. Also, note that the total number of offers over all time intervals is upper bounded by $\\sum_{u\\in\\mathcal{N}}\\sum_{i\\in\\mathcal{I}}m_{ui}^T\\leq LT$. Then, using the Cauchy-Schwartz inequality,\n\\begin{align}\n\\sum_{u\\in\\mathcal{N}}\\sum_{i \\in \\mathcal{I}}\\sum_{t:x_{ui}^t = 1}\\sqrt{\\frac{1}{m_{ui}^t}}\\leq 2\\sqrt{NM\\sum_{u\\in\\mathcal{N}}\\sum_{i\\in\\mathcal{I}}m_{ui}^T}+NM\\log T\\leq O(\\sqrt{NMLT}+NM\\log T).\n\\end{align}\nPutting all together, we conclude the proof of the lemma.\n"}]

Author rebuttal:
We thank all the reviewers for their constructive feedback and thoughtful questions. Please see our separate responses below each review. 

In response to a question from reviewer Hkdu regarding the experiments, we provide the new results in the PDF file. In our initial submission, Figure 4 was generated for experiments with $N = 30$ users and $M = 20$ items. Now, we have improved the time complexity of our simulations using a maximum weight matching algorithm instead of an LP solver as suggested by reviewers 2rbX and ABaL. Therefore, we are now able to run the experiments in a shorter time and generate results for larger experiments. In our revised manuscript, we are committed to repeating this experiment across multiple runs and replacing Figure 4 with those results.

Meta-review: This paper presents an online pricing framework for multi-user multi-item markets. Online algorithms to efficiently offer and price items while learning user valuations from accept/reject feedback are proposed and analyzed. We hope the reviews and feedbacks during the discussions could be helpful for the authors to prepare the final version of this paper.
Decision: Accept (poster)