Arrow Research search

Author name cluster

Y. Narahari

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
1 author row

Possible papers

21

AAMAS Conference 2025 Conference Paper

Regret Guarantees for a UCB-based Algorithm for Volatile Combinatorial Bandits

  • Abhishek Kumar
  • Andra Siva Sai Teja
  • Ganesh Ghalme
  • Sujit Gujar
  • Y. Narahari

We study the combinatorial multi-armed bandit (MAB) problem with an additional constraint that an arbitrary subset of arms is unavailable at any given time instant. We refer to this setting as a volatile combinatorial MAB setting. The bandit algorithm must pull a subset of arms from the set of available arms to minimize the regret. Under some mild smoothness conditions, we show that the proposed CV-UCB algorithm—a straightforward extension of well-known C-UCB algorithm—achieves a 𝑂(log(𝑇)) instancedependent regret guarantee under a semi-bandit feedback setting. We further show that under some mild restrictions on the range of reward functions, CV-UCB incurs 𝑂( √︁ 𝑇 log(𝑇)) regret, which we call weak instance-independent regret. We further show that the instance-independent regret of 𝑂( 3 √︁ 𝑇2 log(𝑇)) for CV-UCB algorithm, completing the hierarchy of regret guarantees obtained by gradually relaxing the dependence on the instance parameters.

PDF

JMLR Journal 2021 Journal Article

Achieving Fairness in the Stochastic Multi-Armed Bandit Problem

  • Vishakha Patil
  • Ganesh Ghalme
  • Vineet Nair
  • Y. Narahari

We study an interesting variant of the stochastic multi-armed bandit problem, which we call the Fair-MAB problem, where, in addition to the objective of maximizing the sum of expected rewards, the algorithm also needs to ensure that at any time, each arm is pulled at least a pre-specified fraction of times. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, which we call $r$-Regret, that takes into account the above fairness constraints and extends the conventional notion of regret in a natural way. Our primary contribution is to obtain a complete characterization of a class of Fair-MAB algorithms via two parameters: the unfairness tolerance and the learning algorithm used as a black-box. For this class of algorithms, we provide a fairness guarantee that holds uniformly over time, irrespective of the chosen learning algorithm. Further, when the learning algorithm is UCB1, we show that our algorithm achieves constant $r$-Regret for a large enough time horizon. Finally, we analyze the cost of fairness in terms of the conventional notion of regret. We conclude by experimentally validating our theoretical results. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

PDF Details

AAAI Conference 2020 Conference Paper

Achieving Fairness in the Stochastic Multi-Armed Bandit Problem

  • Vishakha Patil
  • Ganesh Ghalme
  • Vineet Nair
  • Y. Narahari

We study an interesting variant of the stochastic multi-armed bandit problem, which we call the FAIR-MAB problem, where, in addition to the objective of maximizing the sum of expected rewards, the algorithm also needs to ensure that at any time, each arm is pulled at least a pre-specified fraction of times. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, which we call r-Regret, that takes into account the above fairness constraints and extends the conventional notion of regret in a natural way. Our primary contribution is to obtain a complete characterization of a class of FAIR-MAB algorithms via two parameters: the unfairness tolerance and the learning algorithm used as a black-box. For this class of algorithms, we provide a fairness guarantee that holds uniformly over time, irrespective of the choice of the learning algorithm. Further, when the learning algorithm is UCB1, we show that our algorithm achieves constant r-Regret for a large enough time horizon. Finally, we analyze the cost of fairness in terms of the conventional notion of regret. We conclude by experimentally validating our theoretical results.

PDF Details

AAMAS Conference 2018 Conference Paper

Design of Coalition Resistant Credit Score Functions for Online Discussion Forums

  • Ganesh Ghalme
  • Sujit Gujar
  • Amleshwar Kumar
  • Shweta Jain
  • Y. Narahari

We consider the problem of designing a robust credit score function in the context of online discussion forums. Credit score function assigns a real-valued credit score to each participant based on activities on the forum. A credit score of a participant quantifies the usefulness of contribution made by her. However, participants can manipulate a credit score function by forming coalitions, i. e. , by strategically awarding upvotes, likes, etc. among a subset of agents to maximize their credit scores. We propose a coalition resistant credit score function which discourages such strategic endorsements. We use community detection algorithms to identify closeknit communities in the graph of interactions and characterize coalition identifying community detection metric. In particular, we show that modularity is coalition identifying and provide theoretical guarantees on modularity based credit score function. Finally, we validate our theoretical findings with simulations on illustrative datasets.

PDF

AAMAS Conference 2017 Conference Paper

Parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers

  • Palash Dey
  • Neeldhara Misra
  • Y. Narahari

