  We study the power and limits of optimal dynamic pricing in combinatorial
markets; i.e., dynamic pricing that leads to optimal social welfare. Previous
work by Cohen-Addad et al. [EC'16] demonstrated the existence of optimal
dynamic prices for unit-demand buyers, and showed a market with coverage
valuations that admits no such prices. However, finding the frontier of markets
(i.e., valuation functions) that admit optimal dynamic prices remains an open
problem. In this work we establish positive and negative results that narrow
the existing gap.
  On the positive side, we provide tools for handling markets beyond
unit-demand valuations. In particular, we characterize all optimal allocations
in multi-demand markets. This characterization allows us to partition the items
into equivalence classes according to the role they play in achieving
optimality. Using these tools, we provide a poly-time optimal dynamic pricing
algorithm for up to $3$ multi-demand buyers.
  On the negative side, we establish a maximal domain theorem, showing that for
every non-gross substitutes valuation, there exist unit-demand valuations such
that adding them yields a market that does not admit an optimal dynamic
pricing. This result is the dynamic pricing equivalent of the seminal maximal
domain theorem by Gul and Stacchetti [JET'99] for Walrasian equilibrium. Yang
[JET'17] discovered an error in their original proof, and established a
different, incomparable version of their maximal domain theorem. En route to
our maximal domain theorem for optimal dynamic pricing, we provide the first
complete proof of the original theorem by Gul and Stacchetti.
