Device-to-device communication can assist cellular networks by making certain users equipment (UEs)work as relays between the base station (BS) and other users. In this paper, we present the ultra-dense network (UDN) with D2D relays instead of small cells, where UEs can form into clusters according to the traffic demand in hot-spot areas. Each UE requires to decide whether to connect to the BS, or to get associated with one of the D2D relays, a.k.a. cluster heads (CHs). To optimize the downlink system performance, we propose a game-theoretic user association scheme in the UDN with D2D relays, specifically focused on load balancing among the BS and CHs. The dynamic user association is formulated as a hedonic coalition game where we adopt a simplified but efficient measurement of the utility and select the effective game players in a smaller number. In the game,we estimate the number of users associated with each CH at the Nash-stable state which can indicate the overall expected load condition, and an admission control mechanism is finally employed on the basis of these values. Simulation results show that the UDN adopting the D2D relay technology can achieve a higher system rate than the traditional cellular network,and the proposed user association scheme outperforms the existing schemes while having a small computational complexity.