Approval ballots provide an opportunity for agents to make a comment about every candidate, without incurring the overhead of determining a full ranking on the set of candidates; they are very natural for many practical settings. We study the computational complexity of the committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outliers render the committee selection problem intractable for approval, net approval, and minisum approval voting rules. We next study the parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter namely the number of candidates outside the committee); and the number of outliers (and its dual parameter namely the number of non-outliers). For approval, net approval, and minisum approval voting rules, we provide a dichotomous result, which resolves the parameterized complexity of this problem for all subsets of the above five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). CCS Concepts •Theory of computation → Analysis of Algorithms and Problem Complexity; •Distributed Artificial Intelligence → Multi-agent Systems;

PDF

AAMAS Conference 2017 Conference Paper

Thompson Sampling Based Mechanisms for Stochastic Multi-Armed Bandit Problems

  • Ganesh Ghalme
  • Shweta Jain
  • Sujit Gujar
  • Y. Narahari

This paper explores Thompson sampling in the context of mechanism design for stochastic multi-armed bandit (MAB) problems. The setting is that of an MAB problem where the reward distribution of each arm consists of a stochastic component as well as a strategic component. Many existing MAB mechanisms use upper confidence bound (UCB) based algorithms for learning the parameters of the reward distribution. The randomized nature of Thompson sampling introduces certain unique, non-trivial challenges for mechanism design, which we address in this paper through a rigorous regret analysis. We first propose a MAB mechanism with deterministic payment rule, namely, TSM-D. We show that in TSM- D, the variance of agent utilities asymptotically approaches zero. However, the game theoretic properties satisfied by TSM-D (incentive compatibility and individual rationality with high probability) are rather weak. As our main contribution, we then propose the mechanism TSM-R, with randomized payment rule, and prove that TSM-R satisfies appropriate, adequate notions of incentive compatibility and individual rationality. For TSM-R, we also establish a theoretical upper bound on the variance in utilities of the agents. We further show, using simulations, that the variance in social welfare incurred by TSM-D or TSM-R is much lower when compared to that of existing UCB based mechanisms. We believe this paper establishes Thompson sampling as an attractive approach to be used in MAB mechanism design.

PDF

AAMAS Conference 2016 Conference Paper

A Deterministic MAB Mechanism for Crowdsourcing with Logarithmic Regret and Immediate Payments

  • Shweta Jain
  • Ganesh Ghalme
  • Satyanath Bhat
  • Sujit Gujar
  • Y. Narahari

We consider a general crowdsourcing setting with strategic workers whose qualities are unknown and design a multiarmed bandit (MAB) mechanism, CrowdUCB, which is deterministic, regret minimizing, and offers immediate payments to the workers. The problem involves sequentially selecting workers to process tasks in order to maximize the social welfare while learning the qualities of the strategic workers (strategic about their costs). Existing MAB mechanisms are either: (a) deterministic which potentially cause significant loss in social welfare, or (b) randomized which typically lead to high variance in payments. CrowdUCB completely addresses the above problems with the following features: (i) offers deterministic payments, (ii) achieves logarithmic regret in social welfare, (iii) renders allocations more effective by allocating blocks of tasks to a worker instead of a single task, and (iv) offers payment to a worker immediately upon completion of an assigned block of tasks. CrowdUCB is a mechanism with learning that learns the qualities of the workers while eliciting their true costs, irrespective of whether or not the workers know their own qualities. We show that CrowdUCB is ex-post individually rational (EPIR) and ex-post incentive compatible (EPIC) when the workers do not know their own qualities and when they update their beliefs in sync with the requester. When the workers know their own qualities, CrowdUCB is EPIR and ε−EPIC where ε is sub-linear in terms of the number of tasks.

PDF

IJCAI Conference 2016 Conference Paper

Complexity of Manipulation with Partial Information in Voting

  • Palash Dey
  • Neeldhara Misra
  • Y. Narahari

The Coalitional Manipulation problem has been studied extensively in the literature for many voting rules. However, most studies have focused on the complete information setting, wherein the manipulators know the votes of the non-manipulators. While this assumption is reasonable for purposes of showing intractability, it is unrealistic for algorithmic considerations. In most real-world scenarios, it is impractical for the manipulators to have accurate knowledge of all the other votes. In this paper, we investigate manipulation with incomplete information. In our framework, the manipulators know a partial order for each voter that is consistent with the true preference of that voter. In this setting, we formulate three natural computational notions of manipulation, namely weak, opportunistic, and strong manipulation. We consider several scenarios for which the traditional manipulation problems are easy (for instance, Borda with a single manipulator). For many of them, the corresponding manipulative questions that we propose turn out to be computationally intractable. Our hardness results often hold even when very little information is missing, or in other words, even when the instances are quite close to the complete information setting. Our overall conclusion is that computational hardness continues to be a valid obstruction to manipulation, in the context of a more realistic model.

PDF Details

AAAI Conference 2016 Conference Paper

Frugal Bribery in Voting

  • Palash Dey
  • Neeldhara Misra
  • Y. Narahari

