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

  • 1
    $\begingroup$ 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 $\endgroup$ – Valerio Capraro May 23 '12 at 18:46
  • $\begingroup$ works. Indeed, a google search showed that the problem is solved, but it is not clear the context and the technology used. $\endgroup$ – Valerio Capraro May 23 '12 at 18:47
  • 4
    $\begingroup$ @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. $\endgroup$ – Pietro Majer May 23 '12 at 21:21
  • 1
    $\begingroup$ @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). $\endgroup$ – Pietro Majer May 23 '12 at 21:33
  • $\begingroup$ I am wondering if there is some other version of Lyapunov theorem that one can use. I am thinking about the following situation. Assume $\mu_1,\ldots,\mu_n$ and approximate them by nets $\mu_i^\alpha$ of countably additive measures that are more and more atomless; i.e. something like, if $\mu_i^\alpha(S)>0$, then there is $T\subseteq S$ such that $0<\mu_i^\beta(S)<\mu_i^\alpha$ for all $\beta$ large enough. Maybe one can write down and use a version of Lyapunov theorem where the $n$ measures in the original statement are replaced by $n$ nets with the above (or similar) asymptotic atomless. $\endgroup$ – Valerio Capraro May 23 '12 at 22:14

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.

  • $\begingroup$ 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? $\endgroup$ – Valerio Capraro May 24 '12 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.