  A combinatorial market consists of a set of indivisible items and a set of
agents, where each agent has a valuation function that specifies for each
subset of items its value for the given agent. From an optimization point of
view, the goal is usually to determine a pair of pricing and allocation of the
items that provides an efficient distribution of the resources, i.e., maximizes
the social welfare, or is as profitable as possible for the seller, i.e.,
maximizes the revenue. To overcome the weaknesses of mechanisms operating with
static prices, a recent line of research has concentrated on dynamic pricing
schemes. In this model, agents arrive in an unspecified sequential order, and
the prices can be updated between two agent-arrivals. Though the dynamic
setting is capable of maximizing social welfare in various scenarios, the
assumption that the agents arrive one after the other eliminates the standard
concept of fairness.
  In this paper, we study the existence of optimal dynamic prices under
fairness constraints in unit-demand markets. We propose four possible notions
of envy-freeness of different strength depending on the time period over which
agents compare themselves to others: the entire time horizon, only the past,
only the future, or only the present. For social welfare maximization, while
the first definition leads to Walrasian equilibria, we give polynomial-time
algorithms that always find envy-free optimal dynamic prices in the remaining
three cases. In contrast, for revenue maximization, we show that the
corresponding problems are APX-hard if the ordering of the agents is fixed. On
the positive side, we give polynomial-time algorithms for the setting when the
seller can choose the order in which agents arrive.
