Journal Publications

  • Y. Narahari and Mayank Ratan Bhardwaj. Enabling Farmers through Game Theory and artificial Intelligence Based Services. NABARD Research Chronicle. April 2024, pp. 22-34.
  • Amal Roy, Chandramani Singh, and Y. Narahari. Recent Advances in Modeling and Control of Epidemics using a Mean Field Approach. Sadhana, Indian Academy Proceedings in Engineering Sciences. To appear: 2023 (20 pages).
  • Vishakha Patil, Ganesh Ghalme, Vineet Nair, Y. Narahari. Achieving Fairness in the Stochastic Multi-armed Bandit Problem. Journal of Machine Learning Research (JMLR), Volume 22, Pages 174:1 – 174:31, 2021.
  • D Padmanabhan, S Bhat, KJ Prabuchandran, S Shevade, Y Narahari. Dominant strategy truthful, deterministic multi-armed bandit mechanisms with logarithmic regret for sponsored search auctions. Applied Intelligence, Volume 52, Number 3, pp. 3209-3226, 2022.
  • Ganesh Ghalme, Swapnil Dhamal, Shweta Jain, Sujit Gujar, Y. Narahari. Ballooning Multi-Armed Bandits, Artificial Intelligence, Volume 296, 2021, 31 pages.
  • Satyanath Bhat, Shwetha Jain, Sujit Gujar, and Y. Narahari. An Optimal Bidimensional Multi-Armed Bandit Auction for Multi-Unit Procurement. Annals of Mathematics and Artificial Intelligence.  Springer. Volume 85, Number 1, 2019. pp. 1-19.
  •  Palash Dey, Neeldhara Mishra, and Y. Narahari.  Parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers.  Theoretical Computer Science,  Volume 783,  2019, pp. 53-70.
  • Swapnil Dhamal, Rohith D. Vallam, and Y. Narahari. Modeling Spread of Preferences in Social Networks for Sampling-based Preference Aggregation. IEEE Transactions on Network Science and Engineering, Volume 6, Issue 1,  Jan-Feb 2019, pp. 46-59.
  • Thirumulanathan, Rajesh Sundaresan, and Y. Narahari. Optimal mechanisms for selling two items to a single buyer having uniformly distributed valuations. Journal of Mathematical Economics, Elsevier,  Volume 82, May 2019, pp. 1-30.
  • Thirumulanathan, Rajesh Sundaresan, and Y. Narahari. On optimal mechanisms in the two-item single-buyer unit-demand setting. Journal of Mathematical Economics, Elsevier, Volume 82, May 2019, pp. 31-60.
  •  Palash Dey, Neeldhara Mishra, and Y. Narahari.  Complexity of manipulation with partial information in voting.  Theoretical Computer Science,  Volume 726, pp. 78-99,2018. 
  • Shweta Jain, Sujit Gujar, Satyanath Bhat, Onno Zoeter, and Y. Narahari. A quality-assuring, cost-optimal, multi-armed bandit mechanism for expertsourcing. Artificial Intelligence,  Elsevier, Volume 254,  2018, pp. 44-63.
  • Shivika Narang, Praphul Chandra, Shweta Jain, and Y. Narahari. Foundations of Blockchain Technology for Industrial and Societal Applications.  Advanced Computing and Communications. Volume 1, Number 3, 2018, pp. 32-51.
  • Shourya Roy, Arun Rajkumar, and Y. Narahari. Selection of Automatic Short Answer Grading Techniques Using Contextual Bandits for Different Evaluation Measures. International Journal of Advances in Engineering Sciences and Applied Mathematics (Special Issue on Data Science, commemorating the Golden Jubilee of IIT-Madras), 2017.
  • Divya Padmanabhan, Satyanath Bhat, Shrish K. Shevade, and Y. Narahari. Multi-Label Classification from Multiple Noisy Sources using Topic Models. Information. Volume 8, Number 2, 2017, pp. 52-74.
  • Palash Dey, Neeldhara Mishra, Y. Narahari. Frugal Bribery in Voting. Theoretocal Computer Science. Volume 686, 2017, pp. 15-32.
  • Y. Narahari. Beautiful Results from a Beautiful Mind. Resonance. Volume 21, Number 9, September 2016, pp. 777-801.
  • Swapnil Dhamal, Prabu Chandran, and Y. Narahari. Information Diffusion in Social Networks in Two Phases. IEEE Transactions on Network Science and Engineering. Volume 3, Number 4, 2016, pp. 197-210.
  • Palash Dey, Neeldhara Mishra, Y. Narahari. Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting. Theoretocal Computer Science. Volume 616, 2016, pp. 111-125.
  • Shweta Jain, Satyanath Bhat, Ganesh Ghalme, Divya Padmanabhan, and Y. Narahari. Mechanism design for stochastic multi-armed bandit problems. Indian Journal of Pure and Applied Mathematics. 2016, Volume 47, Number 2, pp. 229-272.
  • Palash Dey and Y. Narahari. Asymptotic Manipulability of Voting Rules. Studies in Microeconomics. Special Issue on Game Theory and its Applications to Social and Economic Networks. Volume 3, Number 1, 2015, pp. 120-139.
  • Swapnil Dhamal and Y. Narahari. Formation of Stable Strategic Networks with Desired Topologies. Studies in Microeconomics. Volume 3, Number 1, 2015, pp. 158-213. Special Issue on Game Theory and its Applications to Social and Economic Networks. 2015.
  • Swaprava Nath, Onno Zoeter, Y. Narahari, Chris Dance. Dynamic mechanism design with interdependent valuations. Review of Economic Design. Volume 19, Number 3, 2015, pp. 211-228.
  • Rohith D. Vallam, C.A. Subramanian, Ramasuri Narayanam, Y. Narahari, and N. Srinath. Strategic Network Formation with Localized Payoffs. Studies in Microeconomics. Volume 2, Number 1, 2014, pp. 63-120.
    • In this investigation, we analyze a network formation game in a strategic setting where payoffs of individuals depend only on their immediate neighbourhood. Our study explores the structure of networks that form, satisfying pairwise stability, or efficiency, or both. We also examine the tradeoffs between topologies of pairwise and efficient networks using the notion of price of stability.
  • Ramasuri Narayanam and Y. Narahari. A novel, decentralized, local information based algorithm for community detection in social networks. CSI Journal of Computing. Volume 2, Number 1-2, 2013, pp. 40-50.
    • In this study, we propose a novel algorithm for community detection in social networks using game theory. In particular, we use the notion of Nash stable partitions to set up a decentralized algorithm that uses only local neighbourhood information. We demonstrate the efficacy of this algorithm through a wide variety of experiments.
  • Vikas Garg, Y. Narahari, M. Narasimha Murty. Novel Biobjective Clustering based on Cooperative Game Theory. IEEE Transactions on Knowledge and Data Engineering (TKDE). Volume 25, Number 5, 2013, 00. 1070-1082.
    • This paper proposes a new approach to clustering. The idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm which we call BiGC. The algorithm yields high quality clustering with respect to average point-to-center distance (potential) as well as average intra-cluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms, through a detailed experimentation on several benchmark datasets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.
  • Sujit Gujar and Y. Narahari. Optimal Combinatorial Auctions with Single Minded Bidders. Operational Research , Special Issue on Digital Economy and E-Commerce. Springer, Volume 13, Number 1, 2013, pp. 27-46.
    • This paper extends the classical Myerson auction and some of its extensions in the literature to a more general, reverse auction setting in which a buyer wishes to minimize the total cost while procuring multiple units of bundles. The sellers are assumed to be single minded.
  • Deepak Bagchi, Shantanu Biswas, Y. Narahari, P. Suresh, Udaya Lakshmi, N. Viswanadham, S.V. Subrahmanya. Carbon Footprint Optimization: Game Theoretic Problems and Solutions. ACM SIGecomm Exchanges. Volume 11, Number 1, 2012, pp. 34-38.
    • Global warming is an issue of significant concern and world over, countries and global companies are actively engaged in various efforts to mitigate the effects of global warming. We introduce the carbon emission reduction problem as a carbon economics problem where the countries or global industries are trying to reduce their carbon footprint at minimum cost. We discuss four problems that we have identified under the umbrella of carbon economics problems: carbon credit allocation (CCA), carbon credit buying (CCB), carbon credit selling (CCS), and carbon credit exchange (CCE). We consider the carbon credit allocation problem and provide an insight on how this problem could be addressed using optimization, game theory, and mechanism design.
  • Akash Das Sharma, Sujit Gujar, and Y. Narahari. Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions. Current Science, Indian Academy of Sciences. November 2012. (Special Section on Game Theory). pp. 1064-1077.
    • In pay-per-click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their advertisements (Ads for short). A sponsored search auction for a keyword is typically conducted for a number of rounds (say T). There are click probabilities associated with each agent-slot pair. The search engine would like to maximize the sum of values of the advertisers for the keyword. However, the search engine does not know the true values advertisers and also does not know the click probabilities. A key problem for the search engine therefore is to learn these click probabilities during the initial rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues, due to their connection to the multi-armed-bandit problem, are aptly referred to as multi-armed-bandit (MAB) mechanisms. When m=1, exact characterizations for truthful MAB mechanisms are available in the literature. This paper explores exact characterizations in the non-trivial general case when m > 1.
  • Chaitanya Nittala and Y. Narahari. Optimal Equilibrium Bidding Strategies for Budget Constrained Bidders in Sponsored Search Auctions. Operational Research. , Special Issue on Digital Economy and E-Commerce. Volume 12, Number 3, 2012, pp. 317-343.
    • Budget optimization (determining an optimal distribution of limited amount of money amongst keywords to bid) and bid optimization (determining optimal bids for the selected keywords) in the face of an unpredictable keyword traffic is a challenging problem facing advertisers in sponsored search auctions. Another key requirement in sponsored search auctions is stability of the bid profile, which is usually characterized using the notion of locally envy free equilibrium. A variety of budget optimization and bid optimization ideas have been proposed in the literature; the bid profiles suggested by them have varying stability properties. In this paper, our objective is to come up with a bidding strategy for advertisers that is optimal for the budget optimization as well as the bid optimization problems and also guarantees convergence to a locally envy free equilibrium. We work with an elegant linear programming formulation.
  • Sujit Gujar and Y. Narahari. Redistribution Mechanisms for Assignment of Heterogeneous Objects. Journal of Artificial Intelligence Research. Volume 41, pp. 131-154, 2011
    • There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. Our main result is an impossibility theorem which rules out linear rebate functions with non-zero efficiency in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with nonzero efficiency are possible when the valuations for the objects have some relationship. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed.
  • Ramasuri Narayanam and Y. Narahari. Topologies of Strategically Formed Social Networks Based on a Generic Value Function – Allocation Rule Model Social Networks. Social Networks , Volume 33, Number 1, pp. 56-69, 2011.
    • We investigate the topologies of networks formed with a generic model of network formation which uses ideas from both noncooperative game theory and cooperative game theory. Our model improves upon exiting models by simulataneously capturing all the following key features: (1) Benefits from immediate neighbours (2) Costs of maintaining links (3) Benefits from non-neighbouring nodes and the decay of these benefits with distance (4) intermediary benefits that arise from multi-step paths. Based on this versatile model, our study explores the structure of networks that satisfy efficiency and/or pairwise stability.
  • Ramasuri Narayanam and Y. Narahari. A Shapley Value Approach to Discovering Influential Nodes in Social Networks. IEEE Transactions on Automation Science and Engineering , Volume 8, Number 1, January 2011, pp. 130-147.
    • Discovering influential nodes in social networks is an important problem, with significant applications in information diffusion, viral marketing, internet advertising, etc. This paper explores a novel approach to this problem. The main idea is to model the extent of diffusion of information in a social network using the characteristic function of a coalitional game. The next idea is to use the Shapley value of this coalitional game to devise an efficient algorithm that finds the top K nodes or the most influential nodes for information diffusion. The work is validated using several real-world data sets as well as synthetically generated random graphs.
  • A. Radhika, Y. Narahari, Deepak Bagchi, P. Suresh, and S.V. Subrahmanya. Mechanism Design Problems in Carbon Economics. Journal of the Indian Institute of Science , Special Issue on Advances in Electrical Sciences, Volume 90, Number 3, July-September 2010, pp. 381-411.
    • Reduction of carbon emissions is of paramount importance in the context of global warming and climate change. Countries and global companies are now engaged in understanding systematic ways of solving carbon economics problems, aimed ultimately at achieving well defined emission targets. This paper proposes mechanism design as an approach to solving carbon economics problems. The paper first introduces carbon economics issues in the world today and next focuses on carbon economics problems facing global industries. The paper identifies four problems faced by global industries: carbon credit allocation (CCA), carbon credit buying (CCB), carbon credit selling (CCS), and carbon credit exchange (CCE). It is argued that these problems are best addressed as mechanism design problems. The discipline of mechanism design is founded on game theory and is concerned with settings where a social planner faces the problem of aggregating the announced preferences of multiple agents into a collective decision, when the actual preferences are not known publicly. The paper provides an overview of mechanism design and presents the challenges involved in designing mechanisms with desirable properties. To illustrate the application of mechanism design in carbon economics, the paper describes in detail one specific problem, the carbon credit allocation problem.
  • D. Garg and Y. Narahari. An Optimal Mechanism for Sponsored Search Auctions and Comparison with other Mechanisms. IEEE Transactions on Automation Science and Engineering , Volume 6, Number 4, pp. 641-657, 2009.
    • The advertiser-supported web site is one of the successful business models in the web landscape. In this article, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well known mechanisms for sponsored search auction – Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call Optimal (OPT) mechanism. The OPT mechanism maximizes the search engine’s expected revenue while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT.
  • Raghav Kumar Gautam, N. Hemachandra, Y. Narahari, Hastagiri Praksh, Datta Kulkarni, and Jeffrey D. Tew. An Optimal Mechanism for Multi-unit Procurement with Volume Discount Bids. International Journal of Operational Research. Special Issue on Game Theory Applications in Operations Research and Management Science. Volume 6, Number 1, 2009, pp. 70-91.
    • In this paper, we extend the classical Myerson auction to the the design of an optimal procurement mechanism which a firm can use while procuring multiple units of a single homogeneous item based on bids submitted by autonomous, rational, and intelligent suppliers. We propose elegant optimal procurement mechanisms for two different situations. In the first situation, each supplier specifies the maximum quantity that can be supplied as well as a per unit price. For this situation, we design an optimal mechanism S-OPT (Optimal with Simple bids). In the more general case, each supplier specifies discounts based on the volume of supply. In this case, we design an optimal mechanism VD-OPT (Optimal with Volume Discount bids). The VD-OPT mechanism uses the S-OPT mechanism as a building block. Both the proposed mechanisms minimize the cost to the buyer, satisfying at the same time, (a) Bayesian incentive compatibility and (b) interim individual rationality.
  • Y. Narahari, N. Hemachandra, Nikesh Kumar Srivastava, Datta Kulkarni, and Jeffrey D. Tew. A Bayesian Incentive Compatible Mechanism for Decentralized Supply Chain Formation. International Journal of Operational Research. Special Issue on Game Theory Applications in Operations Research and Management Science. Volume 6, Number 1, 2009, pp. 27-53.
    • In this paper, we consider a decentralized supply chain formation problem for multi-echelon supply chains when the managers of the individual echelons are autonomous, rational, and intelligent. We develop a mechanism design framework for addressing this problem and propose a Bayesian incentive compatible mechanism for supply chain formation. Existing solutions in the literature, which are based on the classical Vickrey-Clarke-Groves mechanisms, require significant incentives to be paid to the echelon managers for achieving incentive compatibility. The proposed mechanism significantly reduces the cost of supply chain formation.
  • S. Kameshwaran and Y. Narahari. Efficient Algorithms for Nonconvex Piecewise Linear Knapsack Problems. European Journal of Operational Research. Volume 192, Number 1, 2009, Pages: 56-68.
    • This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two different mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.
  • G. Radhanikanth and Y. Narahari. Reverse Combinatorial Auction Based Protocols for Resource Selection in Grids. International Journal of Grid and Utility Computing, Volume 1, Number 2, 2009 Pages:109 – 120
    • Grid computing provides an extremely promising distributed paradigm for executing large scale resource intensive applications. Given a distributed pool of resources, a grid user who wishes to execute a job comprising a large number of tasks on the grid, is faced with the problem of selecting an optimal set of resources. We call this problem the resource selection problem and our approach to modeling and solving this problem is through a reverse combinatorial auction. In the proposed auction, the grid user is the buyer and the resource owners are the sellers. The resource owners submit bids on combinations of resources or tasks in response to the grid user’s request for a bundle of resources. The objective of the grid user is to minimize an appropriately defined cost function based on these bids. Two variants of the problem are considered: (1) resource selection with task level trading and (2) resource selection with resource level trading. In both the cases, the resource selection problem turns out to be an integer linear programming problem. To investigate the performance of the proposed resource selection protocols, NAS grid benchmarks are run using SimGrid and the performance is compared against that of a cost optimization protocol and a time optimization protocol which are part of the Nimrod-G resource broker. The protocols proposed exhibit superior overall performance in terms of turn around time and total cost.
  • S. Kameshwaran and Y. Narahari. A Benders Based Winner Determination Algorithm for Volume Discount Procurement Auctions. International Journal of Logistics and Supply Chain Management Special Issue on Procurement Strategies: Past-Present and the Future, Volume 5, Number 1/2, 2009, Pages: 1-20.
    • This paper considers an industrial procurement problem of a large volume of a single good. The procurement is implemented using volume discount auctions, where the suppliers submit nonconvex piecewise linear cost functions as bids. Such bids enable the suppliers to effectively express their economies of scale and transportation constraints. The winner determination problem faced by the buyer is an NP-hard nonlinear knapsack problem. We propose a mixed integer linear formulation for the problem which has the following exploitable primal structure: if the integer variables are fixed at some feasible values, then solving the remaining linear variables is a continuous knapsack problem. Using this feature, Benders’ decomposition algorithm is developed and various techniques are proposed to accelerate the convergence of the algorithm. Experimental results with different randomly generated test data for the proposed algorithms show the efficacy of the algorithms.
  • N. Rama Suri and Y. Narahari. Design of an Optimal Bayesian Incentive Compatible Broadcast Protocol for Ad-hoc Wireless Networks with Rational Nodes. IEEE Journal on Selected Areas in Communications, Special Issue on Game Theory in Communications Systems, , Volume 26, Number 7, September 2008, pp. 1138–1148.
    • This special issue is edited by J. Huang, D.P. Palomar, N. Mandayam, J. Walrand, S.B. Wicker, and T. Basar and has a foreword by Nobel Laureate John Nash. The paper introduces a paradigm shift from using the classical Vickrey-Clarke-Groves mechanisms towards using Bayesian incentive compatible mechanism, leading to substantial reduction in incentive payments and costs. Nodes in an ad hoc wireless network incur certain costs for forwarding packets since packet forwarding consumes the resources of the nodes. If the nodes are rational, free packet forwarding by the nodes cannot be taken for granted and incentive based protocols are required to stimulate cooperation among the nodes. Existing incentive based approaches are based on the VCG (Vickrey-Clarke-Groves) mechanism which leads to high levels of incentive budgets and restricted applicability to only certain topologies of networks. Moreover, the existing approaches have only focused on unicast and multicast. Motivated by this, we have proposed in this paper an incentive based broadcast protocol that satisfies Bayesian incentive compatibility and minimizes the incentive budgets required by the individual nodes. The proposed protocol, which we call BIC-B (Bayesian incentive compatible broadcast) protocol, also satisfies budget balance. We also derive a necessary and sufficient condition for the ex-post individual rationality of the BIC-B protocol.
  • D. Garg and Y. Narahari. Mechanism Design for Single Stackelberg Problems and Application to Procurement Auction Design. IEEE Transactions on Automation Science and Engineering, Volume 5, Number 3, July 2008, Pages: 377-393. (Recipient of the 2008 Best Application Paper Award of the IEEE Transactions on Automation Science and Engineering).
    • Hierarchical decision making problems arise naturally in many fields including electronic commerce, supply chain management, distributed computing, transportation networks, manufacturing systems, and multi-agent systems. These problems involve interacting decision-making agents with a predefined sequence according to which decisions are taken. If the agents are rational and intelligent, these problems induce a Stackelberg game and for this reason, these problems could be called Stackelberg problems. In this paper, we look at a prominent special class of these problems called Single Leader Rest Follower (SLRF) problems. There are many emerging examples of SLRF problems: auctions with reserve prices, Internet routing, supply chain formation, resource allocation in computational grids, routing in transportation networks, scheduling in manufacturing systems, etc. The main contribution of this paper is to extend classical mechanism design to the class of SLRF problems. Classical mechanism design uses the framework of Bayesian games whereas mechanism design applied to SLRF problems has to deal with the more general Bayesian Stackelberg games. This motivates the theoretical contribution of this paper, which is to extend mechanism design to the setting of SLRF problems. The paper also offers a significant application: designing incentive compatible procurement auctions with reserve prices. Mechanism design or protocol design in the context of all the emerging applications mentioned above will be a rich avenue for applying this theory.
  • D. Garg, Y. Narahari, and S. Gujar. Foundations of Mechanism Design: A Tutorial. Part 1: Key Concepts and Classical Results. Sadhana, Indian Academy Proceedings in Engineering Sciences, Volume 33, Number 2, April 2008, pp. 83-130.
    • Mechanism design, an important tool in microeconomics, has found widespread applications in modeling and solving decentralized design problems in many branches of engineering, notably computer science, electronic commerce, and network economics. The objective of this two part paper is to provide a tutorial introduction to the foundations and key results in mechanism design theory. Part 1 focuses on basic concepts and classical results which form the foundation of mechanism design theory.
  • D. Garg, Y. Narahari, and S. Gujar. Foundations of Mechanism Design: A Tutorial. Part 2 : Advanced Concepts and Results. Sadhana, Indian Academy Proceedings in Engineering Sciences, Volume 33, Number 2, April 2008, pp. 131-174.
    • This is the second part of the tutorial on mechanism design. This part presents key advanced concepts and results in mechanism design.
  • Pankaj Dayama, and Y. Narahari. Design of Multi-Unit Electronic Exchanges through Decomposition. IEEE Transactions on Automation Science and Engineering, Volume 4, Number 1, January 2007, pp. 67-74.
    • In this paper we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst case complexity equal to that of as many as (1+m+n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: (1) forward auction and (2) reverse auction, which turn out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes. The proposed approach has worst case polynomial time complexity and our experimentation shows that the approach produces good quality solutions to the problem.
  • T.S. Chandrashekar, Y. Narahari, Charles H. Rosa, Devadatta Kulkarni, Pankaj Dayama, and Jeffrey D. Tew. Auction Based Mechanisms for Electronic Procurement. IEEE Transactions on Automation Science and Engineering, Volume 4, Number 3, July 2007, pp. 297-321.
    • Since the burst of the dot com bubble, many procurement professionals and purchasing managers have begun to question the ability of the Internet to redefine procurement processes within their firms. In this article we set out to show that this would be a misplaced sense of deja vu because the Internet along with a milieu of decision technologies based on Game Theory and Optimization is proving to be a significant tool in the hands of procurement professionals. Sans all the hype, the dot com phenomena has left behind useful ideas including that of e-platforms for on-line auctions. Building upon this core conceptual construct familiar to most procurement professionals, we set out to survey the exciting field of research this has opened up with a vast potential for immediate and gainful applications. We review the existing state-of-the-art in this field, track its recent developments and classify the models available for different procurement scenarios. We also provide pointers to areas that require further fundamental as well as applied research which calls for the attention of not just academic researchers but also practicing professionals. In our review, we present the mathematical formulations under each of the above categories, bring out the game theoretic and computational issues involved in solving the problems, and summarize the current art. We also present a significant case study of auction based e-procurement at General Motors.
  • C.V.L. Raju, Y. Narahari, and K. Ravi Kumar. Learning dynamic prices in multi-seller electronic markets with with price sensitive customers, stochastic demands, and inventory replenishments. IEEE Transactions on Systems, Man, and Cybernetics, Part C. Special Issue on Game-theoretic Analysis and Stochastic Simulation of Negotiation Agents, Special Issue on Game-theoretic Analysis and Stochastic Simulation of Negotiation Agents, Volume 36, Number 1, January 2006, pp. 92-106.
    • In this paper, we use reinforcement learning (RL) as a tool to study price dynamics in an electronic retail market consisting of two competing sellers and price sensitive and lead time sensitive customers. Sellers, offering identical products, compete on price to satisfy stochastically arriving demands (customers) and follow standard inventory control and replenishment policies to manage their inventories. In such a generalized setting, RL techniques have not been applied before. We consider two representative cases: (1) no information case, where none of the sellers has any information about customer queue levels, inventory levels, or prices at the competitors; and (2) partial information case, where every seller has information about the customer queue levels and inventory levels of the competitors. Sellers employ automated pricing agents or pricebots, which use RL-based pricing algorithms to reset the prices at random intervals based on factors such as number of back orders, inventory levels, and replenishment lead times, with the objective of maximizing discounted cumulative profit. In the no information case, we show that a seller who uses Q-learning outperforms a seller who uses derivative following (DF). In the partial information case, we model the problem as a Markovian game and use actor-critic based RL to learn dynamic prices. We believe our approach to solving these problems is a new promising way of setting dynamic prices in multi-seller environments with stochastic demands, price sensitive customers, and inventory replenishments.
  • D.Garg, Y. Narahari, N. Viswanadham. Achieving sharp deliveries in supply chains through variance pool allocation. European Journal of Operational Research, Volume 171, 2006, pp. 227-254.
    • Variability reduction and business process synchronization are acknowledged as key to achieving sharp and timely deliveries in supply chain networks. In this paper, we develop an approach that facilitates variability reduction and business process synchronization for supply chains in a cost effective way. The approach developed is founded on an analogy between mechanical design tolerancing and supply chain lead time compression. We first present a motivating example to describe this analogy. Next, we define, using process capability indices, a new index of delivery performance called delivery sharpness which, when used with the classical performance index delivery probability, measures the accuracy as well as the precision with which products are delivered to the customers. Following this, we solve the following specific problem: how do we compute the allowable variability in lead time for individual stages of the supply chain so that specified levels of delivery sharpness and delivery probability are achieved in a cost-effective way? We call this the variance pool allocation (VPA) problem. We suggest an efficient heuristic approach for solving the VPA problem and also show that a variety of important supply chain design problems can be posed as instances of the VPA problem. One such problem, which is addressed in this paper, is the supply chain partner selection problem. We formulate and solve the VPA problem for a plastics industry supply chain and demonstrate how the solution can be used to choose the best mix of supply chain partners.
  • S. Kameshwaran, Y. Narahari, C. H. Rosa, D. M. Kulkarni, and J. D. Tew. Multiattribute Electronic Procurement using Goal Programming. European Journal of Operational Research, Volume 179, 2006, pp. 518-536.
    • One of the key challenges of current day electronic procurement systems is to enable procurement decisions transcend beyond a single attribute such as cost. Consequently, multiattribute procurement has emerged as an important research direction. In this paper, motivated by a realistic industrial procurement problem, we develop a multiattribute e-procurement system for procuring a large volume of a single item. Our system is motivated by an industrial procurement scenario for procuring raw material in automotive industries. The procurement scenario demands multiattribute bids, volume discount cost functions, inclusion of business constraints, and consideration of multiple criteria in bid evaluation. We develop a generic framework for an e-procurement system that meets the above requirements. The bid evaluation problem is formulated as a mixed linear integer multiple criteria optimization problem and goal programming is used as the solution technique. We present a numerical study for which we illustrate the proposed approach and a heuristic is proposed to handle the computational complexity arising out of the cost functions used in the bids.
  • Y. Narahari and Pankaj Dayama. Combinatorial Auctions for Electronic Business. Sadhana (Special Issue on Electronic Commerce and Electronic Business, Volume 30, Parts 2 and 3, April/June 2005, pp. 179-212.
    • Combinatorial auctions have recently generated significant interest as an automated mechanism for buying and selling bundles of goods. They are proving to be extremely useful in numerous e-business applications such as e-selling, e-procurement, e-logistics, and B2B exchanges. In this article, we introduce combinatorial auctions and bring out important issues in the design of combinatorial auctions. We also highlight important contributions in current research in this area. This survey emphasizes combinatorial auctions as applied to electronic business situations.
  • Y. Narahari, C.V.L. Raju, K. Ravikumar, and Sourabh Shah. Dynamic Pricing Models for Electronic Business. Sadhana (Special Issue on Electronic Commerce and Electronic Business), Volume 30, Parts 2 and 3, April/June 2005, pp. 231-255.
    • Dynamic pricing is the dynamic adjustment of prices to consumers depending upon the value these customers attribute to a product or service. Today’s digital economy is ready for dynamic pricing, however recent research has shown that the prices will have to be adjusted in fairly sophisticated ways, based on sound mathematical models, to derive the benefits of dynamic pricing. This article attempts to survey different models that have been used in dynamic pricing. We first motivate dynamic pricing and presents underlying concepts, with several examples, and explain conditions under which dynamic pricing is likely to succeed. We then bring out the role of models in computing dynamic prices. The models surveyed include inventory based models, data driven models, auctions, and machine learning. We present a detailed example of an e-business market to show the use of reinforcement learning in dynamic pricing.
  • C.V.L. Raju, Y. Narahari, and K. Ravi Kumar. Learning Dynamic Prices in Electronic Markets with Customer Segmentation. Annals of Operations Research, Springer, Volume 143, Number 1, March 2006, pp. 59-75.
    • In this paper, we use reinforcement learning (RL) techniques to determine dynamic prices in an electronic monopolistic retail market. The market that we consider consists of two natural segments of customers, captives and shoppers. Captives are mature, loyal buyers whereas the shoppers are more price sensitive and are attracted by sales promotions and volume discounts. The seller is the learning agent in the system and uses RL to learn from the environment. Under (reasonable) assumptions about the arrival process of customers, inventory replenishment policy, and replenishment lead time distribution, the system becomes a Markov decision process thus enabling the use of a wide spectrum of learning algorithms. In this paper, we use the Q-learning algorithm for RL to arrive at optimal dynamic prices that optimize the seller’s performance metric (either long term discounted profit or long run average profit per unit time). Our model and methodology can also be used to compute optimal reorder quantity and optimal reorder point for the inventory policy followed by the seller and to compute the optimal volume discounts to be offered to the shoppers.
  • S. Biswas and Y. Narahari. Iterative Combinatorial Dutch Auctions. Annals of Mathematics and Artificial Intelligence, Springer, Volume 44, Number 3, July 2005, pp. 185-205.
    • The combinatorial auction problem can be modeled as a weighted set packing problem. Similarly the reverse combinatorial auction can be modeled as a weighted set covering problem. We use the set packing and set covering formulations to suggest novel iterative Dutch auction algorithms for combinatorial auction problems. We use generalized Vickrey auctions (GVA) with reserve prices in each iteration. We prove the convergence of the algorithms and show that the solutions obtained using the algorithms lie within provable worst case bounds. We conduct numerical experiments to show that in general the solutions obtained using these algorithms are much better than the theoretical bounds.
  • D.Garg, Y. Narahari, N. Viswanadham. Design of Six Sigma Supply Chains. IEEE Transactions on Automation Science and Engineering (Inaugural issue), Volume 1, Number 1, July 2004, pp. 38-57. (Recipient of the 2004 Best Application Paper Award of the IEEE Transactions on Automation Science and Engineering).
    • This paper builds a quite intriguing conceptual bridge between statistical design tolerancing and supply chain lead time compression. In particular, we introduce a new notion, “six sigma supply chains” to describe and quantify supply chains with sharp and timely deliveries, and develop an innovative approach for designing such networks. Informally, a six sigma supply chain is that which delivers finished products within a customer specified delivery window, with at most 3.4 missed deliveries per million. We show that the design of six sigma supply chains can be formulated as a mathematical programming problem, opening up a rich, new framework for studying supply chain design optimization problems. The proposed methodology is illustrated with the case study of a four stage, make-to-order supply chain for liquid petroleum gas.
  • S. Aithal, Y. Narahari, and E.S. Manjunath, Modeling, Analysis, and Acceleration of a Printed Circuit Board Fabrication Process. Sadhana, Indian Academy of Sciences Proceedings in Engineering Sciences, Volume 26, Part 5, October 2001, pp. 447-463.
    • A simple application of plain queueing network modeling to a practically significant problem. We looked into a PCB fabrication company at Bangalore and studied minute flow details of the process, leading to (what else) a queueing network model. After the usual analysis was done, we had some unusual findings having implications for cycle time reduction.
  • S. Biswas and Y. Narahari, Object Oriented Modeling and Decision Support for Supply Chain. European Journal of Operational Research, 2002, Volume 153, pp. 704-726.
    • This article was the 12th most downloaded paper from the Elsevier Journals website during 2002-04 with 1342 downloads in 2004. This paper describes the conceptualization and implementation of DESSCOM, a decision support system for decision making in supply chain networks, that uses object modeling as the foundation. DESSCOM has two major components: 1. A modeling infrastructure comprising a library of carefully designed generic objects for modeling supply chain elements and dynamic interactions among these elements; 2. A decision workbench that can potentially include powerful algorithmic and simulation-based solution methods for supply chain decision-making. Through the modeling infrastructure, high fidelity models of given supply chain systems can be created rapidly at any desired level of abstraction. Given a supply chain decision problem to be solved, the object oriented models created at the right level of detail can be directly transformed into problem formulations that can then be solved using an appropriate strategy from the workbench. DESSCOM has been used in modeling several benchmark supply chain systems.
  • N. Viswanadham and Y. Narahari, Queueing network modeling and lead time compression of pharmaceutical drug development. International Journal of Production Research, Volume 39, Number 2, pp. 395-412, 2001.
    • This is a fascinating application of applying multiclass queueing network models to suggest lead time compression strategies in new drug discovery and development process. We use probabilistic re-entrant lines as the model and show that such a model can capture the project dynamics in drug development organizations that involve multiple, concurrent projects with contention for human/technical resources. We explore how drug development lead times can be reduced using efficient scheduling and critical mass-based resource management. The model captures important facets of any typical drug development organization, such as: concurrent execution of multiple projects, contention for resources, feedback and reworking of project tasks, variability of new project initiations and task execution times, and important scheduling issues.
  • Y. Narahari , Petri nets: An overview. A two part article. Resonance, Volume 4, Number 8, August 1999, pp. 66-77; and Volume 4, Number 9, September 1999, pp . 58-69.
    • A two part popular overview of the Petri net formalism and its applications. The first part provides an overview of Petri nets and presents important conceptual underpinnings of Petri net modeling. The second part describes how important system properties are modeled by Petri nets and then looks into the applications of Petri net models.
  • Y. Narahari, R. Sudarsan, K.W. Lyons, M.R. Duffey, and R.D. Sriram, Design for tolerance of electro-mechanical assemblies: An integrated approach. To appear in: IEEE Transactions on Robotics & Automation, Volume 15, Number 6, December 1999, pp. 1062-1079.
    • This paper originates an integrated approach for “design for quality” of industrial products using statistical and stochastic quality tools such as the Motorola Six-Sigma approach, the Xerox Holistic Probabilistic Design methodology, the Taguchi methods, and Monte-Carlo simulation. The objective of the research is to build in quality into product designs during early stages of design. This research will lead to the design of the next generation concurrent engineering platform and has generated widespread interest in the community. This paper was among eight papers short-listed for the award of the Best Paper Prize of IEEE Transactions in Robotics and Automation for the year 1999.
  • Y. Narahari, N. Viswanadham, and V. Kiran Kumar, Lead time modeling and acceleration of product design and development. IEEE Transactions on Robotics & Automation, Volume 15, Number 5, October 1999, pp. 882-896.
    • New product design and development constitute an important business process in any company and reducing the lead time to market is a major concern. This paper models a product design and development organization at a fairly high level of abstraction using probabilistic re-entrant lines. It is shown how lead time reduction strategies such as input control, load balancing, efficient scheduling, and variability reduction can be put to work using the queueing network model. A highlight of the paper is to argue the usefulness of “fluctuation smoothing scheduling policies” in the context of real-world product development organizations. The approach has been successfully demonstrated on a PCB design organization at Bangalore.
  • N. Hemachandra and Y. Narahari, A linear programming approach to optimal Markovian switching of Poisson arrival streams to a queueing system. QUESTA (Queueing Systems: Theory and Applications), Volume 36, 2001, pp. 443-461.
    • This paper analyzed multi-class manufacturing plants using a queueing model with a Markov modulated arrival process. The innovativeness of the paper lies in arriving at linear programs, fractional linear programs, and simple non-linear programs to optimize the system performance, starting from such a queueing model.
  • Y. Narahari and L. M. Khan, Asymptotic loss of priority scheduling policies in closed stochastic re-entrant lines: A Computational study. European Journal of Operations Research, Volume 110, Number 3, 1998, pp. 585-596.
    • Asymptotic loss of a closed queueing network under a specified scheduling policy is the limiting gap between the best performance achievable by the policy and the best performance achievable by any policy. Computation of asymptotic loss can often be quite challenging. In this paper, asymptotic loss of closed re-entrant lines is studied from a computational angle and several insights are revealed that are consistent with conjectures.
  • Y. Narahari and N. Hemachandra, On the optimality of exhaustive service policies in multiclass queueing systems with modulated arrivals and switchovers. Special Issue of SADHANA on Competitive Manufacturing Systems, Volume 22, Part 1, February 1997, pp. 69-82.
    • This is an extension of a well-known result by Hofri and Ross who in 1987 proved the optimality of certain scheduling policies in single-server multiclass queues with setup times (under certain technical conditions). The extension applies to single-server multiclass queueing systems with setup times, where individual queues are fed by correlated interrupted Poisson streams generated in the state of a stationary modulating Markov chain. The proof uses an interesting stochastic coupling argument but is based on a technical assumption that is quite challenging to verify.
  • Y. Narahari, N. Hemachandra, and M. S. Gaur, Transient analysis of multiclass manufacturing systems with priority scheduling. Computers and Operations Research, Volume 24, Number 5, 1997, pp. 387-398.
    • This looked into manufacturing systems where the presence of multiple part types and priority scheduling causes unpredictable effects which are best captured by transients. Uniformization was used the approach to carry out transient analysis.
  • Y. Narahari and L. M. Khan, Modeling the effect of hot lots in semiconductor manufacturing systems. IEEE Transactions on Semiconductor Manufacturing, Volume 10, Number 1, February 1997, pp. 185-188.
    • Hot lots are high priority wafers in a semiconductor plant. Their presence in the plant upsets original schedules and delays scheduled work in unpredictable ways. To quantify exactly the effect of hot lots on the cycle times of regular lots is an important issue in real-time operation of wafer fabrication plants. Re-entrant lines with priority scheduling were used as the model and the classical mean value analysis technique was extended to yield a highly efficient performance prediction tool.
  • Y. Narahari and L. M. Khan, Modeling re-entrant manufacturing systems with inspections. Journal of Manufacturing Systems, Volume 15, Number 6, 1996, pp. 367-378.
    • This paper proposes an extension to the classical re-entrant lines (proposed by P.R. Kumar) by introducing probabilistic routing in addition to re-entrancy. The extended model is tailor-made for modeling manufacturing systems with inspection stations.
  • Y. Narahari and R. Srigopal, Real-world extensions to scheduling algorithms based on Lagrangian relaxation. Sadhana, Volume 21, Part 4, August 1996, pp. 415-434.
    • Widia is a best practice machine tools company in Bangalore where a completely automated, flexible manufacturing cell was designed and commissioned in 1994. The scheduling of parts on this cell is an intricate problem, solved hitherto only by thumb-rules and experience. We looked into the data of the scheduling problem and mapped it into a standard integer programming problem, for solving which the application of Lagrangian relaxation was but natural. The insights that were gained from the problem formulation and solution structure led to practical suggestions for scheduling work in the cell.
  • Y. Narahari and L. M. Khan, Performance analysis of scheduling policies in re-entrant manufacturing systems. Computers and Operations Research, Volume 23, Number 1, 1996, pp. 37-51.
    • This paper proposed efficient computational methods based on mean value analysis for analyzing the performance of intricate scheduling policies in semiconductor wafer fabrication plants. The Ph D thesis of the second author was awarded a gold medal at the Indian Institute of Science for this work.
  • Y. Narahari and P. Sundarrajan, Performability of fork-join queueing systems. Journal of the Operational Research Society, Volume 46, 1995, pp. 1237–1249.
    • This is a computational-oriented paper which provides an algorithmic methodology to compute first two moments of performability for fork-join queueing systems.
  • K. Ravikumar and Y. Narahari, Dynamic scheduling in manufacturing systems using Brownian approximations. Sadhana, Indian Academy Proceedings in Engineering Sciences, Volume 19, Part 6, December 1994 pp. 891–939.
    • An engineering, yet fairly rigorous overview of dynamic scheduling of queueing networks in heavy traffic, using the Brownian approximation. A must-read for any graduate student interested in a first level exposure to this area.
  • Y. Narahari and N. Viswanadham, Transient analysis of manufacturing systems performance. IEEE Transactions on Robotics and Automation, Vol. 10, No. 2, April 1994, pp. 330–345.
    • This paper articulates in a comprehensive manner the importance of transient performance analysis using Markovian models of manufacturing systems. It was a trend-setter because most performance studies of manufacturing systems until then were based on steady-state analysis.
  • C. R. M. Sundaram and Y. Narahari, Modelling and analysis of the variance in parallelism in parallel computations. Computers and Electrical Engineering, Vol. 19, No. 6, August 1993, pp. 495–506.
    • One more effective application of the PFQN-GSPN hybrid approach to performance modeling. The motivation was provided by the need to model variance of level of parallelism in parallel computing applications.
  • N. Viswanadham, Y. Narahari, and T. L. Johnson, Stochastic modeling of flexible manufacturing systems. Mathematical and Computer Modelling, Vol. 16, No. 3, 1992, pp. 15–34.
    • This is an up-to-date (up to 1991) overview of stochastic modeling approach to manufacturing systems performance evaluation.
  • Y. Narahari, N. Viswanadham, and K. R. Krishna Prasad, Markovian models for deadlock analysis in automated manufacturing systems. Sadhana, Indian Academy Proceedings in Engineering Sciences, Vol. 15, Parts 4 and 5, December 1990, pp. 343–353.
    • Markov chains with absorbing states are a natural model for FMSs with deadlocks. Performance analysis of this class of FMSs entails first passage time distributions to be computed. This is the main idea of this paper.
  • Y. Narahari, N. Viswanadham, C. R. M. Sundaram, and S. Hanumantha Rao, Integrated analytical models for flexible manufacturing systems. Sadhana, Indian Academy Proceedings in Engineering Sciences, Vol. 15, Parts 4 and 5, December 1990, pp. 331–342.
    • Product form queueing networks are highly tractable but entail certain restrictive assumptions to be made while modeling (for example, no priorities, no passive resources, only FCFS scheduling, only certain special probability distributions, etc.). Stochastic Petri nets, on the other hand, can capture all of these features but can lead to the curse of dimensionality. Combining these two approaches (product form QNs and SPNs) using a decomposition setting enables to make the best of both the worlds. This paper explores this idea in the context of FMS performance modeling.
  • N. Viswanadham, Y. Narahari, and T. L. Johnson, Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE Transactions on Robotics and Automation, Vol. 6, No. 6, December 1990, pp. 713–723.
    • This paper articulated for the first time effective strategies for deadlock handling in highly automated manufacturing plants. Deadlocks represent a highly undesirable phenomenon in distributed, concurrent systems. The paper originates systematic and effective ways of preventing and avoiding deadlocks in complex manufacturing plants through a Petri net modeling approach. The paper’s unique contribution was to establish a conceptual bridge between deadlock research in computer operating systems and deadlock research in automated manufacturing systems. The techniques were applied on a real-world factory of General Electric in Pennsylvania. The paper has an impressive citation record of more than 20 citations in International Journals.
  • Y. Narahari and N. Viswanadham, Performance modeling of flexible manufacturing systems. Journal of IETE, Special Issue on Robotics and Flexible Manufacturing systems, Vol. 35, No. 4, July-August 1989, pp. 221–236.
    • This is a survey article that provides a unifying overview of three approaches to performance modeling of flexible manufacturing systems: Markov models; product form and non-product form queueing network models; and stochastic Petri net models.
  • N. Viswanadham and Y. Narahari, Performance evaluation of automated manufacturing systems using stochastic Petri nets. Information and Decision Technologies, Vol. 14, 1988, pp. 125–142.
    • Until 1986, Petri net modeling of manufacturing systems emphasized qualitative modeling (boundedness, liveness, fairness, reversibility, etc.). This paper was one of the first efforts in looking at quantitative performance analysis using using the GSPN (Generalized Stochastic Petri Nets) formalism of Azmone Marsan, Balbo, and Conti.
  • Y. Narahari and N. Viswanadham, Performance modeling of a fault-tolerant multiprocessor using stochastic Petri nets. Sadhana, Indian Academy Proceedings in Engineering Sciences, Vol. 11, Parts 1 and 2, October 1987, pp. 187–208.
    • FTMP (Fault-Tolerant MultiProcessor) was a research effort at NASA in the early eighties. In this paper, we showed that stochastic Petri nets could be used to capture several non-product form features that arise in the modeling of the performance of this architecture. The result is it leads to exact, accurate, and credible estimation of performance of this interesting fault-tolerant architecture.
  • Y. Narahari and N. Viswanadham, A Petri net approach to the modeling and analysis of flexible manufacturing systems. Annals of Operations Research, Vol. 3, 1985, pp. 449–472.
    • This was my first paper and also one of the most cited papers in the area. The paper proposes a Petri net approach to modeling large scale manufacturing systems using an elegant bottom up approach. The approach is founded on a very simple result that we proved for computing the place invariants of a union of individual Petri net models in terms of the place invariants of the individual nets.