BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Palash Dey

Palash Dey appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputer Science and Game TheoryMultiagent SystemsArtificial IntelligenceComputational Complexitycs.CYSocial and Information NetworksDatabasesDiscrete Mathematicsecon.GNNetworking and Internet Architectureq-fin.EC

Catalog footprint

What is connected

18works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2025arXiv

Fair Distribution of Digital Payments: Balancing Transaction Flows for Regulatory Compliance

The concentration of digital payment transactions in just two UPI apps like PhonePe and Google Pay has raised concerns of duopoly in India s digital financial ecosystem. To address this, the National Payments Corporation of India (NPCI) has mandated that no single UPI app should exceed 30 percent of total transaction volume. Enforcing this cap, however, poses a significant computational challenge: how to redistribute user transactions across apps without causing widespread user inconvenience while maintaining capacity limits? In this paper, we formalize this problem as the Minimum Edge Activation Flow (MEAF) problem on a bipartite network of users and apps, where activating an edge corresponds to a new app installation. The objective is to ensure a feasible flow respecting app capacities while minimizing additional activations. We further prove that Minimum Edge Activation Flow is NP-Complete. To address the computational challenge, we propose scalable heuristics, named Decoupled Two-Stage Allocation Strategy (DTAS), that exploit flow structure and capacity reuse. Experiments on large semi-synthetic transaction network data show that DTAS finds solutions close to the optimal ILP within seconds, offering a fast and practical way to enforce transaction caps fairly and efficiently.

0 citations0 reviewsNo code linkedOpen access
preprint2025arXiv

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds

The kidney exchange mechanism allows many patient-donor pairs who are otherwise incompatible with each other to come together and exchange kidneys along a cycle. However, due to infrastructure and legal constraints, kidney exchange can only be performed in small cycles in practice. In reality, there are also some altruistic donors who do not have any paired patients. This allows us to also perform kidney exchange along paths that start from some altruistic donor. Unfortunately, the computational task is NP-complete. To overcome this computational barrier, an important line of research focuses on designing faster algorithms, both exact and using the framework of parameterized complexity. The standard parameter for the kidney exchange problem is the number $t$ of patients that receive a healthy kidney. The current fastest known deterministic FPT algorithm for this problem, parameterized by $t$, is $O^\star\left(14^t\right)$. In this work, we improve this by presenting a deterministic FPT algorithm that runs in time $O^\star\left((4e)^t\right)\approx O^\star\left(10.88^t\right)$. This problem is also known to be W[1]-hard parameterized by the treewidth of the underlying undirected graph. A natural question here is whether the kidney exchange problem admits an FPT algorithm parameterized by the pathwidth of the underlying undirected graph. We answer this negatively in this paper by proving that this problem is W[1]-hard parameterized by the pathwidth of the underlying undirected graph. We also present some parameterized intractability results improving the current understanding of the problem under the framework of parameterized complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

On Binary Networked Public Goods Game with Altruism

In the classical Binary Networked Public Goods (BNPG) game, a player can either invest in a public project or decide not to invest. Based on the decisions of all the players, each player receives a reward as per his/her utility function. However, classical models of BNPG game do not consider altruism which players often exhibit and can significantly affect equilibrium behavior. Yu et al. (2021) extended the classical BNPG game to capture the altruistic aspect of the players. We, in this paper, first study the problem of deciding the existence of a Pure Strategy Nash Equilibrium (PSNE) in a BNPG game with altruism. This problem is already known to be NP-Complete. We complement this hardness result by showing that the problem admits efficient algorithms when the input network is either a tree or a complete graph. We further study the Altruistic Network Modification problem, where the task is to compute if a target strategy profile can be made a PSNE by adding or deleting a few edges. This problem is also known to be NP-Complete. We strengthen this hardness result by exhibiting intractability results even for trees. A perhaps surprising finding of our work is that the above problem remains NP-Hard even for bounded degree graphs when the altruism network is undirected but becomes polynomial-time solvable when the altruism network is directed. We also show some results on computing an MSNE and some parameterized complexity results. In summary, our results show that it is much easier to predict how the players in a BNPG game will behave compared to how the players in a BNPG game can be made to behave in a desirable way.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sampling-Based Winner Prediction in District-Based Elections

In a district-based election, we apply a voting rule $r$ 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 district-based election systems in this paper. When $r$ is plurality and the margin of victory is known to be at least $\varepsilon$ fraction of the total population, we present an algorithm to predict the winner. The sample complexity of our algorithm is $\mathcal{O}\left(\frac{1}{\varepsilon^4}\log \frac{1}{\varepsilon}\log\frac{1}δ\right)$. 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 $r$ is plurality, must sample at least $Ω\left(\frac{1}{\varepsilon^4}\log\frac{1}δ\right)$ votes. We then extend this result to any voting rule $r$. Loosely speaking, we show that we can predict the winner of a district-based election with an extra overhead of $\mathcal{O}\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\right)$ over the sample complexity of predicting the single-district winner under $r$. 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 a district-based election can be predicted with $\mathcal{O}\left(\frac{1}{\varepsilon^4}\log\frac{1}{\varepsilon}\log\frac{1}δ\right)$ samples even when the harmonious order in different districts can be different and even unknown. Finally, we also show some results for estimating the margin of victory of a district-based election within both additive and multiplicative error bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Manipulating Node Similarity Measures in Networks

