Author name cluster

Garima Shakya

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.

7 papers

2 author rows

ECAI Conference 2023 Conference Paper

Balancing Fairness and Efficiency in 3D Repeated Matching in Ridesharing

Garima Shakya
Makoto Yokoo

Ride-hailing services’ main feature is mediating the assignment and transactions between drivers and passengers. Essentially, they decide on the quality of passengers’ experience and the drivers’ workload balancing. To boost the company’s profit, these services try to maximize the utility for the passengers by optimizing the matching, resulting in shorter waiting times and better service availability. Often, in the process of maximizing revenue, drivers’ interests get sidelined. We focus on two objectives: efficiency (minimizing total distance traveled by drivers) and fairness (minimizing the maximum traveled distance by any driver) for shared-mode rides, where the vehicles’ capacity is two passengers. We theoretically show the relation between the optimal solutions of both objectives and as the problem is computationally intractable, we propose a heuristic algorithm to achieve an approximately optimal solution. We also propose a re-assignment-based algorithm when the aim is to achieve maximum matching with fairness up to a given threshold, if that is feasible. The experimental analysis for the proposed algorithms on real-world data from Chicago city shows that our approach can significantly improve fairness for drivers without losing much efficiency.

Details

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

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

Problems in Computational Mechanism Design

Garima Shakya

My research area is interdisciplinary to Mechanism Design and Algorithm Design. The problems I find interesting in Computational Mechanism Design are about Voting preferences, Environment protection by reducing the emission of harmful gases from automobiles, Shareable good allocation on a network and Peer grading. In this paper, I explain two of such problems and roadmaps for them. First is the domain of preferences in the voting. It is often observed that preferences are never completely arbitrary; instead, they possess correlated structures. After learning the preferences, the next main task is to aggregate them and have an outcome out of it. My interest is to explore the different domains of preferences so that we can have specific desirable properties in the social choice function. Another problem I am interested in is, to devise a mechanism which incentivises the riders to prefer to share the ride than to ride solo, where the objective of the mechanism is to reduce the emission of harmful gases and control the pollution in the environment by reducing the total travelled distance by the vehicles. A significant challenge when addressing the problem of ridesharing is that it needs to explore a vast decision space while computing solutions fast enough to provide users with the experience of real-time booking and service.

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