We introduce the notion of a Utilitarian Postman (UP) path on a network Q as one which minimizes the expected time required to find a random (uniformly distributed) point, and show that UP paths must be used in a minimax search of a symmetric network. For any network Q, one may consider the zero-sum search game ⌈(Q) in which the (minimizing) Searcher picks a unit speed path S(t) in Q, the Hider picks a point H in Q, and the payoff is the meeting time T = min{t : S(t) = H}. We show first that if Q is symmetric (edge and vertex transitive), then it is optimal for the Hider to pick H uniformly in Q, so that the Searcher must follow a UP path.
