Author name cluster

Swaprava Nath

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.

19 papers

2 author rows

AAMAS Conference 2025 Conference Paper

Harmonious Balanced Partitioning of a Network of Agents

Pulkit Agarwal
Harshvardhan Agarwal
Vaibhav Raj
Swaprava Nath

We consider the problem of balanced partitioning, i. e. , dividing 𝑛 agents into 𝑘 groups of almost equal size (⌊𝑛/𝑘⌋ or ⌈𝑛/𝑘⌉), where the agents form a friendship network, ensuring various fairness and efficiency criteria. The utility of an agent is the count of its friends in the same group as itself. When partitions into two groups are considered, we show that approximate envy-freeness related to the maximum degree of the graph can be obtained via a linear-time algorithm for arbitrary graphs. We also show that envy-freeness and core properties can be extended along with Pareto optimality in arbitrary graphs for such partitions. We then concentrate on the case of grid graphs having nodes on the 2D integer lattice, and demonstrate the impossibility of perfect envy-freeness. However, weaker guarantees like envy-freeness up to two friends are achievable for balanced 𝑘-partitions in a computationally efficient manner. We show that certain such balanced partitions belong to an exact and an approximate core when considering balanced 2-partitions.

PDF

AAMAS Conference 2025 Conference Paper

Truthful and Welfare-maximizing Resource Scheduling with Application to Electric Vehicles

Ramsundar Anandanarayanan
Swaprava Nath
Prasant Misra

We consider the problem of scheduling resources with monetary transfers among agents in a setting where multiple outlets can dispense these resources at different rates within fixed time-slots. This problem is motivated by applications such as electric vehicle (EV) charging where energy is the resource and EVs are available within a convenient time window of its owners. The agents’ valuations depend on the contiguous time slots at a given outlet that dispense the resource to them. We show that for monotone and its sub-class of dichotomous valuations, computing the social welfare-maximizing allocation is NP-hard, even if there is only one outlet. For monotone and dichotomous valuations, we provide a randomized 2-approximation mechanism that is truthful in dominant strategies and individually rational for a single outlet and a randomized 𝑂( √︁ |𝑆|)-approximation algorithm with the same properties for multiple outlets (𝑆 is the set of time-slots). However, for single-minded valuations, the welfare maximization problem for multiple outlets is in P. This allows us to use standard mechanisms like VCG to ensure truthfulness and individual rationality.

PDF

ECAI Conference 2024 Conference Paper

A Gale-Shapley View of Unique Stable Marriages

Kartik Gokhale
Amit Kumar Mallik
Ankit Kumar Misra
Swaprava Nath

Stable marriage of a two-sided market with unit demand is a classic problem that arises in many real-world scenarios. In addition, a unique stable marriage in this market simplifies a host of downstream desiderata. In this paper, we explore a new set of sufficient conditions for unique stable matching (USM) under this setup. Unlike other approaches that also address this question using the structure of preference profiles, we use an algorithmic viewpoint and investigate if this question can be answered using the lens of the deferred acceptance (DA) algorithm without actually running the algorithm. Our results yield a set of sufficient conditions for USM (viz. , MP and MR) and show that these are disjoint from the previously known sufficiency conditions like sequential preference and no crossing. We provide a characterization of MP that makes it efficiently verifiable (without using DA), and shows the gap between MP and the entire USM class.

Details

AAMAS Conference 2024 Conference Paper

Charging Electric Vehicles Fairly and Efficiently

Ramsundar Anandanarayanan
Swaprava Nath
Rohit Vaish

Motivated by electric vehicle (EV) charging, we formulate the problem of fair and efficient allocation of a divisible resource among agents that arrive and depart over time and consume the resource at different rates. The agents (EVs) derive utility from the amount of charge gained, which depends on their own charging rate as well as that of the charging outlet. The goal is to allocate charging time at different outlets among the EVs such that the final allocation is envyfree, pareto optimal, and in certain contexts, group-strategyproof. The differences in the charging rates of the outlets and the EVs, and a continuous time-window where the arrivals and departures occur make this a non-trivial combinatorial optimization problem. We show possibilities and impossibilities of achieving a combination of properties such as envy-freeness, pareto optimality, leximin, and group-strategyproofness under different operational settings, e. g. , when the EVs have (dis)similar charging technology, or when there are one or more dissimilar charging outlets. We complement the positive existence results with polynomial-time algorithms.

PDF

AAMAS Conference 2024 Conference Paper

Fair Scheduling of Indivisible Chores

Yatharth Kumar
Sarfaraz Equbal
Rohit Gurjar
Swaprava Nath
Rohit Vaish

