Abstract The dense deployment of small-cell base stations in heterogeneous networks (HetNets) requires efficient resource allocation and interference management techniques. Especially, the problem of associating users to base stations (BSs) and allocating frequency channels must be revised and carefully studied. Finding the optimal solution of such problem is NP-hard. Further, it requires huge amount of information exchange between the BSs. In order to efficiently solve this problem in a distributed manner, we model it using non-cooperative game theory. The proposed game model is proved to not always admit pure Nash equilibria (PNEs), even though simulations show that, for slow fading channels, a PNE exists for most instances of the game. It is shown that, when the game admits PNEs, its prices of anarchy and stability are close to one. By modifying the players’ actions set and hence obtaining a new game model, we guarantee the existence of PNEs at the expense of performance degradation. Next, a fully distributed algorithm, based on a learning mechanism, is proposed. It requires no communication between the BSs and needs only one bit of feedback. Simulations show that the fully distributed algorithm has tight-to-optimal performance and solves efficiently the trade-off between complexity, information exchange and performance. We benchmark the proposed algorithm against the centralized optimal algorithm, the maximum signal to interference-plus-noise ratio algorithm, the best response dynamics algorithm and the randomized weighted majority algorithm.