| Abstract: |
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. In combinatorial markets, the goal is typically to determine a pair of pricing and allocation of items that results in an efficient distribution of resources or maximizes the seller's profit. In dynamic pricing schemes, agents arrive in an unspecified sequential order, and the prices can be updated between agent arrivals, which makes the concept of fairness of dynamic prices highly nontrivial. In markets with expected price deflation, a typical agent follows the prices prior to their purchase and become price insensitive after, whereas the opposite happens in markets with expected price inflation. To properly address these differences, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We 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. For social welfare maximization, we give polynomial-time algorithms that always find envy-free optimal dynamic prices. For revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed but are tractable when the seller can choose the ordering. [ABSTRACT FROM AUTHOR] |