• Home
• Recent-Publications
• All Publications
• R&D Projects
• Teaching
• Students
• Others

RECENT PUBLICATIONS

This page lists my representative recent publications. Many of these papers can be downloaded. If you are unable to download any of the papers, please do send email to me and I will be happy to send a softcopy to you.

Pankaj Dayama, Aditya Karnik, and Y. Narahari. Optimal Incentive Timing Strategies for Product Marketing on Social Networks Accepted for Presentation at AAMAS-2011 (Autonomous Agents and Multi Agent Systems), Valencia, Spain June 4–8, 2012.

Swaprava Nath, Onno Zoeter, Y. Narahari, Chris Dance. Dynamic Mechanism Design for Markets with Strategic Resources Proceedings of UAI-2011 (Uncertainty in Artificial Intelligence), Barcelona, Spain, July 2011, pages 539-546.

Mayur Mohite and Y. Narahari. Incentive Compatible Influence Maximization in Social Networks with Application to Viral Marketing. Proceedings of AAMAS-2011 (Autonomous Agents and Multi Agent Systems), Taipei, Taiwan, May 2011, pp.1081-1082.

Premm Raj and Y. Narahari. Influence Limitation in Multi-Campaign Social Networks: A Shapley Value Approach. Proceedings of the Centenary Conference in Electrical Engineering, Indian Institute of Science, December 2011.

Sujit Gujar and Y. Narahari. Redistribution Mechanisms for Assignment of Heterogeneous Objects. Journal of Artificial Intelligence Research. Volume 41, pages 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.

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. A Theory of Mechanism Design for Single Leader Stackelberg Problems. In:   IEEE Transactions on Automation Science and Engineering, Volume 5, Number 3, July 2008, pp. 377-393. (Recipient of the the Best Application paper award of the IEEE Transactions on Automation Science and Engineering for the Year 2008).

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.

Sujit Gujar and Y. Narahari. Redistribution of VCG Payments in Assignment of Heterogeneous Objects. Proceedings of the 4th International Workshop On Internet And Network Economics (WINE), December, Shanghai, China, 2008, Lecture Notes in Computer Science, Pages: 438-445.

In this paper, we seek to design a Groves mechanism for assigning p heterogeneous objects among n competing agents (n > p) with unit demand, satisfying weak budget balance, individual rational- ity, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this prob- lem has been solved by Moulin and Guo and Conitzer. However, it remains an open problem to design such a rebate function when the ob- jects are heterogeneous. We propose a mechanism, HETERO and conjec- ture that HETERO is individually rational and weakly budget balanced. We provide empirical evidence for our conjecture through experimental simulations.

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, pages 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. In:   IEEE Transactions on Automation Science and Engineering , Volume 8, Number 1, pages 130-147, January 2011.

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.

N. Chaitanya and Y. Narahari. Optimal Equilibrium Bidding Strategies for Budget Constrained Bidders in Sponsored Search Auctions. Operational Research: An International Journal, Special Issue on Digital Economy and Electronic Commerce, 2011 (To appear).

Budget optimization (determining an optimal subset of keywords on which to bid subject to a limited budget) 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 is stability of the bid profile, which is usually characterized using the notion of 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. The objective of our work is to come up with a bidding strategy that is optimal for the budget optimization as well as the bid optimization problems and also guarantees convergence to a locally envy free equilibrium. Our approach works with an elegant linear programming formulation.

K. Nagaraj and Y. Narahari Threshold Behavior of Incentives in Social Networks Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM-2010), Toronto, Canada. October 2010.

Devansh Dikshit and Y. Narahari Truthful and Quality Conscious Query Incentive Networks. Proceedings of WINE 2009 (Workshop on Internet and Network Economics), Rome, Italy. December 2009.

Query incentive networks, proposed by Jon Kleinberg and Prabhakar Raghavan in 2005, capture the role of incentives in extracting information from decentralized information networks (such as social networks). Game theoretic models have been formulated and studied for characterizing the dependence of the monetary incentive required to extract the information on various factors such as the network structure, the level of difficulty of the query, required success probability, etc. Our contribution in this paper is to incorporate a practical and important factor, namely, quality of answers, in the monitization of query incentive networks. We propose truthful quality elicitation mechanisms by finding a connection to the brilliant, decades-old work on scoring rules by Nobel Laureate Richard Selten. We also investigate the budget balance properties of the proposed mechanisms.

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, pages 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.

Ramakrishnan Kannan, Dinesh Garg, Karthik Subbian, Y. Narahari. A Nash Bargaining Approach to Retention Enhancing Bid Optimization in Sponsored Search Auctions with Discrete Bids. Fourth Annual IEEE Conference on Automation Science and Engineering (IEEE CASE 2008), Washinton, DC, USA, August 2008, Pages: 1007-1012.

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. In:   International Journal of Operations Research. Special Issue on Game Theory Applications in Operations Research and Management Science. Volume 6, Number 1, 2009, Pages: 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.

S. Kameshwaran and Y. Narahari. Efficient Algorithms for Nonconvex Piecewise Linear Knapsack Problems. In:   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.

T.S. Chandrashekar, Y. Narahari, Charles H. Rosa, Devadatta Kulkarni, Pankaj Dayama, and Jeffrey D. Tew. Auction-Based Mechanisms for Electronic Procurement. In:   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.

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, N. Hemachandra, Nikesh Kumar Srivastava, Datta Kulkarni, and Jeffrey D. Tew. A Bayesian Incentive Compatible Mechanism for Decentralized Supply Chain Formation. In:   International Journal of Operations Research. Special Issue on Game Theory Applications in Operations Research and Management Science. Volume 6, Number 1, 2009, Pages: 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.

Sriram Somanchi, Chaitanya Nittala, and Y. Narahari. A Novel Bid Optimizer for Sponsored Search Auctions based on Cooperative Game Theory. Proceedings of IEEE/WIC/ACM Conference on Intelligent Agent Technologies, Milano, Italy, September 2009.

Ramakrishnan Kannan, Dinesh Garg, Kartik Subbian, and Y. Narahari. Nash Bargaining Based Ad Networks for Sponsored Search Auctions. Proceedings of the IEEE Conference on Commerce and Enterprise Computing (IEEE CEC-2009). Vienna, Austria, July 2009.

Ramasuri Narayanam and Y. Narahari. Design of an Optimal Bayesian Incentive Compatible Broadcast Protocol for Ad-hoc Wireless Networks with Rational Nodes. In:   IEEE Journal on Selected Areas in Communications, Special Issue on Game Theory in Communications Systems, , Volume 26, Number 7, September 2008, Pages: 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.

Devansh Dikshit, Y. Narahari. On a Hybrid Auction Approach to Spectrum Allocation. Working Paper, CoRR abs/0902.3104: (2009) February 2009.

Inspired by the developments in the field of spectrum auctions in the past decade, we have tried to provide a comprehensive framework for the complete end-to-end procedure of spectrum licensing. We have identified the various issues the Governments need to decide upon while designing the licensing procedure and the various options available. We also provide an in depth study of how each of these options would impact the overall procedure along with theoretical and practical results from the past. Our proposal is to combine the best features of two most widely used spectrum auction mechanisms into a novel, hybrid multiple round auction mechanism for spectrum allocation.