Balanced Facilities on Random Graphs

Given a graph G with n vertices and k players, each of which is placing a facility on one of the vertices of G, we define the score of the i'th player to be the number of vertices for which, among all players, the facility placed by the i'th player is the closest. A placement is balanced if all players get roughly the same score. A graph is balanced if all placements on it are balanced. Viewing balancedness as a desired property in various scenarios, in this paper we study balancedness properties of graphs, concentrating on random graphs and on expanders. We show that, while both random graphs and expanders tend to have good balancedness properties, random graphs are, in general, more balanced. In addition, we formulate and prove intractability of the combinatorial problem of deciding whether a given graph is balanced; then, building upon our analysis on random graphs and expanders, we devise two efficient algorithms which, with high probability, generate balancedness certificates. Our first algorithm is based on graph traversal, while the other relies on spectral properties.