Node similarity measures quantify how similar a pair of nodes are in a network. These similarity measures turn out to be an important fundamental tool for many real world applications such as link prediction in networks, recommender systems etc. An important class of similarity measures are local similarity measures. Two nodes are considered similar under local similarity measures if they have large overlap between their neighboring set of nodes. Manipulating node similarity measures via removing edges is an important problem. This type of manipulation, for example, hinders effectiveness of link prediction in terrorists networks. Fortunately, all the popular computational problems formulated around manipulating similarity measures turn out to be NP-hard. We, in this paper, provide fine grained complexity results of these problems through the lens of parameterized complexity. In particular, we show that some of these problems are fixed parameter tractable (FPT) with respect to various natural parameters whereas other problems remain intractable W[1]-hard and W[2]-hard in particular). Finally we show the effectiveness of our proposed FPT algorithms on real world datasets as well as synthetic networks generated using Barabasi-Albert and Erdos-Renyi models.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

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

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) 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 $Θ_{2}^{P}$. We also demonstrate efficient algorithms for the second problem when the input consists of single-peaked rankings. Our contribution fills an essential gap in the literature for these important multi-winner rules.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

We give the first optimal bounds for returning the $\ell_1$-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of $m$ items in $\{1, 2, \dots, n\}$ and parameters $0 < ε< ϕ\leq 1$, let $f_i$ denote the frequency of item $i$, i.e., the number of times item $i$ occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items $i$ for which $f_i \geq ϕm$, returns no items $j$ for which $f_j \leq (ϕ-ε)m$, and returns approximations $\tilde{f}_i$ with $|\tilde{f}_i - f_i| \leq εm$ for each item $i$ that it returns. Our algorithm uses $O(ε^{-1} \logϕ^{-1} + ϕ^{-1} \log n + \log \log m)$ bits of space, processes each stream update in $O(1)$ worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive $εm$ error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of $\ell_1$-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Elicitation for Preferences Single Peaked on Trees

In multiagent systems, we often have a set of agents each of which have a preference ordering over a set of items and one would like to know these preference orderings for various tasks, for example, data analysis, preference aggregation, voting etc. However, we often have a large number of items which makes it impractical to ask the agents for their complete preference ordering. In such scenarios, we usually elicit these agents' preferences by asking (a hopefully small number of) comparison queries --- asking an agent to compare two items. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

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, $k$-approval, and so on), Copeland$^α$ for every $α\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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Preference Elicitation For Single Crossing Domain

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 different access models: when the votes can be accessed at random, as opposed to when they are coming in a pre-defined sequence. In the sequential access model, we distinguish two cases when the ordering is known: the first is that sequence in which the votes appear is also a single-crossing order, versus when it is not. The main contribution of our work is to provide polynomial time algorithms with low query complexity for preference elicitation in all the above six cases. Further, we show that the query complexities of our algorithms are optimal up to constant factors for all but one of the above six cases. We then present preference elicitation algorithms for profiles which are close to being single crossing under various notions of closeness, for example, single crossing width, minimum number of candidates | voters whose deletion makes a profile single crossing.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Sample Complexity for Winner Prediction in Elections

Predicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the preferences of all the voters in a typical prediction scenario, a common algorithm used for winner prediction is to run the election on a small sample of randomly chosen votes and output the winner as the prediction. We analyze the performance of this algorithm for many common voting rules. More formally, we introduce the $(ε, δ)$-winner determination problem, where given an election on $n$ voters and $m$ candidates in which the margin of victory is at least $εn$ votes, the goal is to determine the winner with probability at least $1-δ$. The margin of victory of an election is the smallest number of votes that need to be modified in order to change the election winner. We show interesting lower and upper bounds on the number of samples needed to solve the $(ε, δ)$-winner determination problem for many common voting rules, including scoring rules, approval, maximin, Copeland, Bucklin, plurality with runoff, and single transferable vote. Moreover, the lower and upper bounds match for many common voting rules in a wide range of practically appealing scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymptotic Collusion-Proofness of Voting Rules: The Case of Large Number of Candidates

Classical results in voting theory show that strategic manipulation by voters is inevitable if a voting rule simultaneously satisfy certain desirable properties. Motivated by this, we study the relevant question of how often a voting rule is manipulable. It is well known that elections with a large number of voters are rarely manipulable under impartial culture (IC) assumption. However, the manipulability of voting rules when the number of candidates is large has hardly been addressed in the literature and our paper focuses on this problem. First, we propose two properties (1) asymptotic strategy-proofness and (2) asymptotic collusion-proofness, with respect to new voters, which makes the two notions more relevant from the perspective of computational problem of manipulation. In addition to IC, we explore a new culture of society where all score vectors of the candidates are equally likely. This new notion has its motivation in computational social choice and we call it impartial scores culture (ISC) assumption. We study asymptotic strategy-proofness and asymptotic collusion-proofness for plurality, veto, $k$-approval, and Borda voting rules under IC as well as ISC assumptions. Specifically, we prove bounds for the fraction of manipulable profiles when the number of candidates is large. Our results show that the size of the coalition and the tie-breaking rule play a crucial role in determining whether or not a voting rule satisfies the above two properties.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Detecting Possible Manipulators in Elections

