6 Corrected error in paragraph 3.

The answer is that the above is equivalent to non amenability. Fix a group $(G,*)$. Since $(G,*)$ is non amenable if and only if every finitely generated subgroup is non amenable, we may assume that $G$ is finitely generated.

If $\mu$ and $\nu$ are finitely supported probability measures on $G$, define $$\mu * \nu (Z) = \sum_{x * y \in Z} \mu (\{x\}) \nu (\{y\})$$ Observe that $g * \nu (E) = \nu ( g^{-1} * E)$. If $S$ is a subset of $S$, let $P(S)$ denote all probability measures on $S$ (which are identified with probability measures on $G$ which are supported on $S$). I will identify $G$ with the point masses in $P(G)$.

If $A$ and $B$ are subsets of $G$ and $A$ is finite, we say that $B$ is $\epsilon$-Ramsey with respect to $A$ if for every $E \subseteq B$, then there is a $\nu$ in $P(B)$ such that $P(A) * \nu \subseteq P(B)$ and $$|\mu * \nu (E) - \nu (E)| < \epsilon$$ for all $\mu$ in $P(A)$. Notice that in some sense $E$ is defining a partition of $P(B)$ and we are postulating the existence of a copy of $P(A)$ in $P(B)$ which is homogeneous for $E$ up to an error of $\epsilon$.

Observe

It can be shown with an argument similar to the one below that if $B$ is $\epsilon$-Ramsey with respect to $A$, then for every $f:B \to [0,1]$ there is a $\nu$ in $P(B)$ such that $$|f(\mu * \nu) - f(\nu)| < \epsilon$$ where $f$ has been extended linearly to $P(B)$.To see this, notice that $B$ is assumed to satisfy this statement for $f: B \to \{0,1\}$. Furthermore, $f \mapsto f(\mu * \nu) - f(\nu)$ is linear and $\{0,1\}^B$ is the set of extreme points of $[0,1]^B$. Thus the maxima and minima of this map are realized at elements of $\{0,1\}^B$.

We say that $(G,*)$ is Ramsey if for every finite subset $A \subseteq G$ and every $\epsilon > 0$, there is a finite subset $B$ of $G$ with is $\epsilon$-Ramsey with respect to $A$. Notice that if $B$ satisfies that for every $E \subseteq B$ there is a $\nu$ in $P(B)$ such that $$|g * \nu (E) - \nu (E)| < \epsilon$$ for all $g$ in $A$, then $B$ is contained in a finite set which is $\epsilon$-Ramsey (we need only to replace $B$ by $A * B \cup B$).

To connect this to the question, suppose that $G$ is not Ramsey, as witnessed by a finite $A \subseteq G$ and $\epsilon > 0$. I claim there is a set $E \subseteq G$ such that for every $\mu \in P(G)$, there is a $g \in A$ such that $|\mu(E \cdot g) - \mu (E)| \geq \epsilon/2$. Let $B_n$ $(n < \infty)$ be an increasing sequence of finite sets covering $G$. Let $T_n$ be the set of all subsets $E$ of $B_n$ which witness that $B_n$ is not $\epsilon$-Ramsey with respect to $A$. Observe that if $E$ is in $T_{n+1}$, then $E \cap B_n$ is in $T_n$. Otherwise there would be a $\nu$ in $P(B_n)$ such that $g * \nu$ is in $P(B_n)$ for each $g$ in $A$ and $$|g * \nu (E \cap B_n) - \nu (E \cap B_n)| < \epsilon$$ Such a $\nu$ would also witness that $E$ is not in $T_{n+1}$. Define $T = \bigcup_n T_n$ and order $E \leq_T E'$ if $E = E' \cap B_m$ where $E$ is in $T_n$. This order makes $T$ into an infinite finitely branching tree. By König's lemma, $T$ has an infinite path whose union is some $E \subseteq G$. If there were a measure $\mu$ which was $\epsilon/2$-invariant for $E$ with respect to translates by elements of $A$, there would be a finitely supported $\nu$ which was $\epsilon$-invariant for $E$ with respect to translates in $A$. But this would be a contradiction since then the support of $\nu$ would be contained in some $B_n$ and $\nu$ would witness that $E \cap B_n$ was not in $T$.

