Publications

Journal articles

Prahalad, P., Ding, V. Y., Zaharieva, D. P., Addala, A., Johari, R., Scheinker, D., … Maahs, D. M. (2021). Teamwork, Targets, Technology, and Tight Control in Newly Diagnosed Type 1 Diabetes: Pilot 4T Study. Journal of Clinical Endocrinology and Metabolism (To Appear).

@article{PraEtAl2021Teamwork,
  author = {Prahalad, P. and Ding, V. Y. and Zaharieva, D. P. and Addala, A. and Johari, R. and Scheinker, D. and Desai, M. and Hood, K. and Maahs, D. M.},
  title = {Teamwork, Targets, Technology, and Tight Control in Newly Diagnosed Type 1 Diabetes: {P}ilot {4T} Study},
  journal = {Journal of Clinical Endocrinology and Metabolism (To Appear)},
  year = {2021},
  external = {https://doi.org/10.1210/clinem/dgab859}
}

Ferstad, J. O., Vallon, J. J., Jun, D., Gu, A., Vitko, A., Morales, D. P., … Scheinker, D. (2021). Population-level management of type 1 diabetes via continuous glucose monitoring and algorithm-enabled patient prioritization: Precision health meets population health. Pediatric Diabetes, 22(7), 982–991.

@article{FerEtAl2021Population,
  author = {Ferstad, J. O. and Vallon, J. J. and Jun, D. and Gu, A. and Vitko, A. and Morales, D. P. and Leverenz, J. and Lee, M. Y. and Leverenz, B. and Vasilakis, C. and Osmanlliu, E. and Prahalad, P. and Maahs, D. M. and Johari, R. and Scheinker, D.},
  title = {Population-level management of type 1 diabetes via continuous glucose monitoring and algorithm-enabled patient prioritization: Precision health meets population health},
  journal = {Pediatric Diabetes},
  year = {2021},
  volume = {22},
  number = {7},
  pages = {982 - 991},
  external = {https://doi.org/10.1111/pedi.13256}
}

Johari, R., Li, H., Liskovich, I., & Weintraub, G. (2021). Experimental Design in Two-Sided Platforms: An Analysis of Bias. Management Science (To Appear).
We develop an analytical framework to study experimental design in two-sided marketplaces. Many of these experiments exhibit interference, where an intervention applied to one market participant influences the behavior of another participant. This interference leads to biased estimates of the treatment effect of the intervention. We develop a stochastic market model and associated mean field limit to capture dynamics in such experiments, and use our model to investigate how the performance of different designs and estimators is affected by marketplace interference effects. Platforms typically use two common experimental designs: demand-side ("customer") randomization (CR) and supply-side ("listing") randomization (LR), along with their associated estimators. We show that good experimental design depends on market balance: in highly demand-constrained markets, CR is unbiased, while LR is biased; conversely, in highly supply-constrained markets, LR is unbiased, while CR is biased. We also introduce and study a novel experimental design based on two-sided randomization (TSR) where both customers and listings are randomized to treatment and control. We show that appropriate choices of TSR designs can be unbiased in both extremes of market balance, while yielding relatively low bias in intermediate regimes of market balance.
```
@article{JohLiLisWei2021Experimental,
  author = {Johari, Ramesh and Li, Hannah and Liskovich, Inessa and Weintraub, Gabriel},
  title = {Experimental Design in Two-Sided Platforms: An Analysis of Bias},
  year = {2021},
  external = {https://arxiv.org/abs/2002.05670},
  journal = {Management Science (To Appear)}
}
```
Arnosti, N., Johari, R., & Kanoria, Y. (2021). Managing congestion in matching markets. Manufacturing & Service Operations Management (M&SOM), 23(3), 620–636.
Participants in matching markets face search and screening costs which prevent the market from clearing efficiently. We study the magnitude of this inefficiency, and the effects of simple market interventions. We consider a mean field limit of a stochastic, game theoretic, dynamic model in which “applicants” and “employers” pay costs to search and screen. Importantly, applicants may send applications that are never screened, and employers may screen applicants, only to learn that they have already matched. We prove existence and uniqueness of equilibrium, and characterize welfare for participants on both sides of the market. We also establish that equilibria of our model are approximate equilibria in large finite markets. We provide two main insights. First, we identify that the welfare of market participants depends crucially on whether the market is *screening-limited* or *application-limited*. In screening-limited markets, application costs are low and there are enough employers that most applicants can match. In this case, employers screen many applicants who turn out to be unavailable, and screening costs fully offset the benefit of matching: employers’ expected welfare is zero, and some employers choose not to participate. In contrast, application-limited markets typically feature low screening costs and a shortage of employers. In such markets, applicants engage in wasteful competition, sending many applications that are never read. Our second contribution is to show that simple interventions – such as limiting the number of applications that an individual can send, or making it more costly to apply – can significantly improve the welfare of agents on one or both sides of the market.
```
@article{ArnJohKan2020Managing,
  author = {Arnosti, Nick and Johari, Ramesh and Kanoria, Yash},
  title = {Managing congestion in matching markets},
  year = {2021},
  external = {https://doi.org/10.1287/msom.2020.0927},
  journal = {Manufacturing \& Service Operations Management (M\&SOM)},
  volume = {23},
  number = {3},
  pages = {620 - 636}
}
```
Garg, N., & Johari, R. (2020). Designing Informative Rating Systems for Online Platforms: Evidence from Two Experiments. Manufacturing & Service Operations Management (M&SOM), 23(3), 589–605.
Platforms critically rely on rating systems to learn the quality of market participants. In practice, however, these ratings are often highly inflated, drastically reducing the signal available to distinguish quality. We consider two questions: First, can rating systems better discriminate quality by altering the meaning and relative importance of the levels in the rating system? And second, if so, how should the platform optimize these choices in the design of the rating system? We first analyze the results of a randomized controlled trial on an online labor market in which an additional question was added to the feedback form. Between treatment conditions, we vary the question phrasing and answer choices. We further run an experiment on Amazon Mechanical Turk with similar structure, to confirm the labor market findings. Our tests reveal that current inflationary norms can in fact be countered by re-anchoring the meaning of the levels of the rating system. In particular, scales that are positive-skewed and provide specific interpretations for what each label means yield rating distributions that are much more informative about quality. Second, we develop a theoretical framework to optimize the design of a rating system by choosing answer labels and their numeric interpretations in a manner that maximizes the rate of convergence to the true underlying quality distribution. Finally, we run simulations with an empirically calibrated model and use these to study the implications for optimal rating system design. Our simulations demonstrate that our modeling and optimization approach can substantially improve the quality of information obtained over baseline designs. Overall, our study illustrates that rating systems that are informative in practice can be designed, and demonstrates how to design them in a principled manner.
```
@article{GarJoh2018Designing,
  author = {Garg, Nikhil and Johari, Ramesh},
  title = {Designing Informative Rating Systems for Online Platforms: Evidence from Two Experiments},
  year = {2020},
  external = {https://doi.org/10.1287/msom.2020.0921},
  journal = {Manufacturing \& Service Operations Management (M\&SOM)},
  note = {Finalist, 2020 INFORMS M\&SOM Student Paper Competition},
  volume = {23},
  number = {3},
  pages = {589 - 605}
}
```
Johari, R., Kamble, V., & Kanoria, Y. (2021). Matching While Learning. Operations Research, 69(2), 655–681.
We consider the problem faced by a service platform that needs to match supply with demand, but also to learn attributes of new arrivals in order to match them better in the future. We introduce a benchmark model with heterogeneous workers and jobs that arrive over time. Job types are known to the platform, but worker types are unknown and must be learned by observing match outcomes. Workers depart after performing a certain number of jobs. The payoff from a match depends on the pair of types and the goal is to maximize the steady-state rate of accumulation of payoff. Our main contribution is a complete characterization of the structure of the optimal policy in the limit that each worker performs many jobs. The platform faces a trade-off for each worker between myopically maximizing payoffs (exploitation) and learning the type of the worker (exploration). This creates a multitude of multi-armed bandit problems, one for each worker, coupled together by the constraint on the availability of jobs of different types (capacity constraints). We find that the platform should estimate a shadow price for each job type, and use the payoffs adjusted by these prices, first, to determine its learning goals and then, for each worker, (i) to balance learning with payoffs during the "exploration phase", and (ii) to myopically match after it has achieved its learning goals during the "exploitation phase."
```
@article{JohKamKan2018Matching,
  author = {Johari, Ramesh and Kamble, Vijay and Kanoria, Yash},
  title = {Matching While Learning},
  year = {2021},
  external = {https://doi.org/10.1287/opre.2020.2013},
  journal = {Operations Research},
  volume = {69},
  number = {2},
  pages = {655 - 681}
}
```
Krishnasamy, S., Sen, R., Johari, R., & Shakkottai, S. (2020). Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach. Operations Research, 69(1), 315–330.
Consider a queueing system consisting of multiple servers. Jobs arrive over time and enter a queue for service; the goal is to minimize the size of this queue. At each opportunity for service, at most one server can be chosen, and at most one job can be served. Service is successful with a probability (the service probability) that is a priori unknown for each server. An algorithm that knows the service probabilities (the "genie") can always choose the server of highest service probability. We study algorithms that learn the unknown service probabilities. Our goal is to minimize queue-regret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by the "genie." Since queue-regret cannot be larger than classical regret, results for the standard multi-armed bandit problem give algorithms for which queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior. In particular, as long as the bandit algorithm’s queues have relatively long regenerative cycles, queue-regret is similar to cumulative regret, and scales (essentially) logarithmically. However, we show that this "early stage" of the queueing bandit eventually gives way to a "late stage", where the optimal queue-regret scaling is O(1/t). We demonstrate an algorithm that (order-wise) achieves this asymptotic queue-regret in the late stage. Our results are developed in a more general model that allows for multiple job classes as well.
```
@article{KriSenJohSha2020Learning,
  author = {Krishnasamy, Subhashini and Sen, Rajat and Johari, Ramesh and Shakkottai, Sanjay},
  title = {Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach},
  year = {2020},
  external = {https://doi.org/10.1287/opre.2020.1995},
  journal = {Operations Research},
  volume = {69},
  number = {1},
  pages = {315 - 330}
}
```
Johari, R., Pekelis, L., & Walsh, D. (2021). Always valid inference: Continuous monitoring of A/B tests. Operations Research (To Appear).
A/B tests are typically analyzed via p-values and confidence intervals; but these inferences are wholly unreliable if users make decisions while continuously monitoring their tests. We define always valid p-values that let users try to take advantage of data as fast as it becomes available, providing valid statistical inference whenever they make their decision. Always valid p-values can be interpreted as the natural p-values corresponding to a sequential hypothesis test. Through this connection we derive always valid p-values with good detection properties. Notably, we also extend our approach to address multiple hypothesis testing in the sequential setting. Our methodology has been implemented in a large scale commercial A/B testing platform, from which we present empirical results.
```
@article{JohPekWal2020Always,
  author = {Johari, Ramesh and Pekelis, Leo and Walsh, David},
  title = {Always valid inference: Continuous monitoring of {A/B} tests},
  year = {2021},
  external = {https://doi.org/10.1287/opre.2021.2135},
  journal = {Operations Research (To Appear)}
}
```
Zhang, B., Johari, R., & Rajagopal, R. (2019). Cournot games with uncertainty: Coalitions, competition, and efficiency. IEEE Transactions on Control of Network Systems, 6(2), 884–896.
We investigate the impact of group formations on the efficiency of Cournot games where producers face uncertainties. In particular, we study a market model where producers must determine their output before an uncertainty production capacity is realized. In contrast to standard Cournot models, we show that the game is not efficient when there are many small producers. Instead, producers tend to act conservatively to hedge against their risks. We show that in the presence of uncertainty, the game becomes efficient when producers are allowed to take advantage of diversity to form groups of certain sizes. We characterize the trade-off between market power and uncertainty reduction as a function of group size. Namely, we show that when there are N producers present, competition between groups of size square root of N results in equilibria that are socially optimal.
```
@article{ZhaJohRaj2019Cournot,
  author = {Zhang, Baosen and Johari, Ramesh and Rajagopal, Ram},
  title = {Cournot games with uncertainty: Coalitions, competition, and efficiency},
  year = {2019},
  external = {http://arxiv.org/abs/1503.02479},
  journal = {IEEE Transactions on Control of Network Systems},
  volume = {6},
  number = {2},
  pages = {884 - 896}
}
```
Leduc, M. V., Jackson, M. O., & Johari, R. (2017). Pricing and referrals in diffusion on networks. Games and Economic Behavior, 104, 568–594.
When a new product or technology is introduced, potential consumers can learn its quality by trying it, at a risk, or by letting others try it and free-riding on the information that they generate. We propose a dynamic game to study the adoption of technologies of uncertain value, when agents are connected by a network and a monopolist seller chooses a profit-maximizing policy. Consumers with low degree (few friends) have incentives to adopt early, while consumers with high degree have incentives to free ride. The seller can induce high-degree consumers to adopt early by offering referral incentives – rewards to early adopters whose friends buy in the second period. Referral incentives thus lead to a ‘double-threshold strategy’ by which low and high-degree agents adopt the product early while middle-degree agents wait. We show that referral incentives are optimal on certain networks while inter-temporal price discrimination is optimal on others.
```
@article{LedJacJoh2017Pricing,
  author = {Leduc, Matt V. and Jackson, Matthew O. and Johari, Ramesh},
  title = {Pricing and referrals in diffusion on networks},
  journal = {Games and Economic Behavior},
  volume = {104},
  pages = {568 - 594},
  year = {2017},
  external = {https://doi.org/10.1016/j.geb.2017.05.011}
}
```
Banerjee, S., Johari, R., & Zhou, Z. (2016). The importance of exploration in online marketplaces. IEEE Internet Computing, 20(1), 20–26.
In online marketplaces, a critical objective of the platform’s intermediation is ensuring the sellers’ quality. This is particularly challenging in large marketplaces, where it’s infeasible to pre-screen all sellers, and the platform uses feedback from previous transactions to infer the sellers’ quality. However, this process matches existing buyers to new, untrusted sellers, potentially leading to a poor buyer experience. This raises a natural exploration-exploitation tradeoff in online marketplaces. Here, the authors suggest that the exploration-exploitation tradeoff is closely linked to the nature of externalities in the marketplace. Using a stylized model, they uncover a qualitative difference between exploration and exploitation, based on the underlying network externalities between buyers and sellers in the market. In particular, in many settings, they show that by focusing on exploration, the platform can achieve a higher overall rate of successful matches.
```
@article{BanJohZho2016Importance,
  author = {Banerjee, Siddhartha and Johari, Ramesh and Zhou, Zhengyuan},
  journal = {IEEE Internet Computing},
  title = {The importance of exploration in online marketplaces},
  year = {2016},
  volume = {20},
  number = {1},
  pages = {20-26},
  external = {http://dx.doi.org/10.1109/MIC.2015.139}
}
```
Zhang, B., Johari, R., & Rajagopal, R. (2015). Competition and coalition formation of renewable power producers. IEEE Transactions on Power Systems, 30(3), 1624–1632.
We investigate group formations and strategic behaviors of renewable power producers in electricity markets. These producers currently bid into the day-ahead market in a conservative fashion because of the real-time risk associated with not meeting their bid amount. It has been suggested in the literature that producers would bid less conservatively if they can form large groups to take advantages of spatial diversity to reduce the uncertainty in their aggregate output. We show that large groups of renewable producers would act strategically to lower the aggregate output because of market power. To maximize renewable power production, we characterize the trade-off between market power and generation uncertainty as a function of the size of the groups. We show there is a sweet spot in the sense that there exists groups that are large enough to achieve the uncertainty reduction of the grand coalition, but are small enough such that they have no significant market power. We consider both independent and correlated forecast errors under a fixed real-time penalty. We also consider a real-time market where both selling and buying of energy are allowed. We validate our claims using PJM and NREL data.
```
@article{ZhaJohRaj2015Competition,
  author = {Zhang, Baosen and Johari, Ramesh and Rajagopal, Ram},
  title = {Competition and coalition formation of renewable power producers},
  journal = {IEEE Transactions on Power Systems},
  volume = {30},
  number = {3},
  pages = {1624--1632},
  year = {2015},
  external = {http://dx.doi.org/10.1109/TPWRS.2014.2385869}
}
```
Adlakha, S., Johari, R., & Weintraub, G. Y. (2015). Equilibria of dynamic games with many players: Existence, approximation, and market structure. Journal of Economic Theory, 156, 269–316.
In this paper we study stochastic dynamic games with many players; these are a fundamental model for a wide range of economic applications. The standard solution concept for such games is Markov perfect equilibrium (MPE), but it is well known that MPE computation becomes intractable as the number of players increases. We instead consider the notion of stationary equilibrium (SE), where players optimize assuming the empirical distribution of others’ states remains constant at its long run average. We make two main contributions. First, we provide a rigorous justification for using SE. In particular, we provide a parsimonious collection of exogenous conditions over model primitives that guarantee existence of SE, and ensure that an appropriate approximation property to MPE holds, in a general model with possibly unbounded state spaces. Second, we draw a significant connection between the validity of SE, and market structure: under the same conditions that imply SE exist and approximates MPE well, the market becomes fragmented in the limit of many firms. To illustrate this connection, we study in detail a series of dynamic oligopoly examples. These examples show that our conditions enforce a form of “decreasing returns to larger states;” this yields fragmented industries in the SE limit. By contrast, violation of these conditions suggests “increasing returns to larger states” and potential market concentration. In that sense, our work uses a fully dynamic framework to also contribute to a longstanding issue in industrial organization: understanding the determinants of market structure in different industries.
```
@article{AdlJohWei2015Equilibria,
  author = {Adlakha, Sachin and Johari, Ramesh and Weintraub, Gabriel Y.},
  title = {Equilibria of dynamic games with many players: Existence, approximation,
                 and market structure},
  journal = {Journal of Economic Theory},
  volume = {156},
  pages = {269--316},
  year = {2015},
  external = {http://dx.doi.org/10.1016/j.jet.2013.07.002}
}
```
Iyer, K., Johari, R., & Moallemi, C. C. (2014). Information aggregation and allocative efficiency in smooth markets. Management Science, 60(10), 2509–2524.
Recent years have seen extensive investigation of the information aggregation properties of markets. However, relatively little is known about conditions under which a market will aggregate the private information of rational risk-averse traders who optimize their portfolios over time; in particular, what features of a market encourage traders to ultimately reveal their private information through trades? We consider a market model involving finitely many informed risk-averse traders interacting with a market maker. Our main result identifies a basic asymptotic smoothness condition on prices in the market that ensures information is aggregated as long as portfolios converge; furthermore, under this assumption, the allocation achieved is ex post Pareto efficient. Asymptotic smoothness is fairly mild: it requires that, eventually, infinitesimal purchases or sales should see the same per-unit price. Notably, we demonstrate that, under some mild conditions, algorithmic markets based on cost functions (or, equivalently, markets based on market scoring rules) aggregate the information of traders.
```
@article{IyeJohMoa2014Information,
  author = {Iyer, Krishnamurthy and Johari, Ramesh and Moallemi, Ciamac C.},
  title = {Information aggregation and allocative efficiency in smooth markets},
  journal = {Management Science},
  volume = {60},
  number = {10},
  pages = {2509--2524},
  year = {2014},
  external = {http://dx.doi.org/10.1287/mnsc.2014.1929}
}
```
Iyer, K., Johari, R., & Sundararajan, M. (2014). Mean field equilibria of dynamic auctions with learning. Management Science, 60(12), 2949–2970.
We study learning in a dynamic setting where identical copies of a good are sold over time through a sequence of second-price auctions. Each agent in the market has an unknown independent private valuation that determines the distribution of the reward she obtains from the good; for example, in sponsored search settings, advertisers may initially be unsure of the value of a click. Though the induced dynamic game is complex, we simplify analysis of the market using an approximation methodology known as mean field equilibrium (MFE). The methodology assumes that agents optimize only with respect to long-run average estimates of the distribution of other players’ bids. We show a remarkable fact: In a mean field equilibrium, the agent has an optimal strategy where she bids truthfully according to a conjoint valuation. The conjoint valuation is the sum of her current expected valuation, together with an overbid amount that is exactly the expected marginal benefit of one additional observation about her true private valuation. Under mild conditions on the model, we show that an MFE exists, and that it is a good approximation to a rational agent’s behavior as the number of agents increases. Formally, if every agent except one follows the MFE strategy, then the remaining agent’s loss on playing the MFE strategy converges to zero as the number of agents in the market increases. We conclude by discussing the implications of the auction format and design on the auctioneer’s revenue. In particular, we establish the revenue equivalence of standard auctions in dynamic mean field settings, and discuss optimal selection of reserve prices in dynamic auctions.
```
@article{IyeJohSun2014Mean,
  author = {Iyer, Krishnamurthy and Johari, Ramesh and Sundararajan, Mukund},
  title = {Mean field equilibria of dynamic auctions with learning},
  journal = {Management Science},
  volume = {60},
  number = {12},
  pages = {2949--2970},
  year = {2014},
  external = {http://dx.doi.org/10.1287/mnsc.2014.2018}
}
```
Arcaute, E., Dyagilev, K., Johari, R., & Mannor, S. (2013). Dynamics in tree formation games. Games and Economic Behavior, 79, 1–29.
Network formation games capture two conflicting objectives of selfish nodes in a network: such nodes wish to form a well-connected network and, at the same time, to minimize their cost of participation. We consider three families of such models where nodes avoid forming edges beyond those necessary for connectivity, thus forming tree networks. We focus on two local two-stage best-response dynamics in these models, where nodes can only form links with others in a restricted neighborhood. Despite this locality, both our dynamics converge to efficient outcomes in two of the considered families of models. In the third family of models, both our dynamics guarantee at most constant efficiency loss. This is in contrast with the standard best-response dynamics whose efficiency loss is unbounded in all three families of models. Thus we present a globally constrained network formation game where local dynamics naturally select desirable outcomes.
```
@article{ArcDyaJohMan2013Dynamics,
  author = {Arcaute, Esteban and Dyagilev, Kirill and Johari, Ramesh and Mannor, Shie},
  title = {Dynamics in tree formation games},
  journal = {Games and Economic Behavior},
  volume = {79},
  pages = {1--29},
  year = {2013},
  external = {http://dx.doi.org/10.1016/j.geb.2013.01.002}
}
```
Adlakha, S., & Johari, R. (2013). Mean field equilibrium in dynamic games with strategic complementarities. Operations Research, 61(4), 971–989.
We study a class of stochastic dynamic games that exhibit strategic complementarities between players; formally, in the games we consider, the payoff of a player has increasing differences between her own state and the empirical distribution of the states of other players. Such games can be used to model a diverse set of applications, including network security models, recommender systems, and dynamic search in markets. Stochastic games are generally difficult to analyze, and these difficulties are only exacerbated when the number of players is large (as might be the case in the preceding examples). We consider an approximation methodology called mean field equilibrium to study these games. In such an equilibrium, each player reacts to only the long-run average state of other players. We find necessary conditions for the existence of a mean field equilibrium in such games. Furthermore, as a simple consequence of this existence theorem, we obtain several natural monotonicity properties. We show that there exist a “largest” and a “smallest” equilibrium among all those where the equilibrium strategy used by a player is nondecreasing, and we also show that players converge to each of these equilibria via natural myopic learning dynamics; as we argue, these dynamics are more reasonable than the standard best-response dynamics. We also provide sensitivity results, where we quantify how the equilibria of such games move in response to changes in parameters of the game (for example, the introduction of incentives to players).
```
@article{AdlJoh2013Mean,
  author = {Adlakha, Sachin and Johari, Ramesh},
  title = {Mean field equilibrium in dynamic games with strategic complementarities},
  journal = {Operations Research},
  volume = {61},
  number = {4},
  pages = {971--989},
  year = {2013},
  external = {http://dx.doi.org/10.1287/opre.2013.1192}
}
```
Wu, Y., Bui, L., & Johari, R. (2012). Heavy traffic approximation of equilibria in resource sharing games. IEEE Journal on Selected Areas in Communications, 30(11), 2200–2209.
We consider a model of priced resource sharing that combines both queueing behavior and strategic behavior. We study a priority service model where a single server allocates its capacity to agents in proportion to their payment to the system, and users from different classes act to minimize the sum of their cost for processing delay and payment. As the exact processing time of this system is hard to compute and cannot be characterized in closed form, we introduce the notion of heavy traffic equilibrium as an approximation of the Nash equilibrium, derived by considering the asymptotic regime where the system load approaches capacity. We discuss efficiency and revenue, and in particular provide a bound for the price of anarchy of the heavy traffic equilibrium.
```
@article{WuBuiJoh2012Heavy,
  author = {Wu, Yu and Bui, Loc and Johari, Ramesh},
  title = {Heavy traffic approximation of equilibria in resource sharing games},
  journal = {{IEEE} Journal on Selected Areas in Communications},
  volume = {30},
  number = {11},
  pages = {2200--2209},
  year = {2012},
  external = {http://dx.doi.org/10.1109/JSAC.2012.121212}
}
```
DiPalantino, D., & Johari, R. (2012). Traffic engineering with semiautonomous users: A game-theoretic perspective. IEEE/ACM Transactions on Networking, 20(6), 1938–1949.
In this paper, we explore the interaction between traffic engineering and the users of a network. Because a traffic engineer may be unaware of the structure of content distribution systems or overlay networks, his management of the network does not fully anticipate how traffic might change as a result of his actions. Content distribution systems that assign servers at the application level can respond very rapidly to changes in the routing of the network. Consequently, the traffic engineer’s decisions may not be applied to the intended traffic. We use a game-theoretic framework in which infinitesimal users of a network select the source of content, and the traffic engineer decides how the traffic will route through the network. We formulate a game and prove the existence of equilibria. Additionally, we present a setting in which equilibria are socially optimal, essentially unique, and stable. Conditions under which efficiency loss may be bounded are presented, and the results are extended to the cases of general overlay networks and multiple autonomous systems.
```
@article{DiPJoh2012Traffic,
  author = {DiPalantino, Dominic and Johari, Ramesh},
  title = {Traffic engineering with semiautonomous users: A game-theoretic perspective},
  journal = {{IEEE/ACM} Transactions on Networking},
  volume = {20},
  number = {6},
  pages = {1938--1949},
  year = {2012},
  external = {http://dx.doi.org/10.1109/TNET.2012.2208475}
}
```
Johari, R., & Tsitsiklis, J. N. (2011). Parameterized supply function bidding: Equilibrium and efficiency. Operations Research, 59(5), 1079–1089.
We consider a model where a finite number of producers compete to meet an infinitely divisible but inelastic demand for a product. Each firm is characterized by a production cost that is convex in the output produced, and firms act as profit maximizers. We consider a uniform price market design that uses supply function bidding: firms declare the amount they would supply at any positive price, and a single price is chosen to clear the market. We are interested in evaluating the impact of price-anticipating behavior both on the allocative efficiency of the market and on the prices seen at equilibrium. We show that by restricting the strategy space of the firms to parameterized supply functions, we can provide upper bounds on both the inflation of aggregate cost at the Nash equilibrium relative to the socially optimal level, as well as the markup of the Nash equilibrium price above the competitive level: as long as N > 2 firms are competing, these quantities are both upper bounded by 1 + 1/(N − 2). This result holds even in the presence of asymmetric cost structure across firms. We also discuss several extensions, generalizations, and related issues.
```
@article{JohTsi2011Parameterized,
  author = {Johari, Ramesh and Tsitsiklis, John N.},
  title = {Parameterized supply function bidding: Equilibrium and efficiency},
  journal = {Operations Research},
  volume = {59},
  number = {5},
  pages = {1079--1089},
  year = {2011},
  external = {http://dx.doi.org/10.1287/opre.1110.0980}
}
```
DiPalantino, D., Johari, R., & Weintraub, G. Y. (2011). Competition and contracting in service industries. Operations Research Letters, 39(5), 390–396.
In service industries with congestion effects, two very different contractual structures are commonly observed, depending on whether or not firms choose to offer a guaranteed service level. We analyze the impact of these choices on market outcomes in oligopolistic industries. Our results highlight how different contractual agreements change the intensity of price competition in service industries. Broadly speaking, we show that competition is intensified when firms choose to offer service level guarantees.
```
@article{DiPJohWei2011Competition,
  author = {DiPalantino, Dominic and Johari, Ramesh and Weintraub, Gabriel Y.},
  title = {Competition and contracting in service industries},
  journal = {Operations Research Letters},
  volume = {39},
  number = {5},
  pages = {390--396},
  year = {2011},
  external = {http://dx.doi.org/10.1016/j.orl.2011.06.011}
}
```
Aperjis, C., Johari, R., & Freedman, M. J. (2011). Bilateral and multilateral exchanges for peer-assisted content distribution. IEEE/ACM Transactions on Networking, 19(5), 1290–1303.
Users of the BitTorrent file-sharing protocol and its variants are incentivized to contribute their upload capacity in a bilateral manner: Downloading is possible in return for uploading to the same user. An alternative is to use multilateral exchange to match user demand for content to available supply at other users in the system. We provide a formal comparison of peer-to-peer system designs based on bilateral exchange with those that enable multilateral exchange via a price-based market mechanism to match supply and demand. First, we compare the two types of exchange in terms of the equilibria that arise. A multilateral equilibrium allocation is Pareto-efficient, while we demonstrate that bilateral equilibrium allocations are not Pareto-efficient in general. We show that Pareto efficiency represents the “gap” between bilateral and multilateral equilibria: A bilateral equilibrium allocation corresponds to a multilateral equilibrium allocation if and only if it is Pareto-efficient. Our proof exploits the fact that Pareto efficiency implies reversibility of an appropriately constructed Markov chain. Second, we compare the two types of exchange through the expected percentage of users that can trade in a large system, assuming a fixed file popularity distribution. Our theoretical results as well as analysis of a BitTorrent dataset provide quantitative insight into regimes where bilateral exchange may perform quite well even though it does not always give rise to Pareto-efficient equilibrium allocations.
```
@article{ApeJohFre2011Bilateral,
  author = {Aperjis, Christina and Johari, Ramesh and Freedman, Michael J.},
  title = {Bilateral and multilateral exchanges for peer-assisted content distribution},
  journal = {{IEEE/ACM} Transactions on Networking},
  volume = {19},
  number = {5},
  pages = {1290--1303},
  year = {2011},
  external = {http://dx.doi.org/10.1109/TNET.2011.2114898}
}
```
Johari, R., Weintraub, G. Y., & Roy, B. V. (2010). Investment and market structure in industries with congestion. Operations Research, 58(5), 1303–1317.
We analyze investment incentives and market structure under oligopoly competition in industries with congestion effects. Our results are particularly focused on models inspired by modern technology-based services such as telecommunications and computing services. We consider situations where firms compete by simultaneously choosing prices and investments; increasing investment reduces the congestion disutility experienced by consumers. We define a notion of returns to investment, according to which congestion models inspired by delay exhibit increasing returns, whereas loss models exhibit nonincreasing returns. For a broad range of models with nonincreasing returns to investment, we characterize and establish uniqueness of pure-strategy Nash equilibrium. We also provide conditions for existence of pure-strategy Nash equilibrium. We extend our analysis to a model in which firms must additionally decide whether to enter the industry. Our theoretical results contribute to the basic understanding of competition in service industries and yield insight into business and policy considerations.
```
@article{JohWeiVan2010Investment,
  author = {Johari, Ramesh and Weintraub, Gabriel Y. and Roy, Benjamin Van},
  title = {Investment and market structure in industries with congestion},
  journal = {Operations Research},
  volume = {58},
  number = {5},
  pages = {1303--1317},
  year = {2010},
  external = {http://dx.doi.org/10.1287/opre.1100.0827}
}
```
Aperjis, C., & Johari, R. (2010). Optimal windows for aggregating ratings in electronic marketplaces. Management Science, 56(5), 864–880.
A seller in an online marketplace with an effective reputation mechanism should expect that dishonest behavior results in higher payments now whereas honest behavior results in a better reputation—and thus higher payments—in the future. We study the Window Aggregation Mechanism, a widely used class of mechanisms that shows the average value of the seller’s ratings within some fixed window of past transactions. We suggest approaches for choosing the window size that maximizes the range of parameters for which it is optimal for the seller to be truthful. 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.
```
@article{ApeJoh2010Optimal,
  author = {Aperjis, Christina and Johari, Ramesh},
  title = {Optimal windows for aggregating ratings in electronic marketplaces},
  journal = {Management Science},
  volume = {56},
  number = {5},
  pages = {864--880},
  year = {2010},
  external = {http://dx.doi.org/10.1287/mnsc.1090.1145}
}
```
Özgür, A., Johari, R., Tse, D. N. C., & Lévêque, O. (2010). Information-theoretic operating regimes of large wireless networks. IEEE Transactions on Information Theory, 56(1), 427–437.
In analyzing the point-to-point wireless channel, insights about two qualitatively different operating regimes-bandwidth and power-limited-have proven indispensable in the design of good communication schemes. In this paper, we propose a new scaling law formulation for wireless networks that allows us to develop a theory that is analogous to the point-to-point case. We identify fundamental operating regimes of wireless networks and derive architectural guidelines for the design of optimal schemes. Our analysis shows that in a given wireless network with arbitrary size, area, power, bandwidth, etc., there are three parameters of importance: the short-distance signal-to-noise ratio (SNR), the long-distance SNR, and the power path loss exponent of the environment. Depending on these parameters, we identify four qualitatively different regimes. One of these regimes is especially interesting since it is fundamentally a consequence of the heterogeneous nature of links in a network and does not occur in the point-to-point case; the network capacity is both power and bandwidth limited. This regime has thus far remained hidden due to the limitations of the existing formulation. Existing schemes, either multihop transmission or hierarchical cooperation, fail to achieve capacity in this regime; we propose a new hybrid scheme that achieves capacity.
```
@article{OzgJohTseLev2010Information,
  author = {{\"{O}}zg{\"{u}}r, Ayfer and Johari, Ramesh and Tse, David N. C. and L{\'{e}}v{\^{e}}que, Olivier},
  title = {Information-theoretic operating regimes of large wireless networks},
  journal = {{IEEE} Transactions on Information Theory},
  volume = {56},
  number = {1},
  pages = {427--437},
  year = {2010},
  external = {http://dx.doi.org/10.1109/TIT.2009.2034819}
}
```
Shakkottai, S., & Johari, R. (2010). Demand-aware content distribution on the Internet. IEEE/ACM Transactions on Networking, 18(2), 476–489.
The rapid growth of media content distribution on the Internet in the past few years has brought with it commensurate increases in the costs of distributing that content. Can the content distributor defray these costs through a more innovative approach to distribution? In this paper, we evaluate the benefits of a hybrid system that combines peer-to-peer and a centralized client-server approach against each method acting alone. A key element of our approach is to explicitly model the temporal evolution of demand. In particular, we employ a word-of-mouth demand evolution model due to Bass [2] to represent the evolution of interest in a piece of content. Our analysis is carried out in an order scaling depending on the total potential mass of customers in the market. Using this approach, we study the relative performance of peer-to-peer and centralized client-server schemes, as well as a hybrid of the two–both from the point of view of consumers as well as the content distributor.We show how awareness of demand can be used to attain a given average delay target with lowest possible utilization of the central server by using the hybrid scheme.We also show how such awareness can be used to take provisioning decisions. Our insights are obtained in a fluid model and supported by stochastic simulations.
```
@article{ShaJoh2010Demand,
  author = {Shakkottai, Srinivas and Johari, Ramesh},
  title = {Demand-aware content distribution on the Internet},
  journal = {{IEEE/ACM} Transactions on Networking},
  volume = {18},
  number = {2},
  pages = {476--489},
  year = {2010},
  external = {http://doi.acm.org/10.1145/1816262.1816273}
}
```
Johari, R., & Tsitsiklis, J. N. (2009). Efficiency of scalar-parameterized mechanisms. Operations Research, 57(4), 823–839.
We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we restrict to mechanisms that satisfy certain scalability constraints motivated by large-scale communication networks; in particular, we restrict attention to mechanisms where users are restricted to one-dimensional strategy spaces. We first study the efficiency guarantees possible when the mechanism is not allowed to price differentiate. We study the worst-case efficiency loss (ratio of the utility associated with a Nash equilibrium to the maximum possible utility), and show that Kelly’s proportional allocation mechanism minimizes the efficiency loss when users are price anticipating. We then turn our attention to mechanisms where price differentiation is permitted; using an adaptation of the Vickrey-Clarke-Groves class of mechanisms, we construct a class of mechanisms with one-dimensional strategy spaces where Nash equilibria are fully efficient. These mechanisms are shown to be fully efficient even in general convex environments, under reasonable assumptions. Our results highlight 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.
```
@article{JohTsi2009Efficiency,
  author = {Johari, Ramesh and Tsitsiklis, John N.},
  title = {Efficiency of scalar-parameterized mechanisms},
  journal = {Operations Research},
  volume = {57},
  number = {4},
  pages = {823--839},
  year = {2009},
  external = {http://dx.doi.org/10.1287/opre.1080.0638}
}
```
Arcaute, E., Johari, R., & Mannor, S. (2009). Network formation: Bilateral contracting and myopic dynamics. IEEE Transactions on Automatic Control, 54(8), 1765–1778.
We consider a network formation game where nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form bidirectional communication links; once the network is formed, traffic is routed along shortest paths (if possible). Cost is incurred to a node from four sources: 1) routing traffic; 2) maintaining links to other nodes; 3) disconnection from destinations the node wishes to reach; and 4) payments made to other nodes. We assume that a network is stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together (a variation on the notion of pairwise stability). We study such a game under a form of myopic best response dynamics. In choosing their action, nodes optimize their single period payoff only. We characterize a simple set of assumptions under which these dynamics converge to a stable network; we also characterize an important special case, where the dynamics converge to a star centered at a node with minimum cost for routing traffic. In this sense, our dynamics naturally select an efficient equilibrium.
```
@article{ArcJohMan2009Network,
  author = {Arcaute, Esteban and Johari, Ramesh and Mannor, Shie},
  title = {Network formation: Bilateral contracting and myopic dynamics},
  journal = {{IEEE} Transactions on Automatic Control},
  volume = {54},
  number = {8},
  pages = {1765--1778},
  year = {2009},
  external = {http://dx.doi.org/10.1109/TAC.2009.2024564}
}
```
Waslander, S. L., Roy, K., Johari, R., & Tomlin, C. J. (2008). Lump sum markets for air traffic control with competitive airlines. Proceedings of the IEEE, 96(12), 2113–2130.
Air traffic flow control during adverse weather conditions is managed by the Federal Aviation Administration in today’s air traffic system, although it is the individual airlines that are in the best position to assess the costs of disruptions to scheduled operations. To improve the efficiency of resource allocation, a market mechanism is proposed that enables airlines to participate directly in the flow control decision-making process. Since airlines can be expected to behave strategically, a lump-sum market mechanism is used for which existence of a Nash equilibrium and a bound on the worst case efficiency loss have been shown for agents that anticipate the effects of their own bids on resource prices. The convergence properties of this mechanism are studied for a two-player game with linear utilities, which reveals that restricting the airline bid update step-size can result in a wider range of stable bidding processes. The mechanism is then applied to an air traffic flow control scenario for multiple airports in the northeastern United States, which demonstrates the feasibility of performing market-based resource allocation within the time horizon for reliable weather predictions.
```
@article{WasRoyJohTom2008Lump,
  author = {Waslander, Steven L. and Roy, Kaushik and Johari, Ramesh and Tomlin, Claire J.},
  title = {Lump sum markets for air traffic control with competitive airlines},
  journal = {Proceedings of the {IEEE}},
  volume = {96},
  number = {12},
  pages = {2113--2130},
  year = {2008},
  external = {http://dx.doi.org/10.1109/JPROC.2008.2006197}
}
```
Acemoglu, D., Johari, R., & Ozdaglar, A. E. (2007). Partially optimal routing. IEEE Journal on Selected Areas in Communications, 25(6), 1148–1160.
Most large-scale communication networks, such as the Internet, consist of interconnected administrative domains. While source (or selfish) routing, where transmission follows the least cost path for each source, is reasonable across domains, service providers typically engage in traffic engineering to improve operating performance within their own network. Motivated by this observation, we develop and analyze a model of partially optimal routing, where optimal routing within subnetworks is overlaid with selfish routing across domains. We demonstrate that optimal routing within a subnetwork does not necessarily improve the performance of the overall network. In particular, when Braess’ paradox occurs in the network, partially optimal routing may lead to worse overall network performance. We provide bounds on the worst-case loss of efficiency that can occur due to partially optimal routing. For example, when all congestion costs can be represented by affine latency functions and all administrative domains have a single entry and exit point, the worst-case loss of efficiency is no worse than 25% relative to the optimal solution. In the presence of administrative domains incorporating multiple entry and/or exit points, however, the performance of partially optimal routing can be arbitrarily inefficient even with linear latencies. We also provide conditions for traffic engineering to be individually optimal for service providers.
```
@article{AceJohOzd2007Partially,
  author = {Acemoglu, Daron and Johari, Ramesh and Ozdaglar, Asuman E.},
  title = {Partially optimal routing},
  journal = {{IEEE} Journal on Selected Areas in Communications},
  volume = {25},
  number = {6},
  pages = {1148--1160},
  year = {2007},
  external = {http://dx.doi.org/10.1109/JSAC.2007.070809}
}
```
Feamster, N., Johari, R., & Balakrishnan, H. (2007). Implications of autonomy for the expressiveness of policy routing. IEEE/ACM Transactions on Networking, 15(6), 1266–1279.
Thousands of competing autonomous systems must cooperate with each other to provide global Internet connectivity. Each autonomous system (AS) encodes various economic, business, and performance decisions in its routing policy. The current interdomain routing system enables each AS to express policy using rankings that determine how each router in the AS chooses among different routes to a destination, and filters that determine which routes are hidden from each neighboring AS. Because the Internet is composed of many independent, competing networks, the interdomain routing system should provide autonomy, allowing network operators to set their rankings independently, and to have no constraints on allowed filters. This paper studies routing protocol stability under these conditions. We first demonstrate that "next-hop rankings," commonly used in practice, may not ensure routing stability. We then prove that, when providers can set rankings and filters autonomously, guaranteeing that the routing system will converge to a stable path assignment imposes strong restrictions on the rankings ASes are allowed to choose. We discuss the implications of these results for the future of interdomain routing.
```
@article{FeaJohBal2007Implications,
  author = {Feamster, Nick and Johari, Ramesh and Balakrishnan, Hari},
  title = {Implications of autonomy for the expressiveness of policy routing},
  journal = {{IEEE/ACM} Transactions on Networking},
  volume = {15},
  number = {6},
  pages = {1266--1279},
  year = {2007},
  external = {http://doi.acm.org/10.1145/1373476.1373481}
}
```
Johari, R., Mannor, S., & Tsitsiklis, J. N. (2006). A contract-based model for directed network formation. Games and Economic Behavior, 56(2), 201–224.
We consider a network game where the nodes of the network wish to form a graph to route traffic between themselves. We present a model where costs are incurred for routing traffic, as well as for a lack of network connectivity. We focus on directed links and the link stability equilibrium concept, and characterize connected link stable equilibria. The structure of connected link stable networks is analyzed for several special cases.
```
@article{JohManTsi2006Contract,
  author = {Johari, Ramesh and Mannor, Shie and Tsitsiklis, John N.},
  title = {A contract-based model for directed network formation},
  journal = {Games and Economic Behavior},
  volume = {56},
  number = {2},
  pages = {201--224},
  year = {2006},
  external = {http://dx.doi.org/10.1016/j.geb.2005.08.010}
}
```
Johari, R., & Tsitsiklis, J. N. (2006). A scalable network resource allocation mechanism with bounded efficiency loss. IEEE Journal on Selected Areas in Communications, 24(5), 992–999.
The design of pricing mechanisms for network resource allocation has two important objectives: 1) a simple and scalable end-to-end implementation and 2) efficiency of the resulting equilibria. Both objectives are met by certain recently proposed mechanisms when users are price taking, but not when users can anticipate the effects of their actions on the resulting prices. In this paper, we partially close this gap, by demonstrating an alternative resource allocation mechanism which is scalable and guarantees a fully efficient allocation when users are price taking. In addition, when links have affine marginal cost, this mechanism has efficiency loss bounded by 1/3 when users are price anticipating. These results are derived by studying Cournot games, and in the process we derive the first nontrivial constant factor bounds on efficiency loss in these well-studied economic models.
```
@article{JohTsi2006Scalable,
  author = {Johari, Ramesh and Tsitsiklis, John N.},
  title = {A scalable network resource allocation mechanism with bounded efficiency
                 loss},
  journal = {{IEEE} Journal on Selected Areas in Communications},
  volume = {24},
  number = {5},
  pages = {992--999},
  year = {2006},
  external = {http://doi.ieeecomputersociety.org/10.1109/JSAC.2006.872880}
}
```
Johari, R., Mannor, S., & Tsitsiklis, J. N. (2005). Efficiency loss in a network resource allocation game: The case of elastic supply. IEEE Transactions on Automatic Control, 50(11), 1712–1724.
We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent through the link. It is known that as long as users do not anticipate the effect of their actions on prices, a simple proportional pricing mechanism can maximize the sum of users’ utilities minus the cost (called aggregate surplus). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, we consider the possibility that users anticipate the effect of their actions on link prices. Under the assumption that the links’ marginal cost functions are convex, we establish existence of a Nash equilibrium. We show that the aggregate surplus at a Nash equilibrium is no worse than a factor of \(4\sqrt2-5\)times the optimal aggregate surplus; thus, the efficiency loss when users are selfish is no more than approximately 34%.
```
@article{JohManTsi2005Efficiency,
  author = {Johari, Ramesh and Mannor, Shie and Tsitsiklis, John N.},
  title = {Efficiency loss in a network resource allocation game: The case of
                 elastic supply},
  journal = {{IEEE} Transactions on Automatic Control},
  volume = {50},
  number = {11},
  pages = {1712--1724},
  year = {2005},
  external = {http://dx.doi.org/10.1109/TAC.2005.858687}
}
```
Johari, R., & Tsitsiklis, J. N. (2004). Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 29(3), 407–435.
We explore the properties of a congestion game in which users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we establish that the aggregate utility received by the users is at least 3/4 of the maximum possible aggregate utility. We also consider extensions to a network context, where users submit individual payments for each link in the network they may wish to use. In this network model, we again show that the selfish behavior of the users leads to an aggregate utility that is no worse than 3/4 of the maximum possible aggregate utility. We also show that the same analysis extends to a wide class of resource allocation systems where end users simultaneously require multiple scarce resources. These results form part of a growing literature on the “price of anarchy,” i.e., the extent to which selfish behavior affects system efficiency.
```
@article{JohTsi2004Efficiency,
  author = {Johari, Ramesh and Tsitsiklis, John N.},
  title = {Efficiency loss in a network resource allocation game},
  journal = {Mathematics of Operations Research},
  volume = {29},
  number = {3},
  pages = {407--435},
  year = {2004},
  external = {http://dx.doi.org/10.1287/moor.1040.0091}
}
```
Johari, R., & Tan, D. K. H. (2001). End-to-end congestion control for the Internet: Delays and stability. IEEE/ACM Transactions on Networking, 9(6), 818–832.
Under the assumption that queueing delays will eventually become small relative to propagation delays, we derive stability results for a fluid flow model of end-to-end Internet congestion control. The theoretical results of the paper are intended to be decentralized and locally implemented: each end system needs knowledge only of its own round-trip delay. Criteria for local stability and rate of convergence are completely characterized for a single resource, single user system. Stability criteria are also described for networks where all users share the same round-trip delay. Numerical experiments investigate extensions to more general networks. Through simulations, we are able to evaluate the relative importance of queueing delays and propagation delays on network stability. Finally, we suggest how these results may be used to design network resources.
```
@article{JohTan2001End,
  author = {Johari, Ramesh and Tan, David Kim Hong},
  title = {End-to-end congestion control for the Internet: Delays and stability},
  journal = {{IEEE/ACM} Transactions on Networking},
  volume = {9},
  number = {6},
  pages = {818--832},
  year = {2001},
  external = {http://dx.doi.org/10.1109/90.974534}
}
```
Johari, R., Marks, J., Partovi, A., & Shieber, S. M. (1997). Automatic Yellow-Pages pagination and layout. Journal of Heuristics, 2(4), 321–342.
The compact and harmonious layout of ads and text is a fundamental and costly step in the production of commercial telephone directories (“Yellow Pages”). We formulate a canonical version of Yellow-Pages pagination and layout (YPPL) as an optimization problem in which the task is to position ads and text-stream segments on sequential pages so as to minimize total page length and maximize certain layout aesthetics, subject to constraints derived from page-format requirements and positional relations between ads and text. We present a heuristic-search approach to the YPPL problem. Our algorithm has been applied to a sample of real telephone-directory data, and produces solutions that are significantly shorter and better than the published ones.
```
@article{JohMarParShi1997Automatic,
  author = {Johari, Ramesh and Marks, Joe and Partovi, Ali and Shieber, Stuart M.},
  title = {Automatic Yellow-Pages pagination and layout},
  journal = {Journal of Heuristics},
  volume = {2},
  number = {4},
  pages = {321--342},
  year = {1997},
  external = {http://dx.doi.org/10.1007/BF00132503}
}
```

