# Existence of a sink in directed graphs with a certain structure

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.

-