  We study the problem of online dynamic pricing with two types of fairness
constraints: a "procedural fairness" which requires the proposed prices to be
equal in expectation among different groups, and a "substantive fairness" which
requires the accepted prices to be equal in expectation among different groups.
A policy that is simultaneously procedural and substantive fair is referred to
as "doubly fair". We show that a doubly fair policy must be random to have
higher revenue than the best trivial policy that assigns the same price to
different groups. In a two-group setting, we propose an online learning
algorithm for the 2-group pricing problems that achieves $\tilde{O}(\sqrt{T})$
regret, zero procedural unfairness and $\tilde{O}(\sqrt{T})$ substantive
unfairness over $T$ rounds of learning. We also prove two lower bounds showing
that these results on regret and unfairness are both information-theoretically
optimal up to iterated logarithmic factors. To the best of our knowledge, this
is the first dynamic pricing algorithm that learns to price while satisfying
two fairness constraints at the same time.
