  Maintaining a maximum bipartite matching online while minimizing
recourse/augmentations is a well studied problem, motivated by content
delivery, job scheduling, and hashing. A breakthrough result of Bernstein,
Holm, and Rotenberg (\emph{SODA 2018}) resolved this problem up to a
logarithmic factors. However, we may need a richer class of combinatorial
constraints (e.g., matroid constraints) to model other problems in scheduling
and resource allocation.
  We consider the problem of maintaining a maximum independent set of an
arbitrary matroid $\mathcal{M}$ and a partition matroid $\mathcal{P}$ in the
online setting. Specifically, at each timestep $t$ one part $P_t$ of the
partition matroid (i.e., a subset of elements) is revealed: we must now select
at most one of these newly-revealed elements, but can exchange some of the
previously selected elements for new ones from previous parts, to maintain a
maximum independent set on the elements seen thus far. The goal is to minimize
the number of augmentations/changes done by our algorithm. If $\mathcal{M}$ is
also a partition matroid, we recover the problem of maintaining a maximum
bipartite matching online with recourse as a special case. In our work, we
allow arbitrary matroids $\mathcal{M}$, and so we can model broader classes of
problems.
  Our main result is an $O(n \log^2 n)$-competitive algorithm, where $n$ is the
rank of the largest common base; this matches the current best quantitative
bound for the bipartite matching special case. Our result builds substantively
on the breakthrough result of Bernstein, Holm, and Rotenberg for maintaining
bipartite matchings: a key contribution of our work is to make connections to
market equilibria and prices, and our use of properties of these equilibria in
submodular utility allocation markets to prove our bound on the number of
augmentations.
