| Ramesh Johari |
|
Research
Teaching Activities |
Research »
OverviewCurrent projects:Mean field equilibrium for dynamic gamesEngineers working on the kinds of large scale ecosystems described above have an inadequate collection of tools with which to understand dynamic interactions of self-interested agents. This is a serious limitation: to design, manage, and operate engineered ecosystems, we need tools that allow us to understand how they will react dynamically to changes in design parameters (e.g., market rules). Dynamic game theory provides the most natural methodology to employ. However, existing models of dynamic games are generally computationally intractable for large systems, and often place implausible demands on the rationality of players--leading to a lack of structural insight. These challenges have spurred renewed recent interest in an approximation methodology for dynamic games that we term mean field equilibrium (MFE). In MFE, each player reacts to only the long run average state of other players; this approximation is inspired by a limit where the number of players grows large. This construction simplifies both computational and rationality requirements. In the first paper below, we study a general model of stochastic dynamic games with many players over unbounded state spaces. We provide conditions for existence of MFE, and show that under the same conditions MFE approximates equilibria well in games with a large finite number of players. These conditions naturally provide insight into accuracy of MFE in a wide range of applications, from oligopolies to resource allocation. In the second paper below, we study games with strategic complementarities, used to model a diverse set of applications—including network security models, recommender systems, and dynamic search in markets. We show that players converge to MFE via natural myopic learning dynamics that are akin to model predictive control or receding horizon control; as we argue, these dynamics are more reasonable than the standard best response dynamics. We also quantify how the equilibria of such games move in response to changes in parameters of the game. We are currently employing MFE in a range of settings, including queueing games, multiarmed bandit games, and dynamic market games. A note on terminology: The second paper uses the term "mean field equilibrium" as this is quite common in the control literature. However for the applications considered in the first paper, "stationary equilibrium" is more common terminology, and so we have followed suit.
Information and efficiency in dynamic marketsRecently I have become increasingly interested in understanding how a diverse collection of markets perform over time, both in aggregating the private information of market participants, and in efficiently allocating goods among them. My interest is in studying mechanisms widely used in practice (such as repeated generalized second price auctions in sponsored search settings, or limit order books and specialist markets for trading of financial securities), with a view towards obtaining structural insight that can guide the engineering of such markets. Our work in the first paper below details conditions under which dynamic markets guarantee both informational and allocative efficiency. We develop a simple condition on a market, that we refer to as asymptotic smoothness, under which nonpathological equilibria of a market are eventually efficient. This condition is qualitatively interesting, because it reveals that narrowing of bid-ask spreads over time is essentially sufficient for efficiency, and in particular suggests that we search for market mechanisms that can guarantee this property (as is the case in algorithmic markets used for prediction purposes). More recently, we have been applying mean field equilibrium (see above) to the analysis of dynamic markets. In particular, we have begun studying how bidders learn their valuations in repeated auctions, inspired by settings such as sponsored search. Using a mean field approach, we obtain a structural characterization of the value bidders place on learning; the resulting equilibrium provides insight into the relationship between true valuations and observed bids. (This work is in preparation.)
Past projects:Designing efficient P2P systemsIn this work we start with the observation that most peer-to-peer (P2P) system designs essentially induce an exchange economy, where agents are able to download content in return for uploading. With this abstraction in hand, we consider a fundamental tradeoff: while multilateral, virtual currency-based system designs are efficient, they lack the implementation simplicity of bilateral, barter-based protocols (like BitTorrent). In this way the design of an efficient P2P ecosystem becomes a referendum on the efficiency and complexity of maintaining a currency. We consider the implications of building an entire peer-to- peer system around a virtual currency. Our theoretical and empirical results provide quantitative insight into regimes where bilateral exchange may perform quite well, even if it does not always give rise to Pareto-efficient equilibrium allocations.
Markets for resource allocationWhat "simple" market mechanisms ensure reasonably efficient resource allocation, despite self-interested users? In a range of work, I have considered the basic problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users, using market mechanisms with scalar strategy spaces; this continues earlier work in my Ph.D. thesis. Our work in the paper below characterizes the optimal mechanism among those that set one per-unit price (shown to be Kelly's proportional allocation mechanism), and those that set different per-unit prices for each user (shown to be a scalar variant of the well known Vickrey-Clarke-Groves class). Taken together, we discuss how our results quantify a fundamental insight in mechanism design: when the pricing flexibility available to the mechanism designer is limited, restricting the strategic flexibility of bidders may actually improve the efficiency guarantee.
Autonomy vs. stability in interdomain routingThe Internet consists of thousands of autonomous systems (ASes) that cooperate and compete to provide the global fabric of connectivity that supports billions of users. ASes require autonomy, i.e., flexibility in specifying their own routing policies to dictate where packets traversing their networks should flow; these policies are set to meet contractual obligations. At the same time, this autonomy may lead to a lack of stability in the overall inter-AS routing system. In this work we investigated the tension between autonomy and stability: in particular, we prove a type of routing "impossibility theorem" that shows that maintaining stability limits providers to (essentially) adopt shortest hop-count routing as their policy.
Inefficiency of route optimizationIn a related line of work, we investigate the efficiency implications of simultaneous route optimization decisions by different autonomous systems (e.g., ISPs and content distribution networks). We find a form of ''Braess' paradox'' that emerges: individual parties’ attempts to balance load may leave everyone worse off than if they had been entirely passive in their routing policy. Such effects can be mitigated by providing the correct inter-AS congestion signals as part of the infrastructure.
Externalities in servicesSeveral pieces of my prior work have focused on the role of externalities in service provision. In the first paper below, we study a game among providers who invest to mitigate the congestion effect felt by end users, and set a per-unit price for their resources. Our analysis reveals that the structure of the congestion externality has a first order impact on whether the resulting market is "concentrated" or competitive. We provide a comprehensive analysis, including a discussion of existence, uniqueness, and efficiency of equilibria. On the other hand, note that the preceding results are in a model with a pure congestion effect among the users. In reality, however, many networked services create network effects as well: e.g., in virtual communities or online gaming environments, users derive benefit from being able to reach each other. We characterize the tradeoff between these effects in the second paper below, and study operational consequences for the service provider.
Reputation system designI have also been interested in the evolution of reputation in online ecosystems, particularly marketplaces such as eBay. A reputation mechanism provides a vehicle for buyers to determine whether they trust a seller by aggregating past behavior of a seller. These reduced statistics give prospective buyers an indicator of trustworthiness. Our work shows an important tradeoff: we show that mechanisms that use information from a larger number of past transactions tend to provide incentives for patient sellers to be more truthful, but for higher quality sellers to be less truthful. Depending on the mix of sellers in the marketplace, this type of insight provides guidance into the window sizes that are most likely to lead to efficient trade among participants.
Other projects:I have also worked on a range of other projects, including: analysis of efficiency loss in markets for resource allocation; analysis of hybrid peer-to-peer and client-server content distribution systems; dynamics and contracting in network formation games; market models for air transportation systems; and scaling behavior of large wireless networks. For this and other work, please see Journal Publications and Conference Publications for further details. |
| Page last modified on April 09, 2011, at 11:35 PM |