Mechanism Design with Allocative, Informational and Learning Constraints

Abstract

Efficient allocation of network resources is a highly desirable goal, with applications of interest ranging from bandwidth allocation in unicast/multicast services on the internet, to power allocation in a wireless interference networks and spectrum allocation for cellular networks. In this thesis, we consider such network problems in the presence of strategic decision-makers and solve the various mechanism design and game theoretical problems that arise from it.

In the first four chapters, we present single-shot incentive mechanisms for strategic agents, geared towards the above applications, such that the outcome produced at any Nash equilibrium is socially efficient. The focus in the first three chapters is on developing a systematic approach to designing such mechanisms such that various applications that differ qualitatively can be combined under the same design umbrella. Our approach models each application with its own network allocation constraints. Additionally, the design ensures that the mechanism contract only promises feasible allocation regardless of what messages agents choose i.e., the allocation through the mechanism cannot violate the network constraints. To this end we introduce a new radial allocation scheme. The benefit from this design criterion is that it allows the mechanism to be played off-equilibrium e.g., when agents are still learning the Nash equilibrium.

Chapter 4 focuses on resolving two separate issues that most mechanisms in the Nash implementation literature overlook. The first is the distributed-ness of communication between agents – the message chosen by an agent is assumed to be observed only by that agent’s neighbors on a communication graph (typical mechanism design model assumes that the messages are broadcasted). We demonstrate analytically that the distributed-ness of communication increases the dimensionality of the message space to the order of the average degree of the communication graph. The second issue is that of providing theoretical guarantees on how the one-shot Nash equilibrium can be learnt when agents only possess information about their own utilities and not that of others. We provide positive convergence guarantees for the entire class of adaptive best-response learning dynamics. These are a set of strategies where actions are myopic and depend on the recent history of observed actions. The guarantee provided is such that agents do not need to coordinate with their strategies in order to converge. Resolving both the issues simultaneously further increases the dimensionality of the message space to the order of number of agents.

In Chapter 5, we consider a Bayesian model with uncertainty in agents’ utilities. The objective of the mechanism designer is to achieve fairer allocation than the socially efficient one. We provide sufficient conditions on the fair allocation objective such that a truthful mechanism exists. The results are provided separately for Bayesian and dominant strategy incentive compatibility. Through a concrete example of demand-side management in smart grids we demonstrate numerically, the gains in fairness of the allocation as well as taxes collected through our method.

Chapter 6 considers infinite-horizon dynamic games of asymmetric information and develops a dynamic programming style characterization for calculating a subset of all perfect Bayesian equilibria (PBE). This subset of PBEs is rich enough to exhibit signaling behavior, which is also demonstrated through numerical analysis. The motivation for this work is the possible deployment of this equilibria characterization technique in designing dynamic mechanisms for systems where direct mechanisms are not desired, for instance due to privacy considerations.