In a Fisher market, agents (users) spend a budget of (artificial) currency to buy goods that maximize their utilities while a central planner sets prices on capacity-constrained goods such that the market clears. However, the efficacy of pricing schemes in achieving an equilibrium outcome in Fisher markets typically relies on complete knowledge of users' budgets and utility functions and requires that transactions happen in a static market wherein all users are present simultaneously.

Motivated by these practical considerations, in this work, we study an online variant of Fisher markets, wherein budget-constrained users with privately known utility and budget parameters, drawn i.i.d. from a distribution $\D$, enter the market sequentially. In this setting, we develop an algorithm that adjusts prices solely based on observations of user consumption, i.e., revealed preference feedback, and achieves a regret and capacity violation of $O(\sqrt{n})$, where $n$ is the number of users and the good capacities scale as $O(n)$. Here, our regret measure is the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an offline oracle with complete information on users' budgets and utilities. To establish the efficacy of our approach, we show that any uniform (static) pricing algorithm, including one that sets expected equilibrium prices with complete knowledge of the distribution $\D$, cannot achieve both a regret and constraint violation of less than $\Omega(\sqrt{n})$. While our revealed preference algorithm requires no knowledge of the distribution $\D$, we show that if $\D$ is known, then an adaptive variant of expected equilibrium pricing achieves $O(\log(n))$ regret and constant capacity violation for discrete distributions. Finally, we present numerical experiments to demonstrate the performance of our revealed preference algorithm relative to several benchmarks.

§ INTRODUCTION

In a Fisher market, one of the most fundamental models for resource allocation <cit.>, agents (users) spend a budget of (artificial) currency to purchase goods that maximize their utilities while a central planner sets prices on capacity-constrained goods. Since Fisher introduced his seminal framework, a focal point of the Fisher market literature has been in developing methods to compute market equilibria[A market equilibrium corresponds to a (uniform) price vector (for all users) and an allocation of goods to users such that all goods are sold, and users obtain a utility-maximizing bundle of goods that is affordable under the set prices. We refer to Section <ref> for a formal definition of an equilibrium price vector.]. Most notably, in a seminal work, Eisenberg and Gale <cit.> developed a convex program that maximizes the (weighted) Nash social welfare objective[In the special that all buyers have the same budgets, the market equilibrium outcome maximizes the (unweighted) Nash social welfare objective and is known as a competitive equilibrium from equal incomes (CEEI) <cit.>.], i.e., the (weighted) geometric mean of all users' utilities <cit.>, to compute equilibrium prices and the corresponding allocations for a broad range of utility functions. Despite the many desirable properties of the Eisenberg-Gale program[We refer to Section <ref> for a detailed discussion of the properties of the optimal allocations of the Eisenberg-Gale program.] <cit.>, including it being polynomial time solvable <cit.>, computing equilibrium prices via a centralized optimization problem relies on complete information on users' utilities and budgets, which are typically unavailable in practice.

As a result, there has been a growing interest in developing distributed approaches for market equilibrium computation, e.g., tatonnement <cit.>, proportional response <cit.>, primal-dual <cit.>, alternating direction method <cit.>, and auction-based <cit.> approaches. In the distributed setting, the central planner typically updates the prices of the goods in the market until convergence to market equilibria (under certain, often mild, conditions). To enable the convergence of these algorithms to equilibrium prices, existing distributed approaches for Fisher markets, e.g., tatonnement or proportional response approaches, typically involve a simulated setting wherein all users repeatedly interact in a static market. In practice, however, users generally do not repeatedly interact in the market to enable the central planner to learn equilibrium prices and instead tend to arrive into the market sequentially, as users are often not all present at once.

Motivated by the aforementioned practical limitations of centralized and distributed approaches for Fisher markets, in this work, we study a generalization of Fisher markets to the setting of online user arrival wherein users with privately known utilities and budgets arrive sequentially. As opposed to centralized allocation methods, we develop a novel algorithmic approach to adjust prices in the market based solely on users' revealed preferences, i.e., observations of the bundle of goods users purchase given the set prices. Furthermore, in contrast to traditional distributed approaches for Fisher markets that involve a simulated setting with repeated user interactions, our work considers a real market setting wherein users arrive sequentially over time rather than repeatedly interacting in the market. In the online and incomplete information setting studied in this work, we also establish the performance limitations of uniform (static) pricing, which has been the holy grail in the equilibrium computation literature for Fisher markets[An equilibrium price vector in classical Fisher markets is by definition a single (uniform) price vector that applies to all users in the market.]. As a result, our work points toward developing novel tools and methods to more deeply understand market equilibria in online variants of Fisher markets and, more generally, highlights the benefit of designing adaptive mechanisms for online resource allocation <cit.>.

§.§ Our Contributions

In this work, we study an online variant of Fisher markets wherein budget-constrained users, with privately known utility and budget parameters, arrive into the market sequentially. In particular, we focus on the setting when users have linear utilities and their budget and utility parameters are independently and identically (i.i.d.) distributed according to some probability distribution $\D$. Since traditional methods, e.g., solving the Eisenberg-Gale convex program <cit.>, are not amenable to computing equilibria in this setting, we consider the problem of learning prices online to minimize two performance measures: regret and constraint violation. In this work, regret refers to the optimality gap in the objective of the Eisenberg-Gale convex program between the online allocation and that of an offline oracle with complete information on users' budget and utility parameters, and constraint violation represents the norm of the excess demand for goods beyond their capacity. For a detailed discussion on these performance measures, we refer to Section <ref>.

In this online incomplete information setting, we first study the performance limitations of uniform (static) pricing algorithms, wherein the same price vector $\p$ applies to all users. For any static pricing algorithm, we establish that its expected regret or constraint violation must be $\Omega(\sqrt{n})$, where $n$ is the number of arriving users and the capacities of the goods scale as $O(n)$. As an immediate consequence of this result, even an algorithm that sets expected equilibrium prices with complete knowledge of the distribution $\D$ must have a regret or constraint violation of $\Omega(\sqrt{n})$, which thus serves as a performance benchmark for an algorithm for online Fisher markets.

The performance limitations of static pricing algorithms motivate the design of adaptive (dynamic) pricing algorithms for online Fisher markets. To this end, we first present an adaptive variant of expected equilibrium pricing that achieves an $O(\log(n))$ regret and a constant constraint violation, i.e., independent of the number of users $n$, when the distribution $\D$ is discrete. To establish the regret and constraint violation bound of this algorithm, we leverage and combine techniques from parametric optimization, convex programming duality, and concentration inequalities.

Since the probability distribution $\D$, in general, may not be known (and the distribution may be continuous rather than discrete), we develop a simple yet effective approach to set prices that only relies on users' revealed preferences, i.e., past observations of user consumption. This algorithmic approach not only preserves user privacy as it requires no information on users' utility and budget parameters but also has a computationally efficient price update step, making it practically implementable. Furthermore, under a mild assumption on the distribution $\D$, the revealed preference algorithm achieves an expected regret and constraint violation of $O(\sqrt{n})$ when the good capacities scale with the number of users. That is, our revealed preference algorithm achieves an expected regret and constraint violation (up to constants) that are no more than that of a static expected equilibrium pricing approach (and that of any static pricing algorithm) with complete knowledge of the distribution $\D$. To establish the regret and constraint violation bounds of our revealed preference algorithm, we develop a novel potential function argument that leverages the structural properties of Fisher markets and the price update step of our proposed algorithm.

Finally, we evaluate the performance of our revealed preference algorithm through numerical experiments. Our results validate our theoretical guarantees and highlight a fundamental trade-off between regret and constraint violation, which we observe when comparing our algorithm's performance to two benchmarks with additional information on users' utility and budget parameters.
We also evaluate the performance of our revealed preference algorithm through a numerical comparison between our algorithm's performance to two benchmarks with additional information on users' utility and budget parameters. Our results validate our theoretical guarantees and highlight a fundamental trade-off between regret and constraint violation.

Organization: This paper is organized as follows. Section <ref> reviews related literature. We then present our model and performance measures to evaluate the efficacy of an algorithm for online Fisher markets in Section <ref>. Then, in Section <ref>, we study the performance limitations of static pricing algorithms and develop an adaptive pricing algorithm that outperforms its static pricing counterpart. Next, we introduce our revealed preference algorithm and its regret and constraint violation bounds in Section <ref>. Finally, we conclude the paper and provide directions for future work in Section <ref>.

In the appendix, we provide proofs omitted from the
main text and discuss additional numerical results to further demonstrate the efficacy of the algorithms developed in this work.

§ LITERATURE REVIEW

Online resource allocation problems have been widely studied in operations research and computer science, having found applications in domains including online advertising <cit.>, allocation of food donations to food banks <cit.>, and rationing of social goods <cit.> among others. One of the most well-studied classes of online allocation problems is online linear programming (OLP), wherein columns of the constraint matrix and coefficients of the linear objective are revealed sequentially to an algorithm designer. While the traditional approach to OLP problems has been to develop guarantees for adversarial inputs <cit.>, the often exceedingly pessimistic worst-case guarantees have prompted the study of beyond worst-case methods <cit.> for such problems <cit.>.

Beyond worst-case approaches for OLP problems have focused on designing algorithms under (i) the random permutation and (ii) the stochastic input models. In the random permutation model, the constraints and objective coefficients arrive according to a random permutation of an adversarially chosen input sequence. In this context, <cit.> develop a two-phase algorithm, which includes training the model on a small fraction of the input sequence and then using the learned parameters to make online decisions on the remaining input sequence. Contrastingly, in the stochastic input model, the input sequence is drawn i.i.d. from some potentially unknown probability distribution. In this setting, <cit.> investigate the convergence of the dual price vector and design algorithms using LP duality to obtain logarithmic regret bounds. Since the algorithms developed in <cit.> involve solving an LP at specified intervals, <cit.> developed a gradient descent-based algorithm wherein the dual prices are adjusted solely based on the allocation to users at each time step. More recently, <cit.> devised an adaptive allocation algorithm with a constant regret bound when the samples are drawn from a discrete probability distribution. As with some of these works, we develop algorithms for online Fisher markets under the stochastic input model; however, in contrast to these works that assume a linear objective, we develop regret guarantees for a non-linear concave objective function.

Since non-linear objectives tend to arise in many online resource allocation problems, there has been a growing interest in studying online convex optimization (OCO) <cit.>. In this context, <cit.> study a general class of OCO problems with concave objectives and convex constraints and develop dual-based algorithms with near-optimal regret guarantees under both the random permutation and stochastic input models. More recently, <cit.> developed an online mirror descent algorithm with sub-linear regret guarantees by ensuring that enough resources are remaining at the end of the time horizon. The mirror descent approach of <cit.> was later extended by <cit.> to a class of regularized objective functions. In line with these works, we also study an online resource allocation problem with a concave objective, which, in the Fisher market context, is the budget-weighted log utility objective <cit.>, i.e., the sum of the logarithm of the utilities of all users weighted by their budgets. However, unlike these works that assume non-negativity and boundedness of the concave objective, we make no such assumption since the Fisher social welfare objective we consider involves a logarithm, which can be both unbounded and non-negative.

As in our work that studies an online variant of Fisher markets, several other online variants of Fisher markets have also been considered in the literature. For instance, <cit.> study the setting when goods arrive sequentially and must be allocated irrevocably upon their arrival to a fixed set of users. While <cit.> investigate this repeated allocation setting in Fisher markets from a competitive analysis perspective, <cit.> studies this problem from a regret analysis lens and establishes a connection between this setting and first-price auctions.
In contrast to these works that focus on the repeated allocation setting wherein goods arrive online, we consider the setting wherein users enter the market sequentially and purchase a fixed set of limited resources.

In the context of online user arrival in Fisher markets, <cit.> studies the problem of allocating a fixed set of resources to a random number of users that arrive over multiple rounds. While we also consider the setting of online user arrival in Fisher markets, our work differs from that of <cit.> in several ways. First, <cit.> consider a setting where users belong to a finite set of types where all users have the same budgets. However, in this work, users' preferences can, in general, be drawn from a continuous probability distribution, i.e., the number of user types may not be finite, and users' budgets may not be equal. Next, we introduce and adopt different metrics to evaluate the performance of an algorithm as compared to that considered in <cit.>, and refer to Section <ref> for a detailed discussion of our chosen performance measures. Finally, as opposed to the two-phase algorithms that include a prediction and an optimization step proposed in <cit.>, we develop a dual-based algorithm that adjusts prices solely based on users' revealed preferences.

Our algorithmic approach to adjusting the prices of the goods using users' revealed preferences, i.e., observed user consumption information, is analogous to price update mechanisms that use information from interactions with earlier buyers to inform pricing decisions for future arriving buyers <cit.>. While our dual-based price update mechanism is akin to those used in prior work on revealed preferences <cit.>, our work considers a setting with budget-constrained users, unlike the quasi-linear utility setting studied in these works. Prior literature on revealed preference has also considered the setting of budget-constrained users <cit.>, as in this work. However, these works focus on the problem of learning the budgets and valuation functions of users that rationalize their observed buying behavior rather than designing algorithms with good performance using their revealed preferences, which is one of the main focuses of this work.

Since we focus on jointly optimizing regret and constraint violation, our work closely relates to the literature on online constrained convex optimization with long-term constraints <cit.>. However, compared to these works that focus on a regret measure defined based on the sub-optimality of an optimal static action in hindsight, we adopt a more powerful oracle model, wherein the oracle can vary its actions across time steps as in <cit.>. Even though our chosen regret metric is akin to the dynamic regret notions in these works, our work differs from <cit.> in several ways. First, unlike <cit.>, which consider a setting wherein the central planner observes a convex cost function after each user arrival, we study a revealed preference setting, wherein users' utility and budget parameters are private information. Next, as opposed to the gradient descent projection step used in the algorithms developed in <cit.>, we establish regret and constraint violation bounds for our revealed preference algorithm without projecting the price vector to the non-negative orthant. We do so by developing a novel potential function argument that relies on the specific structural properties of Fisher markets (see Section <ref> and Appendix <ref>). Finally, compared to <cit.>, we also consider the informational setting when the distribution $\D$ is discrete and known to the central planner and develop an adaptive expected equilibrium pricing algorithm in this setting with constant constraint violation and logarithmic regret bounds.

