Question

I recently heard Alan Taylor speak about envy-free fair division and started wondering if questions like these make sense if we replace finitely additive measures with invariant means on amenable groups. Valerio has suggested a few tweaks for this question (thanks!) so I'll post a broad version and the earlier narrow one.

Along these lines, I'll ask the following broad question:

What are some fruitful modifications of cake-cutting fair division problems which replace the cake by an amenable group and the partygoers' preferences by invariant means?

Here's an attempt at such a modification in the discrete case, which was the body of the original question:

Let $G$ be an infinite discrete amenable group with $n$ given distinct left-invariant means $\mu_{1},...,\mu_{n}$. Is it possible to partition $G$ into $n$ parts $\lbrace K_{i} \rbrace_{i=1}^{n}$ so that $\mu_{j}(K_{l})\leq\mu_{j}(K_{j})$ for all $l,j\in \lbrace 1,2,...,n \rbrace$ and $l \neq j$?

Answer 1

Can't you just use the Lyapunov convexity theorem directly?

As usual, identify $\ell^\infty(G)$ with $C(\beta G)$, and work with $\beta G$ the Stone-Cech compactification. As this is a compact Hausdorff space, if $\mu$ is a regular measure on $\beta G$ then an atom of $\mu$ must be a point. So we can decompose $\mu$ as something in $\ell^1(\beta G)$ together with an atom-less measure, say a member of $M_c(\beta G)$ (continuous measures).

(Left) translation by members of $G$ give automorphisms of $\beta G$, and hence leave $\ell^1(\beta G)$ and $M_c(\beta G)$ invariant. I claim that nothing in $\ell^1(\beta G)$ can be left invariant. Let $\mu\in\ell^1(\beta G)$ be left invariant. Write $\beta G$ as the disjoint union of $G$-orbits, say $\bigcup_i G u_i$. Then $\mu$ must be supported on finite orbits (else we couldn't sum the coefficients, so we wouldn't be in $\ell^1$). If $u\in\beta G$ with $Gu$ finite, then there is $s\not=e$ in $G$ with $su=u$. Realise $u$ as an ultrafilter. Let $A\subseteq G$ be maximal with $A\cap s^{-1}A=\emptyset$. This means that if $r\not\in A$ then there is $t\in (A\cup\{r\}) \cap (s^{-1}A\cup\{s^{-1}r\})$, which implies that $t=r\in s^{-1}A\cup\{s^{-1}r\}$, that is, $sr\in A$. So $r\not\in A\implies sr\in A \implies r\in s^{-1}A$, so $G=A\cup s^{-1}A$. So Zorn implies there is $A\subseteq G$ with $A \cap s^{-1}A=\emptyset$ and $A\cup s^{-1}A=G$. Then either $A\in u$ so $A\in su$ so $s^{-1}A\in u$, contradiction; or $s^{-1}A\in u$ so $A\in su=u$ contradiction.

So I (hope!) I've shown that actually for any $u\in\beta G$, the orbit map $G\rightarrow\beta G; s\mapsto su$ is injective.

In particular, invariant means live in $M_c(\beta G)$, and so are atom-less, and so now we can just apply Lyapunov.

Edit: As Valerio points out, this shows that $X=\{ (\mu_1(A),\cdots,\mu_n(A)) : A\subseteq\beta G \text{ is Borel}\}$ is a convex set in $[0,1]^n$. Now, each $A\subseteq G$ induces the clopen set $O_A=\{ u\in\beta G: A\in u \}$, and these sets $O_A$ form a base for the topology. Now each $\mu_i$ is regular, so given $\epsilon>0$ and $A\subseteq\beta G$ Borel, we can find $B,C\subseteq G$ with $O_B \subseteq A\subseteq O_C$ and with $\mu_i(C)-\mu_i(B)<\epsilon$, for all $i$ (under the obvious abuse of notation). (This follows as any open set is a union of sets of the form $O_C$, and then approximate with a finite union.) So $Y=\{ (\mu_1(A),\cdots,\mu_n(A)) : A\subseteq G\}$ is a subset of $X$, and is dense in $X$. I don't see right now why $Y$ need be convex.