  Let $\Gamma$ be a countable group acting on a countable set $X$ by
permutations. We give a necessary and sufficient condition for the action to
have a quasi-invariant mean with a given cocycle. This can be viewed as a
combinatorial analogue of the condition for the existence of a quasi-invariant
measure in the Borel case given by Miller. Then we show a geometric condition
that guarantees that the corresponding action on the Stone-\v{C}ech
compactification is Zimmer amenable. The geometric condition (weighted
hyperfiniteness) resembles Property A. We do not know the exact relation
between the two notions, however, we can show that amenable groups and groups
of finite asymptotic dimension are weighted hyperfinite.
