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 traﬃc is a challenging
problem facing advertisers in sponsored search auctions. Another key requirement in
sponsored search auctions is stability of the bid proﬁle, 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 proﬁles 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.
T.S. Chandrashekar and Y. Narahari.
A Cooperative Game Approach to the Design
of Coordination Protocols for Formation of Procurement Networks.
Communicated.
Procurement network formation is of crucial importance to any global company.
Since the suppliers in a procurement network can be expected to act strategically,
game theoretic models are quite effective in modeling the problem. The model used
in this paper is a surplus maximizing network flow cooperative game where each
edge is owned by a rational, capacity constrained, utility maximizing agent.
The buyer is also a part of this network and has a certain demand. The agents
in the network have to coordiante themselves to meet this demand and the surplus
generated is to be shared among the agents. We first investigate conditions under which
the core of the underlying game is non-empty. We also construct an extensive form
game that implements the chosen core allocation.
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 Managemen
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.