Existence of a sink in directed graphs with a certain structure

Question

I'm not a mathematician (I'm an economist) but I hope that this problem is sufficiently non-trivial that someone here will find it interesting.

Motivation:

I'm trying to model how workers decide what "skills" to acquire when (a) they have different innate abilities for different skills but (b) they face competitive pressure from others that also choose to acquire those skills.

Problem:

Suppose we have $N$ workers that can choose to belong in any of $M$ different groups. Multiple workers can belong to the same group; a worker can be in one and only one group at a time. They can jump from any group to any other group.

A worker $i$ in group $j$ gets value $v_{ij}f(n_m)$ where $n_m$ is the number of workers in that group, and $f'(n_m) < 0$ and $f(1) = 1$ and as $n_m$ approaches infinity, $f$ approaches 0. $v$ is uniformly distributed. Workers jump between groups to try to maximize the value they receive.

Graph theory formulation:

I'm interested in the movement of workers between groups. I've modeled it as a directed graph, where each node is one possible configuration of workers among groups. Two nodes are connected if one worker changing states can convert one node to the other; edges point towards the greatest utility gain for the "jumping" worker.

In simulations, I've found that the system always reaches an equilibrium where no worker wants to jump and I haven't been able to construct a counter-example.

Conjecture:

My conjecture is that this is a general property of graphs with this structure, i.e., for any directed graph with the $(m,n)$ structure described above, there exists at least one "sink" with no outgoing edges and that this sink is reachable from all other nodes.

Ignoring values, it is possible to draw graphs without "sinks" but it leads to contradictions when I try to assign actual values to the worker-group pairings. None of the approaches I've tried so far seem promising enough to mention here.

Answer 1

Your conjectures are proven in the paper "Congestion Games with Player-Specific Payoff Functions" by I. Milchtaich, published in Games and Economic Behavior in 1996.

Usually, the term "congestion game" means a game in which players choose nonempty subsets of the set of resources. Each resource is assigned yields a certain utility (the same utility) to all players choosing it, and this utility depends only on the number of players, not their identities. Each player's total utility is the sum over all resources he has chosen. The general result is that such games are potential games, so they admit pure Nash equilibria (the sinks you consider) and any best-reply improvement path will reach one.

This particular paper considers a related notion of congestion game where players each only select one resource (as in your case). Again, their utility is based on the number of players choosing that resource, but different players choosing the resource may get different utilities. Under a monotonicity assumption slightly more general than the one you have made, the author shows that a pure Nash equilibrium still exists, and while not all best-reply improvement paths reach such an equilibrium, there exists one which can be reached in this way from any starting position.