Arrow Research search

Author name cluster

Palash Dey

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.

41 papers
2 author rows

Possible papers

41

AAMAS Conference 2025 Conference Paper

Maximizing Value in Challenge the Champ Tournaments

  • Umang Bhaskar
  • Juhi Chaudhary
  • Palash Dey

A tournament is a method to decide the winner in a competition, and describes the overall sequence in which matches between the players are held. While deciding a worthy winner is the primary goal of a tournament, a close second is to maximize the value generated for the matches played, with value for a match measured either in terms of tickets sold, television viewership, advertising revenue, or other means. Tournament organizers often seed the players — i. e. , decide which matches are played — to increase this value. We study the value maximization objective in a particular tournament format called Challenge the Champ. This is a simple tournament format where an ordering of the players is decided. The first player in this order is the initial champion. The remaining players in order challenge the current champion; if a challenger wins, she replaces the current champion. We model the outcome of a match between two players using a complete directed graph, called a strength graph, with each player represented as a vertex, and the direction of an edge indicating the winner in a match. The value-maximization objective has been recently explored for knockout tournaments when the strength graph is a directed acyclic graph (DAG). We extend the investigation to Challenge the Champ tournaments and general strength graphs. We study different representations of the value of each match, and completely characterize the computational complexity of the problem.

PDF

AAMAS Conference 2025 Conference Paper

Voter Participation Control in Online Polls

  • Koustav De
  • Palash Dey
  • Swagato Sanyal

News outlets, surveyors, and other organizations often conduct polls on social networks to gain insights into public opinion. Such a poll is typically started by someone on a social network who sends it to her friends. If a person participates in the poll, the poll information gets published on her wall, which in turn enables her friends to participate, and the process continues. Eventually, a subset of the population participates in the poll, and the pollster learns the outcome of that poll. We initiate the study of a new but natural type of election control in such online elections. We study how difficult/easy it is to sway the outcome of such polls in one’s favor/against (aka constructive vs destructive) by any malicious influencer who nudges/bribes people for seemingly harmless actions like non-participation. These questions are important from the standpoint of studying the power of resistance of online voting against malicious behavior.

PDF

AAMAS Conference 2024 Conference Paper

Evaluating District-based Election Surveys with Synthetic Dirichlet Likelihood

  • Adway Mitra
  • Palash Dey

In district-based multi-party elections, electors cast votes in their respective districts. In each district, the party with maximum votes wins the corresponding “seat” in the governing body. Election Surveys try to predict the election outcome (vote shares and seat shares of parties) by querying a random sample of electors. However, the survey results are often inconsistent with the actual results, which could be due to multiple reasons. The aim of this work is to estimate a posterior distribution over the possible outcomes of the election, given one or more survey results. This is achieved using a prior distribution over vote shares, election models to simulate the complete election from the vote share, and survey models to simulate survey results from a complete election. The desired posterior distribution over the space of possible outcomes is constructed using Synthetic Dirichlet Likelihoods, whose parameters are estimated from Monte Carlo sampling of elections using the election models. We further show the same approach can also use be used to evaluate the surveys - whether they were biased or not, based on the true outcome once it is known. Our work offers the first-ever probabilistic model to analyze district-based election surveys. We illustrate our approach with extensive experiments on real and simulated data of district-based political elections in India.

PDF

AAMAS Conference 2024 Conference Paper

Optimal Referral Auction Design

  • Rangeet Bhattacharyya
  • Parvik Dave
  • Palash Dey
  • Swaprava Nath

The auction of a single indivisible item is one of the most celebrated problems in mechanism design with transfers. Despite its simplicity, it provides arguably the cleanest and most insightful results in the literature. When the information that the auction is running is available to every participant, Myerson [19] provided a seminal result to characterize the incentive-compatible auctions along with revenue optimality. However, such a result does not hold in an auction on a network, where the information of the auction is spread via the agents, and they need incentives to forward the information. In recent times, a few auctions (e. g. , [12, 16]) were designed that appropriately incentivized the intermediate nodes on the network to promulgate the information to potentially more valuable bidders. In this paper, we provide a Myerson-like characterization of incentivecompatible auctions on a network and show that the currently known auctions fall within this class of randomized auctions. We then consider a special class called the referral auctions that are inspired by the multi-level marketing mechanisms [1, 5, 6] and obtain the structure of a revenue optimal referral auction for i. i. d. bidders.