Manipulation is a problem of fundamental importance in the context of voting in which the voters exercise their votes strategically instead of voting honestly to prevent selection of an alternative that is less preferred. The Gibbard-Satterthwaite theorem shows that there is no strategy-proof voting rule that simultaneously satisfies certain combinations of desirable properties. Researchers have attempted to get around the impossibility results in several ways such as domain restriction and computational hardness of manipulation. However these approaches have been shown to have limitations. Since prevention of manipulation seems to be elusive, an interesting research direction therefore is detection of manipulation. Motivated by this, we initiate the study of detection of possible manipulators in an election. We formulate two pertinent computational problems - Coalitional Possible Manipulators (CPM) and Coalitional Possible Manipulators given Winner (CPMW), where a suspect group of voters is provided as input to compute whether they can be a potential coalition of possible manipulators. In the absence of any suspect group, we formulate two more computational problems namely Coalitional Possible Manipulators Search (CPMS), and Coalitional Possible Manipulators Search given Winner (CPMSW). We provide polynomial time algorithms for these problems, for several popular voting rules. For a few other voting rules, we show that these problems are in NP-complete. We observe that detecting manipulation maybe easy even when manipulation is hard, as seen for example, in the case of the Borda voting rule.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Estimating the Margin of Victory of an Election using Sampling

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 \textsc{$(c, ε, δ)$--Margin of Victory} problem, where given an election $\mathcal{E}$ on $n$ voters, the goal is to estimate the margin of victory $M(\mathcal{E})$ of $\mathcal{E}$ within an additive factor of $c MoV(\mathcal{E})+εn$. We study the \textsc{$(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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fishing out Winners from Vote Streams

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined by popular voting rules. As we show, finding the exact winner requires storing essentially all the votes. So, we focus on the problem of finding an {\em $\eps$-winner}, a candidate who could win by a change of at most $\eps$ fraction of the votes. We show non-trivial upper and lower bounds on the space complexity of $\eps$-winner determination for several voting rules, including $k$-approval, $k$-veto, scoring rules, approval, maximin, Bucklin, Copeland, and plurality with run off.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting

In the Possible Winner problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the Possible Winner problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge. In this paper, we settle this open question for many common voting rules. We show that the Possible Winner problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that include the Borda voting rule do not admit a polynomial kernel with the number of candidates as the parameter. We show however that the Coalitional Manipulation problem which is an important special case of the Possible Winner problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the Possible Winner problem is harder than the Coalitional Manipulation problem since the Coalitional Manipulation problem admits a polynomial kernel whereas the Possible Winner problem does not admit a polynomial kernel.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Manipulation is Harder with Incomplete Votes

The Coalitional Manipulation (CM) problem has been studied extensively in the literature for many voting rules. The CM problem, however, has been studied only in the complete information setting, that is, when the manipulators know the votes of the non-manipulators. A more realistic scenario is an incomplete information setting where the manipulators do not know the exact votes of the non- manipulators but may have some partial knowledge of the votes. In this paper, we study a setting where the manipulators know a partial order for each voter that is consistent with the vote of that voter. In this setting, we introduce and study two natural computational problems - (1) Weak Manipulation (WM) problem where the manipulators wish to vote in a way that makes their preferred candidate win in at least one extension of the partial votes of the non-manipulators; (2) Strong Manipulation (SM) problem where the manipulators wish to vote in a way that makes their preferred candidate win in all possible extensions of the partial votes of the non-manipulators. We study the computational complexity of the WM and the SM problems for commonly used voting rules such as plurality, veto, k-approval, k-veto, maximin, Copeland, and Bucklin. Our key finding is that, barring a few exceptions, manipulation becomes a significantly harder problem in the setting of incomplete votes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Choosing Committees Based on Approval Votes in the Presence of Outliers

We study the computational complexity of committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outlier consideration makes committee selection problem intractable for approval, net approval, and minisum approval voting rules. We then study parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter, the number of candidates outside the committee), the number of outliers (and its dual parameter, the number of non-outliers). For net approval and minisum approval voting rules, we provide a dichotomous result, resolving the parameterized complexity of this problem for all subsets of five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). For the approval voting rule, we resolve the parameterized complexity of this problem for all subsets of parameters except one. We also study approximation algorithms for this problem. We show that there does not exist any alpha(.) factor approximation algorithm for approval and net approval voting rules, for any computable function alpha(.), unless P=NP. For the minisum voting rule, we provide a pseudopolynomial (1+eps) factor approximation algorithm.

0 citations0 reviewsNo code linkedOpen access