Bribery in elections is an important problem in computational social choice theory. We introduce and study two important special cases of the bribery problem, namely, FRUGAL- BRIBERY and FRUGAL-$BRIBERY where the briber is frugal in nature. By this, we mean that the briber is only able to influence voters who benefit from the suggestion of the briber. More formally, a voter is vulnerable if the outcome of the election improves according to her own preference when she accepts the suggestion of the briber. In the FRUGAL-BRIBERY problem, the goal is to make a certain candidate win the election by changing only the vulnerable votes. In the FRUGAL- $BRIBERY problem, the vulnerable votes have prices and the goal is to make a certain candidate win the election by changing only the vulnerable votes, subject to a budget constraint. We show that both the FRUGAL-BRIBERY and the FRUGAL- $BRIBERY problems are intractable for many commonly used voting rules for weighted as well as unweighted elections. These intractability results demonstrate that bribery is a hard computational problem, in the sense that several special cases of this problem continue to be computationally intractable. This strengthens the view that bribery, although a possible attack on an election in principle, may be infeasible in practice.

PDF Details

IJCAI Conference 2015 Conference Paper

Estimating the Margin of Victory of an Election Using Sampling

  • Palash Dey
  • Y. Narahari

The margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling etc. In this work, we present efficient sampling based algorithms for estimating the margin of victory of elections. More formally, we introduce the (c, ε, δ)–MARGIN OF VICTORY problem, where given an election E on n voters, the goal is to estimate the margin of victory M(E) of E within an additive factor of cM(E)+εn. We study the (c, ε, δ)–MARGIN OF VICTORY problem for many commonly used voting rules including scoring rules, approval, Bucklin, maximin, and Copelandα. We observe that even for the voting rules for which computing the margin of victory is NP-Hard, there may exist efficient sampling based algorithms, as observed in the cases of maximin and Copelandα voting rules.

PDF Details

AAAI Conference 2014 Conference Paper

A Multiarmed Bandit Incentive Mechanism for Crowdsourcing Demand Response in Smart Grids

  • Shweta Jain
  • Balakrishnan Narayanaswamy
  • Y. Narahari

Demand response is a critical part of renewable integration and energy cost reduction goals across the world. Motivated by the need to reduce costs arising from electricity shortage and renewable energy fluctuations, we propose a novel multiarmed bandit mechanism for demand response (MAB-MDR) which makes monetary offers to strategic consumers who have unknown response characteristics, to incetivize reduction in demand. Our work is inspired by a novel connection we make to crowdsourcing mechanisms. The proposed mechanism incorporates realistic features of the demand response problem including time varying and quadratic cost function. The mechanism marries auctions, that allow users to report their preferences, with online algorithms, that allow distribution companies to learn user-specific parameters. We show that MAB-MDR is dominant strategy incentive compatible, individually rational, and achieves sublinear regret. Such mechanisms can be effectively deployed in smart grids using new information and control architecture innovations and lead to welcome savings in energy costs.

PDF Details

AAAI Conference 2012 Conference Paper

Threats and Trade-Offs in Resource Critical Crowdsourcing Tasks Over Networks

  • Swaprava Nath
  • Pankaj Dayama
  • Dinesh Garg
  • Y. Narahari
  • James Zou

In recent times, crowdsourcing over social networks has emerged as an active tool for complex task execution. In this paper, we address the problem faced by a planner to incentivize agents in the network to execute a task and also help in recruiting other agents for this purpose. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner’s goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We define a set of fairness properties that should be ideally satisfied by a crowdsourcing mechanism. We prove that no mechanism can satisfy all these properties simultaneously. We relax some of these properties and define their approximate counterparts. Under appropriate approximate fairness criteria, we obtain a non-trivial family of payment mechanisms. Moreover, we provide precise characterizations of cost critical and time critical mechanisms.

PDF Details

AAMAS Conference 2011 Conference Paper

Incentive Compatible Influence Maximization in Social Networks and Application to Viral Marketing

  • Mayur Mohite
  • Y. Narahari

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use.

PDF

AAMAS Conference 2008 Conference Paper

Determining Top K Nodes in Social Networks using the Shapley Value

  • Narayanam RamaSuri
  • Y. Narahari

In this paper, we consider the problem of selecting, for any given positive integer k, the top-k nodes in a social network, based on a certain measure appropriate for the social network. This problem is relevant in many settings such as analysis of co-authorship networks, diffusion of information, viral marketing, etc. However, in most situations, this problem turns out to be NP-hard. The existing approaches for solving this problem are based on approximation algorithms and assume that the objective function is sub-modular. In this paper, we propose a novel and intuitive algorithm based on the Shapley value, for efficiently computing an approximate solution to this problem. Our proposed algorithm does not use the sub-modularity of the underlying objective function and hence it is a general approach. We demonstrate the efficacy of the algorithm using a co-authorship data set from e-print arXiv (www. arxiv. org), having 8361 authors.

PDF