We study the problem of fairly assigning a set of discrete tasks (or chores) among a set of agents with additive valuations. Each chore is associated with an arrival time and a deadline, and each agent can perform at most one chore at any given time. The goal is to find a fair and efficient schedule of the chores, where fairness pertains to satisfying envy-freeness up to one chore (EF1) and efficiency pertains to maximality (i. e. , no unallocated chore can be feasibly assigned to any agent). Our main result is a polynomialtime algorithm for computing an EF1 and maximal schedule for two agents under monotone valuations when the conflict constraints constitute an arbitrary interval graph. The algorithm uses a coloring technique in interval graphs that may be of independent interest. For an arbitrary number of agents, we provide an algorithm for finding a fair schedule under identical dichotomous valuations when the constraints constitute a path graph. We also rule out the existence of schedules satisfying stronger fairness and efficiency properties, including envy-freeness up to any chore (EFX) together with maximality and EF1 together with Pareto optimality.

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

JAIR Journal 2024 Journal Article

Removing Bias and Incentivizing Precision in Peer-grading

Anujit Chakraborty
Jatin Jindal
Swaprava Nath

Most peer-evaluation practices rely on the evaluator’s goodwill and model them as potentially noisy evaluators. But what if graders are competitive, i.e., enjoy higher utility when their peers get lower scores? We model the setting as a multi-agent incentive design problem and propose a new mechanism, PEQA, that incentivizes these agents (peer-graders) through a score-assignment rule and a grading performance score. PEQA is designed in such a way that it makes grader-bias irrelevant and ensures grader-utility to be monotonically increasing with the grading-precision, despite competitiveness. When grading is costly and costs are private information of the individual graders, a modified version of PEQA implements the socially optimal grading-choices in equilibrium. Data from our classroom experiments is consistent with our theoretical assumptions and show that PEQA outperforms the popular median mechanism, which is used in several massive open online courses (MOOCs).

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Disentangling Societal Inequality from Model Biases: Gender Inequality in Divorce Court Proceedings

Sujan Dutta
Parth Srivastava
Vaishnavi Solunke
Swaprava Nath
Ashiqur R. KhudaBukhsh

Divorce is the legal dissolution of a marriage by a court. Since this is usually an unpleasant outcome of a marital union, each party may have reasons to call the decision to quit which is generally documented in detail in the court proceedings. Via a substantial corpus of 17, 306 court proceedings, this paper investigates gender inequality through the lens of divorce court proceedings. To our knowledge, this is the first-ever large-scale computational analysis of gender inequality in Indian divorce, a taboo-topic for ages. While emerging data sources (e. g. , public court records made available on the web) on sensitive societal issues hold promise in aiding social science research, biases present in cutting-edge natural language processing (NLP) methods may interfere with or affect such studies. A thorough analysis of potential gaps and limitations present in extant NLP resources is thus of paramount importance. In this paper, on the methodological side, we demonstrate that existing NLP resources required several non-trivial modifications to quantify societal inequalities. On the substantive side, we find that while a large number of court cases perhaps suggest changing norms in India where women are increasingly challenging patriarchy, AI-powered analyses of these court proceedings indicate striking gender inequality with women often subjected to domestic violence.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Social Distancing via Social Scheduling

Deepesh Kumar Lall
Garima Shakya
Swaprava Nath

Motivated by the need for social distancing during a pandemic, we consider an approach to schedule the visitors of a facility (e. g. , a general store). Our algorithms take input from the citizens and schedule the store’s discrete time-slots based on their importance in visiting the facility. We consider indivisible customer job requests that take single or multiple slots to complete. The salient properties of our approach are: it (a) ensures social distancing by ensuring a maximum population in a given time-slot at the facility, (b) prioritizes individuals based on the importance of the jobs, (c) maintains truthfulness of the reported importance by adding a cooling-off period after their allocated time-slot, during which the individual cannot re-access the same facility, (d) guarantees voluntary participation of the citizens, and yet (e) is computationally tractable. The mechanisms we propose are prior-free. The problem is NP-complete for indivisible multi-slot jobs, and we provide a polynomial-time mechanism that is truthful, individually rational, and approximately optimal. Experiments with data collected from a store show that visitors with more important (single-slot) jobs are allocated more preferred slots, which comes at the cost of a longer cooling-off period and significantly reduces social congestion. For the multi-slot jobs, our mechanism yields reasonable approximation while reducing the computation time significantly. While our solutions are primarily motivated by the ongoing raging pandemic, our formulation naturally applies to a broad range of scheduling settings.

PDF

ECAI Conference 2023 Conference Paper

Truthful and Equitable Lateral Transshipment in Multi-Retailer Systems

Garima Shakya
Sai Koti Reddy Danda
Swaprava Nath
Pankaj Dayama 0001
Surya Shravan Kumar Sajja

