Visitor's Talk



Mechanisms which Implement in Nash Equilibrium Resource Allocation Problems in Networks

• Speaker: Dr. Tudor M. Stoenescu, NASA-Jet Propulsion Laboratory

• Abstract:
  One of the major problems in today's communication networks is the design of efficient resource allocation schemes that maximize the network's usefulness for its users. The main challenge in designing such schemes comes from the informational decentralized nature of network problems. This informational decentralization arises from the fact that no agent in the allocation problem has full information about the users' service preference and the network's topology and resources.
  Decentralized resource allocation problems have been explored in great detail by mathematical economists in the context of mechanism design. Mechanism design consists of two components: realization theory and implementation theory. Realization theory deals with the design of rules which generate solutions to the resource allocation problem, while satisfying the problem's informational constraints. These rules do not take into account issues of "strategic" behavior of selfish agents who are involved in the allocation process. Implementation theory is concerned with strategic behavior of allocation processes. That is, it is concerned with the design of "game forms" that implement solutions to the problem in certain equilibrium concepts (e.g. Nash equilibrium).
  In this talk I will investigate the design of resource allocation mechanisms in the context of communication networks problems. The talk will be organized as follows: First I will present the main features of mechanism design from both the realization theory and implementation theory point of view. Within the context of realization theory I will present a pricing mechanism, proposed by Kelly, for a rate allocation problem in networks. This mechanism has the property that it achieves an efficient rate allocation in the case in which the users to not behave strategically. Unfortunately, in the case in which the selfish users strategize, the allocations generated by Kelly's mechanism can be arbitrarily bad.
  In the second part of the talk I will investigate a similar rate allocation problem from the implementation theory point of view. I will present a new pricing mechanism, proposed by Stoenescu and Ledyard, which achieves efficient allocations even in the case in which the users behave strategically. Particularly, I will show that all the mechanism's Nash equilibrium messages generate efficient rate allocations. Along with efficiency, I will also show that the equilibrium allocations satisfy budget balance and individual rationality conditions. Finally, I will present a measure for characterizing the informational efficiency of mechanisms, and I will show that under a certain network structure our proposed mechanism is informationally efficient.

• Biographical Sketch:
  Tudor M. Stoenescu is currently a systems engineer in the Telecommunications Architectures Group at NASA-Jet Propulsion Laboratory. He has received his B.S degree in Electrical Engineering and his M.S degree in Mathematics from North Dakota State University in 1999. He has received his M.S.E. and Ph.D. degrees in Electrical Engineering and Computer Science - Systems from the University of Michigan in 2001 and 2004, respectively. Prior to taking a position with JPL, Dr. Stoenescu has been a Postdoctoral Scholar in Information Science and Technology at the California Institute of Technology. Dr. Stoenescu's current research activities fall in the area of resource allocation problems in networked systems. He has designed and developed various resource allocations mechanisms for communication networks. At JPL, he is currently involved in the design and development of the next generation space network, and of various wireless spacecraft networks. Dr. Stoenescu has also conducted extensive research in the areas of stochastic control, ergodic theory and wavelet theory.