Conference papers

Spang, B., Hannan, V., Kunamalla, S., Huang, T.-Y., McKeown, N., & Johari, R. (2021). Unbiased experiments in congested networks. In Internet Measurement Conference (IMC).
When developing a new networking algorithm, it is established practice to run a randomized experiment, or A/B test, to evaluate its performance. In an A/B test, traffic is randomly allocated between a treatment group, which uses the new algorithm, and a control group, which uses the existing algorithm. However, because networks are congested, both treatment and control traffic compete against each other for resources in a way that biases the outcome of these tests. This bias can have a surprisingly large effect; for example, in lab A/B tests with two widely used congestion control algorithms, the treatment appeared to deliver 150% higher throughput when used by a few flows, and 75% lower throughput when used by most flows—despite the fact that the two algorithms have identical throughput when used by all traffic. Beyond the lab, we show that A/B tests can also be biased at scale. In an experiment run in cooperation with Netflix, estimates from A/B tests mistake the direction of change of some metrics, miss changes in other metrics, and overestimate the size of effects. We propose alternative experiment designs, previously used in online platforms, to more accurately evaluate new algorithms and allow experimenters to better understand the impact of congestion on their tests.
```
@inproceedings{SpaHanKunHuaMcKJoh2021Unbiased,
  author = {Spang, Bruce and Hannan, Veronica and Kunamalla, Shravya and Huang, Te{-}Yuan and McKeown, Nick and Johari, Ramesh},
  title = {Unbiased experiments in congested networks},
  booktitle = {Internet Measurement Conference (IMC)},
  year = {2021},
  external = {https://doi.org/10.1145/3487552.3487851}
}
```
Glynn, P., Johari, R., & Rasouli, M. (2020). Adaptive Experimental Design with Temporal Interference: A Maximum Likelihood Approach. In Neural Information Processing Systems (NeurIPS).
Suppose an online platform wants to compare a treatment and control policy, e.g., two different matching algorithms in a ridesharing system, or two different inventory management algorithms in an online retail site. Standard randomized controlled trials are typically not feasible, since the goal is to estimate policy performance on the entire system. Instead, the typical current practice involves dynamically alternating between the two policies for fixed lengths of time, and comparing the average performance of each over the intervals in which they were run as an estimate of the treatment effect. However, this approach suffers from *temporal interference*: one algorithm alters the state of the system as seen by the second algorithm, biasing estimates of the treatment effect. Further, the simple non-adaptive nature of such designs implies they are not sample efficient. We develop a benchmark theoretical model in which to study optimal experimental design for this setting. We view testing the two policies as the problem of estimating the steady state difference in reward between two unknown Markov chains (i.e., policies). We assume estimation of the steady state reward for each chain proceeds via nonparametric maximum likelihood, and search for consistent (i.e., asymptotically unbiased) experimental designs that are efficient (i.e., asymptotically minimum variance). Characterizing such designs is equivalent to a Markov decision problem with a minimum variance objective; such problems generally do not admit tractable solutions. Remarkably, in our setting, using a novel application of classical martingale analysis of Markov chains via Poisson’s equation, we characterize efficient designs via a succinct convex optimization problem. We use this characterization to propose a consistent, efficient online experimental design that adaptively samples the two Markov chains.
```
@inproceedings{GlyJohRas2020Adaptive,
  author = {Glynn, Peter and Johari, Ramesh and Rasouli, Mohammad},
  title = {Adaptive Experimental Design with Temporal Interference: A Maximum
    Likelihood Approach},
  booktitle = {Neural Information Processing Systems (NeurIPS)},
  year = {2020},
  external = {http://arxiv.org/abs/2006.05591}
}
```
Bayati, M., Hamidi, N., Johari, R., & Khosravi, K. (2020). Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms. In Neural Information Processing Systems (NeurIPS).
We study the structure of regret-minimizing policies in the many-armed Bayesian multi-armed bandit problem: in particular, with k the number of arms and T the time horizon, we consider the case where k > \sqrtT. We first show that subsampling is a critical step for designing optimal policies. In particular, the standard UCB algorithm leads to sub-optimal regret bounds in this regime. However, a subsampled UCB (SS-UCB), which samples \sqrtT arms and executes UCB only on that subset, is rate-optimal. Despite theoretically optimal regret, even SS-UCB performs poorly due to excessive exploration of suboptimal arms. In fact, in numerical experiments SS-UCB performs worse than a simple greedy algorithm (and its subsampled version) that pulls the current empirical best arm at every time period. We show that these insights hold even in a contextual setting, using real-world data. These empirical results suggest a novel form of free exploration in the many-armed regime that benefits greedy algorithms. We theoretically study this new source of free exploration and find that it is deeply connected to the distribution of a certain tail event for the prior distribution of arm rewards. This is a fundamentally distinct phenomenon from free exploration as discussed in the recent literature on contextual bandits, where free exploration arises due to variation in contexts. We prove that the subsampled greedy algorithm is rate-optimal for Bernoulli bandits when k > \sqrtT, and achieves sublinear regret with more general distributions. This is a case where theoretical rate optimality does not tell the whole story: when complemented by the empirical observations of our paper, the power of greedy algorithms becomes quite evident. Taken together, from a practical standpoint, our results suggest that in applications it may be preferable to use a variant of the greedy algorithm in the many-armed regime.
```
@inproceedings{BayHamJohKho2020Unreasonable,
  author = {Bayati, Mohsen and Hamidi, Nima and Johari, Ramesh and Khosravi, Khashayar},
  title = {Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms},
  booktitle = {Neural Information Processing Systems (NeurIPS)},
  year = {2020},
  external = {https://arxiv.org/abs/2002.10121}
}
```
Johari, R., Li, H., & Weintraub, G. (2020). Experiment Design in Two-Sided Platforms: An Analysis of Bias. In ACM Conference on Economics and Computation (EC).
We develop an analytical framework to study experimental design in two-sided platforms. In the settings we consider, customers rent listings; rented listings are occupied for some amount of time, then become available. Platforms typically use two common designs to study interventions in such settings: customer-side randomization (CR), and listing-side randomization (LR), along with associated estimators. We develop a stochastic model and associated mean field limit to capture dynamics in such systems, and use our model to investigate how performance of these estimators is affected by interference effects between listings and between customers. Good experimental design depends on market balance: we show that in highly demand-constrained markets, CR is unbiased, while LR is biased; conversely, in highly supply-constrained markets, LR is unbiased, while CR is biased. We also study a design based on two-sided randomization (TSR) where both customers and listings are randomized to treatment and control, and show that appropriate choices of such designs can be unbiased in both extremes of market balance, and also yield low bias in intermediate regimes of market balance.
```
@inproceedings{JohLiWei2020Experiment_EC,
  author = {Johari, Ramesh and Li, Hannah and Weintraub, Gabriel},
  title = {Experiment Design in Two-Sided Platforms: An Analysis of Bias},
  booktitle = {{ACM} Conference on Economics and Computation (EC)},
  year = {2020},
  external = {https://arxiv.org/abs/2002.05670}
}
```
Garg, N., & Johari, R. (2020). Designing Informative Rating Systems for Online Platforms: Evidence from Two Experiments. In ACM Conference on Economics and Computation (EC).
Platforms critically rely on rating systems to learn the quality of market participants. In practice, however, these ratings are often highly inflated, drastically reducing the signal available to distinguish quality. We consider two questions: First, can rating systems better discriminate quality by altering the meaning and relative importance of the levels in the rating system? And second, if so, how should the platform optimize these choices in the design of the rating system? We first analyze the results of a randomized controlled trial on an online labor market in which an additional question was added to the feedback form. Between treatment conditions, we vary the question phrasing and answer choices. We further run an experiment on Amazon Mechanical Turk with similar structure, to confirm the labor market findings. Our tests reveal that current inflationary norms can in fact be countered by re-anchoring the meaning of the levels of the rating system. In particular, scales that are positive-skewed and provide specific interpretations for what each label means yield rating distributions that are much more informative about quality. Second, we develop a theoretical framework to optimize the design of a rating system by choosing answer labels and their numeric interpretations in a manner that maximizes the rate of convergence to the true underlying quality distribution. Finally, we run simulations with an empirically calibrated model and use these to study the implications for optimal rating system design. Our simulations demonstrate that our modeling and optimization approach can substantially improve the quality of information obtained over baseline designs. Overall, our study illustrates that rating systems that are informative in practice can be designed, and demonstrates how to design them in a principled manner.
```
@inproceedings{GarJoh2020Designing,
  author = {Garg, Nikhil and Johari, Ramesh},
  title = {Designing Informative Rating Systems for Online Platforms: Evidence from Two Experiments},
  booktitle = {{ACM} Conference on Economics and Computation (EC)},
  year = {2020},
  external = {https://arxiv.org/abs/1810.13028}
}
```
Shah, V., Blanchet, J., & Johari, R. (2019). Semi-parametric dynamic contextual pricing. In Neural Information Processing Systems (NeurIPS).
We consider a canonical revenue maximization problem where customers arrive sequentially; each customer is interested in buying one product, and the customer purchases the product if her valuation for it exceeds the price set by the seller. The valuations of customers are not observed by the seller; however, the seller can leverage contextual information available to her in the form of noisy covariate vectors describing the customer’s history and the product’s type to set prices. The seller can learn the relationship between covariates and customer valuations by experimenting with prices and observing transaction outcomes. We consider a semi-parametric model where the relationship between the expectation of the log of valuation and the covariates is linear (hence parametric) and the residual uncertainty distribution, i.e., the noise distribution, is non-parametric. We develop a pricing policy, DEEP-C, which learns this relationship with minimal exploration and in turn achieves optimal regret asymptotically in the time horizon.
```
@inproceedings{ShaBlaJoh2019Semi,
  author = {Shah, Virag and Blanchet, Jose and Johari, Ramesh},
  title = {Semi-parametric dynamic contextual pricing},
  booktitle = {Neural Information Processing Systems (NeurIPS)},
  year = {2019},
  external = {https://arxiv.org/abs/1901.02045}
}
```
Schmit, S., Shah, V., & Johari, R. (2019). Optimal Testing in the Experiment-Rich Regime. In Conference on Artificial Intelligence and Statistics (AISTATS).
Motivated by the widespread adoption of large-scale A/B testing in industry, we propose a new experimentation framework for the setting where potential experiments are abundant (i.e., many hypotheses are available to test), and observations are costly; we refer to this as the experiment-rich regime. Such scenarios require the experimenter to internalize the opportunity cost of assigning a sample to a particular experiment. We fully characterize the optimal policy and give an algorithm to compute it. Furthermore, we develop a simple heuristic that also provides intuition for the optimal policy. We use simulations based on real data to compare both the optimal algorithm and the heuristic to other natural alternative experimental design frameworks. In particular, we discuss the paradox of power: high-powered classical tests can lead to highly inefficient sampling in the experiment-rich regime.
```
@inproceedings{SchShaJoh2018Experimentation,
  author = {Schmit, Sven and Shah, Virag and Johari, Ramesh},
  title = {Optimal Testing in the Experiment-Rich Regime},
  booktitle = {Conference on 
  Artificial Intelligence and Statistics (AISTATS)},
  year = {2019},
  external = {https://arxiv.org/abs/1805.11754}
}
```
Garg, N., & Johari, R. (2019). Designing Optimal Binary Rating Systems. In Conference on Artificial Intelligence and Statistics (AISTATS).
Modern online platforms rely on effective rating systems to learn about items. We consider the optimal design of rating systems that collect *binary feedback* after transactions. We make three contributions. First, we formalize the performance of a rating system as the speed with which it recovers the true underlying ranking on items (in a large deviations sense), accounting for both items’ underlying match rates and the platform’s preferences. Second, we provide an efficient algorithm to compute the binary feedback system that yields the highest such performance. Finally, we show how this theoretical perspective can be used to empirically design an implementable, approximately optimal rating system, and validate our approach using real-world experimental data collected on Amazon Mechanical Turk.
```
@inproceedings{GarJoh2019Designing,
  author = {Garg, Nikhil and Johari, Ramesh},
  title = {Designing Optimal Binary Rating Systems},
  booktitle = {Conference on 
  Artificial Intelligence and Statistics (AISTATS)},
  year = {2019},
  external = {https://arxiv.org/abs/1806.06908}
}
```
Johari, R., Kamble, V., Krishnaswamy, A. K., & Li, H. (2018). Exploration vs. Exploitation in Team Formation for Collaborative Work. In Conference on Web and Internet Economics (WINE).
An online labor platform faces an online learning problem in matching workers with jobs and using the performance on these jobs to create better future matches. This learning problem is complicated by the rise of complex tasks on these platforms, such as web development and product design, that require a team of workers to complete. The success of a job is now a function of the skills and contributions of all workers involved, which may be unknown to both the platform and the client who posted the job. These team matchings result in a structured correlation between what is known about the individuals and this information can be utilized to create better future matches. We analyze two natural settings where the performance of a team is dictated by its strongest and its weakest member, respectively. We find that both problems pose an exploration-exploitation tradeoff between learning the performance of untested teams and repeating previously tested teams that resulted in a good performance. We establish fundamental regret bounds and design near-optimal algorithms that uncover several insights into these tradeoffs.
```
@inproceedings{JohKamKriLi2018Exploration,
  author = {Johari, Ramesh and Kamble, Vijay and Krishnaswamy, Anilesh K. and Li, Hannah},
  title = {Exploration vs. Exploitation in Team Formation for Collaborative Work},
  booktitle = {Conference on Web and Internet Economics (WINE)},
  year = {2018},
  external = {https://arxiv.org/abs/1809.06937}
}
```
Shah, V., Blanchet, J., & Johari, R. (2018). Bandit Learning with Positive Externalities. In Advances in Neural Information Processing Systems (NIPS).
In many platforms, user arrivals exhibit a self-reinforcing behavior: future user arrivals are likely to have preferences similar to users who were satisfied in the past. In other words, arrivals exhibit positive externalities. We study multiarmed bandit (MAB) problems with positive externalities. We show that the self-reinforcing preferences may lead standard benchmark algorithms such as UCB to exhibit linear regret. We develop a new algorithm, Balanced Exploration (BE), which explores arms carefully to avoid suboptimal convergence of arrivals before sufficient evidence is gathered. We also introduce an adaptive variant of BE which successively eliminates suboptimal arms. We analyze their asymptotic regret, and establish optimality by showing that no algorithm can perform better.
```
@inproceedings{ShaBlaJoh2018Bandit,
  author = {Shah, Virag and Blanchet, Jose and Johari, Ramesh},
  title = {Bandit Learning with Positive Externalities},
  booktitle = {Advances in Neural Information Processing Systems (NIPS)},
  year = {2018},
  external = {https://arxiv.org/abs/1802.05693}
}
```
Schmit, S., & Johari, R. (2018). Learning with abandonment. In International Conference on Machine Learning (ICML).
Consider a platform that wants to learn a personalized policy for each user, but the platform faces the risk of a user abandoning the platform if they are dissatisfied with the actions of the platform. For example, a platform is interested in personalizing the number of newsletters it sends, but faces the risk that the user unsubscribes forever. We propose a general thresholded learning model for scenarios like this, and discuss the structure of optimal policies. We describe salient features of optimal personalization algorithms and how feedback the platform receives impacts the results. Furthermore, we investigate how the platform can efficiently learn the heterogeneity across users by interacting with a population and provide performance guarantees.
```
@inproceedings{SchJoh2018Learning,
  author = {Schmit, Sven and Johari, Ramesh},
  title = {Learning with abandonment},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = {2018},
  external = {http://proceedings.mlr.press/v80/schmit18a.html}
}
```
Chaturapruek, S., Dee, T. S., Johari, R., Kizilcec, R. F., & Stevens, M. L. (2018). How a data-driven course planning tool affects college students’ GPA: evidence from two field experiments. In ACM Conference on Learning at Scale.
College students rely on increasingly data-rich environments when making learning-relevant decisions about the courses they take and their expected time commitments. However, we know little about how their exposure to such data may influence student course choice, effort regulation, and performance. We conducted a large-scale field experiment in which all the undergraduates at a large, selective university were randomized to an encouragement to use a course-planning web application that integrates information from official transcripts from the past fifteen years with detailed end-of-course evaluation surveys. We found that use of the platform lowered students’ GPA by 0.28 standard deviations on average. In a subsequent field experiment, we varied access to information about course grades and time commitment on the platform and found that access to grade information in particular lowered students’ overall GPA. Our exploratory analysis suggests these effects are not due to changes in the portfolio of courses that students choose, but rather by changes to their behavior within courses.
```
@inproceedings{ChaDeeJohKizSte2018How,
  author = {Chaturapruek, Sorathan and Dee, Thomas S. and Johari, Ramesh and Kizilcec, Ren{\'{e}} F. and Stevens, Mitchell L.},
  title = {How a data-driven course planning tool affects college students' {GPA:}
                 evidence from two field experiments},
  booktitle = {{ACM} Conference on Learning at Scale},
  year = {2018},
  external = {http://doi.acm.org/10.1145/3231644.3231668},
  note = {\textbf{Best paper award}}
}
```
Johari, R., Koomen, P., Pekelis, L., & Walsh, D. (2017). Peeking at A/B Tests: Why it matters, and what to do about it. In ACM Conference on Knowledge Discovery and Data Mining (KDD).
This paper reports on novel statistical methodology, which has been deployed by the commercial A/B testing platform Optimizely to communicate experimental results to their customers. Our methodology addresses the issue that traditional p-values and confidence intervals give unreliable inference. This is because users of A/B testing software are known to *continuously monitor* these measures as the experiment is running. We provide *always valid* p-values and confidence intervals that are provably robust to this effect. Not only does this make it safe for a user to continuously monitor, but it empowers her to detect true effects more efficiently. This paper provides simulations and numerical studies on Optimizely’s data, demonstrating an improvement in detection performance over traditional methods.
```
@inproceedings{JohKooPekWal2017Peeking,
  author = {Johari, Ramesh and Koomen, Pete and Pekelis, Leonid and Walsh, David},
  title = {Peeking at {A/B} Tests: Why it matters, and what to do about it},
  booktitle = {{ACM} Conference on Knowledge Discovery and Data Mining (KDD)},
  year = {2017},
  external = {http://doi.acm.org/10.1145/3097983.3097992}
}
```
Johari, R., Kamble, V., & Kanoria, Y. (2017). Matching while Learning. In ACM Conference on Economics and Computation (EC).
We consider the problem faced by a service platform that needs to match supply with demand, but also to learn attributes of new arrivals in order to match them better in the future. We introduce a benchmark model with heterogeneous workers and jobs that arrive over time. Job types are known to the platform, but worker types are unknown and must be learned by observing match outcomes. Workers depart after performing a certain number of jobs. The payoff from a match depends on the pair of types and the goal is to maximize the steady-state rate of accumulation of payoff. Our main contribution is a complete characterization of the structure of the optimal policy in the limit that each worker performs many jobs. The platform faces a trade-off for each worker between myopically maximizing payoffs (exploitation) and learning the type of the worker (exploration). This creates a multitude of multi-armed bandit problems, one for each worker, coupled together by the constraint on availability of jobs of different types (capacity constraints). We find that the platform should estimate a shadow price for each job type, and use the payoffs adjusted by these prices, first, to determine its learning goals and then, for each worker, (i) to balance learning with payoffs during the “exploration phase”, and (ii) to myopically match after it has achieved its learning goals during the “exploitation phase.”
```
@inproceedings{JohKamKan2017Matching,
  author = {Johari, Ramesh and Kamble, Vijay and Kanoria, Yash},
  title = {Matching while Learning},
  booktitle = {{ACM} Conference on Economics and Computation (EC)},
  year = {2017},
  external = {http://doi.acm.org/10.1145/3033274.3084095}
}
```
Riquelme, C., Johari, R., & Zhang, B. (2017). Online Active Linear Regression via Thresholding. In AAAI Conference on Artificial Intelligence.
- [ abstract ]
- [ bib ]
We consider the problem of online active learning to collect data for regression modeling. Specifically, we consider a decision maker with a limited experimentation budget who must efficiently learn an underlying linear population model. Our main contribution is a novel threshold-based algorithm for selection of most informative observations; we characterize its performance and fundamental lower bounds. We extend the algorithm and its guarantees to sparse linear regression in high-dimensional settings. Simulations suggest the algorithm is remarkably robust: it provides significant benefits over passive random sampling in real-world datasets that exhibit high nonlinearity and high dimensionality—significantly reducing both the mean and variance of the squared error.
```
@inproceedings{RiqJohZha2017Online,
  author = {Riquelme, Carlos and Johari, Ramesh and Zhang, Baosen},
  title = {Online Active Linear Regression via Thresholding},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017}
}
```
Krishnasamy, S., Sen, R., Johari, R., & Shakkottai, S. (2016). Regret of Queueing Bandits. In Advances in Neural Information Processing Systems (NIPS).
We consider a variant of the multiarmed bandit problem where jobs queue for service, and service rates of different servers may be unknown. We study algorithms that minimize queue-regret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by a genie-aided matching algorithm that knows exact service rates. A naive view of this problem would suggest that queue-regret should grow logarithmically: since queue-regret cannot be larger than classical regret, results for the standard MAB problem give algorithms that ensure queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior. In particular, the naive intuition is correct as long as the bandit algorithm’s queues have relatively long regenerative cycles: in this case queue-regret is similar to cumulative regret, and scales (essentially) logarithmically. However, we show that this "early stage" of the queueing bandit eventually gives way to a "late stage", where the optimal queue-regret scaling is O(1/t). We demonstrate an algorithm that (order-wise) achieves this asymptotic queue-regret, and also exhibits close to optimal switching time from the early stage to the late stage.
```
@inproceedings{KriSenJohSha2016Regret,
  author = {Krishnasamy, Subhashini and Sen, Rajat and Johari, Ramesh and Shakkottai, Sanjay},
  title = {Regret of Queueing Bandits},
  booktitle = {Advances in Neural Information Processing Systems {(NIPS)}},
  year = {2016},
  external = {https://nips.cc/Conferences/2016/Schedule?showEvent=8499}
}
```
Verroios, V., Papadimitriou, P., Johari, R., & Garcia-Molina, H. (2015). Client clustering for hiring modeling in work marketplaces. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD).
- [ abstract ]
- [ bib ]
An important problem that online work marketplaces face is grouping clients into clusters, so that in each cluster clients are similar with respect to their hiring criteria. Such a separation allows the marketplace to “learn” more accurately the hiring criteria in each cluster and recommend the right contractor to each client, for a successful collaboration. We propose a Maximum Likelihood definition of the “optimal” client clustering along with an efficient Expectation-Maximization clustering algorithm that can be applied in large marketplaces. Our results on the job hirings at oDesk over a seven-month period show that our client-clustering approach yields significant gains compared to “learning” the same hiring criteria for all clients. In addition, we analyze the clustering results to find interesting differences between the hiring criteria in the different groups of clients.
```
@inproceedings{VerPapJohGar2015Client,
  author = {Verroios, Vasilis and Papadimitriou, Panagiotis and Johari, Ramesh and {Garcia-Molina}, Hector},
  title = {Client clustering for hiring modeling in work marketplaces},
  booktitle = {{ACM} {SIGKDD} Conference on Knowledge Discovery and Data Mining {(KDD)}},
  year = {2015}
}
```
Michelony, A., Antonellis, I., & Johari, R. (2015). Predicting bad job outcomes in online workplaces. In Workshop on Crowdsourcing and Machine Learning (CrowdML).
More than one billion dollars’ worth of work takes place every year in online workplaces like Upwork.com and Elance.com. We analyze the structure of these jobs and build a classifier using logistic regression and gradient tree boosting to identify jobs in trouble. We then report the effectiveness of this classifier in a user experi- ment. This submission to the ICML crowdsourcing workshop is part of a longer work involving detecting and intervening on bad jobs and preventing bad jobs in the future.
```
@inproceedings{MicAntJoh2015Predicting,
  author = {Michelony, Aaron and Antonellis, Ioannis and Johari, Ramesh},
  title = {Predicting bad job outcomes in online workplaces},
  booktitle = {Workshop on Crowdsourcing and Machine Learning {(CrowdML)}},
  year = {2015},
  external = {http://crowdml.cc/icml2015/}
}
```
Horton, J. J., & Johari, R. (2015). At what quality and what price? Eliciting buyer preferences as a market design problem. In ACM Conference on Economics and Computation (EC).
Buyers and sellers in markets often signal to inform the other side about their preferences. Both have a mutual incentive to reveal information with respect to horizontal differentiation, but the case of vertical differentiation is more complex: a buyer claiming they place a high value on quality may attract more sellers of the right “type” increasing efficiency, but they might also simply pay a higher price. Although an efficiency-minded social planner may not care about higher prices, if this fear prevents a buyer from stating his of her true preferences, then desirable sorting caused by information-revelation may be unattainable. In this paper, we consider the buyer’s vertical differentiation disclosure problem through the lens of a large field experiment conducted in an online labor market. A new signaling mechanism was introduced into the market that allowed buyers to state their relative preferences over price and quality. We find that the buyer signal improved seller-side sorting, with more sellers going to buyers of the right “type”; the total number of applications also fell. However, sellers also clearly tailored their wages bid to the type of buyer they faced. Despite this markup, buyers chose to honestly disclose their preferences, suggesting they found the sorting effect to dominate the bargaining power effect.
```
@inproceedings{HorJoh2015Quality,
  author = {Horton, John Joseph and Johari, Ramesh},
  title = {At what quality and what price? Eliciting buyer preferences as a
                 market design problem},
  booktitle = {{ACM} Conference on Economics and Computation {(EC)}},
  year = {2015},
  external = {http://doi.acm.org/10.1145/2764468.2764516}
}
```
Banerjee, S., Johari, R., & Riquelme, C. (2015). Pricing in ride-sharing platforms: A queueing-theoretic approach. In ACM Conference on Economics and Computation (EC).
We study optimal pricing strategies for ride-sharing platforms, using a queueing-theoretic economic model. Analysis of pricing in such settings is complex: On one hand these platforms are two-sided — this requires economic models that capture the incentives of both drivers and passengers. On the other hand, these platforms support very high temporal-resolution for data collection and pricing — this requires stochastic models that capture the dynamics of drivers and passengers in the system. We focus our attention on the value of dynamic pricing: where prices can react to instantaneous imbalances between available supply and incoming demand. We find two main results: We first show that profit under any dynamic pricing strategy cannot exceed profit under the optimal static pricing policy (i.e., one which is agnostic of stochastic fluctuations in the system load). This result belies the prevalence of dynamic pricing in practice. Our second result explains the apparent paradox: we show that dynamic pricing is much more robust to fluctuations in system parameters compared to static pricing. Moreover, these results hold even if the monopolist maximizes welfare or throughput. Thus dynamic pricing does not necessarily yield higher performance than static pricing — however, it lets platforms realize the benefits of optimal static pricing, even with imperfect knowledge of system parameters.
```
@inproceedings{BanJohRiq2015Pricing,
  author = {Banerjee, Siddhartha and Johari, Ramesh and Riquelme, Carlos},
  title = {Pricing in ride-sharing platforms: {A} queueing-theoretic approach},
  booktitle = {{ACM} Conference on Economics and Computation {(EC)}},
  year = {2015},
  external = {http://doi.acm.org/10.1145/2764468.2764527}
}
```
Banerjee, S., Zhou, Z., & Johari, R. (2014). The importance of exploration in online marketplaces. In IEEE Conference on Decision and Control (CDC).
Nearly all online marketplaces face the challenge of ensuring the quality of sellers; this is particularly challenging in large marketplaces, where it may be infeasible to pre-screen all sellers. A growing trend in such settings is to use feedback from past transactions to infer the quality of new sellers. However, this process requires that existing buyers-the most valuable users of the platform-be subjected to matching to new, untrusted sellers, potentially leading to a bad experience. We investigate this tradeoff in a setting where existing buyers help uncover seller quality. We develop a stylized model, which captures the salient features inherent in such markets, while retaining analytical tractability. Our model uncovers a qualitative difference between exploration and exploitation, based on underlying network externalities between buyers and sellers in the market. In particular, in many settings, pure exploration achieves the optimal rate of successful matches.
```
@inproceedings{BanZhoJoh2014Importance,
  author = {Banerjee, Siddhartha and Zhou, Zhengyuan and Johari, Ramesh},
  title = {The importance of exploration in online marketplaces},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2014},
  external = {http://dx.doi.org/10.1109/CDC.2014.7039932}
}
```
Huang, T.-Y., Johari, R., McKeown, N., Trunnell, M., & Watson, M. (2014). A buffer-based approach to rate adaptation: Evidence from a large video streaming service. In ACM SIGCOMM.
Existing ABR algorithms face a significant challenge in estimating future capacity: capacity can vary widely over time, a phenomenon commonly observed in commercial services. In this work, we suggest an alternative approach: rather than presuming that capacity estimation is required, it is perhaps better to begin by using only the buffer, and then ask when capacity estimation is needed. We test the viability of this approach through a series of experiments spanning millions of real users in a commercial service. We start with a simple design which directly chooses the video rate based on the current buffer occupancy. Our own investigation reveals that capacity estimation is unnecessary in steady state; however using simple capacity estimation (based on immediate past throughput) is important during the startup phase, when the buffer itself is growing from empty. This approach allows us to reduce the rebuffer rate by 10-20% compared to Netflix’s then-default ABR algorithm, while delivering a similar average video rate, and a higher video rate in steady state.
```
@inproceedings{HuaJohMcKTruWat2014Buffer,
  author = {Huang, Te{-}Yuan and Johari, Ramesh and McKeown, Nick and Trunnell, Matthew and Watson, Mark},
  title = {A buffer-based approach to rate adaptation: Evidence from a large
                 video streaming service},
  booktitle = {{ACM} {SIGCOMM}},
  year = {2014},
  external = {http://doi.acm.org/10.1145/2619239.2626296}
}
```
Arnosti, N., Johari, R., & Kanoria, Y. (2014). Managing congestion in decentralized matching markets. In ACM Conference on Economics and Computation (EC).
We consider a decentralized two-sided matching market in which agents arrive and depart asynchronously. As a result, it is possible that an agent on one side of the market (a "buyer") identifies an agent on the other side of the market (a "seller") who is a suitable match, only to find that the seller is already matched. We find using a mean field approach that lack of knowledge about availability can create large welfare losses to both buyers and sellers. We consider a simple intervention available to the platform: limiting visibility of sellers. We find that this intervention can significantly improve the welfare of agents on both sides of the market; sellers pay lower application costs, while buyers are less likely to find that the sellers they screen have already matched. Somewhat counterintuitively, the benefits of showing fewer sellers to each buyer are greatest in markets in which there is a shortage of sellers.
```
@inproceedings{ArnJohKan2014Managing,
  author = {Arnosti, Nick and Johari, Ramesh and Kanoria, Yash},
  title = {Managing congestion in decentralized matching markets},
  booktitle = {{ACM} Conference on Economics and Computation {(EC)}},
  year = {2014},
  external = {http://doi.acm.org/10.1145/2600057.2602893}
}
```
Yiakoumis, Y., Katti, S., Huang, T.-Y., McKeown, N., Yap, K.-K., & Johari, R. (2012). Putting home users in charge of their network. In ACM Conference on Ubiquitous Computing (Ubicomp).
Policy-makers, ISPs and content providers are locked in a debate about who can control the Internet traffic that flows into our homes. In this paper we argue that the user, not the ISP or the content provider, should decide how traffic is prioritized to and from the home. Home users know most about their preferences, and if they can express them well to the ISP, then both the ISP and user are better off. To test the idea we built a prototype that lets users express highlevel preferences that are translated to low-level semantics and used to control the network.
```
@inproceedings{YiaKatHuaMcKYapJoh2012Putting,
  author = {Yiakoumis, Yiannis and Katti, Sachin and Huang, Te{-}Yuan and McKeown, Nick and Yap, Kok{-}Kiong and Johari, Ramesh},
  title = {Putting home users in charge of their network},
  booktitle = {{ACM} Conference on Ubiquitous Computing (Ubicomp)},
  year = {2012},
  external = {http://doi.acm.org/10.1145/2370216.2370451}
}
```
Huang, T.-Y., Handigol, N., Heller, B., McKeown, N., & Johari, R. (2012). Confused, timid, and unstable: Picking a video streaming rate is hard. In ACM SIGCOMM Internet Measurement Conference (IMC).
Today’s commercial video streaming services use dynamic rate selection to provide a high-quality user experience. Most services host content on standard HTTP servers in CDNs, so rate selection must occur at the client. We measure three popular video streaming services – Hulu, Netflix, and Vudu – and find that accurate client-side bandwidth estimation above the HTTP layer is hard. As a result, rate selection based on inaccurate estimates can trigger a feedback loop, leading to undesirably variable and low-quality video. We call this phenomenon the "downward spiral effect", and we measure it on all three services, present insights into its root causes, and validate initial solutions to prevent it.
```
@inproceedings{HuaHanHelMcKJoh2012Confused,
  author = {Huang, Te{-}Yuan and Handigol, Nikhil and Heller, Brandon and McKeown, Nick and Johari, Ramesh},
  title = {Confused, timid, and unstable: Picking a video streaming rate is hard},
  booktitle = {{ACM} {SIGCOMM} Internet Measurement Conference (IMC)},
  year = {2012},
  external = {http://doi.acm.org/10.1145/2398776.2398800}
}
```