PDF

AAMAS Conference 2023 Conference Paper

Feature-based Individual Fairness in k-clustering

  • Debajyoti Kar
  • Mert Kosan
  • Debmalya Mandal
  • Sourav Medya
  • Arlei Silva
  • Palash Dey
  • Swagato Sanyal

Ensuring fairness in machine learning algorithms is a challenging and essential task. We consider the problem of clustering a set of points while satisfying fairness constraints. While there have been several attempts to capture group fairness in the 𝑘-clustering problem, fairness at an individual level is not so well-studied. We introduce a new notion of individual fairness in 𝑘-clustering based on features not necessarily used for clustering. The problem is NPhard and does not admit a constant factor approximation. Therefore, we design a randomized heuristic algorithm. Our experimental results against six competing baselines validate that our algorithm produces individually fairer clusters than the fairest baseline.

PDF

AAMAS Conference 2023 Conference Paper

Sampling-Based Winner Prediction in District-Based Elections

  • Debajyoti Kar
  • Palash Dey
  • Swagato Sanyal

In a district-based election, we apply a voting rule 𝑟 to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the election. We present efficient sampling-based algorithms to predict the winner of such districtbased election systems in this paper. When 𝑟 is plurality (i. e. , the candidate receiving a maximum number of votes is declared as the winner) and the margin of victory is known to be at least 𝜀 fraction of the total population, we present an algorithm to predict the winner with probability at least 1−𝛿, whose sample complexity is O 1 𝜀4 log 1 𝜀 log 1 𝛿. We complement this result by proving that any algorithm, from a natural class of algorithms, for predicting the winner in a district-based election when 𝑟 is plurality, must sample at least Ω 1 𝜀4 log 1 𝛿 votes. We then extend this result to any voting rule 𝑟. Loosely speaking, we show that we can predict the winner of a district-based election with an extra overhead of O 1 𝜀2 log 1 𝛿 over the sample complexity of predicting the single-district winner under 𝑟. We further extend our algorithm for the case when the margin of victory is unknown, but we have only two candidates. We then consider the median voting rule when the set of preferences in each district is single-peaked. We show that the winner of such a district-based election can be predicted with probability at least 1 − 𝛿 with O 1 𝜀4 log 1 𝜀 log 1 𝛿 samples.

PDF

AAMAS Conference 2022 Conference Paper

How Hard is Safe Bribery?

  • Neel Karia
  • Faraaz Mallick
  • Palash Dey

Bribery in an election is one of the well-studied control problems in computational social choice. In this paper, we propose and study the safe bribery problem. Here the goal of the briber is to ask the bribed voters to vote in such a way that the briber never prefers the original winner (of the unbribed election) more than the new winner, even if the bribed voters do not fully follow the briber’s advice. Indeed, in many applications of bribery, campaigning for example, the briber often has limited control on whether the bribed voters eventually follow her recommendation and thus it is conceivable that the bribed voters can either partially or fully ignore the briber’s recommendation. We provide a comprehensive complexity theoretic landscape of the safe bribery problem for many common voting rules in this paper.

PDF

AAMAS Conference 2022 Conference Paper

On Parameterized Complexity of Binary Networked Public Goods Game

  • Arnab Maiti
  • Palash Dey

In the Binary Networked Public Goods (BNPG for short) game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP-complete. This casts doubt on predictive power of PSNE in BNPG games. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show W[1]-hardness, XP, and FPT results. Hence, our work significantly improves our understanding of BNPG games where PSNE serves as a reliable solution concept. We finally prove that some graph classes, for example path, cycle, bi-clique, and complete graph, always have a PSNE if the utility function of the players are same.

PDF

IJCAI Conference 2022 Conference Paper

Parameterized Algorithms for Kidney Exchange

  • Arnab Maiti
  • Palash Dey

