Envy-Free Dynamic Pricing Schemes

A combinatorial market consists of a set of indivisible goods and a set of buyers, where each buyer has a valuation function that represents the buyer’s preferences over the subsets of items. In the dynamic pricing model, the buyers arrive in a sequential order, and each buyer selects a bundle of the remaining items that maximizes her utility. The buyers’ preferences are known in advance, and the seller is allowed to update the prices between the arrivals of buyers based upon the remaining set of items but without knowing the identity of the next buyer. We study the existence of optimal dynamic prices under fairness constraints in unit-demand markets and propose five possible notions of envy-freeness depending on the period over which agents compare themselves to others: the entire time horizon, only the past, only the future, a mixture of the two, or only the present.