Gummadi, R., Johari, R., & Yu, J. Y. (2012). Mean field equilibria of multiarmed bandit games. In ACM Conference on Electronic Commerce (EC).

@inproceedings{GumJohYu2012Mean-EC,
  author = {Gummadi, Ramakrishna and Johari, Ramesh and Yu, Jia Yuan},
  title = {Mean field equilibria of multiarmed bandit games},
  booktitle = {{ACM} Conference on Electronic Commerce {(EC)}},
  year = {2012},
  external = {http://doi.acm.org/10.1145/2229012.2229060}
}

Iyer, K., Johari, R., & Moallemi, C. C. (2012). Information and the value of execution guarantees. In ACM Conference on Electronic Commerce (EC).
In many markets, uncertainty about whether a trade is executed can be removed by paying a price premium. We use financial markets as a particular setting in which to study this trade-off. In particular, we assess the role of information in the choice between certain trade at a price premium in an intermediated dealer market and contingent trade in a dark pool. Our setting consists of intrinsic traders and speculators, each endowed with heterogeneous fine-grained private information as to an asset’s value, that endogenously decide between these two venues. We solve for an equilibrium in this setting, and address three main questions: First, how does the level of information of a trader and her competitors affect their behavior-i.e., how does the choice between certain and contingent trade depend on information structure? Second, how does the level of premium for certain trade over contingent trade affect the strategic behavior of traders? And finally, how should market makers intermediating certain trade set transaction costs to maximize profit, in the presence of an option for contingent trade? We derive the following implications from our model: (1) Information and the choice between certain and contingent trade. We find that, in general, the dark pool is utilized by uninformed or mildly informed traders, whereas highly informed traders will trade in the open market. Furthermore, there is adverse selection in the dark pool, in the sense that buy (sell) orders are more likely to be filled when the dark pool price is above (resp. below) the true value. (2) The impact of transaction costs on adverse selection. Surprisingly, in the partial equilibrium setting where the transaction costs in the open market are exogenously specified, the fill rate in the dark pool (and therefore adverse selection) is not monotonically related to the bid-offer spread: for example, when the dark pool price is above true value, the fill rate for buyers in the dark pool falls at lower transaction costs, and rises at higher transaction costs. (3) Market making in the open market. We find that a dark pool lowers a monopolist’s choice of transaction cost in the open market. Further, we find the surprising insight that the monopolist’s profit also increases as traders become more informed.
```
@inproceedings{IyeJohMoa2012Information,
  author = {Iyer, Krishnamurthy and Johari, Ramesh and Moallemi, Ciamac Cyrus},
  title = {Information and the value of execution guarantees},
  booktitle = {{ACM} Conference on Electronic Commerce {(EC)}},
  year = {2012},
  external = {http://doi.acm.org/10.1145/2229012.2229064}
}
```
Nadav, U., Johari, R., & Roughgarden, T. (2011). Uncoupled potentials for proportional allocation markets. In IEEE Conference on Decision and Control (CDC).
We study resource allocation games where allocations to agents are made in proportion to their bids. We show that the existence of a potential function in the allocation space, and a virtual price function are sufficient for the convergence of better response dynamics to Nash equilibrium. Generally, resource allocation games do not admit a potential in their strategy space, and are not in the class of potential games. However, for many interesting examples, including the Kelly mechanism, the best response functions are “well-behaved” on the allocation space, and consequently a potential in that space exists. We demonstrate how our sufficient condition is satisfied by three classes of market mechanisms. The first is the class of smooth market-clearing mechanisms, where the market is cleared using a single nondiscriminatory price. The second example is the class of simple g-mechanisms where an efficient Nash equilibrium is implemented with price discrimination. Finally we show our results apply to a subset of scalar strategy VCG (SSVCG) mechanisms, that generalizes simple g-mechanisms.
```
@inproceedings{NadJohRou2011Uncoupled,
  author = {Nadav, Uri and Johari, Ramesh and Roughgarden, Tim},
  title = {Uncoupled potentials for proportional allocation markets},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2011},
  external = {http://dx.doi.org/10.1109/CDC.2011.6160986}
}
```
Bui, L., Johari, R., & Mannor, S. (2011). Committing bandits. In Advances in Neural Information Processing Systems (NIPS).
We consider a multi-armed bandit problem where there are two phases. The first phase is an experimentation phase where the decision maker is free to explore multiple options. In the second phase the decision maker has to commit to one of the arms and stick with it. Cost is incurred during both phases with a higher cost during the experimentation phase. We analyze the regret in this setup, and both propose algorithms and provide upper and lower bounds that depend on the ratio of the duration of the experimentation phase to the duration of the commitment phase. Our analysis reveals that if given the choice, it is optimal to experiment \(Θ(\ln T)\)steps and then commit, where \(T\)is the time horizon.
```
@inproceedings{BuiJohMan2011Committing,
  author = {Bui, Loc and Johari, Ramesh and Mannor, Shie},
  title = {Committing bandits},
  booktitle = {Advances in Neural Information Processing Systems {(NIPS)}},
  year = {2011},
  external = {http://papers.nips.cc/paper/4223-committing-bandits}
}
```
Valancius, V., Lumezanu, C., Feamster, N., Johari, R., & Vazirani, V. V. (2011). How many tiers? Pricing in the internet transit market. In ACM SIGCOMM.
ISPs are increasingly selling "tiered" contracts, which offer Internet connectivity to wholesale customers in bundles, at rates based on the cost of the links that the traffic in the bundle is traversing. Although providers have already begun to implement and deploy tiered pricing contracts, little is known about how to structure them. While contracts that sell connectivity on finer granularities improve market efficiency, they are also more costly for ISPs to implement and more difficult for customers to understand. Our goal is to analyze whether current tiered pricing practices in the wholesale transit market yield optimal profits for ISPs and whether better bundling strategies might exist. In the process, we deliver two contributions: 1) we develop a novel way of mapping traffic and topology data to a demand and cost model, and 2) we fit this model on three large real-world networks: an European transit ISP, a content distribution network, and an academic research network, and run counterfactuals to evaluate the effects of different bundling strategies. Our results show that the common ISP practice of structuring tiered contracts according to the cost of carrying the traffic flows (e.g., offering a discount for traffic that is local) can be suboptimal and that dividing contracts based on both traffic demand and the cost of carrying it into only three or four tiers yields near-optimal profit for the ISP.
```
@inproceedings{ValLumFeaJohVaz2011HowMany,
  author = {Valancius, Vytautas and Lumezanu, Cristian and Feamster, Nick and Johari, Ramesh and Vazirani, Vijay V.},
  title = {How many tiers? Pricing in the internet transit market},
  booktitle = {ACM SIGCOMM},
  year = {2011},
  external = {http://doi.acm.org/10.1145/2018436.2018459}
}
```
Iyer, K., Johari, R., & Sundararajan, M. (2011). Mean field equilibria of dynamic auctions with learning. In ACM Conference on Electronic Commerce (EC).
Auctions are observed as a market mechanism in a wide range of economic transactions involving repeated interactions among the market participants: sponsored search markets run by Google and Yahoo!, online marketplaces such as eBay and Amazon, crowdsourcing, etc. In many of these markets, the participants typically have incomplete information; for example, the participants may not know the quality of the good being auctioned or their value for the good. In such settings, repeated interactions among the participants give rise to extremely complex bidder behavior due to the presence of learning among the participants. To study learning, we consider a dynamic setting where identical copies of a good are sold through a sequence of second price auctions over time. Each agent in the market has an independent private valuation which determines the distribution of the reward she obtains from the good. However, the agents are unaware of their own private valuations. Every time an agent wins an auction and obtains a copy of the good, her realized reward from the good informs her about her valuation. Thus, each agent faces a trade-off between exploration (by bidding higher) and exploitation (by bidding close to her expected rewards).
```
@inproceedings{IyeJohSun2011Mean,
  author = {Iyer, Krishnamurthy and Johari, Ramesh and Sundararajan, Mukund},
  title = {Mean field equilibria of dynamic auctions with learning},
  booktitle = {{ACM} Conference on Electronic Commerce {(EC)}},
  year = {2011},
  external = {http://doi.acm.org/10.1145/1993574.1993631}
}
```
Wu, Y., Bui, L., & Johari, R. (2011). Heavy traffic approximation of equilibria in resource sharing games. In Workshop on Internet and Network Economics (WINE).
We consider a model of priced resource sharing that combines both queueing behavior and strategic behavior. We study a priority service model where a single server allocates its capacity to agents in proportion to their payment to the system, and users from different classes act to minimize the sum of their cost for processing delay and payment. As the exact processing time of this system is hard to compute, we introduce the notion of heavy traffic equilibrium as an approximation of the Nash equilibrium, derived by considering the asymptotic regime where the system load approaches capacity. We discuss efficiency and revenue, and in particular provide a bound for the price of anarchy of the heavy traffic equilibrium.
```
@inproceedings{WuBuiJoh2011Heavy,
  author = {Wu, Yu and Bui, Loc and Johari, Ramesh},
  title = {Heavy traffic approximation of equilibria in resource sharing games},
  booktitle = {Workshop on Internet and Network Economics {(WINE)}},
  year = {2011},
  external = {http://dx.doi.org/10.1007/978-3-642-25510-6_30}
}
```
Adlakha, S., Johari, R., Weintraub, G. Y., & Goldsmith, A. J. (2010). On oblivious equilibrium in large population stochastic games. In IEEE Conference on Decision and Control (CDC).
We study stochastic games with a large number of players, where players are coupled via their payoff functions. A standard solution concept for such games is Markov perfect equilibrium (MPE). It is well known that the computation of MPE suffers from the “curse of dimensionality.” To deal with this complexity, several researchers have introduced the idea of oblivious equilibrium (OE). In OE, each player reacts to only the long-run average state of other players. In this paper, we study existence of OE, and also find conditions under which OE approximates MPE well.
```
@inproceedings{AdlJohWeiGol2010Oblivious,
  author = {Adlakha, Sachin and Johari, Ramesh and Weintraub, Gabriel Y. and Goldsmith, Andrea J.},
  title = {On oblivious equilibrium in large population stochastic games},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2010},
  external = {http://dx.doi.org/10.1109/CDC.2010.5717048}
}
```
Adlakha, S., & Johari, R. (2010). Mean field equilibrium in dynamic games with complementarities. In IEEE Conference on Decision and Control (CDC).
We study stochastic dynamic games with a large number of players, where players are coupled via their payoff functions. We consider mean field equilibrium for such games: in such an equilibrium, each player reacts to only the long run average state of other players. In this paper we focus on a special class of stochastic games, where a player experiences strategic complementarities from other players; formally the payoff of a player has increasing differences between her own state and the aggregate empirical distribution of the states of other players. We find necessary conditions for the existence of a mean field equilibrium in such games. Furthermore, we show that there exist a “largest” and “smallest” equilibrium among all those where the equilibrium strategy used by a player is nondecreasing.
```
@inproceedings{AdlJoh2010Mean-CDC,
  author = {Adlakha, Sachin and Johari, Ramesh},
  title = {Mean field equilibrium in dynamic games with complementarities},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2010},
  external = {http://dx.doi.org/10.1109/CDC.2010.5717416}
}
```
Johari, R., & Kumar, S. (2010). Congestible services and network effects. In ACM Conference on Electronic Commerce (EC).
We study a system where many identical users of a service share a common resource. Each user is sensitive to congestion at the resource, but also experiences a positive network effect. We consider a model where both effects depend on the usage of individuals in the system, as well as potentially the number of users in the system. We consider two benchmark scales for the service: the subscriber base most preferred by an individual user (the "user-preferred" club size), and the subscriber base most preferred by the service manager (the "manager-preferred" club size). We find that the user-preferred size is always smaller than that chosen by a service manager; however, somewhat surprisingly, usage in the user-preferred club size is always efficient. Next, we carry out an asymptotic analysis in the regime where the network effect is increased without bound. We find that in this regime, the asymptotic behavior of the user-preferred club can be quite different from that formed by a service manager: for example, the user-preferred club size may remain finite, even if the club formed by a service manager has infinitely many members.
```
@inproceedings{JohKum2010Congestible,
  author = {Johari, Ramesh and Kumar, Sunil},
  title = {Congestible services and network effects},
  booktitle = {{ACM} Conference on Electronic Commerce {(EC)}},
  year = {2010},
  external = {http://doi.acm.org/10.1145/1807342.1807356}
}
```
Iyer, K., Johari, R., & Moallemi, C. C. (2010). Information aggregation in smooth markets. In ACM Conference on Electronic Commerce (EC).
We study stochastic games with a large number of players, where players are coupled via their payoff functions. A standard solution concept for such games is Markov perfect equilibrium (MPE). It is well known that the computation of MPE suffers from the "curse of dimensionality." Recently an approximate solution concept called "oblivious equilibrium" (OE) was developed by Weintraub et al., where each player reacts to only the average behavior of other players. In this work, we characterize a set of games in which OE approximates MPE. Specifically, we show that if system dynamics and payoff functions are concave in state and action and have decreasing differences in state and action, then an oblivious equilibrium of such a game approximates MPE. These exogenous conditions on model primitives allow us to characterize a set of games where OE can be used as an approximate solution concept.
```
@inproceedings{IyeJohMoa2010Information,
  author = {Iyer, Krishnamurthy and Johari, Ramesh and Moallemi, Ciamac Cyrus},
  title = {Information aggregation in smooth markets},
  booktitle = {{ACM} Conference on Electronic Commerce {(EC)}},
  year = {2010},
  external = {http://doi.acm.org/10.1145/1807342.1807373}
}
```
Adlakha, S., Johari, R., Weintraub, G. Y., & Goldsmith, A. (2009). Oblivious equilibrium: An approximation to large population dynamic games with concave utility. In Conference on Game Theory for Networks (GAMENETS).
We study stochastic games with a large number of players, where players are coupled via their payoff functions. A standard solution concept for such games is Markov perfect equilibrium (MPE). It is well known that the computation of MPE suffers from the "curse of dimensionality." Recently an approximate solution concept called "oblivious equilibrium" (OE) was developed by Weintraub et al., where each player reacts to only the average behavior of other players. In this work, we characterize a set of games in which OE approximates MPE. Specifically, we show that if system dynamics and payoff functions are concave in state and action and have decreasing differences in state and action, then an oblivious equilibrium of such a game approximates MPE. These exogenous conditions on model primitives allow us to characterize a set of games where OE can be used as an approximate solution concept.
```
@inproceedings{AdlJohWeiGol2009Oblivious,
  author = {Adlakha, Sachin and Johari, Ramesh and Weintraub, Gabriel Y. and Goldsmith, Andrea},
  title = {Oblivious equilibrium: An approximation to large population dynamic
                 games with concave utility},
  booktitle = {Conference on Game Theory for Networks {(GAMENETS)}},
  year = {2009},
  external = {http://dx.doi.org/10.1109/GAMENETS.2009.5137384}
}
```
DiPalantino, D., & Johari, R. (2009). Traffic engineering, content distribution, and continuous potential games. In Conference on Game Theory for Networks (GAMENETS).
We explore the interaction between content distribution and traffic engineering. Because a traffic engineer may be unaware of the structure of content distribution systems or overlay networks, his management of the network does not fully anticipate how traffic might change as a result of his actions. Content distribution systems that assign servers at the application level can respond very rapidly to changes in the routing of the network. Consequently, the traffic engineer’s decisions may almost never be applied to the intended traffic. We use a game-theoretic framework in which infinitesimal users of a network select the source of content, and the traffic engineer decides how the traffic will route through the network. We formulate a game and prove the existence of equilibria. Additionally, we present a setting in which equilibria are socially optimal, essentially unique, and stable. Conditions under which efficiency loss may be bounded are presented, and the results are extended to the cases of general overlay networks and multiple autonomous systems.
```
@inproceedings{DiPJoh2009Traffic,
  author = {DiPalantino, Dominic and Johari, Ramesh},
  title = {Traffic engineering, content distribution, and continuous potential
                 games},
  booktitle = {Conference on Game Theory for Networks {(GAMENETS)}},
  year = {2009},
  external = {http://dx.doi.org/10.1109/GAMENETS.2009.5137389}
}
```
DiPalantino, D., & Johari, R. (2009). Traffic engineering vs. content distribution: A game theoretic perspective. In IEEE International Conference on Computer Communications (INFOCOM).
In this paper we explore the interaction between content distribution and traffic engineering. Because a traffic engineer may be unaware of the structure of content distribution systems or overlay networks, this management of the network does not fully anticipate how traffic might change as a result of his actions. Content distribution systems that assign servers at the application level can respond very rapidly to changes in the routing of the network. Consequently, the traffic engineer’s decisions may almost never be applied to the intended traffic. We use a game-theoretic framework in which infinitesimal users of a network select the source of content, and the traffic engineer decides how the traffic will route through the network. We formulate a game and prove the existence of equilibria. Additionally, we present a setting in which equilibria are socially optimal, essentially unique, and stable. Conditions under which efficiency loss may be bounded are presented, and the results are extended to the cases of general overlay networks and multiple autonomous systems.
```
@inproceedings{DiPJoh2009Traffic2,
  author = {DiPalantino, Dominic and Johari, Ramesh},
  title = {Traffic engineering vs. content distribution: {A} game theoretic perspective},
  booktitle = {{IEEE} International Conference on Computer Communications {(INFOCOM)}},
  year = {2009},
  external = {http://dx.doi.org/10.1109/INFCOM.2009.5061960}
}
```
Adlakha, S., Johari, R., Weintraub, G. Y., & Goldsmith, A. J. (2008). Oblivious equilibrium for large-scale stochastic games with unbounded costs. In IEEE Conference on Decision and Control (CDC).
We study stochastic dynamic games with a large number of players, where players are coupled via their cost functions. A standard solution concept for stochastic games is Markov perfect equilibrium (MPE). In MPE, each player’s strategy is a function of its own state as well as the state of the other players. This makes MPE computationally prohibitive as the number of players becomes large. An approximate solution concept called oblivious equilibrium (OE) was introduced, where each player’s decision depends only on its own state and the "long-run average" state of other players. This makes OE computationally more tractable than MPE. It was shown that, under a set of assumptions, as the number of players become large, OE closely approximates MPE. In this paper we relax those assumptions and generalize that result to cases where the cost functions are unbounded. Furthermore, we show that under these relaxed set of assumptions, the OE approximation result can be applied to large population linear quadratic Gaussian (LQG) games.
```
@inproceedings{AdlJohWeiGol2008Oblivious,
  author = {Adlakha, Sachin and Johari, Ramesh and Weintraub, Gabriel Y. and Goldsmith, Andrea J.},
  title = {Oblivious equilibrium for large-scale stochastic games with unbounded costs},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2008},
  external = {http://dx.doi.org/10.1109/CDC.2008.4739389}
}
```
Aperjis, C., Freedman, M. J., & Johari, R. (2008). Peer-assisted content distribution with prices. In ACM Conference on Emerging Network Experiment and Technology (CoNEXT).
Peer-assisted content distribution matches user demand for content with available supply at other peers in the network. Inspired by this supply-and-demand interpretation of the nature of content sharing, we employ price theory to study peer-assisted content distribution. The market-clearing prices are those which align supply and demand, and the system is studied through the characterization of price equilibria. We discuss the efficiency and robustness gains of price-based multilateral exchange, and show that simply maintaining a single price per peer (even across multiple files) suffices to achieve these benefits. Our main contribution is a system design—PACE (Price-Assisted Content Exchange)—that effectively and practically realizes multilateral exchange. Its centerpiece is a market-based mechanism for exchanging currency for desired content, with a single, decentralized price per peer. Honest users are completely shielded from any notion of prices, budgeting, allocation, or other market issues, yet strategic or malicious clients cannot unduly damage the system’s efficient operation. Our design encourages sharing of desirable content and network-friendly resource utilization. Bilateral barter-based systems such as BitTorrent have been attractive in large part because of their simplicity. Our research takes a significant step in understanding the efficiency and robustness gains possible with multilateral exchange.
```
@inproceedings{ApeFreJoh2008Peer,
  author = {Aperjis, Christina and Freedman, Michael J. and Johari, Ramesh},
  title = {Peer-assisted content distribution with prices},
  booktitle = {{ACM} Conference on Emerging Network Experiment
                 and Technology {(CoNEXT)}},
  year = {2008},
  external = {http://doi.acm.org/10.1145/1544012.1544029}
}
```
Valancius, V., Feamster, N., Johari, R., & Vazirani, V. V. (2008). MINT: A Market for INternet Transit. In ACM Conference on Emerging Network Experiment and Technology (CoNEXT).
Today’s Internet’s routing paths are inefficient with respect to both connectivity and the market for interconnection. The former manifests itself via needlessly long paths, de-peering, etc. The latter arises because of a primitive market structure that results in unfulfilled demand and unused capacity. Today’s networks make pairwise, myopic interconnection decisions based on business considerations that may not mirror considerations of the edge networks (or end systems) that would benefit from the existence of a particular interconnection. These bilateral contracts are also complex and difficult to enforce. This paper proposes MINT, a market structure and routing protocol suite that facilitates the sale and purchase of end-to-end Internet paths. We present MINT’s structure, explain how it improves connectivity and market efficiency, explore the types of connectivity that might be exchanged (vs. today’s "best effort" connectivity), and argue that MINT’s deployment is beneficial to both stub networks and transit providers. We discuss research challenges, including the design both of the protocol that maintains information about connectivity and of the market clearing algorithms. Our preliminary evaluation shows that such a market quickly reaches equilibrium and exhibits price stability.
```
@inproceedings{ValFeaJohVaz2008MINT,
  author = {Valancius, Vytautas and Feamster, Nick and Johari, Ramesh and Vazirani, Vijay V.},
  title = {{MINT:} {A} {M}arket for {IN}ternet {T}ransit},
  booktitle = {{ACM} Conference on Emerging Network Experiment and Technology {(CoNEXT)}},
  year = {2008},
  external = {http://doi.acm.org/10.1145/1544012.1544082}
}
```

