Paradoxical Decompositions and Colouring Rules

A colouring rule is a way to colour the points $x$ of a probability space according to the colours of finitely many measure preserving tranformations of $x$. The rule is paradoxical if the rule can be satisfied a.e. by some colourings, but by none whose inverse images are measurable with respect to any finitely additive extension for which the transformations remain measure preserving. We show that proper graph colouring as a rule can be paradoxical. And we demonstrate rules defined via optimisation that are paradoxical. A connection to measure theoretic paradoxes is established.