Cake-cutting and amenable groups - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T14:45:47Z http://mathoverflow.net/feeds/question/97773 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97773/cake-cutting-and-amenable-groups Cake-cutting and amenable groups Jon Bannon 2012-05-23T15:57:14Z 2012-05-24T19:33:13Z <p>I recently heard Alan Taylor speak about <a href="http://en.wikipedia.org/wiki/Envy-free" rel="nofollow">envy-free</a> <a href="http://en.wikipedia.org/wiki/Fair_division" rel="nofollow">fair division</a> 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.</p> <p>Along these lines, I'll ask the following broad question:</p> <blockquote> <p>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?</p> </blockquote> <p>Here's an attempt at such a modification in the discrete case, which was the body of the original question:</p> <blockquote> <p>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$?</p> </blockquote> http://mathoverflow.net/questions/97773/cake-cutting-and-amenable-groups/97835#97835 Answer by Matthew Daws for Cake-cutting and amenable groups Matthew Daws 2012-05-24T13:18:44Z 2012-05-24T19:33:13Z <p>Can't you just use the Lyapunov convexity theorem directly?</p> <p>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).</p> <p>(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 <code>$t\in (A\cup\{r\}) \cap (s^{-1}A\cup\{s^{-1}r\})$</code>, which implies that <code>$t=r\in s^{-1}A\cup\{s^{-1}r\}$</code>, 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.</p> <p>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.</p> <p>In particular, invariant means live in $M_c(\beta G)$, and so are atom-less, and so now we can just apply Lyapunov.</p> <p><strong>Edit:</strong> As Valerio points out, this shows that <code>$X=\{ (\mu_1(A),\cdots,\mu_n(A)) : A\subseteq\beta G \text{ is Borel}\}$</code> is a convex set in $[0,1]^n$. Now, each $A\subseteq G$ induces the clopen set <code>$O_A=\{ u\in\beta G: A\in u \}$</code>, 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)&lt;\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 <code>$Y=\{ (\mu_1(A),\cdots,\mu_n(A)) : A\subseteq G\}$</code> is a subset of $X$, and is dense in $X$. <strong>I don't see right now why $Y$ need be convex.</strong></p>