Freedman, M. J., Aperjis, C., & Johari, R. (2008). Prices are right: Managing resources and incentives in peer-assisted content distribution. In International Conference on Peer-to-Peer Systems (IPTPS).

@inproceedings{FreApeJoh2008Prices,
  author = {Freedman, Michael J. and Aperjis, Christina and Johari, Ramesh},
  title = {Prices are right: Managing resources and incentives in peer-assisted
                 content distribution},
  booktitle = {International Conference on Peer-to-Peer Systems {(IPTPS)}},
  year = {2008},
  external = {http://www.cs.toronto.edu/iptps2008/}
}

Özgür, A., Johari, R., Tse, D., & Lévêque, O. (2008). Information theoretic operating regimes of large wireless networks. In IEEE International Symposium on Information Theory (ISIT).
In analyzing the point-to-point wireless channel, insights about two qualitatively different operating regimes-bandwidth- and power-limited-have proven indispensable in the design of good communication schemes. In this paper, we propose a new scaling law formulation for wireless networks that allows us to develop a theory that is analogous to the point-to-point case. We identify fundamental operating regimes of wireless networks and derive architectural guidelines for the design of optimal schemes. Our analysis shows that in a given wireless network with arbitrary size, area, power, etc., there are three parameters of importance: the short-distance SNR, the long-distance SNR, and the power path loss exponent. Depending on these parameters we identify four qualitatively different regimes. One of these regimes is especially interesting since it is fundamentally a consequence of the heterogeneous nature of links in a network and does not occur in the point-to-point case; the network capacity is both power- and bandwidth-limited. This regime has thus far remained hidden due to the limitations of the existing formulation. Existing schemes, either multihop transmission or hierarchical cooperation, fail to achieve capacity in this regime; we propose a new hybrid scheme that achieves capacity.
```
@inproceedings{OzgJohTseLev2008Information,
  author = {{\"{O}}zg{\"{u}}r, Ayfer and Johari, Ramesh and Tse, David and L{\'{e}}v{\^{e}}que, Olivier},
  title = {Information theoretic operating regimes of large wireless networks},
  booktitle = {{IEEE} International Symposium on Information Theory {(ISIT)}},
  year = {2008},
  external = {http://dx.doi.org/10.1109/ISIT.2008.4594973}
}
```
Aperjis, C., Freedman, M. J., & Johari, R. (2008). A comparison of bilateral and multilateral exchanges for peer-assisted content distribution. In Workshop on Network Control and Optimization (NET-COOP).
Peer-assisted content distribution matches user demand for content with available supply at other peers in the network. Inspired by this supply-and-demand interpretation of the nature of content sharing, we employ price theory to study peer-assisted content distribution. In this approach, the market-clearing prices are those which exactly align supply and demand, and the system is studied through the characterization of price equilibria. We rigorously analyze the efficiency and robustness gains that are enabled by price-based multilateral exchange. We show that multilateral exchanges satisfy several desirable efficiency and robustness properties that bilateral exchanges do not, e.g., equilibria in bilateral exchange may fail to exist, be inefficient if they do exist, and fail to remain robust to collusive deviations even if they are Pareto efficient. Further, we show that an equilibrium in bilateral exchange corresponds to a multilateral exchange equilibrium if and only if it is robust to deviations by coalitions of users.
```
@inproceedings{ApeFreJoh2008Comparison,
  author = {Aperjis, Christina and Freedman, Michael J. and Johari, Ramesh},
  title = {A comparison of bilateral and multilateral exchanges for peer-assisted
                 content distribution},
  booktitle = {Workshop on Network Control and Optimization {(NET-COOP)}},
  year = {2008},
  external = {http://dx.doi.org/10.1007/978-3-642-00393-6_1}
}
```
Arcaute, E., Johari, R., & Mannor, S. (2008). Local two-stage myopic dynamics for network formation games. In Workshop on Internet and Network Economics (WINE).
Network formation games capture two conflicting objectives of self-interested nodes in a network. On one hand, such a node wishes to be able to reach all other nodes in the network; on the other hand, it wishes to minimize its cost of participation. We focus on myopic dynamics in a class of such games inspired by transportation and communication models. A key property of the dynamics we study is that they are local: nodes can only deviate to form links with others in a restricted neighborhood. Despite this locality, we find that our dynamics converge to efficient or nearly efficient outcomes in a range of settings of interest.
```
@inproceedings{ArcJohMan2008Local,
  author = {Arcaute, Esteban and Johari, Ramesh and Mannor, Shie},
  title = {Local two-stage myopic dynamics for network formation games},
  booktitle = {Workshop on Internet and Network Economics {(WINE)}},
  year = {2008},
  external = {http://dx.doi.org/10.1007/978-3-540-92185-1_33}
}
```
Arcaute, E., Dallal, E., Johari, R., & Mannor, S. (2007). Dynamics and stability in network formation games with bilateral contracts. In IEEE Conference on Decision and Control (CDC).
We consider a network formation game where a finite number of nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form communication links; once the network is formed, traffic is routed along shortest paths (if possible). Cost is incurred to a node from four sources: (1) routing traffic; (2) maintaining links to other nodes; (3) disconnection from destinations the node wishes to reach; and (4) payments made to other nodes. We assume that a network is stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together. We characterize stable networks, and study the efficiency of those networks. We also consider myopic best response dynamics in the case where links are bidirectional. Under certain assumptions, these myopic dynamics converge to a stable network; further, they naturally select an efficient equilibrium out of the set of possible equilibria.
```
@inproceedings{ArcDalJohMan2007Dynamics,
  author = {Arcaute, Esteban and Dallal, Eric and Johari, Ramesh and Mannor, Shie},
  title = {Dynamics and stability in network formation games with bilateral contracts},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2007},
  external = {http://dx.doi.org/10.1109/CDC.2007.4434965}
}
```
Abhishek, V., Adlakha, S., Johari, R., & Weintraub, G. Y. (2007). Oblivious equilibrium for general stochastic games with many players. In Allerton Conference for Communication, Control, and Computing.
- [ abstract ]
- [ bib ]
This paper studies a solution concept for large stochastic games. A standard solution concept for a stochastic game is Markov perfect equilibrium (MPE). In MPE, each player’s optimal action depends on his own state and the state of the other players. By contrast, oblivious equilibrium (OE) is an approximation introduced by Weintraub et al. where each player makes decisions based on his own state and the “average” state of the other players. For this reason OE is computationally more tractable than MPE. It was shown by Weintraub et al. that as the number of players becomes large, OE closely approximates MPE; however, this result was established under a set of assumptions specific to industry dynamic models. In this paper we develop a parsimonious set of assumptions under which the result of Weintraub et al. can be generalized to a broader class of stochastic games with a large number of players.
```
@inproceedings{AbhAdlJohWei2007Oblivious,
  author = {Abhishek, Vineet and Adlakha, Sachin and Johari, Ramesh and Weintraub, Gabriel Y.},
  title = {Oblivious equilibrium for general stochastic games with many players},
  booktitle = {Allerton Conference for Communication, Control, and Computing},
  year = {2007}
}
```
Arcaute, E., Johari, R., & Mannor, S. (2007). Network formation: Bilateral contracting and myopic dynamics. In Workshop on Internet and Network Economics (WINE).
We consider a network formation game where a finite number of nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form bidirectional communication links; once the network is formed, traffic is routed along shortest paths (if possible). Cost is incurred to a node from four sources: (1) routing traffic; (2) maintaining links to other nodes; (3) disconnection from destinations the node wishes to reach; and (4) payments made to other nodes. We assume that a network is stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together (a variation on the notion of pairwise stability). We study such a game under a form of myopic best response dynamics. In choosing their best strategy, nodes optimize their single period payoff only. We characterize a simple set of assumptions under which these dynamics will converge to a pairwise stable network topology; we also characterize an important special case, where the dynamics converge to a star centered at a node with minimum cost for routing traffic. In this sense, our dynamics naturally select an efficient equilibrium. Further, we show that these assumptions are satisfied by a contractual model motivated by bilateral Rubinstein bargaining with infinitely patient players.
```
@inproceedings{ArcJohMan2007Network,
  author = {Arcaute, Esteban and Johari, Ramesh and Mannor, Shie},
  title = {Network formation: Bilateral contracting and myopic dynamics},
  booktitle = {Workshop on Internet and Network Economics {(WINE)}},
  year = {2007},
  external = {http://dx.doi.org/10.1007/978-3-540-77105-0_20}
}
```
Feamster, N., Johari, R., & Balakrishnan, H. (2005). Implications of autonomy for the expressiveness of policy routing. In ACM SIGCOMM.
Thousands of competing autonomous systems must cooperate with each other to provide global Internet connectivity. Each autonomous system (AS) encodes various economic, business, and performance decisions in its routing policy. The current interdomain routing system enables each AS to express policy using rankings that determine how each router inthe AS chooses among different routes to a destination, and filters that determine which routes are hidden from each neighboring AS. Because the Internet is composed of many independent, competing networks, the interdomain routing system should provide autonomy, allowing network operators to set their rankings independently, and to have no constraints on allowed filters. This paper studies routing protocol stability under these conditions. We first demonstrate that certain rankings that are commonly used in practice may not ensure routing stability. We then prove that, when providers can set rankings and filters autonomously, guaranteeing that the routing system will converge to a stable path assignment essentially requires ASes to rank routes based on AS-path lengths. We discuss the implications of these results for the future of interdomain routing.
```
@inproceedings{FeaJohBal2005Implications,
  author = {Feamster, Nick and Johari, Ramesh and Balakrishnan, Hari},
  title = {Implications of autonomy for the expressiveness of policy routing},
  booktitle = {ACM SIGCOMM},
  year = {2005},
  external = {http://doi.acm.org/10.1145/1080091.1080096}
}
```
Johari, R., Mannor, S., & Tsitsiklis, J. N. (2004). Efficiency loss in a network resource allocation game: A single link in elastic supply. In IEEE Conference on Decision and Control (CDC).
We consider a resource allocation problem where individual users wish to send data across a single link to maximize their utility, and a cost is incurred dependent on the total flow sent on the link. It has been shown that as long as users do not anticipate the effect of their actions on prices, a simple proportional pricing mechanism can maximize the sum of users’ utilities minus the cost (called social welfare). Continuing previous efforts to quantify the effects of selfish behavior in network pricing mechanisms, our research considers the possibility that users may anticipate the effect of their actions on the link price. Under the simple assumption that the link’s marginal cost function is convex, we establish existence of a Nash equilibrium, and show that the system utility is no worse than a factor of \(4\sqrt2-5\)times the optimal system utility; thus, the efficiency loss when users are selfish is no more than approximately 34%.
```
@inproceedings{JohManTsi2004Efficiency,
  author = {Johari, Ramesh and Mannor, Shie and Tsitsiklis, John N.},
  title = {Efficiency loss in a network resource allocation game: {A} single link in elastic supply},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2004},
  external = {http://dx.doi.org/10.1109/CDC.2004.1429527}
}
```
Johari, R., & Tsitsiklis, J. N. (2004). Routing and peering in a competitive Internet. In IEEE Conference on Decision and Control (CDC).
Today’s Internet is a loose federation of independent network providers, each acting in their own self interest. In this paper, we consider some implications of this economic reality. Specifically, we consider how the incentives of the providers might determine where they choose to interconnect with each other; we show that for any given provider, determining an optimal placement of interconnection links is generally NP-complete. However, we present simple solutions for some special cases of this placement problem. We also consider the phenomenon of nearest-exit, or "hot-potato," routing, where outgoing traffic exits a provider’s network as quickly as possible. If each link in a network is assessed a linear cost per unit flow through the link, we show that the total cost of nearest exit routing is no worse than three times the optimal cost.
```
@inproceedings{JohTsi2004Routing,
  author = {Johari, Ramesh and Tsitsiklis, John N.},
  title = {Routing and peering in a competitive {I}nternet},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2004},
  external = {http://dx.doi.org/10.1109/CDC.2004.1430265}
}
```
Johari, R., & Tsitsiklis, J. N. (2003). Network resource allocation and a congestion game: The single link case. In IEEE Conference on Decision and Control (CDC).
We explore the properties of a congestion game where users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we show existence and uniqueness of the Nash equilibrium, and establish that the aggregate utility received by the users is at least 3/4 of the maximum possible aggregate utility. These results form part of a growing literature on the "price of anarchy," i.e., the extent to which selfish behavior affects system efficiency.
```
@inproceedings{JohTsi2003Network,
  author = {Johari, Ramesh and Tsitsiklis, John N.},
  title = {Network resource allocation and a congestion game: The single link case},
  booktitle = {{IEEE} Conference on Decision and Control {(CDC)}},
  year = {2003},
  external = {http://dx.doi.org/10.1109/CDC.2003.1272929}
}
```

Monograph

Berry, R. A., & Johari, R. (2013). Economic Modeling in Networking: A Primer. Foundations and Trends in Networking, 6(3), 165–286.
- [ abstract ]
- [ bib ]
- [ pdf ]
- [ link ]
In recent years, engineers have been increasingly called upon to have basic skills in economic modeling and game theory at their disposal for two related reasons. First, the economics of networks has a significant effect on the adoption and creation of network innovations, and second, and perhaps more importantly, engineered networks serve as the platform for many of our basic economic interactions today. This monograph aims to provide engineering students who have a basic training in economic modeling and game theory an understanding of where and when game theoretic models are employed, the assumptions underpinning key models, and conceptual insights that are broadly applicable.
```
@article{BerJoh13Economic,
  author = {Berry, Randall A. and Johari, Ramesh},
  title = {Economic Modeling in Networking: {A} Primer},
  journal = {Foundations and Trends in Networking},
  volume = {6},
  number = {3},
  pages = {165--286},
  year = {2013},
  external = {http://dx.doi.org/10.1561/1300000011}
}
```

Book chapters

Banerjee, S., & Johari, R. (2019). Ride sharing. In M. Hu (Ed.), Sharing Economy: Making Supply Meet Demand. Springer.
Ridesharing platforms such as Didi, Lyft, Ola and Uber are increasingly important components of the transportation infrastructure. However, our understanding of their design and operations, and their effect on society at large, is not yet well understood. From an academic perspective, these platforms present challenges in large-scale learning, real-time stochastic control, and market design. Their popularity has led to a growing body of academic work across several disciplines, with researchers addressing similar questions with vastly different tools and models. Our aim in this chapter is to outline the main challenges in ridesharing, and to present an approach to modeling, optimizing, and reasoning about such platforms. We describe how rigorous analysis has been used with great success in designing efficient algorithms for real-time decision making, in informing the market design aspects of these platforms, and in understanding the impact of these platforms in their larger societal context.
```
@incollection{BanJoh2019Ride,
  author = {Banerjee, Siddhartha and Johari, Ramesh},
  title = {Ride sharing},
  booktitle = {Sharing Economy: Making Supply Meet Demand},
  editor = {Hu, Ming},
  publisher = {Springer},
  year = {2019},
  external = {https://www.springer.com/la/book/9783030018627}
}
```
Johari, R. (2015). Mechanism design. In J. Baillieul & T. Samad (Eds.), Encyclopedia of Systems and Control. Springer.
Mechanism design is concerned with the design of strategic environments to achieve desired outcomes at equilibria of the resulting game. We briefly overview central ideas in mechanism design. We survey both objectives the mechanism designer may seek to achieve, as well as equilibrium concepts the designer may use to model agents. We conclude by discussing a seminal example of mechanism design at work: the Vickrey-Clarke-Groves (VCG) mechanisms.
```
@incollection{Joh2015Mechanism,
  author = {Johari, Ramesh},
  title = {Mechanism design},
  booktitle = {Encyclopedia of Systems and Control},
  editor = {Baillieul, John and Samad, Tariq},
  publisher = {Springer},
  year = {2015},
  external = {http://dx.doi.org/10.1007/978-1-4471-5102-9_38-1}
}
```
Adlakha, S., Johari, R., & Goldsmith, A. (2014). Competition in wireless systems via Bayesian interference games. In T. Alpcan, H. Boche, M. L. Honig, & H. V. Poor (Eds.), Mechanisms and Games for Dynamic Spectrum Allocation (pp. 32–56). Cambridge University Press.
In this chapter we study competition between wireless devices with incomplete informa- tion about their opponents and model such interactions as Bayesian interference games. Each wireless device selects a power profile over the entire available bandwidth to maximize its data rate (measured via Shannon capacity), which requires mitigating the effect of interference caused by other devices. Such competitive models represent situations in which several wireless devices share spectrum without any central authority or coordinated protocol.
In contrast to games where devices have complete information about their opponents, we consider scenarios where the devices are unaware of the interference they cause to other devices. Such games, which are modeled as Bayesian games, can exhibit significantly different equilibria. We first consider a simple scenario where the devices select their power profile simultaneously. In such simultaneous move games, we show that the unique Bayes–Nash equilibrium is where devices spread their power equally across the entire bandwidth. We then extend this model to a two-tiered spectrum sharing case where users act sequentially. Here one of the devices, called the primary user, is the owner of the spectrum and it selects its power profile first. The second device (called the secondary user) then responds by choosing a power profile to maximize its Shannon capacity. In such sequential move games, we show that there exist equilibria in which the primary user obtains a higher data rate by using only a part of the bandwidth.
In a repeated Bayesian interference game, we show the existence of reputation effects: an informed primary user can “bluff” to prevent spectrum usage by a secondary user who suffers from lack of information about the channel gains. The resulting equilibrium can be highly inefficient, suggesting that competitive spectrum sharing is highly suboptimal. This observation points to the need for some regulatory protocol to attain a more efficient spectrum sharing solution.
```
@incollection{AdlJohGol2014Mechanisms,
  author = {Adlakha, Sachin and Johari, Ramesh and Goldsmith, Andrea},
  title = {Competition in wireless systems via {Bayesian} interference games},
  booktitle = {Mechanisms and Games for Dynamic Spectrum Allocation},
  editor = {Alpcan, Tansu and Boche, Holger and Honig, Michael L. and Poor, H. Vincent},
  publisher = {Cambridge University Press},
  pages = {32--56},
  year = {2014},
  external = {http://www.cambridge.org/us/academic/subjects/engineering/communications-and-signal-processing/mechanisms-and-games-dynamic-spectrum-allocation?format=HB}
}
```
Johari, R. (2007). Efficiency loss and the design of scalable resource allocation mechanisms. In N. Nisan, T. Roughgarden, E. Tardos, & V. V. Vazirani (Eds.), Algorithmic Game Theory (pp. 543–567). Cambridge University Press.
- [ abstract ]
- [ bib ]
- [ pdf ]
- [ link ]
In this chapter, we study the allocation of a single infinitely divisible resource among multiple competing users. While we aim for efficient allocation of the resource, the task is complicated by the fact that users’ utility functions are typically unknown to the resource manager. We study the design of resource allocation mechanisms that are approximately efficient (i.e., have a low price of anarchy), with low communication requirements (i.e., the strategy spaces of users are low dimensional).
Our main results concern the proportional allocation mechanism, for which a tight bound on the price of anarchy can be provided. We also show that in a wide range of market mechanisms that use a single market-clearing price, the proportional allocation mechanism minimizes the price of anarchy. Finally, we relax the assumption of a single market-clearing price, and show that by extending the class of Vickrey-Clarke-Groves mechanisms all Nash equilibria can be guaranteed to be fully efficient.
```
@incollection{Joh2007Efficiency,
  author = {Johari, Ramesh},
  title = {Efficiency loss and the design of scalable resource allocation mechanisms},
  booktitle = {Algorithmic Game Theory},
  editor = {Nisan, Noam and Roughgarden, Tim and Tardos, Eva and Vazirani, Vijay V.},
  publisher = {Cambridge University Press},
  pages = {543--567},
  year = {2007},
  external = {http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/algorithmic-game-theory?format=HB}
}
```
Johari, R., & Tsitsiklis, J. N. (2005). A game theoretic view of efficiency loss in resource allocation. In E. H. Abed (Ed.), Advances in Control, Communication Networks, and Transportation Systems: In Honor of Pravin Varaiya (pp. 203–224). Birkhauser.
Motivated by resource allocation problems in communication networks as well as power systems, we consider the design of market mechanisms for such settings which are robust to gaming behavior by market participants. Recent results in this work are reviewed, including: (1) efficiency loss guarantees for a data rate allocation mechanism first proposed by Kelly, both when link capacities are fixed and when they are elastic; (2) characterization of mechanisms that minimize the efficiency loss, within a certain class of “simple” mechanisms; (3) extensions to general networks; and (4) mechanism design for supply function bidding in electric power systems.
```
@incollection{JohTsi2005Game,
  author = {Johari, Ramesh and Tsitsiklis, John N.},
  title = {A game theoretic view of efficiency loss in resource allocation},
  booktitle = {Advances in Control, Communication Networks, and Transportation Systems: In Honor of Pravin Varaiya},
  editor = {Abed, Eyad H.},
  publisher = {Birkhauser},
  pages = {203--224},
  year = {2005},
  external = {http://www.springer.com/us/book/9780817643850}
}
```

Ph.D. thesis

Johari, R. (2004). Efficiency loss in market mechanisms for resource allocation (PhD thesis). Massachusetts Institute of Technology.
- [ abstract ]
- [ bib ]
- [ pdf ]
- [ link ]
This thesis addresses a problem at the nexus of engineering, computer science, and economics: in large scale, decentralized systems, how can we efficiently allocate scarce resources among competing interests? On one hand, constraints are imposed on the system designer by the inherent architecture of any large scale system. These constraints are counterbalanced by the need to design mechanisms that efficiently allocate resources, even when the system is being used by participants who have only their own best interests at stake.
We consider the design of resource allocation mechanisms in such environments. The analytic approach we pursue is characterized by four salient features. First, the monetary value of resource allocation is measured by the aggregate surplus (aggregate utility less aggregate cost) achieved at a given allocation. An efficient allocation is one which maximizes aggregate surplus. Second, we focus on market-clearing mechanisms, which set a single price to ensure demand equals supply. Third, all the mechanisms we consider ensure a fully efficient allocation if market participants do not anticipate the effects of their actions on market-clearing prices. Finally, when market participants are price anticipating, full efficiency is generally not achieved, and we quantify the efficiency loss.
We make two main contributions. First, for three economic environments, we consider specific market mechanisms and exactly quantify the efficiency loss in these environments when market participants are price anticipating. The first two environments address settings where multiple consumers compete to acquire a share of a resource in either fixed or elastic supply; these models are motivated by resource allocation in communication networks. The third environment addresses competition between multiple producers to satisfy an inelastic demand; this model is motivated by market design in power systems.
Our second contribution is to establish that, under reasonable conditions, the mechanisms we consider minimize efficiency loss when market participants anticipate the effects of their actions on market-clearing prices. Formally, we show that in a class of market-clearing mechanisms satisfying certain simple mathematical assumptions and for which there exist fully efficient competitive equilibria, the mechanisms we consider uniquely minimize efficiency loss when market participants are price anticipating.
```
@phdthesis{Joh2004Efficiency,
  author = {Johari, Ramesh},
  title = {Efficiency loss in market mechanisms for resource allocation},
  school = {Massachusetts Institute of Technology},
  year = {2004},
  external = {http://hdl.handle.net/1721.1/16694}
}
```

Working papers

Krishnasamy, S., Arapostathis, A., Johari, R., & Shakkottai, S. (2018). On Learning the cμ Rule in Single and Parallel Server Networks.
We consider learning-based variants of the cμ rule for scheduling in single and parallel server settings of multi-class queueing systems. In the single server setting, the cμ rule is known to minimize the expected holding-cost (weighted queue-lengths summed over classes and a fixed time horizon). We focus on the problem where the service rates μ are unknown with the holding-cost regret (regret against the cμ rule with known μ) as our objective. We show that the greedy algorithm that uses empirically learned service rates results in a constant holding-cost regret (the regret is independent of the time horizon). This free exploration can be explained in the single server setting by the fact that any work-conserving policy obtains the same number of samples in a busy cycle. In the parallel server setting, we show that the cμ rule may result in unstable queues, even for arrival rates within the capacity region. We then present sufficient conditions for geometric ergodicity under the cμ rule. Using these results, we propose an almost greedy algorithm that explores only when the number of samples falls below a threshold. We show that this algorithm delivers constant holding-cost regret because a free exploration condition is eventually satisfied.
```
@article{KriAraJohSha2018OnLearning,
  author = {Krishnasamy, Subhashini and Arapostathis, Ari and Johari, Ramesh and Shakkottai, Sanjay},
  title = {On Learning the cμ Rule in Single and Parallel Server Networks},
  year = {2018},
  external = {https://arxiv.org/abs/1802.06723}
}
```
Bastani, H., Bayati, M., Braverman, M., Gummadi, R., & Johari, R. (2016). Analysis of Medicare pay-for-performance contracts.
Medicare has sought to improve patient care through pay-for-performance (P4P) programs that better align hospitals’ financial incentives with quality of service. However, the design of these policies is subject to a variety of practical and institutional constraints, such as the use of "small" performance-based incentives. We develop a framework based on a stylized principal-agent model to characterize the optimal P4P mechanism within any set of feasible mechanisms in the regime of small incentives. Importantly, our feasible set can be flexibly modified to include institutional constraints. We apply our results to examine debated design choices in existing Medicare P4P programs, and offer several insights and policy recommendations. In particular, we find that these mechanisms may benefit by incorporating bonuses for top-performers, and using a single performance cutoff to uniformly assess performance-based payments. We also examine a number of comparative statics that shed light on when P4P mechanisms are effective.
```
@article{BasBayBraGumJoh2016Analysis,
  author = {Bastani, Hamsa and Bayati, Mohsen and Braverman, Mark and Gummadi, Ramki and Johari, Ramesh},
  title = {Analysis of Medicare pay-for-performance contracts},
  year = {2016},
  external = {https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2839143}
}
```
Gummadi, R., Johari, R., Schmit, S., & Yu, J. Y. (2016). Mean field analysis of multi-armed bandit games.
Much of the classical work on algorithms for multi-armed bandits focuses on rewards that are stationary over time. By contrast, we study multi-armed bandit (MAB) games, where the rewards obtained by an agent also depend on how many other agents choose the same arm (as might be the case in many competitive or cooperative scenarios). Such systems are naturally nonstationary due to the interdependent evolution of agents, and in general MAB games can be intractable to analyze using typical equilibrium concepts (such as perfect Bayesian equilibrium). We introduce a general model of multi-armed bandit games, and study the dynamics of these games under a large system approximation. We investigate conditions under which the bandit dynamics have a steady state we refer to as a mean field steady state (MFSS). In an MFSS, the proportion of agents playing the various arms, called the population profile, is assumed stationary over time; the steady state definition then requires a consistency check that this stationary profile arises from the policies chosen by the agents. We establish the following results in the paper. First, we establish existence of an MFSS under broad conditions. Second, we show under a contraction condition that the MFSS is unique, and that the population profile converges to it from any initial state. Finally, we show that under the contraction condition, MFSS is a good approximation to the behavior of finite systems with many agents. The contraction condition requires that the agent population regenerates sufficiently often, and that the sensitivity of the reward function to the population profile is low enough. Through numerical experiments, we find that in settings with negative externalities among the agents, convergence obtains even when our condition is violated; while in settings with positive externalities among the agents, our condition is tighter.
```
@article{GumJohSchYu2016Mean,
  author = {Gummadi, Ramki and Johari, Ramesh and Schmit, Sven and Yu, Jia Yuan},
  title = {Mean field analysis of multi-armed bandit games},
  year = {2016},
  external = {https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2045842}
}
```
Banerjee, S., Riquelme, C., & Johari, R. (2015). Pricing in ride-share platforms: A queueing-theoretic approach.
We study optimal pricing strategies for ride-sharing platforms, such as Lyft, Sidecar, and Uber. Analysis of pricing in such settings is complex: On one hand these platforms are two-sided – this requires economic models that capture the incentives of both drivers and passengers. On the other hand, these platforms support high temporal-resolution for data collection and pricing – this requires stochastic models that capture the dynamics of drivers and passengers in the system. In this paper we build a queueing-theoretic economic model to study optimal platform pricing. In particular, we focus our attention on the value of dynamic pricing: where prices can react to instantaneous imbalances between available supply and incoming demand. We find two main results: We first show that performance (throughput and revenue) under any dynamic pricing strategy cannot exceed that under the optimal static pricing policy (i.e., one which is agnostic of stochastic fluctuations in the system load). This result belies the prevalence of dynamic pricing in practice. Our second result explains the apparent paradox: we show that dynamic pricing is much more robust to fluctuations in system parameters compared to static pricing. Thus dynamic pricing does not necessarily yield higher performance than static pricing – however, it lets platforms realize the benefits of optimal static pricing, even with imperfect knowledge of system parameters.
```
@article{BanRiqJoh2015Pricing,
  author = {Banerjee, Siddhartha and Riquelme, Carlos and Johari, Ramesh},
  title = {Pricing in ride-share platforms: A queueing-theoretic approach},
  year = {2015},
  external = {https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2568258}
}
```