Choice functions, dynamics, and equal representation

Abstract

In this thesis, we study dynamics of systems evolving according to choice functions; such scenarios have the potential of being applicable in data and network processing, decision theory, and sampling. In particular, consider n linearly ordered size-one "spots" and k classes from which to fill the spots (where repetitions are allowed). Each time period, there is a shift - a new member enters the system on the right and the left-most member leaves; choice arises in selecting a new member. We are interested in choice functions on subsets of {1,2,...,k} which ensure equal representation among classes both locally and over time. Graph representations encapsulating domination properties of the given choice function have proven to be helpful in obtaining results. Other related matters that could have potential application include determining "optimal" choice functions with minimal period lengths and low burn-in.