Mechanism Design with Allocative, Informational and Learning constraints

Abstract:

Scarcity of resources on networks means that efficient allocation of network resources is a highly desirable goal. Some network applications of interest are bandwidth allocation in unicast/multicast services on the internet, power allocation in a wireless interference networks and spectrum allocation for cellular networks. In this talk I will present incentive mechanisms for strategic agents, geared towards the above applications, such that the outcome produced (at Nash equilibrium) is socially efficient.

The first part of the talk will focus on a systematic approach to designing mechanisms for allocation problems with non-trivial network allocation constraints. The systematic approach has the benefit of creating a template that applies to several applications. The second part of the talk focuses on mechanisms that simultaneously satisfy agents' informational and learning constraints. Informational constraints imply distributed communication between agents i.e., agents cannot broadcast their chosen message (in the mechanism) to all other agents and thus their communication is restricted by a "communication graph". The learning constraints address the issue of how to learn the efficient Nash equilibrium by dynamic adjustment of strategy. In this regard, the design is undertaken such that positive convergence guarantees can be provided when the mechanism is played repeatedly and agents are allowed to use any "adaptive" learning strategy.