Our work is also closely related to the line of literature on the design and analysis of artificial currency mechanisms <cit.>. Such mechanisms have found applications in various resource allocation settings, including the allocation of food to food banks <cit.>, the allocation of students to courses <cit.>, and the allocation of public goods to people <cit.>. Mechanisms that involve artificial currencies have also been designed for repeated allocation settings <cit.>, as is the main focus of this paper. However, unlike <cit.> that studies the repeated allocation of goods that arrive online, we investigate the setting of online user arrival.

§ MODEL AND PROBLEM FORMULATION

In this section, we introduce our modeling assumptions and the individual optimization problem of users (Section <ref>), present the Eisenberg-Gale convex program used to compute equilibrium prices (Section <ref>), and introduce the performance measures used to evaluate the efficacy of an online algorithm (Section <ref>).

§.§ Preliminaries and Individual Optimization Problem

We study the problem of allocating $m$ divisible goods to a population of $n$ users that arrive sequentially over time. Each good $j \in [m]$ has a capacity $c_j = n d_j$, where we denote $\c \in \mathbb{R}^m$ as the vector of good capacities, $\d \in \mathbb{R}^m$ as the vector of good capacities per user, and the set $[m] = \{1, \ldots, m \}$. Each user $t \in [n]$ has a budget $w_t$ of (artificial) currency, and to model users' preferences over the goods, we assume that each user's utility is linear in their allocations. In particular, for a vector of allocations $\x_t \in \mathbb{R}^m$, where $x_{tj}$ represents the consumption of good $j$ by user $t$, the utility function $u_t(\x_t): \mathbb{R}^m \rightarrow \mathbb{R}$ is given by $u_t(\x_t) = \u_t^\top \x_t = \sum_{j = 1}^m u_{tj} x_{tj}$, where $\u_t \in \mathbb{R}^m$ is a vector of utility coefficients and $u_{tj}$ is the utility received by user $t$ for consuming one unit of good $j$. Then, for a given price vector $\p \in \mathbb{R}^m$, the individual optimization problem for user $t$ can be described as
\beginmaxi!|s|[2]
𝐱_t ∈ℝ^m
_̆t^⊤_t = ∑_j = 1^m u_ij x_ij,

\endmaxi!
where (<ref>) is a budget constraint, and (<ref>) are non-negativity constraints. Since each user's utility function is linear, a property of the optimal solution of Problem (<ref>)-(<ref>) is that given a price vector $\p$, users will only purchase goods that maximize their bang-per-buck. In other words, user $t$ will purchase an affordable bundle of goods in the set $S_t^*(\p) = \{j: j \in \argmax_{j' \in [m]} \frac{u_{tj'}}{p_{j'}} \}$.

The prices of the goods in the market that users best respond to through the solution of Problem (<ref>)-(<ref>) are set by a central planner whose goal is to set equilibrium prices, defined as follows.

(Equilibrium Price Vector)
A price vector $\p^* \in \mathbb{R}_{\geq 0}^m$ is an equilibrium price if there are allocations $\x_t^*(\p^*) \in \mathbb{R}^m$ for each user $t \in [n]$ such that:

* The allocation $\x_t^*(\p^*) \in \mathbb{R}^m$ is a solution of Problem (<ref>)-(<ref>) for all users $t \in [n]$ given the price vector $\p^*$;

* The prices of all goods are non-negative and the demand for all goods is no more than their capacity, i.e., $p_j^* \geq 0$ and $\sum_{t = 1}^n x_{tj}^*(\p^*) \leq c_j$ for all goods $j \in [m]$;

* If the price of a good $j$ is strictly positive, then the total demand for that good is equal to its capacity, i.e., if $p_j^*>0$ for some good $j \in [m]$, then $\sum_{t = 1}^n x_{tj}^*(\p^*) = c_j$.

The computation of equilibrium prices has been a holy grail in the Fisher market literature as it corresponds to one uniform price vector for all users at which the market clears. In classical (offline) Fisher markets, several methods, such as the Eisenberg-Gale convex program, to compute market equilibria have been developed. However, these approaches assume that the central planner has complete knowledge of users' budget and utility parameters. For a detailed discussion on offline Fisher markets and the Eisenberg-Gale convex program, we refer to Section <ref>.

Since information on users' utility and budget parameters are typically not known, and, in real markets, users tend to arrive sequentially over time, we study the online user arrival setting with incomplete information. In this context, we assume that users arrive sequentially with budget and utility parameters drawn i.i.d. from some unknown distribution $\D$ with bounded and non-negative support. That is, the budget and utility parameters $(w_t, \u_t) \stackrel{i.i.d.}{\sim} \D$ for each user $t$, where the budget $w_t \in [\underline{w}, \Bar{w}]$ for some $\underline{w}> 0$ and the utility vector $\u_t \in [\underline{\u}, \Bar{\u}]$ for some $\underline{\u} \geq \0$. We note that the stochastic input assumption has been used extensively in online Fisher markets <cit.> and in line with the Fisher market literature in the offline setting, we make the following assumption on the distribution $\D$.

[All Goods have Potential Buyers]
The distribution $\D$ is such that for each good $j \in [m]$, there exists a positive probability that users have a strictly positive utility for that good, i.e., $\mathbb{P}_{\D}((w, \u): u_{j}>0) > 0$.

Assumption <ref> is akin to analogous assumptions in classical Fisher markets that require each good to have a potential buyer to guarantee the existence of equilibria <cit.>. In particular, <cit.> shows that if each good has a potential buyer and users have linear utilities, then equilibrium prices exist and are positive. Assumption <ref> is mild since if no proportion of users had a positive utility for certain goods, those goods can be removed from the market as no user prefers to purchase them.

A few comments about our modeling assumptions are in order. First, we assume that each agent's utility function is linear in their allocations, a commonly used and well-studied utility function in classical Fisher markets <cit.>. Next, as in the Fisher market literature, we assume that the goods are divisible, and thus fractional allocations are possible. Furthermore, in the online setting, we study the arrival of users under the stochastic input model, which has been widely studied in the online linear programming <cit.> and the online convex optimization <cit.> literature. We note that the stochastic input assumption naturally arises in several applications and is commonly used in modeling customer arrivals <cit.>. Finally, in line with an extensive body of literature in online learning <cit.>, we also assume that the number of users $n$ is known a priori and we defer the question of extending our results to the setting when $n$ is unknown <cit.> to future research.

§.§ Offline Allocations Using the Eisenberg-Gale Convex Program

In the offline setting, when complete information on the budgets and utilities of all users is known, the central planner can compute equilibrium prices through the dual variables of the capacity constraints of the following Eisenberg-Gale convex program <cit.>
\beginmaxi!|s|[2]
𝐱_t ∈ℝ^m, ∀t ∈[n]
U(𝐱_1, ..., 𝐱_n) = ∑_t = 1^n w_t log( ∑_j = 1^m u_tj x_tj ) ,

∑_t = 1^n x_tj ≤c_j,   ∀j ∈[m],
x_tj≥0,   ∀t ∈[n], j ∈[m],
\endmaxi!
where (<ref>) are capacity constraints, (<ref>) are non-negativity constraints, and the Objective (<ref>) represents a budget-weighted geometric mean of buyer's utilities and is closely related to the Nash social welfare objective <cit.>. If the prices in the market are set based on the dual variables of the capacity Constraints (<ref>), then the optimal allocations of each user's individual optimization Problem (<ref>)-(<ref>) can be shown to be equal to that of the social optimization Problem (<ref>)-(<ref>) <cit.>. That is, the dual variables of the capacity Constraints (<ref>) correspond to equilibrium prices.

Properties of the Eisenberg-Gale Convex Program and its Optimal Allocations:

The Eisenberg-Gale convex program has several computational advantages that make it practically feasible. In particular, the computational complexity of solving Problem (<ref>)-(<ref>) is identical to that of a linear program <cit.>, i.e., it can be solved in polynomial time <cit.> with the same complexity as that of maximizing a linear objective function. Furthermore, in the special case that the utility coefficients, budgets, and good capacities are all rational, the optimal solution of Problem (<ref>)-(<ref>) is also rational <cit.>, i.e., the solution to Problem (<ref>)-(<ref>) can be exactly computed.

In addition to its computational advantages, the weighted geometric mean objective has several desirable properties compared to optimizing other social welfare objectives. First, the weighted geometric mean objective results in an allocation that satisfies both Pareto efficiency, i.e., no user can be made better off without making another user worse off, and envy-freeness, i.e., each user prefers their allocation compared to that of other users. However, other social welfare objectives often only satisfy one of these desirable properties, e.g., the utilitarian welfare (weighted sum of user's utilities) and egalitarian welfare (maximizing the minimum utility) objectives only achieve Pareto efficiency. Next, maximizing the weighted geometric mean of users' utilities achieves a natural compromise between the utilitarian and egalitarian objectives <cit.>, thereby resulting in a simultaneously efficient and fair allocation. In particular, compared to maximizing utilitarian welfare, which may result in unfair allocations <cit.> since some users may obtain zero utilities, under Objective (<ref>) all users receive a strictly positive utility. Furthermore, compared to the egalitarian objective that may result in highly inefficient outcomes, optimizing the geometric mean of users' utilities is more robust since it provides a lower bound on the utilitarian welfare.

§.§ Algorithm Design and Performance Measures in Online Setting

While the offline allocations corresponding to the Eisenberg-Gale program have several desirable properties, achieving such allocations is generally not possible in the online setting when the central planner does not have access to information on users' utility and budget parameters. As a result, we focus on devising algorithms that achieve good performance relative to an offline oracle with complete information on users' utilities and budgets. In particular, we evaluate the efficacy of an online allocation policy through two metrics: (i) expected regret, i.e., the optimality gap in the social welfare Objective (<ref>) of this allocation policy relative to the optimal offline allocation, and (ii) expected constraint violation, i.e., the degree to which the goods are over-consumed relative to their capacities. Here the expectation is taken with respect to the distribution $\D$ from which users' budget and utility parameters are drawn. In this section, we first present the class of online policies (algorithms) we focus on in this work (Section <ref>) and then formally define the regret and constraint violation metrics to evaluate the performance of these online algorithms (Section <ref>).

§.§.§ Algorithm Design in Online Fisher Markets

In online Fisher markets, a central planner needs to make an allocation $\x_t$ (or a pricing decision $\p^t$) instantaneously upon the arrival of each user $t \in [n]$. The allocation or pricing decisions made by the central planner depend on the information set $\I_t$ available to it at the time of arrival of each user. Some examples of the information sets $\I_t$ include the distribution $\D$ from which users' budget and utility parameters are drawn, the history of past user allocations, i.e., $\{ \x_{t'} \}_{t' = 1}^{t-1}$, and the history of budget and utility parameters of users that have arrived prior to user $t$, i.e., $(w_{t'}, \u_{t'})_{t' =1}^{t-1}$. Under a given information set $\I_t$, the allocations $\x_t$ (or pricing decisions $\p^t$) for each user are specified by a policy $\ppi^A = (\pi_1, \ldots, \pi_n)$ (or $\ppi^P = (\pi_1, \ldots, \pi_n)$), where $\x_t = \pi_t^A(\I_t)$ (or $\p^t = \pi_t^P(\I_t)$). Here the superscript “$A$” refers to an allocation-based policy, while the superscript “$P$” refers to a pricing-based policy. Note that when the central planner makes pricing decisions $\p^t = \pi_t^P(\I_t)$ for each user, the corresponding allocations $\x_t$ are given by the optimal solution to Problem (<ref>)-(<ref>) given the price vector $\p^t$. For the remainder of this work, since we focus on designing pricing policies, we drop the superscript in the notation for conciseness and use $\ppi$ to refer to a pricing policy. However, we do mention that our pricing policies have corresponding allocation-based analogues, as elucidated for one of our designed algorithms (Algorithm <ref>) in Section <ref>, and that both pricing and allocation policies are closely connected to each other by duality.

