My interests include investigating the role of game theory, mechanism design, and machine learning in E-commerce applications like crowdsourcing, social networks and prediction markets. My interests also involve social network analysis involving the study of network formation models and also investigation of processes like influence propagation/limitation, virus inoculation, etc
Strategic Network Formation with Localized Payoffs Rohith D. Vallam, C. A. Subramanian, Ramasuri Narayanam, Y. Narahari, and Srinath Narasimha. Studies in Microeconomics, Vol 2(1), pp 63-119, 2014. [abstract] [PDF]
In this investigation, we analyze a network formation game in a strategic setting where pay-offs of individuals depend only on their immediate neighbourhood. These localized pay-offs incorporate the social capital emanating from bridging positions that nodes hold in the network. Using this simple and novel model of network formation, our study explores the structure of networks that form, satisfying pairwise stability or efficiency or both. We derive sufficient conditions for the pairwise stability of several interesting network structures. We characterize topologies of efficient networks by drawing upon classical results from extremal graph theory and discover that the Turan graph (or the complete equi-bipartite network) emerges as the unique efficient network under many configurations of parameters. We examine the trade-offs between topologies of pairwise stable networks and efficient networks using the notion of price of stability. Interestingly, we find that price of stability is equal to 1 for almost all configurations of parameters in the proposed model; and for the rest of the configurations, we obtain a lower bound of 0.5. This leads to another key insight of this article: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized pay-offs. We study the dynamics of the proposed model by designing a simple myopic best response updating rule and implementing it on a customized network formation testbed.
A Non-Cooperative Game-theoretic Approach to Channel Assignment in Multi-Radio Wireless Networks Rohith D Vallam, Arun A Kanagasabapathy, C Siva Ram Murthy Wireless Networks, Volume 17, Number 2, Pages 411-435, February 2011, DOI=http://dx.doi.org/10.1007/s11276-010-0288-5 [abstract] [PDF]
Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.
Conference
A Stackelberg game approach for incentivizing participation in online educational forums with heterogeneous student population Rohith Dwarakanath Vallam, Priyanka Bhatt, Debmalya Mandal, Y. Narahari Proceedings of 29th AAAI Conference on Artificial Intelligence (AAAI 2015), Austin, Texas, USA, To Appear
[abstract] [PDF]
Increased interest in web-based education has spurred the proliferation of online learning environments.
However, these platforms suffer from high dropout rates due to lack of sustained motivation among the students taking the course. In an effort to address this problem, we propose an incentive-based, instructor-driven approach to orchestrate the interactions in online educational forums (OEFs). Our approach takes into account the heterogeneity in skills among the students as well as the limited budget available to the instructor. We first analytically model OEFs in a non-strategic setting using ideas from lumpable continuous time Markov chains and compute expected aggregate transient net-rewards for the instructor and the students. We next consider a strategic setting where we use the rewards computed above to set up a mixed-integer linear program which views an OEF as a single-leader-multiple-followers Stackelberg game and recommends an optimal plan to the instructor for maximizing student participation. Our experimental results reveal several interesting phenomena including a striking non-monotonicity in the level of participation of students vis-a-vis the instructor's arrival rate.
Topologies of stable strategic networks with localized payoffs Rohith Dwarakanath Vallam, C. A. Subramanian, Y. Narahari, Ramasuri Narayanam, Srinath Narasimha Proceedings of 9th IEEE International Conference on Automation Science and Engineering (CASE'13), Madison, Wisconsin, USA, Pages 279-286, May 2013, DOI=http://dl.acm.org/citation.cfm?id=2484967
[abstract] [PDF]
There are numerous types of networks in the realworld which involve strategic actors: supply chain networks, logistics networks, company networks, and social networks. In this investigation, we explore the topologies of decentralized networks that will be formed by strategic actors who interact with one another. In particular, we analyze a network formation game in a strategic setting where payoffs of individuals depend only on their immediate neighbourhood. These localized payoffs incorporate the social capital emanating from bridging positions that nodes hold in the network. Using this novel and appealing model of network formation, our study explores the structure of networks that form, satisfying pairwise stability or efficiency or both. We derive sufficient conditions for the pairwise stability of several interesting network structures. We characterize topologies of efficient networks by applying classical results from extremal graph theory and discover that the Tur“an graph (or the complete equi-bipartite network) emerges as the unique efficient network under many configurations of parameters. We examine the tradeoffs between topologies of pairwise stable networks and efficient networks using the notion of price of stability. We identify several parameter configurations where the price of stability is 1 (or at least lower bounded by 0:5) in the proposed model. This leads to another key insight of this paper: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized payoffs. We study the dynamics of the proposed model by designing a simple myopic best response updating rule and implementing it on a customized network formation test-bed.
Eliciting High Quality Feedback from Crowdsourced Tree Networks
using Continuous Scoring Rules
Ratul Ray, Rohith D Vallam, Y. Narahari Proceedings of 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'13), Saint Paul, Minnesota, USA, Pages 844 - 849, August 2013. DOI=http://dx.doi.org/10.1109/CoASE.2013.6654013.
[abstract] [PDF]
Eliciting accurate information on any object (perhaps a new product or service or person) using the wisdom of a crowd of individuals utilizing web-based platforms such as social networks is an important and interesting problem. Peer-prediction method is one of the known efforts in this direction but is limited to a single level of participating nodes. We non-trivially generalize the peer-prediction mechanism to the setting of a tree network of participating nodes that would get formed when the query about the object originates at a root node and propagates to nodes in a social network through forwarding. The feedback provided by the participating nodes must be aggregated hierarchically to generate a high quality answer at the root level. In the proposed tree-based peer-prediction mechanism, we use proper scoring rules for continuous distributions and prove that honest reporting is a Nash Equilibrium when prior probabilities are common knowledge in the tree and the observations made by the sibling nodes are
stochastically relevant. To compute payments, we explore the logarithmic, quadratic, and spherical scoring rules using techniques from complex analysis. Through detailed simulations, we obtain several insights including the relationship between the budget of the mechanism designer and the quality of answer generated at the root node.
Modelling Co-operative MAC Layer Misbehaviour in IEEE 802.11 Ad Hoc Networks with Heterogeneous Loads. Rohith D Vallam, A Antony Franklin , C Siva Ram Murthy Proceedings of 6th International Symposium on Modeling and
Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'08), Berlin, Germany.
Pages 197-206, April 2008. DOI= http://dx.doi.org/10.1109/WIOPT.2008.4586065. [abstract] [PDF]
Misbehaviour due to back-off distribution manipulation has been one of the significant problems faced in IEEE 802.11 wireless ad hoc networks which has been explored recently by the research community. In addition, collusion between misbehaving nodes adds another dimension to this security problem. We examine this problem in a three-node network scenario wherein two nodes are assumed to be malicious colluding adversaries causing unfair channel access to the other legitimate node. The misbehaving nodes, through back-off manipulation, will try to minimize the channel access share got by the legitimate node and at the same time maximize the detection delay to detect such an attack. We explore this problem and its solution, analytically, in a non-saturated setting, by modelling a single IEEE 802.11 node as a discrete time Markov chain (DTMC) and suggest a measure for evaluating fairness in the network. We then propose an attacker-detector non-linear optimization model through which the joint optimal attacker distribution is evaluated by applying results from the area of variational calculus. We finally use the sequential probability ratio test (SPRT) for estimating the average number of samples for detecting colluding adversaries in the network. We validate all the models using MATLAB and verify the model results by sampling values from the evaluated optimal attacker distribution using a robust statistical library called UNU.RAN.
Topics in Game Theory - Repeated Games and Subgame Perfect Equilibrium,
Extensive Form Games, Evolutionary Stable Strategies, Basic Mechanism Design Concepts.
Design and Analysis of Algorithms - Network Flow Algorithms, Randomized Algorithms,
Some Problems in Combinatorial Geometry like Convex Hull, etc.
Real Analysis - Basic Topological Concepts, Calculus of Single/Several Variables.
Game Theory - Nash Equilibrium Computation, Correlated Equilibrium, Concepts like Core,
Shapley value, Bayesian Games, Mechanism Design Concepts - Incentive Compatibility
and some fundamental Impossibility theorems like Gibbard-Satterthwaite theorem, etc.
Computational Methods of Optimization - First/Second Order Conditions for Local Extrema,
Conjugate Gradient, Steepest Descent, Newton/Quasi-Newton methods to Solve
Unconstrained Optimization Problems, Constrained Optimization - KKT conditions,
Linear Programming - Simplex method and its analytical foundations.
Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. The following is IEEE's copyright notice; other publishers have similar ones.
IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therin are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of the works published in IEEE publications in other works must be obtained from the IEEE.