Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
46,273 characters · 12 sections · 28 citation commands
Doubly Fair Dynamic Pricing
Pricing problems have been studied since cournot1897researches. In a classical pricing problem setting such as kleinberg2003value, broder2012dynamic, besbes2015surprising, the seller (referred as “we”) sells identical products in the following scheme.
\fbox{\parbox{0.98\textwidth}{Online pricing. For $t=1,2,\ldots, T$:
} }
Here $T$ is the time horizon known to the seller in advance\footnote{Here we assume $T$ known for simplicity of notations. In fact, if $T$ is unknown, then we may apply a “doubling epoch” trick as javanmard2019dynamic and the regret bounds are the same.}, and $y_t$'s are drawn from a fixed distribution independently. The goal is to approach an optimal price that maximizes the expected revenue-price function. In order to make this, we should learn gradually from the binary feedback and improve our knowledge on customers' valuation distribution (or so-called “demands” kleinberg2003value).
In recent years, with the development of price discrimination and personalized pricing strategies, fairness issues on pricing arose social and academic concerns kaufmann1991fairness, chapuis2012price, richards2016personalized, eyster2021pricing. Customers are usually not satisfied with price discrimination, which would in turn undermine both their willing to purchase and the sellers' reputation. In the online pricing problem defined above, when we are selling identical items to customers from different groups (e.g., divided by gender, race, age, etc.), it can be unfair if we propose a specific optimal price for each group: These optimal prices in different groups are not necessarily the same, and unfairness occurs if different customers are provided or buying the same item with different prices. Inspired by the concept of procedural and substantive unconscionabilityelfin1988future, we define a procedural unfairness measuring the difference of proposed prices between the two groups, and a substantive unfairness measuring that of \emph{accepted prices} between the two groups. Given these notions, our goal is to approach the optimal pricing policy that maximizes the expected total revenue with no procedural and substantive unfairness.
{ The concept of procedural fairness has been well established in cohen2022price as “price fairness”, while the concept of the substantive fairness is new to this paper. In fact, both procedural and substantive fairness have significant impacts on customers' experience and social justice. For instance, these notions help prevent the following two scenarios:
Therefore, a good pricing strategy has to satisfy both procedural and substantive fairness. }
However, these constraints are very hard to satisfy even with full knowledge on customers' demands. If we want to fulfill those two sorts of fairness perfectly by proposing deterministic prices for different groups, the only thing we can do is to trivially set the same price in all groups and to maximize the weighted average revenue function by adjusting this uniformly fixed price with existing methods such as kleinberg2003value. Consider the following example:
In (ref), the only way to guarantee both fairness constraints is to propose the same price for both groups, and the optimal price is \$1 whose expected revenue is $\mathit{\$0.5}$ as is shown in the figure.
However, if we instead propose a random price distribution to each group and inspect those fairness notions in expectation, then there may exist price distributions that satisfy both fairness constraints and achieve higher expected revenue than any fixed-price strategy. Here a price distribution is the distribution over the prices for customers, and the exact price for each customer is sampled from this distribution independently. This random price sampling process can be implemented by marketing campaigns such as random discounts or randomly-distributed coupons. Again, we consider (ref) and the following random policy:
Under this policy, the expected proposed price and the expected accepted price in both groups are $\mathit{\$\frac{43}{58}}$ and $\mathit{\$\frac8{11}}$ respectively. Furthermore, the expected revenue is $\mathit{\$\frac{74}{145}}>\mathit{\$0.5}$, which means that this random policy performs better than the best fixed-price policy. It is worth mentioning that this is exactly the optimal random policy in this specific setting, but the proof of its optimality is highly non-trivial (and we put it in (ref) as part of the proof of (ref) ).
In this work, we consider a two-group setting and we denote a policy as the tuple of two price distributions over the two groups respectively. Therefore, we can formally define the optimal policy as follows:
Here $\pi^1, v_t^1, y_t^1, \mathbb{D}^1$ and $\pi^2, v_t^2, y_t^2, \mathbb{D}^2$ are the proposed price distributions, proposed prices, customer's valuations and valuation distributions of Group 1 and Group 2 respectively, and $q$ is the proportion of Group 1 among all customers. From (ref), the optimal policy under the in-expectation fairness constraints should be random in general\footnote{Notice that a fixed-price policy can also be considered as “random”.}. However, even we know the exact $\mathbb{D}^1$ and $\mathbb{D}^2$, it is still a very hard problem to get $\pi_*$: Both sides of the second constraint in (ref) are conditional expectations (i.e., fractions of expected revenue over expected acceptance rate) and is thus not convex ( and also not quasiconvex). To make it harder, the seller actually has no direct access to customers' demands $\mathbb{D}^1$ and $\mathbb{D}^2$ at the beginning. Therefore, in this work we consider a $T$-round online learning and pricing setting, where we could learn these demands from those Boolean-censored feedback (i.e., customers' decisions) and improve our pricing policy to approach $\pi_*$ in (ref).
In order to measure the performance of a specific policy, we define a regret metric that equals the expected revenue difference between this policy and the optimal policy. We also quantify the procedural and substantive unfairness that equals the absolute difference of expected proposed/accepted prices in two groups. We will establish a more detailed problem setting in (ref).
\paragraph{Summary of Results} Our contributions are threefold:
To the best of our knowledge, we are the first to study a pricing problem with multiple fairness constraints, where the optimal pricing policy is necessary to be random. We also develop an algorithm that is able to approach the best random pricing policy with high probability and at the least cost of revenue and fairness.
\paragraph{Technical Novelty.} Our algorithm is a “conservative policy-elimination”-based strategy that runs in epochs with doubling batch sizes as in auer2002finite. We cannot directly apply the action-elimination algorithm for multi-armed bandits as in cesa2013online, because the policy space is an infinite set and we cannot afford to try each one out. The fairness constraints further complicate things. Our solution is to work out just a few representative policies that are “good-and-exploratory”, which can be used to evaluate the revenue and fairness of all other policies, then eliminate those that are unfair or have suboptimal revenue. Since we do not have direct access to the demand function, the estimated fairness constraints are changing over epochs due to estimation error, it is non-trivial to keep the target optimal policy inside our “good policy set” during iterations. We settle this issue by setting the criteria of a “good policy” conservatively.
Our lower bound is new too and it involves techniques that could be of independent interest to the machine learning theory community. Notice that it is possible to have a perfectly fair algorithm by trivially proposing the same fixed price for both groups. It is highly non-trivial to show the unfairness lower bound within the family of regret-optimal algorithms. We present our result in (ref) by establishing two similar problem settings that any algorithm cannot distinguish them efficiently and showing that a mismatch would cause a compatible amount of regret and substantive unfairness.
Here we discuss some literature that are closely related to this work. For a broader discussion, please refer to (ref).
\paragraph{Dynamic Pricing} Single product dynamic pricing problem has been well-studied through kleinberg2003value, besbes2009dynamic, wang2014close, chen2019nonparametric, wang2021multimodal. The crux is to learn and approach the optimal of a revenue curve from Boolean-censored feedback. In specific, kleinberg2003value proves $\Theta(\log\log{T}), \Theta(\sqrt{T})$ and $\Theta(T^{\frac23})$ minimax regret bounds under noise-free, infinitely smooth and stochastic/adversarial valuation assumptions, sequentially. wang2021multimodal further shows a $\Theta(T^{\frac{K+1}{2K+1}})$ minimax regret bound for $K^{\text{th}}$-smooth revenue functions. In all these works, the decision space is continuous. In our problem setting, we fix the proposed prices to be chosen in a fixed set of $d$ prices, and show a bandit-style $\Omega(\sqrt{dT})$ regret lower bound with a similar method to auer2002nonstochastic.
\paragraph{Fairness in Machine Learning} Fairness is a long-existing topic that has been extensively studied. In the machine learning community, fairness is defined from mainly two perspectives: the group fairness and the individual fairness. In a classification problem, for instance, dwork2012fairness defines these two notions as follows: (1) A group fairness requires different groups to have identical result distributions in statistics, which further includes the concepts of “demographic parity” (predictions independent to group attributes) and “equalized odds” (predictions independent to group attributes conditioning on the true labels). In agarwal2018reductions, these group fairness are reduced to linear constraints. The two fairness definitions we make in this work, the procedural fairness and the substantive fairness, belong to group fairness. (2) An individual fairness hardt2016equality requires the difference of predictions on two individuals to be upper bounded by a distance metric of their intrinsic features. The notion “time fairness” is often considered as individual fairness as well. { We provide a more detailed discussion on the line of work that address fairness concerns or stochastic constraints with online learning techniques in (ref).}
\paragraph{Fairness in Pricing} Recently there are many works contributing to pricing fairness problems kaufmann1991fairness, frey1993fairness, chapuis2012price, richards2016personalized, priester2020special, eyster2021pricing,yang2022fairness. As is stated in cohen2022price, in a pricing problem with fairness concerns, the concept of fairness in existing works is modeled either as a utility or budget that trades-off the revenue or as a hard constraint that prevent us from taking the best action directly.cohen2022price chooses the second model and defines four different types of fairness in pricing: price fairness, demand fairness, surplus fairness and no-purchase valuation fairness, each of which indicates the difference of prices, the acceptance rate, the surplus (i.e., (valuation $-$ price) if bought and 0 otherwise) and the average valuation of not-purchasing customers in two groups is bounded, sequentially. They show that it is impossible to achieve any pair of different fairness notions simultaneously (with deterministic prices). In fact, this can be satisfied if they allow random pricing policies. maestre2018reinforcement indeed builds their fairness definition upon random prices by introducing a “Jain's Index”, which indicates the homogeneity of price distributions among different groups (i.e., our procedural fairness notion). They develop a reinforcement-learning-based algorithm to provide homogeneous prices, with no theoretic guarantees.
cohen2021dynamic and chen2021fairness study the online-learning-fashion pricing problem as we do. cohen2021dynamic considers both group (price) fairness and individual (time) fairness, and their algorithm FaPU solves this problem with sublinear regret while guaranteeing fairness. They further study the pricing problem with demand fairness that are unknown and needs learning. In this setting, they propose another FaPD algorithm that achieves the optimal $\tilde O(\sqrt{T})$ regret and guarantees the demand fairness “almost surely”, i.e., upper bounded by $\delta\cdot T$ as a budget. chen2021fairness considers two different sorts of fairness constraints: (1) Price fairness constraints (as in cohen2022price) are enforced; (2)Price fairness constraints are generally defined (and maybe not accessible), where they adopt “soft fairness constraints” by adding the fairness violation to the regret with certain weights. In both cases, they achieve $\tilde{O}(T^{\frac45})$ regrets. These learning-based fairness requirements are quite similar to our problem setting, but in our setting the fairness constraints are non-convex (while theirs are linear) and are also optimized to corresponding information-theoretic lower bounds without undermining the optimal regret.
In this section, we describe the problem setting of online pricing, introduce new fairness definitions and set the goal of our algorithm design.
\paragraph{Problem Description.} We start with the online pricing process. The whole selling session involves customers from two groups ($G_1$ and $G_2$) and lasts for $T$ rounds. Prices are only allowed to be chosen from a known and fixed set of $d$ prices: $\mathbf{V} = \{v_1, v_2, \ldots, v_d\}$, where $0<v_1<v_2<\ldots<v_d\leq1$. Denote $\Delta^d = \{x\in\mathbb{R}_+^d, \|x\|_1 = 1\}$ as the probabilistic simplex. At each time $t=1,2,\ldots, T$, we propose a pricing policy $\pi = (\pi^1, \pi^2)$ consisting of two probabilistic distributions $\pi^1, \pi^2\in\Delta^d$ over all $d$ prices. A customer then arrives with an observable group attribution $G_e$ ($e\in\{1,2\}$), and we propose a price by sampling a $v_t^e$ from $\mathbf{V}$ according to distribution $\pi^e$. At the same time, the customer generates a valuation $y_t^e$ in secret, where $y_t^e$ is sampled independently and identically from some fixed unknown distribution $\mathbb{D}_e$. Afterward, we observe a feedback $\mathbf{1}_t^e = \mathbf{1}(v_t^e\leq y_t^e)$ and receive a reward(revenue) $r_t^e = \mathbf{1}_t^e\cdot v_t^e$.
\paragraph{Key Quantities.}
Here we define a few quantities and functions that is necessary to formulate the problem. Denote $\mathbf{v}:=[v_1, v_2, \ldots, v_d]^{\top}$, $[d]:=\{1,2,\ldots, d\}$ and $\mathds{1}:=[1,1,\ldots, 1]^{\top}\in\mathbb{R}^d$ for simplicity. Denote $F_e(i):=\Pr_{\mathbb{D}_e}[y_t^e\geq v_i], e=1,2, i\in[d]$ as the probability of price $v_i$ being accepted in $G_e$, and we know that $F_e(1)\geq F_e(2)\geq\ldots\geq F_e(d)$. Notice that all $F_e(i)$'s are unknown to us. Define a matrix $F_e := \mathrm{diag}(F_e(1), F_e(2), \ldots, F_e(d))$.
As a result, for a customer from $G_e$ ($e\in\{1,2\}$), we know that
Denote the proportion of $G_1$ in all potential customers as $q$ ($0<q<1$) which is fixed and known to us, and we assume that every customer is chosen from all potential customers uniformly at random. As a consequence, we can define the expected revenue of a policy $\pi$.
Also, we can define the two different unfairness notions based on these results above.
Procedural unfairness is totally tractable as we have full access to $\mathbf{v}^{\top}$ and $\pi$. Therefore, we can define a policy family $\Pi:=\{\pi=(\pi^1, \pi^2), U(\pi)=0\}$ that contains all policies with no procedural unfairness. Now we define a substantive unfairness as another metric.
Substantive unfairness is not as tractable as procedural unfairness, as we have no direct access to the true $F_1$ and $F_2$. Ideally, the optimal policy that we would like to achieve is:
The feasibility of this problem is trivial: policies such as $\pi^1 = \pi^2 = [0, \ldots, 0,1,0,\ldots,0]^{\top}$ (i.e., proposing the same fixed price despite the customer's group attribution) are always feasible. However, this problem is in general highly non-convex and non-quasi-convex. Finally, we define a (cumulative) regret that measure the performance of any policy $\pi$:
Notice that we define the per-round regret by comparing the performance of $\pi_t$ with the optimal policy $\pi_*$ under constraints. Therefore, $Reg(\pi_t; F_1, F_2)$ is possible to be negative if $\pi\in\Pi$ but $U(\pi_t) > 0\text{ or } S(\pi_t; F_1, F_2) > 0$. Similarly, we define a cumulative substantive unfairness as $S_T(\mathcal{A}):=\sum_{t=1}^T S(\pi; F_1, F_2)$.
\paragraph{Goal of Algorithm Design} Our ultimate goal is to approach $\pi_*$ in the performance. In the online pricing problem setting we adopt, however, we cannot guarantee $S(\pi_t; F_1, F_2)=0$ for all $\pi_t$ we propose at time $t=1,2,\ldots, T$ since we do not know $F_1$ and $F_2$ in advance. Instead, we may suffer a gradually vanishing unfairness as we learn $F_1$ and $F_2$ better. Therefore, our goal in this work is to design an algorithm that guarantees an optimal regret while suffering $0$ cumulative procedural unfairness and the least cumulative substantive unfairness.
\paragraph{Technical Assumptions.} Here we make some mild assumptions that help our analysis.
(ref) not only ensures the definition of expected accepted price to be sound (by ruling out these unacceptable prices), but also implies $S(\pi, F_1, F_2)$ to be Lipschitz. Besides, we can always achieve this by reducing $v_d$. We will provide a detailed discussion in (ref).
(ref) is a necessary condition of applying $\Omega(\sqrt{dT})$ regret lower bound, and here we make it to show the optimality of our algorithm w.r.t. $T$.
In this section, we propose our Fairly Pricing Algorithm (FPA) in Algorithm 1 and then discuss the techniques we develop and apply to achieve the “no-regret” and “no-unfairness” goal.
(ref) takes the following inputs: time horizon $T$, price set $\mathbf{V}$, error probability $\epsilon$, a universal constant $L$ { as the coefficient of the performance-fairness tradeoff on constraint relaxations} (see (ref)), and $q$ as the proportion that $G_1$ takes. In the “before epochs” stage, we keep proposing the highest price $v_d$ for $\tau_0=O(\log T)$ rounds to estimate(lower-bound) the least acceptance rate $F_{\min}$. We also adopt the following techniques that serve as components of FPA and contribute to its no-regret and no-unfairness performance.
\paragraph{Doubling Epochs} Despite the “before epochs” stage, we divide the whole time space into epochs $k=1,2,\ldots$, where each epoch $k$ has a length $\tau_k=O(\sqrt{T}\cdot2^k)$ that doubles that of epoch $(k-1)$. Within each epoch $k$, we run a set of “good-and-exploratory policies” (to be introduced in (ref)) with equal shares of $\tau_k$. At the end of each epoch $k$, we update the estimates of $F_1$ and $F_2$, eliminate the sub-optimal policies and update the set of “good-and-exploratory policies” for the next epoch. Since the estimates of parameters get better as $k$ increases, a doubling-epoch trick would ensure that we run better policies in longer { epochs} and therefore save the regret.
\paragraph{Policy Eliminations} At the end of each epoch $k$, we update the candidate policy set by eliminating those substantially sub-optimal policies: Firstly, we select an empirical optimal policy $\hat{\pi}_{k,*}$ that maximizes $R(\pi,\hat{F}_{k,1}, \hat{F}_{k,2})$ while guaranteeing $S(\pi,\hat{F}_{k,1}, \hat{F}_{k,2})\leq\delta_{k,s}$. After that, we eliminate those policies that satisfy one of the following two criteria:
Here we adopt two subtractors on the regret criteria: $\delta_{k,r}$ for the estimation error in $R(\pi)$ caused by $\hat{F}_{k,e}$, and $L\cdot\delta_{k,s}$ for the possible increase of optimal reward by allowing $S(\pi)\leq \delta_{k,s}$ instead of $S(\pi)=0$. In this way, we can always ensure the optimal policy $\pi_*$ (i.e., the solution of (ref)) to remain and also guarantee the other remaining policies perform similarly to $\pi_*$.
\paragraph{Good-and-Exploratory Policies} Although all remaining policies perform good, not all of them are suitable of running in consideration of exploration. It is important to update the estimates of all $F_1(i)$ and $F_2(i)$ as they are required in the policy elimination. We solve this issue by keeping a set of good-and-exploratory policies: After eliminating sub-optimal policies at the end of previous epoch, for each price $v_i$ in group $G_e$ we find out a policy in the remaining policies that maximizes the probability of proposing $v_i$ in $G_e$ at the beginning of current epoch. The larger this probability is, the more times $v_i$ can be chosen in $G_e$, which would lead to a better estimate of $F_e(i)$. Here we give up to estimate the acceptance probability of those $v_i$ with $\leq\frac1{\sqrt{T}}$ to be chosen by the optimal policy $\pi_*$, as it would not affect the elimination process and the performance substantially.
Our FPA algorithm is oracle-efficient due to the doubling-epoch design, as we only run each oracle and update each parameter for $O(\log T)$ times. However, the implementation of these oracles could be time-consuming: On the one hand, each set $\Pi_k$ contains infinite policies, and a discretization would lead to exponential computational cost w.r.t. $d$. On the other hand, both (ref) and (ref) are highly non-convex on the constraints and are hard to solve with off-the-shelf methods.
In this section, we analyze the regret and unfairness of our FPA algorithm. We first present an $\tilde{O}(\sqrt{T}d^{\frac32})$ regret upper bound along with an $\tilde{O}(\sqrt{T}d^{\frac32})$ unfairness upper bound. Then we show both of them are optimal (w.r.t. $T$) up to $\log\log T$ factors by presenting matching lower bounds.
First of all, we propose the following theorem as the main results for our (ref) (FPA).
Here we show the regret lower bound of this pricing problem.
We may prove (ref) by a reduction to online pricing problem with no fairness constraints: Given a problem setting where the two groups are identical, i.e. $F_1(i)=F_2(i), \forall i\in[d]$, and let $q=0.5$. Notice that any policy satisfying $\pi^1=\pi^2$ is fair, and the optimal policy is to always propose the best fixed price. Therefore, this can be reduced to an online identical-product pricing problem, and we present a bandit-style lower bound proof in (ref) inspired by auer2002nonstochastic.
Here we show that any optimal algorithm has to suffer an $\Omega(\sqrt{T})$ substantive unfairness.
It is worth mentioning that this result is different from ordinary lower bounds on the regret, as it also requires the algorithm to be optimal. In general, we propose 2 different problem settings, and we show the following four facts:
In order to prove this, we make use of (ref) presented in (ref). One of the settings is exactly (ref), and the other one is identical to it except these $0.5$ probabilities are now $(0.5-\zeta)$ in both groups. We get close-form solutions to both problem settings and show that they are indistinguishable in information theory. Please refer to (ref) for more details.
Here we discuss some open issues and potential extensions of this work. For more discussions on settings, techniques and social impacts, please refer to (ref).
\paragraph{Improvement on Technical Assumptions.} In this work, we assumed the existence of a lower bound $F_{\min}>0$ of the acceptance rate of all prices for both groups. This assumption is stronger than our expectation, as the seller would not know the highest price that customers would accept. We assume this for two reasons: (1) Without assuming $F_e(i)>0$, the substantive unfairness function might be undefined. For instance, if a pricing policy is completely unacceptable in $G_1$ (with no accepted prices) but is acceptable in $G_2$, then is it a fair policy? (2) With a constantly large probability of acceptance, we can estimate every $F_e(i)$ and bound it away from $0$ and therefore leads to the Lipschitzness of $S(\pi, \hat{F}_1, \hat{F_2})$. However, there might exist an algorithm that works for $F_e(i)>0$ generally and maintains these optimalities as well, which is an open problem to the future.
\paragraph{Feelings of Fairness in FPA.} In our FPA algorithm, notice that we run each $\tilde\pi\in A_k$ for a continuous batch of $\frac{\tau_k}{|A_k|} =\Omega(\sqrt{T}\cdot2^k)$, which is long enough for customers to experience the fairness by comparing their proposed prices and accepted prices with customers from the other group.
\paragraph{Relaxation on Substantive Fairness.} In this work, our algorithm approached the optimal policy as the solution of (ref) through an online learning framework. This ensures an asymptotic fairness as $T\rightarrow+\infty$, but we still cannot guarantee an any-time fair algorithm precisely. Therefore, it is more practical to consider the following inequality-constraint optimization problem:
Comparing (ref) with (ref), we know that $R(\pi_*)\leq R(\pi_{\delta,*})$. According to (ref), we further know that $R(\pi_*)\geq R(\pi_{\delta,*})-L\cdot\delta$. Naturally, the substantive unfairness definition is now $\max\{0,S(\pi; F_1, F_2)-\delta\}$. If we still consider this problem under the framework of online learning, then two questions arose naturally: What are the optimal regret rate and (substantive) unfairness rate like? And how can we achieve them simultaneously? From our results in this work, we only know that (1) If $\delta=0$, then both rates are $\Theta(\sqrt{T})$, and (2) if $\delta\geq1$, then the optimal regret is $\Theta(\sqrt{T})$ and the optimal unfairness is $0$ (as it is reduced to the unconstrained pricing problem). In fact, for $\delta= O(\sqrt{1/T})$, we may still achieve $O(\sqrt{T})$ regret and unfairness, but it is not clear if they are always optimal. For $\delta>\sqrt{1/T}$, we conjecture that the optimal regret is still $\Theta(\sqrt{T})$ and the optimal unfairness could be $\Theta(1/(\sqrt{T}\delta))$.
\paragraph{Optimal Policy on the Continuous Space.} In this work, we restrict our price choices in a fixed price set $\mathbf{V}=\{v_1, v_2, \ldots, v_d\}$ and aims at the optimal distributions on these $v_i$'s. However, if we are allowed to propose any price within $[0,1]$, then the optimal policy could be a tuple of two continuous distributions that outperforms any policy restricted on $\mathbf{V}$. Even if we know that customers' valuations are all from $\mathbf{V}$, the optimal policy is not necessarily located inside $\mathbf{V}$ due to the fairness constraints. This optimization problem is even harder than (ref), and the online-learning scheme further increases its hardness. Existing methods such as continuous distribution discretization xu2022towards might work, but would definitely lead to an exponential time complexity.
In this work, we studied the online pricing problem with fairness constraints. We introduced two fairness notions, a procedural fairness and a substantive fairness indicating the equality of proposed and accepted prices between two different groups respectively. In order to fulfill these two constraints simultaneously, we adopted random pricing policies and established the objective function and rewards in expectation. To solve this problem with unknown demands, we designed a policy-elimination-based algorithm, FPA, that achieves an $\tilde{O}(\sqrt{T})$ regret within an $\tilde{O}(\sqrt{T})$ unfairness. We showed that our algorithm is optimal up to $\log\log T$ factors by proving an $\Omega(\sqrt{T})$ regret lower bound and an $\Omega(\sqrt{T})$ unfairness lower bound for any optimal algorithm with an $O(\sqrt{T})$ regret.