# Cake-cutting and amenable groups

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.

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$?

-
I think this can be an interesting question, but I am wondering whether it is well formulated. Indeed, take a usual* cake (i.e. a disk) it seems to me that you allow the $\mu_i$'s to be equal to the Lebesgue measure and the problem gets trivial. Most importantly, it does not reflect the real-life problem, where maybe a piece of cake contains more chocolate and it's more preferred by a guy and less by a girl. I think one should allow every finitely additive measure or most of them. A think that one starting point should be to understand how the proof of existence of an envy-free fair division –  Valerio Capraro May 23 '12 at 18:46
works. Indeed, a google search showed that the problem is solved, but it is not clear the context and the technology used. –  Valerio Capraro May 23 '12 at 18:47
@Valerio: the model of the fair division is exactly that each partecipant has his/her own measure (so e.g. your measure may be concentrated on the chocolate, and mine on the cherry etc). In the case of n probability non-atomic measures on a measurable space, the Lyapunov convexity theorem ensures (the existence of) a perfect subdivision, i.e. a partition s.t. μi(Kj)=1/n for all i and j. Here of course it can't be applied, I think, because the measures are not countably additive and not divisible, in general. –  Pietro Majer May 23 '12 at 21:21
@Jon: I think the inequality is not correct as you wrote it: it should be $\mu_j(K_l)\le\mu_j(K_j)$ (meaning that the $j$-th participant evaluates her own piece not worse than any other, according to her measure). –  Pietro Majer May 23 '12 at 21:33
Thanks, Pietro. Fixed. –  Jon Bannon May 23 '12 at 21:35

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.

-
There is something that is not clear to me. The solutions sets $K_1,\ldots, K_n$ that you find live inside $\beta G$. Is it trivial that $K_i'=K_i\cap G$ is a solution of the original problem? –  Valerio Capraro May 24 '12 at 16:48