We consider a multi-retailer system where the sellers are connected with each other via a transportation network and the transactions with the consumers happen on a platform. Each consumer is serviced by only one retailer. Since the demands to the sellers (i. e. , the retailers on the platform) are stochastic in nature, supplies can be either in excess or in deficit. Transshipping these items laterally among the retailers benefits both, the platform and the retailers. For retailers, excess supply leads to wastage and deficit to a loss of revenue, while via transshipment, they get a better outcome. The platform can also earn some revenue in facilitating this process. However, only the sellers know their excess (which can be salvaged at a price or transshipped to another seller) or the deficit (which can be directly procured from a supplier or transshipped from another seller), both of which have multiple information that is private. We propose a model that allows lateral transshipment at a price and design mechanisms such that the sellers are incentivized to voluntarily participate and be truthful. Experimenting on different types of network topologies, we find that the sellers at more central locations in the network get an unfair advantage in the classical mechanism that aims for economic efficiency. We, therefore, propose a modified mechanism with tunable parameters which can ensure that the mechanism is more equitable for non-central retailers. Our synthetic data experiments show that such mechanisms do not compromise too much on efficiency, and also reduce budget imbalance.

Details

TCS Journal 2021 Journal Article

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 district consisting of 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 outcome 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 one (without any attack). 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 only 3 candidates. 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 ( k a, k d ). 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 ( k a, k d ). We propose two greedy algorithms for the Optimal Defense problem and empirically show that they perform effectively on many voting profiles.

Details DOI

ICAPS Conference 2021 Conference Paper

OMCoRP: An Online Mechanism for Competitive Robot Prioritization

Sankar Narayan Das
Swaprava Nath
Indranil Saha 0001

We propose a collision-avoiding mechanism for a group of robots moving on a shared workspace. Existing algorithms solve this problem either (a) in an offline manner using the source-destination information of all the robots or (b) in an online manner with cooperative robots. We take a paradigm shift to the setting with competitive robots, that may strategically reveal their urgency of reaching the destinations and design online mechanisms that take decisions on-the-fly, reducing the overhead of an offline planning. We propose a mechanism OMCoRP in this setting that ensures truthful revelation of the robots' priorities using principles of economic theory and provides locally efficient movement of the robots. It is free from collisions and deadlocks, and handles dynamic arrival of robots. In practice, this mechanism gives a smaller delay for robots of higher priority and scales well for a large number of robots without compromising on the path optimality too much.

Details

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

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

Preference Elicitation For Participatory Budgeting

Gerdus Benade
Swaprava Nath
Ariel Procaccia
Nisarg Shah

Participatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences; it has already had a sizable real-world impact. But making the most of this new paradigm requires a rethinking of some of the basics of computational social choice, including the very way in which individuals express their preferences. We analytically compare four preference elicitation methods — knapsack votes, rankings by value or value for money, and threshold approval votes — through the lens of implicit utilitarian voting, and ﬁnd that threshold approval votes are qualitatively superior. This conclusion is supported by experiments using data from real participatory budgeting elections.

PDF Details

JAIR Journal 2017 Journal Article

Subset Selection Via Implicit Utilitarian Voting

Ioannis Caragiannis
Swaprava Nath
Ariel D. Procaccia
Nisarg Shah

How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach -- which we refer to as implicit utilitarian voting -- assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of RoboVote.org, a not-for-profit website that helps users make group decisions via AI-driven voting methods.

PDF Details DOI

IJCAI Conference 2016 Conference Paper

Subset Selection via Implicit Utilitarian Voting

Ioannis Caragiannis
Swaprava Nath
Ariel D. Procaccia
Nisarg Shah

How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach - which we refer to as implicit utilitarian voting - assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of an upcoming social choice website.

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

UAI Conference 2011 Conference Paper

Dynamic Mechanism Design for Markets with Strategic Resources

Swaprava Nath
Onno Zoeter
Yadati Narahari
Christopher R. Dance

The assignment of tasks to multiple resources becomes an interesting game theoretic problem, when both the task owner and the resources are strategic. In the classical, nonstrategic setting, where the states of the tasks and resources are observable by the controller, this problem is that of finding an optimal policy for a Markov decision process (MDP). When the states are held by strategic agents, the problem of an efficient task allocation extends beyond that of solving an MDP and becomes that of designing a mechanism. Motivated by this fact, we propose a general mechanism which decides on an allocation rule for the tasks and resources and a payment rule to incentivize agents' participation and truthful reports. In contrast to related dynamic strategic control problems studied in recent literature, the problem studied here has interdependent values: the benefit of an allocation to the task owner is not simply a function of the characteristics of the task itself and the allocation, but also of the state of the resources. We introduce a dynamic extension of Mezzetti's two phase mechanism for interdependent valuations. In this changed setting, the proposed dynamic mechanism is efficient, within period ex-post incentive compatible, and within period ex-post individually rational.

Details