Now the claim is that the Ramsey property of a discrete group is equivalent to its amenability. That amenability implies the Ramsey property follows from Følner's characterization of amenability. Also observe that $G$ is amenable provided that for every $\epsilon > 0$, every finite list $E_i$ $(i < n)$ of subsets of $G$, and $g_i$ $(i < n)$ in $G$, there is a finitely supported $\mu$ such that $$|\mu (g_i * E_i) - \mu (E_i) | < \epsilon.$$ Set $B_{-1} = \{1_G\} \cup \{g^{-1}_i :i < n\}$ and construct a sequence $B_i$ $(i < n)$ such that $B_{i+1}$ is $\epsilon/2$-Ramsey with respect to $B_i$.

Now inductively construct $\nu_i$ $(i < n)$ by downward recursion on $i$. If $\nu_j$ $(i < j)$ has been constructed, let $\nu_i \in P(B_i)$ be such that $$|\mu * \nu_{i} * \ldots * \nu_{n-1} (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2$$ for all $\mu$ in $P(B_{i-1})$. Set $\mu = \nu_0 * \ldots * \nu_{n-1}$. If $i < n$, then since $\nu_0 * \ldots * \nu_{i-1}$ and $g_i^{-1} * \nu_0 * \ldots * \nu_{i-1}$ are in $P(B_{i-1})$, $$|g_i^{-1} * \mu (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2$$ $$|\mu (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2$$ and therefore $|\mu (g_i * E_i) - \mu (E_i)| < \epsilon$.

5 added details to the paragraph "To connect"
Let $T$ T_n$be the tree whose$n$th level consists set of all subsets$E$of$B_n$which witness thatHere we Observe that if$E$is in$T_{n+1}$, then$E \cap B_n$is in$T_n$.Otherwise there would be a$\nu$in$P(B_n)$such that$g * \nu$is in$P(B_n)$for each$g$in$A$and|g * \nu (E \cap B_n) - \nu (E \cap B_n)| < \epsilonSuch a$\nu$would also witness that$E$is not in$T_{n+1}$.Define$T = \bigcup_n T_n$and order the tree by putting$E \leq_T E'$if$E = E' \cap B_n$, B_m$ where $E$ is on the in $n$th level ofThis order makes $T$.Since this tree is T$into an infinite finitely branching and infinitetree.By König's lemma, it$T$has an infinite path whose union is 4 Fixed o in Folner The answer is that the above is equivalent to non amenability. Fix a group$(G,*)$. Since$(G,*)$is non amenable if and only if every finitely generated subgroup is non amenable, we may assume that$G$is finitely generated. If$\mu$and$\nu$are finitely supported probability measures on$G$, define $$\mu * \nu (Z) = \sum_{x * y \in Z} \mu (\{x\}) \nu (\{y\})$$ Observe that$g * \nu (E) = \nu ( g^{-1} * E)$. If$S$is a subset of$S$, let$P(S)$denote all probability measures on$S$(which are identified with probability measures on$G$which are supported on$S$). I will identify$G$with the point masses in$P(G)$. If$A$and$B$are subsets of$G$and$A$is finite, we say that$B$is$\epsilon$-Ramsey with respect to$A$if for every$E \subseteq B$, then there is a$\nu$in$P(B)$such that$P(A) * \nu \subseteq P(B)$and $$|\mu * \nu (E) - \nu (E)| < \epsilon$$ for all$\mu$in$P(A)$. Notice that in some sense$E$is defining a partition of$P(B)$and we are postulating the existence of a copy of$P(A)$in$P(B)$which is homogeneous for$E$up to an error of$\epsilon$. Observe that if$B$is$\epsilon$-Ramsey with respect to$A$, then for every$f:B \to [0,1]$there is a$\nu$in$P(B)$such that $$|f(\mu * \nu) - f(\nu)| < \epsilon$$ where$f$has been extended linearly to$P(B)$. To see this, notice that$B$is assumed to satisfy this statement for$f: B \to \{0,1\}$. Furthermore,$f \mapsto f(\mu * \nu) - f(\nu)$is linear and$\{0,1\}^B$is the set of extreme points of$[0,1]^B$. Thus the maxima and minima of this map are realized at elements of$\{0,1\}^B$. We say that$(G,*)$is Ramsey if for every finite subset$A \subseteq G$and every$\epsilon > 0$, there is a finite subset$B$of$G$with is$\epsilon$-Ramsey with respect to$A$. Notice that if$B$satisfies that for every$E \subseteq B$there is a$\nu$in$P(B)$such that $$|g * \nu (E) - \nu (E)| < \epsilon$$ for all$g$in$A$, then$B$is contained in a finite set which is$\epsilon$-Ramsey (we need only to replace$B$by$A * B \cup B$). To connect this to the question, suppose that$G$is not Ramsey, as witnessed by a finite$A \subseteq G$and$\epsilon > 0$. I claim there is a set$E \subseteq G$such that for every$\mu \in P(G)$, there is a$g \in A$such that$|\mu(E \cdot g) - \mu (E)| \geq \epsilon/2$. Let$B_n(n < \infty)$be an increasing sequence of finite sets covering$G$. Let$T$be the tree whose$n$th level consists of all subsets$E$of$B_n$which witness that$B_n$is not$\epsilon$-Ramsey with respect to$A$. Here we order the tree by putting$E \leq_T E'$if$E = E' \cap B_n$, where$E$is on the$n$th level of$T$. Since this tree is finitely branching and infinite, it has an infinite path whose union is some$E \subseteq G$. If there were a measure$\mu$which was$\epsilon/2$-invariant for$E$with respect to translates by elements of$A$, there would be a finitely supported$\nu$which was$\epsilon$-invariant for$E$with respect to translates in$A$. But this would be a contradiction since then the support of$\nu$would be contained in some$B_n$and$\nu$would witness that$E \cap B_n$was not in$T$. Now the claim is that the Ramsey property of a discrete group is equivalent to its amenability. That amenability implies the Ramsey property follows from F\o lner's Følner's characterization of amenability. Also observe that$G$is amenable provided that for every$\epsilon > 0$, every finite list$E_i(i < n)$of subsets of$G$, and$g_i(i < n)$in$G$, there is a finitely supported$\mu$such that $$|\mu (g_i * E_i) - \mu (E_i) | < \epsilon.$$ Set$B_{-1} = \{1_G\} \cup \{g^{-1}_i :i < n\}$and construct a sequence$B_i(i < n)$such that$B_{i+1}$is$\epsilon/2$-Ramsey with respect to$B_i$. Now inductively construct$\nu_i(i < n)$by downward recursion on$i$. If$\nu_j(i < j)$has been constructed, let$\nu_i \in P(B_i)$be such that $$|\mu * \nu_{i} * \ldots * \nu_{n-1} (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2$$ for all$\mu$in$P(B_{i-1})$. Set$\mu = \nu_0 * \ldots * \nu_{n-1}$. If$i < n$, then since$\nu_0 * \ldots * \nu_{i-1}$and$g_i^{-1} * \nu_0 * \ldots * \nu_{i-1}$are in$P(B_{i-1})$, $$|g_i^{-1} * \mu (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2$$ $$|\mu (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2$$ and therefore$|\mu (g_i * E_i) - \mu (E_i)| < \epsilon\$.

3 Revised substantially to address coments of Andreas and Kate. See my comment.
2 Edited to clarify the connection to the original question.
1