In kidney exchange programs, multiple patient-donor pairs each of whom are otherwise incompatible, exchange their donors to receive compatible kidneys. The Kidney Exchange problem is typically modelled as a directed graph where every vertex is either an altruistic donor or a pair of patient and donor; directed edges are added from a donor to its compatible patients. The computational task is to find if there exists a collection of disjoint cycles and paths starting from altruistic donor vertices of length at most l_c and l_p respectively that covers at least some specific number t of non-altruistic vertices (patients). We study parameterized algorithms for the kidney exchange problem in this paper. Specifically, we design FPT algorithms parameterized by each of the following parameters: (1) the number of patients who receive kidney, (2) treewidth of the input graph + max{l_p, l_c}, and (3) the number of vertex types in the input graph when l_p <= l_c. We also present interesting algorithmic and hardness results on the kernelization complexity of the problem. Finally, we present an approximation algorithm for an important special case of Kidney Exchange.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Parameterized Algorithms for Kidney Exchange

  • Arnab Maiti
  • Palash Dey

In kidney exchange programs, multiple patient-donor pairs each of whom are otherwise incompatible, exchange their donors to receive compatible kidneys. The Kidney Exchange problem is typically modelled as a directed graph where every vertex is either an altruistic donor or a pair of patient and donor; directed edges are added from a donor to its compatible patients. The computational task is to find if there exists a collection of disjoint cycles and paths starting from altruistic donor vertices of length at most ℓ𝑐 and ℓ𝑝 respectively that covers at least some specific number 𝑡 of nonaltruistic vertices (patients). We study parameterized algorithms for the kidney exchange problem in this paper. Specifically, we design FPT algorithms parameterized by each of the following parameters: (1) the number of patients who receive kidney, (2) treewidth of the input graph + max{ℓ𝑝, ℓ𝑐 }, and (3) the number of vertex types in the input graph when ℓ𝑝 ≤ ℓ𝑐. We also present interesting algorithmic and hardness results on the kernelization complexity of the problem. Finally, we present an approximation algorithm for an important special case of Kidney Exchange.

PDF

AAMAS Conference 2022 Conference Paper

Priced Gerrymandering

  • Palash Dey

We initiate the study of the gerrymandering problem when changing the district of a voter incurs a certain cost. In this problem, the input is a set of voters having votes over a set of alternatives, a graph on the voters, a partition of voters into connected districts, a cost of every voter for changing her district, a budget, and a target winner. We need to compute if the given partition can be modified so that (i) the target alternative wins the resulting election, (ii) the modification is budget feasible, and (iii) every new district is connected. We study four natural variants of the above problem – the graph on the voters being arbitrary vs complete graph (corresponds to removing the connectivity requirement for districts) and the cost of moving every voter being uniform vs non-uniform. We show that all the four problems are NP-complete even under quite restrictive scenarios. Hence, our results show that district based elections are quite resistant under this new kind of electoral attack. We complement our intractability results by showing that two of our problems admit polynomial-time algorithms if the budget or the number of districts is a constant.

PDF

AAMAS Conference 2021 Conference Paper

Network Robustness via Global k -cores

  • Palash Dey
  • Suman Kalyan Maity
  • Sourav Medya
  • Arlei Silva

Network robustness is a measure a network’s ability to survive adversarial attacks. But not all parts of a network are equal. Kcores, which are dense subgraphs, are known to capture some of the key properties of many real-life networks. Therefore, previous work has attempted to model network robustness via the stability of its k-core. However, these approaches account for a single core value and thus fail to encode a global network resilience measure. In this paper, we address this limitation by proposing a novel notion of network resilience that is defined over all cores. In particular, we evaluate the stability of the network under node removals with respect to each node’s initial core. Our goal is to compute robustness via a combinatorial problem: find b most critical nodes to delete such that the number of nodes that fall from their initial cores is maximized. One of our contributions is showing that it is NPhard to achieve any polynomial factor approximation of the given objective. We also present a fine-grained complexity analysis of this problem under the lens of parameterized complexity theory for several natural parameters. Moreover, we show two applications of our notion of robustness: measuring the evolution of species and characterizing networks arising from different domains.

