A practical mechanism for network utility maximization for unicast flows on the internet

In this paper we consider the scenario of unicast service on the Internet where a network operator wishes to allocate rates among strategic users in a way that maximizes overall user satisfaction while respecting capacity constraints on every link in the network. In particular, we construct two mechanisms that fully implement social welfare maximizing allocation in Nash equilibria (NE) for the above scenario when agents´ utilities are their private information. The emphasis of this work is on full implementation, which means that all NE of the induced game result in the optimal allocation of the centralized allocation problem, and thus no extraneous/ unwanted equilibria are created, as is the case in general mechanism design. The constructed mechanisms are amenable to learning, an essential requirement when using NE as a solution concept. This is achieved by ensuring that they result in feasible allocations on and off equilibrium and are budget balanced.