While a range of information sets $\I_t$ have been investigated in the study of online resource allocation <cit.>, of particular interest in this work is the privacy-preserving setting where each user's parameters are private information, known only to the users. As a result, we focus on designing a revealed preference dual-based algorithm (see Section <ref>) that adjusts the prices of the goods in the market solely based on past user consumption data, which is directly observable to the central planner. In particular, we focus on devising a pricing policy $\ppi = (\pi_1, \ldots, \pi_n)$ that sets a sequence of prices $\p^1, \ldots, \p^n$ such that $\p^t = \pi_t(\{ \x_{t'} \}_{t' = 1}^{t-1})$, where $\x_t$ is an optimal consumption vector given by the solution of Problem (<ref>)-(<ref>) for user $t$ given the price vector $\p^t$. We note that our focus on designing a dual-based algorithm in Section <ref> that only relies on users' revealed preferences is in contrast to traditional primal algorithms that require information on the attributes of users that have previously arrived in the system to make subsequent allocation decisions <cit.>.

§.§.§ Performance Measures

We now detail the regret and constraint violation performance measures used to evaluate the efficacy of an online pricing policy.

Regret: We evaluate the regret of any online algorithm (pricing policy) $\ppi$ through the difference between the optimal objective of Problem (<ref>)-(<ref>) and that corresponding to the allocations resulting from the online pricing policy $\ppi$. For a given set of utility and budget parameters for all users $t \in [n]$, let $U_n^*$ denote the optimal Objective (<ref>), i.e., $U_n^* = U(\x_1^*, \ldots, \x_n^*)$, where $\x_1^*, \ldots, \x_n^*$ are the optimal offline allocations corresponding to the solution of Problem (<ref>)-(<ref>). Further, let $\x_t$ be the solution to the individual optimization Problem (<ref>)-(<ref>) given the price vector $\p^t$ corresponding to the policy $\ppi$ for each user $t \in [n]$.
Then, the social welfare Objective (<ref>) obtained by the policy $\ppi$ is $U_n(\ppi) = U(\x_1, \ldots, \x_n)$, and the corresponding expected regret of an algorithm $\ppi$ is given by

\begin{align*}
R_n(\ppi) = \mathbb{E}_{\D} \left[ U_n^* - U_n(\ppi) \right],
\end{align*}

where the expectation is taken with respect to the distribution $\D$ from which the budget and utility parameters are drawn. In the rest of this work, with a slight abuse of notation, we drop the subscript $\D$ in the expectation and assume all expectations are with respect to $\D$, unless stated otherwise.

While the regret measure is defined with respect to the objective of the social optimization Problem (<ref>)-(<ref>), we note that regret guarantees derived for Objective (<ref>) directly translate into corresponding guarantees for the Nash social welfare objective, defined as $NSW(\x_1, \ldots, \x_n) = \left( \prod_{t = 1}^n u_t(\x_t^*) \right)^{\frac{1}{n}}$. In particular, if the regret of an algorithm $\ppi$ is $o(n)$, then the ratio of the Nash social welfare objective of the algorithm $\ppi$ approaches that of the optimal offline oracle as $n$ becomes large, i.e., if $U_n^* - U_n(\ppi) \leq o(n)$ for some algorithm $\ppi$, then $\frac{NSW(\x_1^*, \ldots, \x_n^*)}{NSW(\x_1, \ldots, \x_n)} \rightarrow 1$ as $n \rightarrow \infty$. We present a detailed discussion of this fundamental connection between the above-defined regret measure, which applies to Objective (<ref>), and the ratio between the Nash social welfare objective of the optimal offline oracle and that corresponding to an online algorithm in Appendix <ref>.

Constraint Violation: We evaluate the constraint violation of algorithm through the norm of the expected over-consumption of the goods beyond their capacity. In particular, for the consumption bundles $\x_1, \ldots, \x_n$ corresponding to the pricing policy $\ppi$, the vector of excess demands is given by $\v(\x_1, \ldots, \x_n) = \left( \sum_{t = 1}^n \x_{t} - \c \right)_+$, and the corresponding expected norm of the constraint violation is

\begin{align*}
V_n(\x_1, \ldots, \x_n) = \mathbb{E} \left[\norm{\v(\x_1, \ldots, \x_n)}_2 \right].
\end{align*}

\begin{align*}
\v(\x_1, \ldots, \x_n) = \left( \sum_{t = 1}^n \x_{t} - \c \right)_+,
\end{align*}

A few comments about the above regret and constraint violation metrics are in order. First, we reiterate that we define our regret metric based on the budget-weighted geometric mean Objective (<ref>). Our choice of this objective, as opposed to, for example, a utilitarian welfare one, stems from the superior properties of the allocations corresponding to the Eisenberg-Gale convex program elucidated in Section <ref>. Next, observe that the budget-weighted geometric mean Objective (<ref>) is nonlinear and unbounded. As a result, our regret metric differs from that considered in the online linear programming and online convex optimization literature that either assumes a linear or a concave objective that is bounded and non-negative. Finally, while we defined our constraint violation metric with the $L_2$ norm, by norm-equivalence, any constraint violation guarantees obtained with the $L_2$ norm can be extended to any $p$-norm, e.g., the $L_{\infty}$ norm.

In this work, we jointly optimize for regret and constraint violation, as in <cit.>, for two primary reasons. First, designing strictly feasible algorithms in online Fisher markets can result in infinite regret due to the logarithmic objective, as all the resources may be exhausted before the arrival of some users who would receive zero utility. Second, we optimize for both regret and constraint violation metrics since achieving good performance on either is typically easy. In particular, setting the prices of all goods to be very low will result in low regret but potentially lead to constraint violations since users will purchase large quantities of goods at lower prices. On the other hand, setting exceedingly large prices will have the opposite effect, in that the constraint violations will be low, but the regret is likely to be high. Due to this fundamental trade-off between regret and constraint violation <cit.>, we focus on optimizing both metrics in this work.

Finally, we note that allowing for some constraint violation is natural and aligns with the literature on online constrained convex optimization where the constraints are only required to be approximately satisfied in the long run <cit.>. Furthermore, in practical resource allocation applications, and, in particular, in online settings, resource capacities are often not hard constraints as there is often some degree of flexibility in the number of goods that can be made available during the online allocation process. Thus, small degrees of constraint violation is acceptable in practical resource allocation contexts. We also note that the algorithms we develop can be readily modified to satisfy capacity constraints; however, we allow for some capacity violations for the simplicity of presentation and defer a deeper exploration of algorithms for online stochastic Fisher markets that exactly satisfy the capacity constraints to future research.

§ STATIC PRICING LIMITS AND ADAPTIVE PRICING ENHANCEMENTS

In classical Fisher markets, the central planner determines one uniform price vector that applies to all users, i.e., an equilibrium price vector, which can be computed through the solution of the Eisenberg-Gale convex program. As a result, we begin our study of online Fisher markets by establishing the performance limitations of static pricing in this online incomplete information setting. In particular, we develop a $\Omega(\sqrt{n})$ lower bound on the expected regret and constraint violation of static pricing algorithms, which includes an algorithm that sets expected equilibrium prices with complete knowledge of the distribution $\D$ (Section <ref>). Given the performance limitations of static pricing, we present an adaptive (dynamic) variant of expected equilibrium prices that achieves an $O(\log(n))$ regret and constant (i.e., independent of the number of users $n$) constraint violation (Section <ref>). We mention that we also compare the static and adaptive expected equilibrium pricing algorithms through numerical experiments, which we present in Appendix <ref>.

§.§ Lower Bound for Static Pricing Algorithms

While equilibrium pricing, i.e., a uniform price vector for all users, has been the holy grail in classical Fisher markets, in this section, we establish the performance limitations of any static pricing algorithm in the online variant of Fisher markets studied in this work. In particular, we show that the expected regret or constraint violation of any static pricing algorithm that sets prices $\p^t = \p^{t'}$ for all $t, t' \in [n]$ must be $\Omega(\sqrt{n})$ in the online incomplete information setting.

Suppose that users' budget and utility parameters are drawn i.i.d. from a distribution $\D$. Then, there exists a market instance for which either the expected regret or expected constraint violation of any static pricing algorithm is $\Omega(\sqrt{n})$, where $n$ is the number of arriving users.

To prove this claim, we consider a setting with $n$ users (with a budget of one for all users) and two goods, each with a capacity of $n$. Furthermore, let the utility parameters of users be drawn i.i.d. from a probability distribution, where the users have utility $(1, 0)$ and a utility of $(0, 1)$, each with probability $0.5$. For this instance, to derive a lower bound on the regret, we first lower bound the expected optimal social welfare objective, i.e., Objective (<ref>), which we obtain by utilizing the property that users' utility distribution is binomial. Next, to prove the desired lower bound on the expected regret and constraint violation, we consider two cases: (i) the price of either of the two goods is at most $0.5$, and (ii) the price of both goods is strictly greater than $0.5$. In the first case, we use the central limit theorem to establish that the expected constraint violation is $\Omega(\sqrt{n})$. In the second case, we show that either the expected constraint violation or the expected regret is $\Omega(\sqrt{n})$ utilizing both the central limit theorem and the obtained lower bound on the expected optimal social welfare objective, which establishes our claim.

For a complete proof of Theorem <ref>, see Appendix <ref>. We note that the key to establishing Theorem <ref> was in deriving a lower bound on the expected optimal social welfare Objective (<ref>). We also note that the counterexample to prove Theorem <ref> highlights a fundamental tradeoff between regret and constraint violation metrics and can be readily modified to the setting where the support of the utility distribution is strictly positive (see Section <ref>), i.e., the utility distribution of users is $(\epsilon, 1)$ and $(1, \epsilon)$ with probability $0.5$ each for some small $\epsilon>0$. Theorem <ref> establishes the limitations of static pricing algorithms in online Fisher markets and is in stark contrast to the efficacy of equilibrium pricing in classical Fisher markets, wherein one uniform price vector applies to all users. This result points toward developing novel methods for understanding market equilibria in online Fisher markets and augments the literature in online resource allocation where static pricing or allocation approaches have limited performance <cit.>.

While the lower bound result in Theorem <ref> does not apply to adaptive pricing algorithms, Theorem <ref> provides a benchmark for the performance of any algorithm for online Fisher markets as static pricing includes an expected equilibrium pricing approach with complete knowledge of the distribution $\D$. Since Theorem <ref> establishes a lower bound on the expected regret and constraint violation of all static pricing algorithms, it, in particular, implies that even with complete information on the distribution $\D$, setting expected equilibrium prices will result in either an expected regret or constraint violation of $\Omega(\sqrt{n})$, as highlighted by the following corollary.

Suppose that the budget and utility parameters of users are drawn i.i.d. from a distribution $\D$. Then, there exists a market instance for which the expected constraint violation of an algorithm that sets equilibrium prices based on the expected number of user arrivals, i.e., the algorithm has complete information on the distribution $\D$, is $\Omega(\sqrt{n})$.

We reiterate that the static expected equilibrium pricing policy $\ppi$ utilizes distributional information, and thus $\p^t = \pi_t(\D)$ for all users $t\in [n]$. As this price vector is uniform across all users, Corollary <ref> follows as an immediate consequence of Theorem <ref>, and thus we omit its proof.

Suppose that the budget and utility parameters of users are drawn i.i.d. from a distribution $\D$. Then, there exists a market instance for which the expected constraint violation of an algorithm that sets equilibrium prices based on the expected number of user arrivals, i.e., the algorithm has complete information on the distribution $\D$, is $\Omega(\sqrt{n})$. Furthermore, the corresponding expected equilibrium prices that satisfy the capacity constraints of the goods with high probability will result in a regret of $\Omega(\sqrt{n})$.

To prove this claim, we consider a setting with $n$ users with a fixed budget of one and two goods, each with a capacity of $n$. Furthermore, let the utility parameters of users be drawn i.i.d. from a probability distribution, where the users have utility $(1, 0)$ with probability $0.5$ and a utility of $(0, 1)$ with probability $0.5$. That is, users either only have utility for good one or for good two, each with equal probability. For this instance, we first derive a tight bound for the expected optimal social welfare objective, and show that $\mathbb{E}[U_n^*] \geq n \log(2) - 1$. Next, we consider the equilibrium prices set by an algorithm that has complete information on the distribution $\D$ from which the utility parameters of users are drawn. In particular, since $\frac{n}{2}$ users of each utility type arrive in expectation, the expected equilibrium pricing policy corresponds to $\p^* = (0.5, 0.5)$, which is the price vector shown to all users and meets the capacity constraints in expectation. We then use the central limit theorem to establish that the expected constraint violation under this equilibrium pricing policy is $\Omega(\sqrt{n})$.

If, on the other hand, the central planner desired to satisfy the capacity constraints with high probability, then, using the derived lower bound on the expected optimal social welfare objective, it follows that setting the corresponding expected equilibrium prices using distributional information will result in an expected regret of $\Omega(\sqrt{n})$.

Theorem <ref> provides a lower bound on the regret or constraint violation of any static pricing algorithm, and, in particular,

Observe that a special case of a static pricing algorithm an expected equilibrium pricing algorithm with perfect information on the distribution from which the utility and budget parameters of users are drawn

Theorem <ref> provides a benchmark for the performance of an online algorithm since it establishes a lower bound on the regret and constraint violation of an expected equilibrium pricing algorithm with perfect information on the distribution from which the utility and budget parameters of users are drawn. That is, even with complete information on the distribution of the budgets and utilities of the arriving users, setting expected equilibrium prices will result in either an expected regret or constraint violation of $\Omega(\sqrt{n})$. We reiterate that our lower bound result in Theorem <ref> is not an algorithm independent lower bound but is a lower bound on the regret and constraint violation of an expected equilibrium pricing algorithm with complete knowledge of the distribution $\D$.

§.§ Adaptive Variant of Expected Equilibrium Pricing

Motivated by the performance limitations of static pricing, we now turn to develop adaptive pricing algorithms for online Fisher markets. To this end, in this section, we introduce an adaptive variant of expected equilibrium pricing for discrete probability distributions $\D$ (Section <ref>), as in the counterexample used to prove Theorem <ref>, and show that it achieves an $O(\log(n))$ regret and constant constraint violation (Section <ref>), thereby highlighting the benefit of adaptivity in algorithm design for online Fisher markets.

§.§.§ Adaptive Expected Equilibrium Pricing Algorithm

To present the adaptive expected equilibrium pricing algorithm, we first introduce some notation and the certainty equivalent problem used to set static equilibrium prices. In particular, we assume that the utility and budget parameters $(w, \u)$ of users are drawn i.i.d. from a discrete probability distribution with known and finite support $(\Tilde{w}_k, \Tilde{\u}_k)_{k = 1}^K$, where the support size $K \in \mathbb{N}$, and the probability of a user having budget and utility parameters $(\Tilde{w}_k, \Tilde{\u}_k)$ is given by $q_k$. That is, $\mathbb{P}((w_t, \u_t) = (\Tilde{w}_k, \Tilde{\u}_k)) = q_k$ for all $k \in [K]$, where $q_k \geq 0$ and $\sum_{k \in [K]} q_k = 1$. Then, to set static expected equilibrium prices, we can define the following certainty equivalent formulation of the Eisenberg-Gale program
\beginmaxi!|s|[2]
𝐳_k ∈ℝ^m, ∀k ∈[K]
U(_1, ..., _K) = ∑_k = 1^K q_k w_k log( ∑_j = 1^m  u_kj z_kj ) ,

∑_k = 1^K z_kj q_k  ≤d_j,   ∀j ∈[m],
z_kj≥0,   ∀k ∈[K], j ∈[m],
\endmaxi!
where (<ref>) is the objective of the Eisenberg-Gale program weighted by the probability of occurrence of the corresponding budget and utility parameters, and (<ref>) are the capacity constraints wherein the allocations are weighted by their corresponding probabilities. For succinctness, we denote the certainty equivalent Problem (<ref>)-(<ref>) as $CE(\d)$ for a vector of average resource capacities $\d$.

Observe that the optimal dual variables of the capacity constraints of this certainty equivalent problem correspond to the static expected equilibrium prices. As an example, for the two-good counterexample used to prove Theorem~\ref{thm:lbStatic}, the distribution support size $K = 2$, where the budget and utility parameters $(w, )̆$ are $(1, (1, 0))$ and $(1, (0, 1))$, each with probability $q_1 = q_2 = 0.5$, and the average resource capacity of each good per user is one, i.e., $d_1 = d_2 = 1$. For these parameters, the optimal dual variables of the capacity constraints of the certainty equivalent Problem~\eqref{eq:FisherSocOptScenario}-\eqref{eq:FisherSocOpt3Scenario} correspond to a price vector of $(0.5, 0.5)$, which are the static expected equilibrium prices for the market instance described in the proof of Theorem~\ref{thm:lbStatic}.

However, as observed in Corollary~\ref{cor:expectedEqPricing}, an issue with static expected equilibrium prices is that it can result in large constraint violations as some goods may be consumed too early, i.e., well before the arrival of the last user, due to the stochasticity in user arrivals. To circumvent this issue, we design an adaptive variant of the aforementioned expected equilibrium pricing approach (see Algorithm~\ref{alg:AlgoProbKnownDiscrete}) that increases the prices (relative to the static expected equilibrium prices) of goods that have been over-consumed and vice-versa. In particular, Algorithm~\ref{alg:AlgoProbKnownDiscrete} keeps track of the average ``remaining'' capacity of all goods at the time of arrival of each user $t$, i.e., a vector $_̣t$, where $d_tj = c_j - ∑_t'=1^t-1x_t'j/n-t+1$ for all users $t ∈{1, …, n}$, and sets prices based on the certainty equivalent problem $CE(_̣t)$ with the updated average remaining good capacities. Such a dynamic adjustment of the average remaining good capacities ensures that over-consumed goods have higher dual prices (relative to the static expected equilibrium prices), guaranteeing that no resource is consumed too quickly in Algorithm~\ref{alg:AlgoProbKnownDiscrete}.

Finally, since the certainty equivalent problem $CE(_̣t)$ is only well-defined for an average capacity vector $_̣t > 0$, in Algorithm~\ref{alg:AlgoProbKnownDiscrete} we adopt two pricing mechanisms depending on the difference between the average remaining capacity $_̣t$ and the initial average capacity $_̣1 = /n$. In particular, if the average remaining capacity $_̣t$ does not deviate too far from the initial average capacity $_̣1 = /n$, i.e., $_̣t ∈[-̣ Δ, +̣ Δ]$ for some constant vector $<Δ< $̣, e.g., $\Delta = \frac{\d}{2}$, then prices are set based on the dual variables of the above certainty equivalent Problem $CE(\d_t)$, which is well defined for any such $\d_t \in [\d - \Delta, \d + \Delta]$. After the first time $\tau$ that $\d_t \notin [\d - \Delta, \d + \Delta]$, the static expected equilibrium prices are set in the market. Note that the pricing policy $\ppi$ in Algorithm <ref> depends on the distribution $\D$ and the history of past allocations, i.e., $\p^t = \pi_t(\D, \{ \x_{t'} \}_{t' = 1}^{t-1})$. In response to the set prices, users consume their optimal bundle of goods given by the solution of Problem (<ref>)-(<ref>).

Initial Good Capacities $\c$, Number of Users $n$, Threshold Parameter Vector $Δ$, Support of Probability Distribution ${ w_k, _̆k }_k = 1^K$, Occurrence Probabilities ${q_k}_k = 1^K$}
Initialize $_̧1 = $̧ and the average remaining good capacity to $\d_1 = \frac{\c}{n}$

$t = 1, 2, ..., n$
Phase I: Set Price

$\d_{t'} \in [\d - \Delta, \d+\Delta] \text{ for all } t' \leq t$
Set price $\p^t$ as the dual variables of the capacity constraints of the certainty equivalent problem $CE(\d_t)$ with capacity $\d_t$

Set price $\p^t$ using the dual variables of the capacity constraints of the certainty equivalent problem $CE(\d)$ with capacity $\d = \d_1$

Phase II: Observed User Consumption and Update Available Good Capacities

User purchases optimal bundle $\x_t$ by solving Problem (<ref>)-(<ref>) given price $\p^t$
Update the available good capacities $\c_{t+1} = \c_{t} - \x_{t}$
Compute the average remaining good capacities $\d_{t+1} = \frac{\c_{t+1}}{n-t}$

Adaptive Expected Equilibrium Pricing

We note that Algorithm <ref> is similar in spirit to the adaptive allocation algorithm in <cit.>; however, in contrast to the algorithm in <cit.>, which applies for online linear programs, our algorithm applies for online Fisher markets with a non-linear objective. Furthermore, while the algorithm in <cit.> involves solving a sampling based linear program using observed parameters of users that have previously arrived, Algorithm <ref> entails solving a certainty equivalent problem at each step when a user arrives. We also note that there is an allocation-based variant of Algorithm <ref>, as with the allocation-based algorithm in <cit.>. In particular, for a remaining average good capacity $\d_t$, where $\z_1^*, \ldots, \z_K^*$ are the optimal solutions of the certainty equivalent problem $CE(\d_t)$, the allocation made to user $t$ can be given by $\x_t = \z_k^*$ if user $t$ has the budget and utility parameters $(\Tilde{w}_k, \Tilde{\u}_k)$. Note here that $\z_k^*$ is one of the optimal consumption vectors given the price $\p^t$ for a user $t$ of type $k \in [K]$. Furthermore, note that as compared to the adaptive expected equilibrium pricing, which only requires information on the distribution $\D$ and the history of past allocations, this allocation-based policy additionally requires information on the budget and utility parameters of the user for which an allocation decision needs to be made, i.e., $\x_t = \pi_t^A(\D, \{ \x_{t'} \}_{t' = 1}^{t-1}, (w_t, \u_t))$.

§.§.§ Regret and Constraint Violation Guarantee of Algorithm <ref>

We now show that Algorithm <ref> achieves an $O(\log(n))$ regret and a constant constraint violation, as is elucidated through the following theorem.

Suppose that the budget and utility parameters of users are drawn i.i.d. from a discrete probability distribution $\D$ satisfying Assumption <ref>, and let $\ppi$ denote the online pricing policy described by Algorithm <ref>, with $\underline{p}, \bar{p}>0$ as the lower and upper bounds, respectively, for the prices $p_j^t$ for all goods $j$ and for all users $t \in [n]$. Furthermore, let $\x_1, \ldots, \x_n$ be the allocations for the $n$ users, where $\x_t$ is an optimal solution for that user corresponding to the certainty equivalent problem $CE(\d_t)$ for $t \leq \tau$, where $\tau$ is the first time at which $\d_t \notin [\d-\Delta, \d+\Delta]$, and $\x_t$ is an optimal solution to $CE(\d)$ for $t > \tau$. Then, the constraint violation $V_n(\ppi) \leq O(1)$ and the regret $R_n(\ppi) \leq O(\log(n))$.

To this end, we require the following assumption, which imposes a stability restriction on the change in the dual prices of the certainty equivalent problem $CE(\d_t)$ for small changes in the average remaining capacities $\d_t$.

[Price Stabilization]
Let two average capacity vectors $\Tilde{\d}, \d'>\0$ be such that $\norm{\Tilde{\d} - \d'}_2 \leq O(\frac{1}{n-t})$ for a given $t \in [n-1]$. Then, the optimal price vectors $\Tilde{\p}, \p'$ of the certainty equivalent problems $CE(\Tilde{\d})$ and $CE(\d')$, respectively, satisfy $\norm{\Tilde{\p} - \p'}_2 \leq O(\frac{1}{n-t})$.

Assumption <ref> implies that small changes in the average capacity vector will result in only small changes in the optimal dual prices of the certainty equivalent Problem (<ref>)-(<ref>). Such a stability assumption on the dual prices aligns with prior work on adaptive allocation algorithms <cit.>, wherein stability and uniformity assumptions are required to establish regret guarantees for an algorithm that allocates goods based on the average remaining good capacities at each step. We also numerically validate Assumption <ref> through experiments in Appendix <ref>.

We now establish that Algorithm <ref> achieves a constant constraint violation, i.e., independent of the number of users $n$, and, under Assumption <ref>, an $O(\log(n))$ expected regret, as is elucidated by the following theorem.

Suppose that the budget and utility parameters of users are drawn i.i.d. from a discrete probability distribution $\D$ satisfying Assumption <ref>, and let $\ppi$ denote the online pricing policy described by Algorithm <ref>, with $\underline{p}, \bar{p}>0$ as the lower and upper bounds, respectively, for the prices $p_j^t$ for all goods $j$ and for all users $t \in [n]$. Furthermore, let $\x_1, \ldots, \x_n$ be the allocations for the $n$ users, where $\x_t$ is an optimal solution for that user corresponding to the certainty equivalent problem $CE(\d_t)$ for $t \leq \tau$, where $\tau$ is the first time at which $\d_t \notin [\d-\Delta, \d+\Delta]$, and $\x_t$ is an optimal solution to $CE(\d)$ for $t > \tau$. Then, the constraint violation $V_n(\ppi) \leq O(1)$ and, under Assumption <ref>, the regret $R_n(\ppi) \leq O(\log(n))$.

We prove this claim using four intermediate lemmas, presented in Appendix <ref>. Our first lemma establishes a generic upper bound on the regret of an algorithm for online Fisher markets using convex programming duality. This regret upper bound is composed of two terms: (i) the first term is akin to the constraint violation of
the algorithm and, in particular, accounts for the loss corresponding to over (or under-consuming)
goods, and (ii) the second term accounts for the loss of setting prices that deviate far from the static expected equilibrium prices. To bound the first term of the generic regret bound (and the constraint violation of Algorithm <ref>), we first note that the expected constraint violation is upper bounded by $O(\mathbb{E}[n-\tau])$, where $\tau$ is the stopping time at which the average remaining resource capacity vector $\d_t \notin [\d - \Delta, \d+\Delta]$. Then, using concentration inequalities and arguments analogous to those in <cit.>, we show that $O(\mathbb{E}[n-\tau])$ is a constant, establishing our desired constraint violation bound. Finally, to upper bound the second term in the generic regret bound, we first leverage techniques from parametric optimization to establish a lipschitzness relation between the optimal price of the certainty equivalent Problem $CE(\d_t)$ and the average remaining capacity vector $\d_t$. That is, we establish that small changes in the average remaining capacity vector will only result in small changes in the corresponding optimal price vector of the certainty equivalent problem $CE(\d_t)$. We then apply this Lipschitzness relation and use induction on the optimal dual prices of the certainty equivalent problem $CE(\d_t)$ to bound the difference between the adaptive and static expected equilibrium prices for each user, which gives the desired $O(\log(n))$ regret upper bound, thereby establishing our claim.

For a complete proof of Theorem <ref>, see Appendix <ref>. We note that in addition to the tools used to analyse the algorithm in <cit.> for linear programs, our regret analysis leverages the structural properties of Fisher markets and combines that with techniques from parametric optimization to establish necessary sensitivity relations for the non-linear Eisenberg-Gale program. Furthermore, as the counterexample used to prove Theorem <ref> involved a discrete distribution with finite support, an implication of Theorem <ref> is that Algorithm <ref> achieves a constant constraint violation and logarithmic regret on the distribution $\D$ in that counterexample. As mentioned in the statement of Theorem <ref>, we reiterate that the prices $p_j^t$ are strictly positive and bounded throughout the operation of Algorithm <ref>. To see this, first note that the boundedness of the optimal dual prices of the certainty equivalent problem at each step follows directly from the restriction that the vector of average remaining capacities $\d_t \in [\d-\Delta, \d+\Delta]$ for some $\Delta < \d$. In particular, the optimal dual prices of the certainty equivalent problem $CE(_̣t)$ for any vector $_̣t>0$ remain bounded as long as users' budgets and utilities are bounded. Next, the optimal dual prices of the certainty equivalent problem are guaranteed to be positive under Assumption~\ref{asmpn:mainRestriction}~\cite{vazirani_2007}, i.e., as long as the distribution $$ is such that for each good $j$, there is at least one type $k ∈[K]$ with probability $q_k>0$ such that the utility $u_kj>0$. In other words, the positivity of the prices during the operation of Algorithm~\ref{alg:AlgoProbKnownDiscrete} follows for any distribution $$ where some proportion of users have a positive utility for each good.

We also note in the statement of Theorem~\ref{thm:RegretCapVioAlgo4} that the allocation $_t$ is a solution to the corresponding certainty equivalent problem at each step. That is, if user $t$ is of type $k ∈[K]$, then the allocation $_t = _k^*$ as in the case of the allocation-based analogue of Algorithm~\ref{alg:AlgoProbKnownDiscrete} presented in Section~\ref{subsubsec:adaptiveExEq}, where $_k^*$ is a solution to the certainty equivalent problem $CE(_̣t)$. Observe that such an allocation corresponds to one of the optimal consumption vectors for each arriving user given the price $^t$, which is the dual price of that certainty equivalent problem. Furthermore, in some special cases, e.g., the counter-example in the proof of Theorem~\ref{thm:lbStatic} where users only have utility for one good, there is only one optimal consumption vector, characterized by the solution of the certainty equivalent problem, for each user for any price vector $^t>$. Given this observation and noting that the utility accrued by a user remains the same at all optimal consumption vectors given a price $^t$, focusing on the optimal solution to the corresponding certainty equivalent problem is without loss of generality. Our purpose for doing so is that it guarantees that the expected consumption at each step is equal to the average remaining good capacity, i.e., $𝔼[_t] = _̣t$ for all $t ≤τ$, which we require to analyse the constraint violation in the proof of Theorem~\ref{thm:RegretCapVioAlgo4}.

%We recall that these allocations corresponding to the optimal solution of the certainty equivalent problem $CE(\d_t)$ at each step can also be implemented using a primal-based algorithm, as elucidated in Section~\ref{subsubsec:adaptiveExEq}.

%Note that these allocations corresponding to the optimal solution of the certainty equivalent problem $CE(\d_t)$ at each step can also be implemented in Algorithm~\ref{alg:AlgoProbKnownDiscrete} using a primal-based algorithm, as in~\cite{chen2021linear}, wherein users are given allocations $\x_t = \z_k^*$ based on their type $k \in [K]$ at each step.

%, as in~\cite{chen2021linear}, wherein users are given allocations $\x_t = \z_k^*$ based on their type $k \in [K]$ at each step.

%In this proof, we leverage the fact that the allocations $\x_t$ are given by the optimal solution of the certainty equivalent problem $CE(\d_t)$ for $t \leq \tau$, which is one of the optimal consumption vectors corresponding to the price $\p^t$. Note that doing so is without loss of generality, since the utility of the users is unchanged for any optimal consumption bundle. Furthermore, note the allocations corresponding to the optimal solution of the certainty equivalent problem $CE(\d_t)$ at each step can be implemented in Algorithm~\ref{alg:AlgoProbKnownDiscrete} using a primal-based algorithm, wherein users are given allocations based on their observed type $k \in [K]$.

%Note that if no group of users had a strictly positive utility for certain goods, those goods can be removed from the market as no user prefers to purchase those goods.

Theorem~\ref{thm:RegretCapVioAlgo4} implies that Algorithm~\ref{alg:AlgoProbKnownDiscrete} is feasible, up to constants, with respect to the capacity constraints and achieves an $O(log(n))$ regret, which significantly improves upon the $Ω(√(n))$ lower bound on either the expected regret or constraint violation of any static pricing algorithm obtained in Theorem~\ref{thm:lbStatic}. As a result, Theorem~\ref{thm:RegretCapVioAlgo4} highlights the benefit of adaptivity in online Fisher markets and motivates the further development of adaptive pricing algorithms for this novel problem setting. To further highlight the advantages of Algorithm~\ref{alg:AlgoProbKnownDiscrete} as compared to static pricing approaches, we present numerical experiments in Appendix~\ref{apdx:staticVdynamic}, which show that Algorithm~\ref{alg:AlgoProbKnownDiscrete} achieves a low regret with almost no constraint violation even for large problem instances with $n=20,000$ users.

%In addition to Theorem~\ref{thm:RegretCapVioAlgo4}, we present numerical experiments in Appendix~\ref{apdx:staticVdynamic} to further highlight the advantages of Algorithm~\ref{alg:AlgoProbKnownDiscrete} in achieving low regret with almost no constraint violation for even $20,000$ users as compared to its static pricing counterpart that incurs a much larger constraint violation to achieve a slightly lower regret.

Despite the significant advantages of Algorithm~\ref{alg:AlgoProbKnownDiscrete} as compared to static pricing approaches, it has its limitations in applications when the distribution $$ is non-discrete and knowledge of the distribution $$ is not readily available (in which case the certainty equivalent problem $CE(_̣t)$ cannot be solved at each step). To address these concerns of Algorithm~\ref{alg:AlgoProbKnownDiscrete}, in the next section, we develop a revealed preference algorithm that does not use any distributional information when making pricing decisions and is applicable for general (non-discrete) probability distributions.

\section{Revealed Preference Algorithm and Regret Guarantees} \label{sec:PPARMain}

In this section, we present a revealed preference algorithm for online Fisher markets and its corresponding regret and constraint violation guarantees. In particular, this algorithm solely utilizes observations of past user consumption to inform pricing decisions for future arriving users without requiring any
information on users’ utility and budget parameters, thereby preserving user privacy. We further show that this algorithm achieves a regret and constraint violation of $O(√(n))$. Note that this guarantee matches, up to constants, the corresponding lower bound on the regret and constraint violation of a static pricing algorithm with complete distributional information on the budget and utility parameters of users (see Theorem~\ref{thm:lbStatic} and Corollary~\ref{cor:expectedEqPricing}). To motivate the revealed preference algorithm, we first present the dual of the Eisenberg-Gale convex Program~\eqref{eq:FisherSocOpt}-\eqref{eq:FisherSocOpt3} (Section~\ref{sec:dualProblem}), which also plays an essential role in our upper bound regret analysis. Then, we present the revealed preference algorithm (Section~\ref{sec:algoMain}), which follows from performing gradient descent on the dual of the Eisenberg-Gale convex program, and establish an upper bound on both its regret and constraint violation in Section~\ref{sec:regret-ub}. Finally, in Section~\ref{sec:numericalsec5}, we present numerical experiments to compare the performance of the revealed preference algorithm to several benchmarks on both regret and constraint violation metrics.

\subsection{Dual Formulation of Eisenberg-Gale Program} \label{sec:dualProblem}

Letting the price $p_j$ be the dual variable of the capacity Constraint~\eqref{eq:FisherSocOpt1} corresponding to good $j$, the dual of the Problem~\eqref{eq:FisherSocOpt}-\eqref{eq:FisherSocOpt3} is
\begin{equation} \label{eq:dual}
\begin{aligned}
\min_{\mathbf{p}} \quad & \sum_{t = 1}^n w_t \log(w_t) - \sum_{t = 1}^n w_t \log \left( \min_{j \in [m]} \frac{p_j}{u_{tj}} \right) + \sum_{j = 1}^m p_j c_j - \sum_{t = 1}^n w_t.
\end{aligned}
\end{equation}
For a derivation of the above dual using the Lagrangian of Problem~\eqref{eq:FisherSocOpt}-\eqref{eq:FisherSocOpt3}, we refer to Appendix~\ref{apdx:dual-pf}. We note that the above dual problem is the unconstrained version of the dual problem presented in~\cite{duality2017CDGJMVY} with the additional terms $∑_t = 1^n w_t log(w_t)$ and $- ∑_t = 1^n w_t$ in the objective. Observe that these terms in the objective are independent of the prices and thus do not influence the optimal solution of the dual problem but are necessary to analyze the regret of the algorithm we develop.

Since users' budget and utility parameters are drawn i.i.d. from the same distribution, this dual problem can be re-formulated as the following sample average approximation (SAA) problem
\begin{equation} \label{eq:SAA2}
\begin{aligned}
\min_{\mathbf{p}} \quad & D_n(\p) = \sum_{j = 1}^m p_j d_j + \frac{1}{n} \sum_{t = 1}^n \left( w_t \log(w_t) - w_t \log \left(\min_{j \in [m]} \frac{p_j}{u_{tj}} \right) - w_t \right)
\end{aligned}
\end{equation}
by dividing the dual objective in Problem~\eqref{eq:dual} by the number of users $n$, where, recall that $d_j = c_j/n$. Note that each term in the second summation of the objective of the above problem is independent of each other under the i.i.d. assumption on the utility and budget parameters of users.

%We mention here that our privacy-preserving algorithm follows as a direct consequence of performing gradient descent on Problem~\eqref{eq:SAA2} with respect to the prices, as is described in Section~\ref{sec:algoMain}.

\subsection{Revealed Preference Algorithm} \label{sec:algoMain}

In this section, we present a revealed preference algorithm to dynamically update the prices of the goods in the market solely based on observations of user consumption. In particular, we devise a pricing policy $= (π_1, …, π_n)$ that sets a sequence of prices $^1, …, ^n$ such that the pricing decision at each step only depends on the observed history of user consumption at the previous steps, i.e., $^t = π_t({ _t' }_t' = 1^t-1)$, where the allocations $_t$ are given by the optimal solutions to Problem~\eqref{eq:Fisher1}-\eqref{eq:Fishercon3} given the price vector $^t$. Our algorithm adjusts the prices in the market when a user arrives based on whether the previous arriving user consumed more or less than their respective market share of each good. In particular, the price of a good $j$ is increased (decreased) if the previous arriving user consumed more (less) than the average good capacity $d_j = c_j/n$ units of good $j$. The prices are updated using a step size $γ_t$. This process of updating the prices based on the observed optimal consumption of users is presented formally in Algorithm~\ref{alg:PrivacyPreserving}.

%In this section, we present a revealed preference algorithm to dynamically update the prices of the goods in the market when the budget and utility parameters of the arriving users are drawn from an unknown probability distribution. Our algorithm adjusts the prices in the market when a user arrives based on whether the previous arriving user consumed more or less than their respective market share of each good. In particular, the price of a good $j$ is increased (decreased) if the previous arriving user consumed more (less) than $\frac{c_j}{n}$ units of good $j$. The prices are updated using a step size $\gamma_t$, which we specify in Section~\ref{sec:regret-ub}. Finally, in response to a given price vector $\p^t$, each user best responds by purchasing an optimal bundle of goods corresponding to the solution of their individual optimization Problem~\eqref{eq:Fisher1}-\eqref{eq:Fishercon3}. This process of updating the prices based on the observed optimal consumption of users is presented formally in Algorithm~\ref{alg:PrivacyPreserving}.

\begin{algorithm}
\SetAlgoLined
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{Number of users $n$, Vector of good capacities per user $\d = \frac{\c}{n}$}
Initialize $\p^1 > \0$ \;
\For{$t = 1, 2, ..., n$}{
\textbf{Phase I:} User Consumes Optimal Bundle $\x_t$ by solving Problem~\eqref{eq:Fisher1}-\eqref{eq:Fishercon3} given the price $\p^t$ \;
\textbf{Phase II (Price Update):} $\p^{t+1} \leftarrow \p^t - \gamma_t \left( \d - \x_{t} \right) $  \;
\caption{Revealed Preference Algorithm for Online Fisher Markets}
\label{alg:PrivacyPreserving}
\end{algorithm}

A few comments about Algorithm~\ref{alg:PrivacyPreserving} are in order. First, Algorithm~\ref{alg:PrivacyPreserving} is akin to several revealed preference approaches in the literature~\cite{roth2016watch,ji2018social,Jalota.ea.CDC22.extended}. However, unlike prior approaches that focus on the setting when users have quasi-linear utilities, Algorithm~\ref{alg:PrivacyPreserving} applies when users are budget-constrained, as in the context of Fisher markets. Furthermore, as opposed to prior literature on online learning, in our price update step, we do not project the price vector $^t$ to the non-negative orthant. Instead, we develop a novel potential function argument to show that the prices will always remain positive and bounded throughout the operation of Algorithm~\ref{alg:PrivacyPreserving} under a mild assumption on the distribution $$ (see Section~\ref{sec:regret-ub}). Next, since Algorithm~\ref{alg:PrivacyPreserving} relies on users' revealed preferences, the price update step does not require any information on the budgets and utilities of users and thus preserves user privacy. Furthermore, Algorithm~\ref{alg:PrivacyPreserving} is practically implementable with low computational overhead since the computational complexity of the price updates is only $O(m)$ at each time a user arrives. Note here that Phase I of Algorithm~\ref{alg:PrivacyPreserving}, wherein each arriving user solves their individual optimization problem, also has an $O(m)$ complexity as users purchase the good with the maximum bang-per-buck ratio. However, since Phase I of Algorithm~\ref{alg:PrivacyPreserving} is a distributed step, the central planner only incurs a cost when performing the price updates in Phase II. Finally, for each user $t$, the price update step follows from performing gradient descent on the $t$'th term of the dual Problem~\eqref{eq:SAA2}. In particular, if the optimal consumption set $S_t^*$ for user $t$, given the price vector $^t$, consists of one good, then the sub-gradient of the $t$'th term of the dual Problem~\eqref{eq:SAA2} is given by
\begin{align*}
\left.\partial_{\p}\left( \sum_{j = 1}^m p_{j} d_j + w_t \log \left(w_t\right)-w_t \log \left(\min _{j \in[m]} \frac{p_{j}}{u_{tj}}\right) - w_t \right)\right|_{\p=\p^t} = \d - \x_t,
\end{align*}
where $_t$ is an optimal bundle corresponding to the solution of the individual optimization Problem~\eqref{eq:Fisher1}-\eqref{eq:Fishercon3} of agent $t$. Note here that $x_tj^* = w_t/p_tj^*$ for the good $j^*$ in its optimal consumption set $S_t^*$, which is of cardinality one, and $x_tj = 0$ for all goods $j ≠j^*$. \ifarxiv \else Given the connection between gradient descent and the price updates in Algorithm~\ref{alg:PrivacyPreserving}, we also note that other price update steps could also have been used in Algorithm~\ref{alg:PrivacyPreserving} based on mirror descent (see Appendix~\ref{apdx:mirrorDescentStep}). \fi

\ifarxiv

Given the connection between gradient descent and the price updates in Algorithm~\ref{alg:PrivacyPreserving}, we note that other price update steps could also have been used in Algorithm~\ref{alg:PrivacyPreserving} based on mirror descent. For instance, instead of adjusting the prices through an additive update, as in Algorithm~\ref{alg:PrivacyPreserving}, prices can be modified through a multiplicative update using the following widely studied~\cite{CHEUNG2019,Balseiro2020DualMD} update rule
\begin{align} \label{eq:multiplicativeUpdate}
\p^{t+1} \leftarrow \p^t e^{- \gamma_t \left( \d - \x_{t} \right)}.
\end{align}
In Appendix~\ref{apdx:AddVMult}, we present a comparison between the regret and constraint violation of Algorithm~\ref{alg:PrivacyPreserving} with the additive price update step and the corresponding algorithm with a multiplicative price update step through numerical experiments. For our theoretical analysis in Section~\ref{sec:regret-ub}, we focus on the additive price update step in Algorithm~\ref{alg:PrivacyPreserving} and defer an exploration of the regret and constraint violation guarantees resulting from the multiplicative price update steps to future research. To this end, we do mention that this mirror descent-based multiplicative price update rule achieves $O(√(n))$ regret guarantees in~\cite{Balseiro2020DualMD} for bounded and non-negative concave utilities and believe that some of their techniques can be extended to the budget-weighted log utility objective, i.e., Objective~\eqref{eq:FisherSocOpt} that can be negative and is unbounded, studied in this work.

\fi

\vspace{-3pt}

\subsection{Regret and Constraint Violation Upper Bound} \label{sec:regret-ub}
\vspace{-3pt}
In this section, we establish an $O(√(n))$ upper bound on both the expected regret and constraint violation of Algorithm~\ref{alg:PrivacyPreserving}. To establish the regret and constraint violation bounds, we make the following regularity assumption on the utility and budget parameters of arriving users, which ensures that all users' utilities and budgets are strictly positive and bounded.
\vspace{-4pt}
\begin{assumption} [Support of $\D$] \label{asmpn:regularity}
The support of the distribution $\D$ is such that the utilities and budgets are strictly positive and bounded, i.e., $\u \in [\underline{\u}, \Bar{\u}]$ and $w \in [\underline{w}, \Bar{w}]$, where $\underline{u}, \underline{w}>0$.
\end{assumption}
\vspace{-4pt}
Assumption~\ref{asmpn:regularity} imposes a mild restriction on the set of allowable distributions from which the budget and utility parameters of users are drawn. In particular, the boundedness of the utilities and user budgets are standard assumptions in the Fisher market literature, and the positivity of the budgets is a natural condition as users with no budgets have no buying power and can thus be removed from consideration of the set of users in the market. Furthermore, the condition on the positivity of the utilities is mild and introduced mainly for simplicity as it aligns with practical contexts where users typically receive some positive utility (given by any small constant $u>0$) for obtaining resources. Note that changing the utility parameters from zero to some small positive constant also generally does not influence the optimal choice set of users. %and helps ensure that the prices remain strictly positive during the operation of Algorithm~\ref{alg:PrivacyPreserving}.

We now present the main result of this section, which establishes an $O(√(n))$ upper bound on both the expected regret and constraint violation of Algorithm~\ref{alg:PrivacyPreserving}.
\vspace{-3pt}
\begin{theorem} [Regret and Constraint Violation Bounds for Algorithm~\ref{alg:PrivacyPreserving}] \label{thm:PrivacyPreserving}
Suppose that the budget and utility parameters of users are drawn i.i.d. from a distribution $\D$ satisfying Assumptions~\ref{asmpn:mainRestriction} and~\ref{asmpn:regularity}. Furthermore, let $\ppi$ denote the online pricing policy described by Algorithm~\ref{alg:PrivacyPreserving}, $\x_1, \ldots, \x_n$ be the corresponding allocations for the $n$ users. Then, for a step size $\gamma = \gamma_t = \frac{\Bar{D}}{\sqrt{n}}$ for some constant $\Bar{D}>0$ for all users $t \in [n]$, the regret $R_n(\ppi) \leq O(\sqrt{n})$ and the constraint violation $V_n(\ppi) \leq O(\sqrt{n})$.
\end{theorem}
\vspace{-6pt}

\begin{hproof}
The proof of Theorem~\ref{thm:PrivacyPreserving} relies on two intermediate lemmas. First, we show that if the price vector at every step of Algorithm~\ref{alg:PrivacyPreserving} is bounded above and below by some positive constant, then the $O(\sqrt{n})$ upper bounds on both the regret and expected constraint violation hold. The proof of this claim uses convex programming duality and the stochastic assumption on the budget and utility parameters of the arriving users. We then show that the price vector $\p^t$ in Algorithm~\ref{alg:PrivacyPreserving} remains strictly positive and bounded for all users $t \in [n]$ if the distribution $\D$ satisfies Assumption~\ref{asmpn:regularity}. To prove this result, we proceed in two steps. First, we show that if the price vector $\p^t$ at each iteration of Algorithm~\ref{alg:PrivacyPreserving} is bounded below by some vector $\underline{\p} > \0$, then the price vector also remains bounded above. In other words, the positivity of prices during the operation of Algorithm~\ref{alg:PrivacyPreserving} implies the boundedness of the prices. Next, we show that the prices of the goods will always remain positive under Assumption~\ref{asmpn:regularity}. To show this, we develop a novel potential function argument that leverages the structural properties of Fisher markets and the price update rule in Algorithm~\ref{alg:PrivacyPreserving}. In particular, we define a potential $V_t = (\p^t)^T \d$, and show that this potential is non-decreasing, i.e., $V_{t+1} \geq V_t$, if the prices of all goods are below a specified threshold for user $t$. We then combine this potential function argument with Assumption~\ref{asmpn:regularity} to show that the prices of all goods are lower bounded by some price $\underline{p}>0$, which establishes our claim.
\end{hproof}
\vspace{-3pt}
For a more detailed proof sketch of Theorem~\ref{thm:PrivacyPreserving}, see Appendix~\ref{sec:pfThm3}, and for a complete proof of the lemmas presented in Appendix~\ref{sec:pfThm3} that are required to prove Theorem~\ref{thm:PrivacyPreserving}, we refer to Appendices~\ref{apdx:ubpf} and~\ref{apdx:positivePricesPf}. We reiterate here that, as opposed to prior literature on online learning, our regret analysis enables us to establish the regret and constraint violation bounds for Algorithm~\ref{alg:PrivacyPreserving} without projecting the price vector $\p^t$ to the non-negative orthant. Note that if the price of some good became non-positive during the operation of Algorithm~\ref{alg:PrivacyPreserving}, then users would purchase an infinite amount of that good by the optimal solution of Problem~\eqref{eq:Fisher1}-\eqref{eq:Fishercon3}, resulting in an unbounded constraint violation. Thus, our potential function argument to show that the positivity of prices throughout the operation of Algorithm~\ref{alg:PrivacyPreserving} is crucial to establishing the regret and constraint violation bounds in Theorem~\ref{thm:PrivacyPreserving}.

Theorem~\ref{thm:PrivacyPreserving} establishes that the expected regret and constraint violation of Algorithm~\ref{alg:PrivacyPreserving} are sub-linear in the number of users $n$. As with Theorem~\ref{thm:RegretCapVioAlgo4}, the obtained regret and constraint violation bounds depend on the specific problem instance and the support of the distribution $\D$ (see Appendices~\ref{apdx:ubpf} and~\ref{apdx:positivePricesPf}), but we focus our attention here on the dependency of the regret bound on the number of users $n$. Note that Theorems~\ref{thm:lbStatic} and~\ref{thm:PrivacyPreserving} jointly imply that Algorithm~\ref{alg:PrivacyPreserving}, while preserving user privacy, achieves expected regret and constraint violation guarantees, up to constants, that are no more than that of an expected equilibrium pricing approach (see Corollary~\ref{cor:expectedEqPricing}) with complete information on the distribution from which users' budget and utility parameters are drawn. On the other hand, as compared to Algorithm~\ref{alg:AlgoProbKnownDiscrete} that achieves a constant constraint violation and an $O(\log(n))$ regret (see Theorem~\ref{thm:RegretCapVioAlgo4}), Algorithm~\ref{alg:PrivacyPreserving} achieves a higher regret and constraint violation of $O(\sqrt{n})$. We defer the problem of closing the performance gap between these algorithms as a topic for future research and note that under similar informational assumptions to that of Algorithms~\ref{alg:AlgoProbKnownDiscrete} and~\ref{alg:PrivacyPreserving} a similar performance gap is observed even in the online linear programming literature~\cite{li2020simple,chen2021linear}.

%In particular, even in online linear programming a square root regret is the best achievable performance bound if the arriving data is not revealed

While the regret and constraint violation bounds of Algorithms~\ref{alg:AlgoProbKnownDiscrete} and~\ref{alg:PrivacyPreserving} highlight that there is a performance loss in algorithm design for online Fisher markets in the absence of distributional information, we reiterate that Algorithm~\ref{alg:PrivacyPreserving} has several advantages to Algorithm~\ref{alg:AlgoProbKnownDiscrete}. First, Algorithm~\ref{alg:PrivacyPreserving} is applicable for a broader range of probability distributions compared to Algorithm~\ref{alg:AlgoProbKnownDiscrete}, which only applies for discrete probability distributions $\D$. Next, the price update step in Algorithm~\ref{alg:PrivacyPreserving} has a very low computational overhead, while updating prices in Algorithm~\ref{alg:AlgoProbKnownDiscrete} involves solving a convex program at each step. Finally, Algorithm~\ref{alg:PrivacyPreserving} is more likely to be practically viable as it only relies on users' revealed preferences, while Algorithm~\ref{alg:AlgoProbKnownDiscrete} requires complete knowledge of the distribution $\D$.

We also note that while Assumption~\ref{asmpn:regularity} is crucial to establishing Theorem~\ref{thm:PrivacyPreserving}, we can also extend this result to distributions such as in the counterexample used to prove Theorem~\ref{thm:lbStatic}. In particular, in Appendix~\ref{apdx:ubPrices}, we show for distributions such as in the counterexample to prove Theorem~\ref{thm:lbStatic} that the prices remain strictly positive through the operation of Algorithm~\ref{alg:PrivacyPreserving} with high probability using concentration inequalities. We also validate the positivity of prices through the operation of Algorithm~\ref{alg:PrivacyPreserving} using numerical experiments in Appendix~\ref{apdx:numericalValidationStrictPositivity}.

\begin{comment}
two important observations in the case when the prices of all goods are small. First, if the prices of all goods are below a specified threshold, then there is a non-decreasing potential that depends on the prices of the goods, which implies that the price of at least one good must increase in subsequent iterations. Next, combining this fact with Assumption~\ref{asmpn:regularity}, it follows that if the price of any good drops too low, then any arriving user will purchase that good given that they have a strictly positive utility for it.

We reiterate that Assumption~\ref{asmpn:regularity} plays a crucial role in showing that the price vector remains strictly positive during the operation of Algorithm~\ref{alg:PrivacyPreserving}. In particular, by Assumption~\ref{asmpn:regularity}, if the price of any good drops too low, then any arriving user will purchase that good given that they have a strictly positive utility for it. We also note that for distributions $\D$ where the utilities of users

We conclude this section by presenting a result that is of independent interest, which is used to prove Lemma~\ref{lem:PositivePrices}.

While Lemma~\ref{lem:PositivePrices} applies to distributions $\D$ with strictly positive utilities, we note that the argument of Lemma~\ref{lem:PositivePrices} can also be extended to distributions $\D$ where

A few comments about Lemma~\ref{lem:PositivePrices} are in order. First, the result of Lemma~\ref{lem:PositivePrices} is deterministic, i.e., it applies to any sequence of utilities and budgets drawn from the distribution $\D$ satisfying Assumption~\ref{asmpn:regularity}.

Assumption~\ref{asmpn:regularity} plays a crucial role in showing that the price vector remains strictly positive during the operation of Algorithm~\ref{alg:PrivacyPreserving}.
, as if the price of any good drops too low then any arriving user will purchase that good given that they have a strictly positive utility for it. We note, however, that this argument will not apply for the counter example used to lower bound the performance of static pricing algorithms in Theorem~\ref{thm:lbStatic}, as users have utilities $(0, 1)$ and $(1, 0)$, each with equal probability in that setting. In particular, the above argument does not hold as there could be instances when only users with utility $(0, 1)$ arrive in which case the price of good two will necessarily drop below zero during the operation of Algorithm~\ref{alg:PrivacyPreserving}, as no arriving user will purchase good one in such an instance. However, we note that the probability of such an event occurring is low and thus for instances such as the one in the proof of Theorem~\ref{thm:lbStatic}, we show using concentration inequalities that the price vector $\p^t$ will remain strictly positive with high probability during the operation of Algorithm~\ref{alg:PrivacyPreserving}.
\end{comment}

\begin{comment}
\subsection{}

present two intermediate lemmas necessary to prove this result

present lemma on potential function argument

state that result can also extend to (0, 1) and (1, 0) type utility functions as in the proof of theorem 1

For a complete proof of Theorem~\ref{thm:PrivacyPreserving}, we refer to Appendix~\ref{apdx:ubpf}. Theorem~\ref{thm:PrivacyPreserving} establishes that the expected regret and constraint violation of Algorithm~\ref{alg:PrivacyPreserving} are sub-linear in the number of users $n$. Note that Theorems~\ref{thm:lbStatic} and~\ref{thm:PrivacyPreserving} jointly imply that Algorithm~\ref{alg:PrivacyPreserving}, while preserving user privacy, achieves expected regret and constraint violation guarantees, up to constants, that are no more than that of an expected equilibrium pricing approach (see Corollary~\ref{cor:expectedEqPricing}) with complete information on the distribution from which users' budget and utility parameters are drawn. On the other hand, as compared to Algorithm~\ref{alg:AlgoProbKnownDiscrete} that achieves a constant constraint violation and an $O(\log(n))$ regret (see Theorem~\ref{thm:RegretCapVioAlgo4}), Algorithm~\ref{alg:PrivacyPreserving} achieves a higher regret and constraint violation of $O(\sqrt{n})$. We defer the problem of closing the performance gap between these algorithms as a topic for future research.

While the regret and constraint violation bounds of Algorithms~\ref{alg:AlgoProbKnownDiscrete} and~\ref{alg:PrivacyPreserving} highlight that there is a performance loss in algorithm design for online Fisher markets in the absence of distributional information, we reiterate that Algorithm~\ref{alg:PrivacyPreserving} has several advantages to Algorithm~\ref{alg:AlgoProbKnownDiscrete}. First, Algorithm~\ref{alg:PrivacyPreserving} is applicable for a broader range of probability distributions compared to Algorithm~\ref{alg:AlgoProbKnownDiscrete}, which only applies for discrete probability distributions $\D$. Next, the price update step in Algorithm~\ref{alg:PrivacyPreserving} has a very low computational overhead, while updating prices in Algorithm~\ref{alg:AlgoProbKnownDiscrete} involves solving a convex program at each step. Finally, Algorithm~\ref{alg:PrivacyPreserving} is more likely to be practically viable as it only relies on users' revealed preferences, while Algorithm~\ref{alg:AlgoProbKnownDiscrete} requires complete knowledge of the distribution $\D$.

Finally, a few comments about the assumption in the statement of Theorem~\ref{thm:PrivacyPreserving} that the price vector $\p^t$ is strictly positive and bounded during the operation of Algorithm~\ref{alg:PrivacyPreserving} are in order. In particular, first note that if the price vector $\p^t$ at each iteration of Algorithm~\ref{alg:PrivacyPreserving} is bounded below by some vector $\underline{\p}$, then the price vector also remains bounded above by $\Bar{\p}$, where $\Bar{p}>0$ is a constant, as we show in Lemma~\ref{lem:PosImplBounded} in Appendix~\ref{apdx:ubPrices}. In other words, the positivity of prices during the operation of Algorithm~\ref{alg:PrivacyPreserving} implies the boundedness of the prices; however, we still retain the boundedness assumption in the statement of Theorem~\ref{thm:PrivacyPreserving} to simplify the exposition in its proof presented in Appendix~\ref{apdx:ubpf}. Next, under Assumption~\ref{asmpn:mainRestriction} on the distribution $\D$, it holds that users with a positive utility for each good will arrive with a high probability for a large number of users $n$. As a result, for a small constant $\Bar{D}>0$ for the price updates in Algorithm~\ref{alg:PrivacyPreserving}, the prices of any good will not drop below a small constant $\underline{p}>0$, as eventually, users will purchase large quantities of that good (at lower prices) to drive the prices of that good up through the price update in Algorithm~\ref{alg:PrivacyPreserving}. We present some more formalism behind this intuition by using concentration inequalities in Appendix~\ref{apdx:ubPrices} to further motivate the positivity of the price vector $\p^t$ during the operation of Algorithm~\ref{alg:PrivacyPreserving}. %is without much loss of generality.
Furthermore, we validate the positivity of prices through the operation of Algorithm~\ref{alg:PrivacyPreserving} using numerical experiments presented in Appendix~\ref{apdx:numericalValidationStrictPositivity}.
\end{comment}

%which corresponds to the additional loss in decision making for online Fisher markets in the absence of distributional information. We defer the problem of closing the gap between these two algorithms as an important direction for future research.

\begin{comment}
For complete proofs of Lemmas~\ref{lem:PrivacyPreservingPositive} and~\ref{lem:PrivacyPreservingPositive2}, see Appendices~\ref{apdx:ubPrices} and~\ref{apdx:ubpf}, respectively. Note that Lemmas~\ref{lem:PrivacyPreservingPositive} and~\ref{lem:PrivacyPreservingPositive2} jointly imply Theorem~\ref{thm:PrivacyPreserving}.

In this section, we present an $O(\sqrt{n})$ upper bound on both the regret and constraint violation of Algorithm~\ref{alg:PrivacyPreserving}.
\end{comment}

\begin{comment}
Our second intermediary result states that if the price vector at every step of the algorithm is bounded above and below by some positive constant then the $O(\sqrt{n})$ upper bounds on both the regret and expected constraint violation hold. We formalize this claim through the following lemma.

\begin{lemma} [Regret and Constraint Violation for Strictly Positive Prices] \label{lem:PrivacyPreservingPositive2}
Let $\ppi$ denote the online pricing policy described by Algorithm~\ref{alg:PrivacyPreserving} and let $\x_1, \ldots, \x_n$ be the corresponding allocations for the $n$ users. Furthermore, suppose that the price vector $\p^t$ is such that $\0< \p^t \leq \Bar{\p}$ for all users $t \in [n]$. Then, for a step size $\gamma_t = \frac{\Bar{D}}{\sqrt{n}}$ for some constant $\Bar{D}>0$, it holds that $R_n(\ppi) \leq O(\sqrt{n})$ and $V_n(\ppi_3) \leq O(\sqrt{n})$.
\end{lemma}

\begin{hproof}
To establish this result, we proceed in three steps. First, we first prove an $O(\sqrt{n})$ upper bound on the constraint violation for the price update rule in Algorithm~\ref{alg:PrivacyPreserving} by showing that the constraint violation is upper bounded by $O(\Bar{p} \sqrt{n})$, where $\Bar{p}$ is an upper bound on the good prices, as in the statement of the lemma. Then, to establish an upper bound on the expected regret, we use duality (see Section~\ref{sec:dualProblem}) to derive a generic upper bound on the regret of any online algorithm as long as the prices $\p^t$ are strictly positive and bounded for all users $t \in [n]$, which holds by Lemma~\ref{lem:PrivacyPreservingPositive} with high probability. Finally, we apply the price update rule in Algorithm~\ref{alg:PrivacyPreserving} and the generic regret upper bound to establish an $O(\sqrt{n})$ upper bound on the regret for a step size $\gamma = \frac{\Bar{D}}{\sqrt{n}}$ for some constant $\Bar{D}>0$.
\end{hproof}

For complete proofs of Lemmas~\ref{lem:PrivacyPreservingPositive} and~\ref{lem:PrivacyPreservingPositive2}, see Appendices~\ref{apdx:ubPrices} and~\ref{apdx:ubpf}, respectively. Note that Lemmas~\ref{lem:PrivacyPreservingPositive} and~\ref{lem:PrivacyPreservingPositive2} jointly imply Theorem~\ref{thm:PrivacyPreserving}.
\end{comment}

%For a complete proof of Theorem~\ref{thm:PrivacyPreserving}, see Appendix~\ref{apdx:ubpf}. Theorem~\ref{thm:PrivacyPreserving} establishes that both the regret and constraint violation of Algorithm~\ref{alg:PrivacyPreserving} are sub-linear in the number of arriving users $n$. Note that Theorems~\ref{thm:lbStatic} and~\ref{thm:PrivacyPreserving} jointly imply that Algorithm~\ref{alg:PrivacyPreserving}, while preserving user privacy, achieves expected regret and constraint violation guarantees, up to constants, that are no more than that of an expected equilibrium pricing approach with complete information on the distribution $\D$ from which the utility and budget parameters of users are drawn. We also note here that the assumption in Theorem~\ref{thm:PrivacyPreserving} on strictly positive and bounded prices throughout the course of Algorithm~\ref{alg:PrivacyPreserving} follows as a consequence of Assumption~\ref{asmpn:privacyPreserving}, which imposes a mild restriction on the utility distribution of the arriving users. In particular, the price of each good will be adjusted downward with probability one if its price is too high since users that have positive utility for goods with lower prices will eventually arrive. Analogously, since a certain fraction of users have strictly positive utility for each good, if the price of a good is too small, that good belongs to the optimal consumption set of such users. Note that the condition on the step size of the price updates ensures that the prices are updated in small increments at each step. This guarantees that users with strictly positive utilities for a particular good will arrive with probability one before its price drops below zero when the number of users $n$ is large. As a result, goods with low prices will eventually be purchased, thereby raising their prices and preventing them from falling below zero. We mention that the numerical experiments also verify the strict positivity and the boundedness of the prices through the operation of Algorithm~\ref{alg:PrivacyPreserving} for appropriately chosen step sizes $\gamma$ (see Section~\ref{sec:numericalMain}).

%Note that if this assumption did not hold for certain goods, those goods could be removed from the market since no user wishes to purchase them as they have no utility for it. Assumption~\ref{asmpn:privacyPreserving} ensures that the optimal equilibrium prices of all goods in the market must be strictly positive.

\begin{comment}
\begin{assumption} [Distributional Assumption] \label{asmpn:privacyPreserving}
The support of the utility parameters of users %for all goods
$[\u^{\min}, \u^{\max}]$ is such that $\u^{\max} > \0$ and the distribution $\D$ is such that the probability of observing strictly positive utilities for each good is strictly greater than zero.
\end{assumption}
We note that Assumption~\ref{asmpn:privacyPreserving} imposes a mild restriction on the set of allowable distributions from which the utility parameters of users are drawn. In particular, the assumption on the utility distribution implies that for each good, there are a certain fraction of the arriving users that have strictly positive utility for it. Note that if this assumption did not hold for certain goods, those goods could be removed from the market since no user wishes to purchase them as they have no utility for it. Assumption~\ref{asmpn:privacyPreserving} ensures that the optimal equilibrium prices of all goods in the market must be strictly positive.

%We now present the main result of this work, which establishes an $O(\sqrt{n})$ upper bound on both the regret and expected constraint violation of Algorithm~\ref{alg:PrivacyPreserving}.
\end{comment}

%In particular, note that the price of a good strictly decreases at each step if the good does not belong to the optimal consumption set of the arriving user, which will typically hold if the prices of a good are too high. However, since a certain fraction of users have strictly positive utility for each good, if the price of a good is small, that good belongs to the optimal consumption set of such users. Next, the condition on the step size of the price updates ensures that the prices are updated in small increments at each step. This guarantees that users with strictly positive utilities for a particular good will arrive with probability one before its price drops below zero when the number of users $n$ is large. As a result, goods with low prices will eventually be purchased, thereby raising their prices and preventing them from falling below zero. We mention that the numerical experiments also verify the strict positivity and the boundedness of the prices through the operation of Algorithm~\ref{alg:PrivacyPreserving} for appropriately chosen step sizes $\gamma$ (see Section~\ref{sec:numericalMain}).

\vspace{-3pt}

\subsection{Experimental Comparison of Performance of Algorithm~\ref{alg:PrivacyPreserving} to Benchmarks} \label{sec:numericalsec5}
\vspace{-2pt}
We now compare the performance of Algorithm~\ref{alg:PrivacyPreserving} to several benchmarks on both regret and constraint violation metrics. Our experimental results not only validate the theoretical bounds obtained in Theorem~\ref{thm:PrivacyPreserving} (see Appendix~\ref{apdx:theoryBoundsValidationThm3}) but also demonstrate the efficacy of Algorithm~\ref{alg:PrivacyPreserving} compared to two benchmarks with access to additional information on users' utility and budget parameters.

\emph{Overview of Benchmarks:} Our first benchmark (\emph{Stochastic Program}) assumes knowledge of the distribution $\D$ from which users' budget and utility parameters are drawn, as with an algorithm that sets expected equilibrium prices, and involves solving a stochastic program to set prices. The second benchmark (\emph{Dynamic Learning SAA}) assumes that users' utility and budget parameters are revealed to the central planner when they enter the market. In this benchmark, a sampled version of the Eisenberg-Gale program is solved with the observed budget and utility parameters of users that have previously arrived to set prices for subsequent users. For a more detailed discussion of these benchmarks and the numerical implementation details, we refer to Appendix~\ref{apdx:numericalBenchmarks}.

\emph{Comparisons between Algorithm~\ref{alg:PrivacyPreserving} and Benchmarks:} We now compare Algorithm~\ref{alg:PrivacyPreserving} and the two benchmarks on regret and constraint violation metrics. The left of Figure~\ref{fig:comparisonPlot} depicts the ratio of the regret and the optimal offline objective of the three algorithms, and the right of Figure~\ref{fig:comparisonPlot} depicts the ratio between their constraint violation and the capacities of the goods. From this figure, we observe that while Algorithm~\ref{alg:PrivacyPreserving} incurs a higher regret than the two benchmarks, it does not violate any capacity constraints. A zero constraint violation of Algorithm~\ref{alg:PrivacyPreserving} for the tested problem instance depicted in Figure~\ref{fig:comparisonPlot} is attributable to a higher regret, as not all resources are getting consumed during the operation of Algorithm~\ref{alg:PrivacyPreserving}. However, we note that, in general, the constraint violation of Algorithm~\ref{alg:PrivacyPreserving} for different problem instances, i.e., distributions $\D$ of the utility and budget parameters, may be non-zero, as depicted through additional experiments in Appendix~\ref{apdx:AddVMult}.

On the other hand, we observe from Figure~\ref{fig:comparisonPlot} that both the benchmarks violate capacity constraints to achieve an overall lower regret. As a result, Figure~\ref{fig:comparisonPlot} highlights a fundamental trade-off between regret and constraint violation and underscores the practical viability of Algorithm~\ref{alg:PrivacyPreserving} as it achieves a social welfare efficiency loss (i.e., the ratio between the regret and the optimal offline objective) of only about $5 \%$ for a market with $5000$ users while not violating capacity constraints. We further reiterate that Algorithm~\ref{alg:PrivacyPreserving} achieves the performance depicted in Figure~\ref{fig:comparisonPlot} without relying on the additional assumptions on users' budget and utility parameters the two benchmarks require.

%\color{blue} Finally, we note that a zero constraint violation of Algorithm~\ref{alg:PrivacyPreserving} for the tested problem instance depicted in Figure~\ref{fig:comparisonPlot} is attributable to a higher regret, as not all resources are getting consumed during the operation of Algorithm~\ref{alg:PrivacyPreserving}. However, we note that, in general, the constraint violation of Algorithm~\ref{alg:PrivacyPreserving} for different problem instances, i.e., distributions $\D$ of the utility and budget parameters, may be non-zero, as depicted through additional experiments in Appendix~\ref{apdx:AddVMult}. \color{black}

\vspace{-8pt}
\begin{figure}[tbh!]
\centering
\includegraphics[width=0.65\linewidth]{Figures/CompAlgo2Benchmarks_v2.png}
\vspace{-10pt}
\caption{{\small \sf Comparison between Algorithm~\ref{alg:PrivacyPreserving} and the two benchmarks presented in Section~\ref{sec:benchmarks} on regret and constraint violation metrics. While Algorithm~\ref{alg:PrivacyPreserving} incurs a higher regret than the two benchmarks, it does not violate any capacity constraints. On the other hand, the two benchmarks violate the capacity constraints to achieve an overall lower level of regret.
\label{fig:comparisonPlot}
\end{figure} \vspace{-10pt}

\begin{comment}
\section{Numerical Experiments} \label{sec:numericalMain}

We now compare the performance of Algorithm~\ref{alg:PrivacyPreserving} to several benchmarks on both regret and constraint violation metrics. The results of our experiments not only validate the theoretical bounds obtained in Theorem~\ref{thm:PrivacyPreserving} but also demonstrate the efficacy of Algorithm~\ref{alg:PrivacyPreserving} as compared to two benchmarks that have access to additional information on users' utility and budget parameters. In this section, we introduce two benchmarks to which we compare Algorithm~\ref{alg:PrivacyPreserving} (Section~\ref{sec:benchmarks}), describe the implementation details of Algorithm~\ref{alg:PrivacyPreserving} and the benchmarks (Section~\ref{sec:impl-details}), and present results to demonstrate the performance of Algorithm~\ref{alg:PrivacyPreserving} (Section~\ref{sec:results}). %We additionally present numerical experiments to compare the performance of Algorithm~\ref{alg:PrivacyPreserving} with an additive price update step to that with a multiplicative price update step, presented in Equation~\eqref{eq:multiplicativeUpdate}, in Appendix~\ref{apdx:AddVMult}.

\subsection{Benchmarks} \label{sec:benchmarks}

In our experiments, we compare Algorithm~\ref{alg:PrivacyPreserving} to two benchmarks, akin to several classical algorithms developed in the online resource allocation literature~\cite{li2021online,online-agrawal}, with additional information on users' utility and budget parameters. In particular, the first benchmark assumes knowledge of the distribution $\D$ from which the budget and utility parameters are drawn, as is the case for an algorithm that sets expected equilibrium prices. The second benchmark assumes that users' utility and budget parameters are revealed to the central planner when they enter the market and can be used to set prices for subsequent users. We mention that these algorithms are solely for benchmark purposes, and thus we do not discuss the practicality of the corresponding informational assumptions of these benchmarks. We also reiterate that, as opposed to these benchmarks, the price updates in Algorithm~\ref{alg:PrivacyPreserving} only rely on users' revealed preferences rather than relying on additional information on their budget and utility parameters.

\paragraph{Stochastic Program:}

We begin with the benchmark wherein the distribution $\D$ from which the budget and utility parameters are generated i.i.d. is known. In this case, the SAA Problem~\eqref{eq:SAA2} is related to the following stochastic program
\begin{equation} \label{eq:stochastic2}
\begin{aligned}
\min_{\mathbf{p}} \quad & D(\p) = \sum_{j = 1}^m p_j d_j + \mathbb{E}_{(w,\u) \sim \D }\left[\left(w \log \left(w\right)-w \log \left(\min _{j \in [m]} \frac{p_{j}}{u_{j}}\right)-w\right)\right],
\end{aligned}
\end{equation}
which can be solved to give an optimal price vector $\p^*$. Note that this price vector $\p^*$ corresponds to the static expected equilibrium price, as it takes an expectation over the distribution $\D$. The corresponding pricing policy $\ppi$ only depends on the distribution $\D$ is thus given by $\p^t = \p^* = \pi_t(\D)$ for all users $t \in [n]$. Given the price vector $\p^*$, all arriving users will purchase an affordable utility-maximizing bundle of goods by solving their individual optimization Problem~\eqref{eq:Fisher1}-\eqref{eq:Fishercon3}. Note here that the price vector $\p^*$ is computed before the online procedure, which is possible due to the prior knowledge of the distribution $\D$. For numerical implementation purposes, we consider a sample average approximation to compute the expectation in Problem~\eqref{eq:stochastic2}, as elucidated in Section~\ref{sec:impl-details}.

\paragraph{Dynamic Learning using SAA:}

In this benchmark, we consider the setting wherein users' budget and utility parameters are revealed to the central planner each time a user arrives. In this context, the prices are set based on the dual variables of the capacity constraints of the sampled Eisenberg-Gale program with the observed budget and utility parameters of agents that have previously arrived. That is, the pricing policy $\ppi$ depends on the history of users' budget and utility parameters, i.e., $\p^t = \pi_t((w_{t'}, \u_{t'})_{t' = 1}^{t-1})$. We note that to improve on the computational complexity, we update the dual prices at geometric intervals, as in earlier work~\cite{li2021online,online-agrawal}. Users arriving in each interval observe the corresponding price vector for that interval and solve their individual optimization problems to obtain their most favorable goods under the set prices. We formally present the algorithm for this benchmark in Appendix~\ref{apdx:dynamicLearningSAA}.
\end{comment}

\begin{comment}
\subsection{Implementation Details} \label{sec:impl-details}

To numerically evaluate the performance of Algorithm~\ref{alg:PrivacyPreserving} and the benchmarks, we consider a market instance of $m = 5$ goods, each with a capacity of $10 n$ when there are $n$ users in the market. Each arriving user's budget and utility parameters are generated i.i.d. from a probability distribution $\D$, specified as follows. In particular, each user's budget can take on one of three values: $2$, $5$, or $10$, which represent users with low, medium, and high budgets, and a user can have either of these budgets with a probability of $\frac{1}{3}$. Furthermore, each user's utility for the goods is independent of their budget, and their utility for each good is drawn uniformly at random between the range $[5, 10]$. We choose a continuous utility distribution to validate the theoretical regret and constraint violation guarantee in Theorem~\ref{thm:PrivacyPreserving}, as Algorithm~\ref{alg:PrivacyPreserving} applies for general (non-discrete) probability distributions. Since this utility distribution is continuous, the adaptive expected equilibrium pricing algorithm (Algorithm~\ref{alg:AlgoProbKnownDiscrete}) does not apply in this setting. Thus, we focus on comparing Algorithm~\ref{alg:PrivacyPreserving} to the two benchmarks in this section and refer to Appendix~\ref{apdx:staticVdynamic} for numerical experiments comparing Algorithm~\ref{alg:AlgoProbKnownDiscrete} to a static expected equilibrium pricing approach.

Under the above defined market instance, we implement Algorithm~\ref{alg:PrivacyPreserving} using a step size of $\gamma = \gamma_t = \frac{1}{100 \sqrt{n}}$ for all users $t \in [n]$. Furthermore, to implement the stochastic programming benchmark, we compute the solution to Problem~\eqref{eq:stochastic2} using a sample average approximation with $5000$ samples of budget and utility parameters generated from the above described distribution $\D$ to evaluate the expectation.

\subsection{Results} \label{sec:results}

\paragraph{Assessment of Theoretical Bounds:}

We first assess the theoretical bounds on the regret and constraint violation obtained in Theorem~\ref{thm:PrivacyPreserving}. To this end, Figure~\ref{fig:theoryBounds} depicts the infinity norm of the constraint violation (right) and a log-log plot of the regret of Algorithm~\ref{alg:PrivacyPreserving}. As expected, the black dots representing the empirically observed regret of Algorithm~\ref{alg:PrivacyPreserving} on the market instance described in Section~\ref{sec:impl-details} are very close to the theoretical $O(\sqrt{n})$ upper bound, represented by a line with a slope of $0.5$ on the log-log plot. On the other hand, the empirical results for the constraint violation (right of Figure~\ref{fig:theoryBounds}) of Algorithm~\ref{alg:PrivacyPreserving} indicate that no good capacities are violated. As a result, the $O(\sqrt{n})$ upper bound on the constraint violation is also satisfied.

%We note that for the tested problem instance the

\begin{figure}[tbh!]
\centering
\includegraphics[width=0.85\linewidth]{Figures/OFM_TheoryBounds.png}
\caption{Validation of theoretical regret and constraint violation upper bounds of Algorithm~\ref{alg:PrivacyPreserving} on market instance described in Section~\ref{sec:impl-details}. The regret of Algorithm~\ref{alg:PrivacyPreserving} is presented on a log-log plot (left), and the empirically observed performance, represented by the black dots, is very close to the theoretical $O(\sqrt{n})$ bound, represented by a line of slope $0.5$. The infinity norm of the excess demand is zero for all instances and thus trivially satisfies the $O(\sqrt{n})$ upper bound on the constraint violation.
\label{fig:theoryBounds}
\end{figure}

\paragraph{Comparisons between Algorithm~\ref{alg:PrivacyPreserving} and Benchmarks:}

We now compare Algorithm~\ref{alg:PrivacyPreserving} and the two benchmarks on regret and constraint violation metrics. The left of Figure~\ref{fig:comparisonPlot} depicts the ratio of the regret and the optimal offline objective of the three algorithms, and the right of Figure~\ref{fig:comparisonPlot} depicts the ratio between their constraint violation and the capacities of the goods. From this figure, we observe that while Algorithm~\ref{alg:PrivacyPreserving} incurs a higher regret than the two benchmarks, it does not violate any capacity constraints. On the other hand, both the benchmarks violate capacity constraints to achieve an overall lower regret. This observation highlights the fundamental trade-off between regret and constraint violation and underscores the practical viability of Algorithm~\ref{alg:PrivacyPreserving} as it achieves a social welfare efficiency loss (i.e., the ratio between the regret and the optimal offline objective) of only about $5 \%$ for a market with $5000$ users while not violating capacity constraints. We further reiterate that Algorithm~\ref{alg:PrivacyPreserving} achieves the performance depicted in Figure~\ref{fig:comparisonPlot} without relying on the additional assumptions on users' budget and utility parameters the two benchmarks require.

\color{blue} Finally, we note that a zero constraint violation of Algorithm~\ref{alg:PrivacyPreserving} for the tested problem instance depicted in Figure~\ref{fig:comparisonPlot} is attributable to a higher regret, as not all resources are getting consumed during the operation of Algorithm~\ref{alg:PrivacyPreserving}. However, we note that, in general, the constraint violation of Algorithm~\ref{alg:PrivacyPreserving} for different problem instances, i.e., distributions $\D$ of the utility and budget parameters, may be non-zero, as depicted through additional experiments in Appendix~\ref{apdx:AddVMult}.

\begin{figure}[tbh!]
\centering
\includegraphics[width=0.9\linewidth]{Figures/CompAlgo2Benchmarks.png}
\caption{{\small \sf Comparison between Algorithm~\ref{alg:PrivacyPreserving} and the two benchmarks presented in Section~\ref{sec:benchmarks} on regret and constraint violation metrics. While Algorithm~\ref{alg:PrivacyPreserving} incurs a higher regret than the two benchmarks, it does not violate any capacity constraints. On the other hand, the two benchmarks violate the capacity constraints to achieve an overall lower level of regret.
\label{fig:comparisonPlot}
\end{figure}
\end{comment}

\begin{comment}
\begin{figure}[tbh!]
\centering
\begin{subfigure}[t]{0.49\columnwidth}
\centering
\include{Figures/OFM_theoryregret}
\end{subfigure} %\hspace{10pt}
\begin{subfigure}[t]{0.49\columnwidth}
\centering %\vspace{-6pt}
\include{Figures/OFM_theoryCapVio}
\end{subfigure} %\vspace{-15pt}
\caption{Validation of theoretical regret and constraint violation upper bounds of Algorithm~\ref{alg:PrivacyPreserving} on market instance described in Section~\ref{sec:impl-details}. The regret of Algorithm~\ref{alg:PrivacyPreserving} is plotted on a log-log plot (left), and the empirically observed performance, represented by the black dots, is very close to the theoretical $O(\sqrt{n})$ bound, represented by a line of slope $0.5$. The infinity norm of the excess demand is zero for all instances and thus trivially satisfies the $O(\sqrt{n})$ upper bound on the constraint violation as well.
\label{fig:theoryBounds}
\end{figure}
\end{comment}

\begin{comment}
\begin{figure}[tbh!]
\centering
\begin{subfigure}[t]{0.49\columnwidth}
\centering
\include{Figures/test_rovero}
\end{subfigure} %\hspace{10pt}
\begin{subfigure}[t]{0.49\columnwidth}
\centering
\include{Figures/test_norm}
\end{subfigure}
\caption{{\small \sf Comparison between Algorithm~\ref{alg:PrivacyPreserving} and the two benchmarks presented in Section~\ref{sec:benchmarks} on regret and constraint violation metrics.
\label{fig:comparisonPlot}
\end{figure}
\end{comment}

\section{Conclusion and Future Work} \label{sec:conclusion}
\ifarxiv
In this work, we studied an online variant of Fisher markets wherein users with linear utilities arrive sequentially and have privately known budget and utility parameters drawn i.i.d. from some distribution $\D$. \ifarxiv Since classical approaches for market equilibrium computation are not suitable in this online incomplete information setting, we studied the problem of setting prices online to minimize regret and constraint violation. \fi In this setting, we first established that no static pricing algorithm, including an algorithm that sets expected equilibrium prices with complete information of the distribution $\D$, can achieve a regret and constraint violation of less than $\Omega(\sqrt{n})$ (where $n$ is the number of users). Given the performance limitations of static pricing, we developed adaptive pricing algorithms with improved performance guarantees. To this end, we first developed an adaptive expected equilibrium pricing approach with $O(\log(n))$ regret and constant constraint violation for discrete probability distributions $\D$. For the setting of general probability distributions (and when the distribution $\D$ is unknown), we proposed an online learning approach to adjust prices solely based on users' revealed preferences, i.e., past observations of user consumption, thereby preserving user privacy. Our revealed preference algorithm has a computationally efficient price update rule that makes it practically viable and achieves an $O(\sqrt{n})$ upper bound on the expected regret and constraint violation. \ifarxiv Finally, we used numerical experiments to evaluate the efficacy of our proposed revealed preference algorithm, which highlighted a fundamental trade-off between the regret and constraint violation measures. \fi

\else

In this work, we studied an online variant of Fisher markets wherein users with linear utilities arrive sequentially and have privately known budget and utility parameters drawn i.i.d. from some distribution $\D$. In this setting, we established the performance limits of static pricing algorithms and developed adaptive pricing algorithms with improved performance guarantees. In particular, we developed an adaptive expected equilibrium pricing approach with $O(\log(n))$ regret and constant constraint violation for discrete distributions $\D$ (where $\D$ is known). Furthermore, we developed a revealed preference algorithm with an $O(\sqrt{n})$ upper bound on the expected regret and constraint violation for general probability distributions (where $\D$ is unknown). Notably, our revealed preference approach only relies on past observations of user consumption, thereby preserving user privacy, and has a computationally efficient price update rule that makes it practically viable.

\fi

%In this work, we studied an online variant of Fisher markets wherein users with linear utilities arrive into the market sequentially and have budget and utility parameters drawn i.i.d. from an unknown distribution. While a central planner can derive equilibrium prices by solving a convex optimization problem in classical Fisher markets in the offline setting, such an approach is practically infeasible in many real-world settings where users arrive in the market sequentially with privately known budgets and utilities. As a result, we proposed an online learning approach to set prices on the goods in the market without relying on any information on each user's budget and utility parameters. In particular, our algorithm adjusts the prices of the goods at each time a user arrives solely based on the past observations of user consumption, thereby preserving user privacy, and has a computationally efficient price update rule that makes it practically viable. Furthermore, we established that our approach achieves an $O(\sqrt{n})$ (where $n$ is the number of users) upper bound on the expected regret and constraint violation and that an algorithm that sets expected equilibrium prices with complete information on the distribution $\D$ cannot achieve both a regret and constraint violation of better than $\Omega(\sqrt{n})$. We established these results in the setting when the capacities of the goods scale with the number of users, i.e., $c_j = O(n)$ for all goods $j$, which implies a vanishing ratio between the constraint violation of Algorithm~\ref{alg:PrivacyPreserving} and the corresponding good capacities. Finally, we used numerical experiments to evaluate the efficacy of our proposed approach relative to several natural benchmarks. Our experiments validated our theoretical regret and constraint violation upper guarantees and highlighted a fundamental trade-off between the regret and constraint violation performance measures.

There are several directions for future research. First, as we obtained a lower bound on the regret and constraint violation of static pricing algorithms (Theorem~\ref{thm:lbStatic}), it would be worthwhile to develop algorithm-independent lower bounds to characterize the performance limits of adaptive pricing algorithms for online Fisher markets. Next, while Algorithm~\ref{alg:AlgoProbKnownDiscrete} achieved an $O(\log(n))$ regret and constant constraint violation for discrete distributions, it would be interesting to study whether adaptive pricing algorithms can achieve a performance better than the $O(\sqrt{n})$ regret and constraint violation of the revealed preference algorithm (Algorithm~\ref{alg:PrivacyPreserving}) for general probability distributions. There is also scope to generalize the model studied in this work to settings with more general concave utility functions, e.g., homogeneous degree one utilities, beyond linear utilities, and study settings beyond the stochastic input model of user arrival, e.g., the random permutation model. %Finally, it would also be interesting to investigate whether there are bandit problems where the weighted geometric mean objective studied in this work is more applicable than the traditionally used linear objectives.