PDF

MFCS Conference 2020 Conference Paper

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

  • Palash Dey
  • Jaikumar Radhakrishnan
  • Santhoshini Velusamy

We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m, n, t) (resp. s_N(m, n, t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m, n, t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2, t ≥ ⌊log n⌋+1. In this work, we improve this bound when the probes are allowed to be superlinear in n, i. e. , when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m, n, t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m, n, t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m, n, 3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i. e. , s_N(m, 2, 3) ≥ Ω(√m).

Details

IJCAI Conference 2020 Conference Paper

On the Complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules

  • Chinmay Sonar
  • Palash Dey
  • Neeldhara Misra

The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) dissatisfaction score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee? , and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for Theta_2^P. Our contribution fills an essential gap in the literature for these important multi-winner rules.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

A Parameterized Perspective on Protecting Elections

  • Palash Dey
  • Neeldhara Misra
  • Swaprava Nath
  • Garima Shakya

We study the parameterized complexity of the optimal defense and optimal attack problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers k_a and k_d corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the optimal defense problem, we want to know if it is possible for the defender to commit to a strategy of defending at most k_d voter groups such that, no matter which k_a voter groups the attacker attacks, the out-come of the election does not change. In the optimal attack problem, we want to know if it is possible for the attacker to commit to a strategy of attacking k_a voter groups such that, no matter which k_d voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one. We show that both the optimal defense problem and the optimal attack problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only3candidates. We also show that the optimal defense problem for every scoring rule and the Condorcet voting rule is W[2]-hard for both the parameters k_a and k_d, while it admits a fixed parameter tractable algorithm parameterized by the combined parameter (ka, kd). The optimal attack problem for every scoring rule and the Condorcet voting rule turns out to be much harder – it is W[1]-hard even for the combined parameter (ka, kd). We propose two greedy algorithms for the OPTIMAL DEFENSE problem and empirically show that they perform effectively on reasonable voting profiles.

PDF Details

AAMAS Conference 2019 Conference Paper

Covert Networks: How Hard is It to Hide?

  • Palash Dey
  • Sourav Medya

Covert networks are social networks that often consist of harmful users. Social Network Analysis (SNA) has played an important role in reducing criminal activities (e. g. , counter terrorism) via detecting the influential users in such networks. There are various popular measures to quantify how influential or central any vertex is in a network. As expected, strategic and influential miscreants in covert networks would try to hide herself and her partners (called leaders) from being detected via these measures by introducing new edges. Waniek et al. [72] show that the corresponding computational problem, called Hiding Leader, is NP-complete for the degree and closeness centrality measures. We study the popular core centrality measure and show that the problem is NP-complete even when the core centrality of every leader is only 3. On the contrary, we prove that the problem becomes polynomial time solvable for the degree centrality measure if the degree of every leader is bounded above by any constant. We then focus on the optimization version of the problem and show that the Hiding Leader problem admits a 2 factor approximation algorithm for the degree centrality measure. We complement it by proving that one cannot hope to have any (2 − ε) factor approximation algorithm for any constant ε > 0 unless there is a ε/2 factor polynomial time algorithm for the Densest k-Subgraph problem which would be considered a significant breakthrough. We empirically establish that our 2 factor approximation algorithm frequently finds out a near optimal solution. On the contrary, for the core centrality measure, we show that the Hiding Leader problem does not admit any (1 − α) lnn factor approximation algorithm for any constant α ∈ (0, 1) unless P = NP even when the core centrality of every leader is only 3. Hence, our work shows that, although classical complexity theoretic framework fails to shed any light on relative difficulty of Hiding Leader for different centrality measures, the problem is significantly “harder” for the core centrality measure than the degree centrality one.

PDF

AAMAS Conference 2019 Conference Paper

Local Distance Restricted Bribery in Voting

  • Palash Dey

Studying complexity of various bribery problems has been one of the main research focus in computational social choice. In all the models of bribery studied so far, the briber has to pay every voter some amount of money depending on what the briber wants the voter to report and the briber has some budget at her disposal. Although these models successfully capture many real world applications, in many other scenarios, the voters may be unwilling to deviate too much from their true preferences. In this paper, we study the computational complexity of the problem of finding a preference profile which is as close to the true preference profile as possible and still achieves the briber’s goal subject to budget constraints. We call this problem Local Distance Restricted $Bribery. We consider three important measures of distances, namely, swap distance, footrule distance, and maximum displacement distance, and resolve the complexity of the local distance restricted bribery problem for many common voting rules.

PDF

AAMAS Conference 2019 Conference Paper

Testing Preferential Domains using Sampling

  • Palash Dey
  • Swaprava Nath
  • Garima Shakya

A preferential domain is a collection of sets of preferences which are linear orders over a set of alternatives. These domains have been studied extensively in social choice theory due to both its practical importance and theoretical elegance. Examples of some extensively studied preferential domains include single peaked, single crossing, Euclidean, etc. In this paper, we study the sample complexity of testing whether a given preference profile is close to some specific domain. We consider two notions of closeness: (a) closeness via preferences, and (b) closeness via alternatives. We further explore the effect of assuming that the outlier preferences/alternatives to be random (instead of arbitrary) on the sample complexity of the testing problem. In most cases, we show that the above testing problem can be solved with high probability for all commonly used domains by observing only a small number of samples (independent of the number of preferences, n, and often the number of alternatives, m). In the remaining few cases, we prove either impossibility results or Ω(n) lower bound on the sample complexity. We complement our theoretical findings with extensive simulations to figure out the actual constant factors of our asymptotic sample complexity bounds.

PDF

AAAI Conference 2018 Conference Paper

Manipulative Elicitation — A New Attack on Elections with Incomplete Preferences

  • Palash Dey

Lu and Boutilier (2011) proposed a novel approach based on “minimax regret” to use classical score based voting rules in the setting where preferences can be any partial (instead of complete) orders over the set of alternatives. We show here that such an approach is vulnerable to a new kind of manipulation which was not present in the classical (where preferences are complete orders) world of voting. We call this attack “manipulative elicitation. ” More specifically, it may be possible to (partially) elicit the preferences of the agents in a way that makes some distinguished alternative win the election who may not be a winner if we elicit every preference completely. More alarmingly, we show that the related computational task is polynomial time solvable for a large class of voting rules which includes all scoring rules, maximin, Copelandα for every α ∈ [0, 1], simplified Bucklin voting rules, etc. We then show that introducing a parameter per pair of alternatives which specifies the minimum number of partial preferences where this pair of alternatives must be comparable makes the related computational task of manipulative elicitation NP-complete for all common voting rules including a class of scoring rules which includes the plurality, k-approval, k-veto, veto, and Borda voting rules, maximin, Copelandα for every α ∈ [0, 1], and simplified Bucklin voting rules. Hence, in this work, we discover a fundamental vulnerability in using minimax regret based approach in partial preferential setting and propose a novel way to tackle it.

PDF Details

MFCS Conference 2017 Conference Paper

On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

  • Palash Dey
  • Neeldhara Misra

We consider election scenarios with incomplete information, a situation that arises often in practice. There are several models of incomplete information and accordingly, different notions of outcomes of such elections. In one well-studied model of incompleteness, the votes are given by partial orders over the candidates. In this context we can frame the problem of finding a possible winner, which involves determining whether a given candidate wins in at least one completion of a given set of partial votes for a specific voting rule. The Possible Winner problem is well-known to be NP-Complete in general, and it is in fact known to be NP-Complete for several voting rules where the number of undetermined pairs in every vote is bounded only by some constant. In this paper, we address the question of determining precisely the smallest number of undetermined pairs for which the Possible Winner problem remains NP-Complete. In particular, we find the exact values of t for which the Possible Winner problem transitions to being NP-Complete from being in P, where t is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad subclass of scoring rules which includes all the commonly used scoring rules (such as plurality, veto, Borda, and k-approval), Copeland^\alpha for every \alpha in [0, 1], maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the Possible Winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates.

Details

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

Proportional Representation in Vote Streams

  • Palash Dey
  • Nimrod Talmon
  • Otniel van Handel

We consider elections where the voters come one at a time, in a streaming fashion, and devise space-efficient algorithms which identify an approximate winning committee with respect to common multiwinner proportional representation voting rules; specifically, we consider the Approval-based and the Borda-based variants of both the Chamberlin– Courant rule and the Monroe rule. We complement our algorithms with lower bounds. Somewhat surprisingly, our results imply that, using space which does not depend on the number of voters it is possible to efficiently identify an approximate representative committee of fixed size over vote streams with huge number of voters. CCS Concepts •Computing methodologies → Multi-agent systems; •Theory of computation → Streaming, sublinear and near linear time algorithms;

PDF

AAAI Conference 2017 Conference Paper

Query Complexity of Tournament Solutions

  • Palash Dey

A directed graph where there is exactly one edge between every pair of vertices is called a tournament. Finding the “best” set of vertices of a tournament is a well studied problem in social choice theory. A tournament solution takes a tournament as input and outputs a subset of vertices of the input tournament. However, in many applications, for example, choosing the best set of drugs from a given set of drugs, the edges of the tournament are given only implicitly and knowing the orientation of an edge is costly. In such scenarios, we would like to know the best set of vertices (according to some tournament solution) by “querying” as few edges as possible. We, in this paper, precisely study this problem for commonly used tournament solutions: given an oracle access to the edges of a tournament T, find f(T ) by querying as few edges as possible, for a tournament solution f. We first show that the set of Condorcet non-losers in a tournament can be found by querying 2n−⌊log n⌋−2 edges only and this is tight in the sense that every algorithm for finding the set of Condorcet non-losers needs to query at least 2n−⌊log n⌋−2 edges in the worst case, where n is the number of vertices in the input tournament. We then move on to study other popular tournament solutions and show that any algorithm for finding the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, the Banks set, and the top cycle must query Ω(n2 ) edges in the worst case. On the positive side, we are able to circumvent our strong query complexity lower bound results by proving that, if the size of the top cycle of the input tournament is at most k, then we can find all the tournament solutions mentioned above by querying O(nk + n log n/log(1−1/k)) edges only.

PDF Details

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

IJCAI Conference 2016 Conference Paper

Elicitation for Preferences Single Peaked on Trees

  • Palash Dey
  • Neeldhara Misra

Eliciting preferences of a set of agents over a set of items is a problem of fundamental interest in artificial intelligence in general and social choice theory in particular. Prior works on preference elicitation focus on unrestricted domain and the domain of single peaked preferences and show that the preferences in single peaked domain can be elicited by much less number of queries compared to unrestricted domain. We extend this line of research and study preference elicitation for single peaked preferences on trees which is a strict superset of the domain of single peaked preferences. We show that the query complexity crucially depends on the number of leaves, the path cover number, and the distance from path of the underlying single peaked tree, whereas the other natural parameters like maximum degree, diameter, pathwidth do not play any direct role in determining query complexity. We then investigate the query complexity for finding a weak Condorcet winner for preferences single peaked on a tree and show that this task has much less query complexity than preference elicitation. Here again we observe that the number of leaves in the underlying single peaked tree and the path cover number of the tree influence the query complexity of the problem.

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 2016 Conference Paper

Preference Elicitation for Single Crossing Domain

  • Palash Dey
  • Neeldhara Misra

Eliciting the preferences of a set of agents over a set of alternatives is a problem of fundamental importance in social choice theory. Prior work on this problem has studied the query complexity of preference elicitation for the unrestricted domain and for the domain of single peaked preferences. In this paper, we consider the domain of single crossing preference profiles and study the query complexity of preference elicitation under various settings. We consider two distinct situations: when an ordering of the voters with respect to which the profile is single crossing is known versus when it is unknown. We also consider random and sequential access models. The main contribution of our work is to provide polynomial time algorithms with low query complexity for preference elicitation in all the above cases. Further, we show that the query complexities of our algorithms are optimal up to constant factors for all but one of the above cases.

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