NS Seminar

Date and Location

May 24, 2017 - 4:45pm to 5:45pm
Bldg 434, rm 122


A Practical Mechanism for Network Utility Maximization for Unicast Flows on the Internet (presented by Pedro Cisneros, Dept of Electrical and Computer Engineering)

A. Sinha and A. Anastasopoulos, "A practical mechanism for network utility maximization for unicast flows on the internet," 2015 IEEE International Conference on Communications (ICC), London, 2015, pp. 5679-5684.

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.

Mechanism Design for Resource Allocation in Networks with Intergroup Competition and Intragroup Sharing (presented by Pedro Cisneros, Dept of Electrical and Computer Engineering)

A. Sinha; A. Anastasopoulos, "Mechanism design for resource allocation in networks with intergroup competition and intragroup sharing," in IEEE Transactions on Control of Network Systems , vol.PP, no.99, pp.1-1

We consider a network where strategic agents, who are contesting for allocation of resources, are divided into fixed groups. The network control protocol is such that within each group agents get to share the resource and across groups they contest for it. A prototypical example is the allocation of data rate on a network with multicast/multirate architecture. Compared to the unicast architecture (which is a special case), the multicast/multirate architecture can result in substantial bandwidth savings. However, design of a market mechanism in such a scenario requires dealing with both private and public good problems as opposed to just private goods in unicast. The mechanism proposed in this work ensures that social welfare maximizing allocation on such a network is realized at all Nash equilibria (NE) i.e., full implementation in NE. In addition it is individually rational, i.e., agents have an incentive to participate in the mechanism. The mechanism, which is constructed in a quasi-systematic way starting from the dual of the centralized problem, has a number of useful properties. Specifically, due to a novel allocation scheme, namely “radial projection”, the proposed mechanism results in feasible allocation even off equilibrium. This is a practical necessity for any realistic mechanism since agents have to “learn” the NE through a dynamic process. Finally, it is shown how strong budget balance at equilibrium can be achieved with a minimal increase in message space as an add-on to a weakly budget balanced mechanism.