Author name cluster

Arpita Biswas

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.

17 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Maximin Share Guarantees via Limited Cost-Sensitive Sharing

Hana Salavcova
Martin Černý
Arpita Biswas

We study the problem of fairly allocating indivisible goods when limited sharing is allowed, that is, each good may be allocated to up to 𝑘 agents, while incurring a cost for sharing. While classic maximin share (MMS) allocations may not exist in many instances, we demonstrate that allowing controlled sharing can restore fairness guarantees that are otherwise unattainable in certain scenarios. (1) Our first contribution shows that exact maximin share (MMS) allocations are guaranteed to exist whenever goods are allowed to be cost-sensitively shared among at least half of the agents and the number of agents is even; for odd numbers of agents, we obtain a slightly weaker MMS guarantee. (2) We further design a Shared Bag-Filling Algorithm that guarantees a (1−𝐶)(𝑘−1)-approximate MMS allocation, where𝐶 is the maximum cost of sharing a good. Notably, when (1 −𝐶)(𝑘 − 1) ≥ 1, our algorithm recovers an exact MMS allocation. (3) We additionally introduce the Sharing Maximin Share (SMMS) fairness notion, a natural extension of MMS to the 𝑘-sharing setting. (4) We show that SMMS allocations always exist under identical utilities and for instances with two agents. (5) We construct a counterexample to show the impossibility of the universal existence of an SMMS allocation. (6) Finally, we establish a connection between SMMS and constrained MMS (CMMS), yielding approximation guarantees for SMMS via existing CMMS results. These contributions provide deep theoretical insights for the problem of fair resource allocation when a limited sharing of resources are allowed in multi-agent environments.

PDF

AAMAS Conference 2024 Conference Paper

Fair Allocation of Conflicting Courses under Additive Utilities

Arpita Biswas
Yiduo Ke
Samir Khuller
Quanquan C. Liu

We investigate the problem of fair allocation of indivisible items when certain item pairs conflict, where conflicts are represented by an interval graph. In this setting, no two conflicting items may be allocated to the same agent. Our problem has practical applications specifically for course allocation where students are agents and course seats are items; courses may have conflicting schedules. We devise algorithms for finding fair, specifically envy-freeness up to one item (EF1), allocations of courses to students in the most general setting: when students have non-uniform, non-identical, additive utility functions. In this extended abstract, we provide one of the algorithms that finds a EF1 solution under identical utilities, implying that, for any course, all students have the same utility.

PDF

AAMAS Conference 2023 Conference Paper

Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks

Arpita Biswas
Jackson A. Killian
Paula Rodriguez Diaz
Susobhan Ghosh
Milind Tambe

Motivated by applications such as machine repair, project monitoring, and anti-poaching patrol scheduling, we study intervention planning of stochastic processes under resource constraints. This planning problem has previously been modeled as restless multi-armed bandits (RMAB), where each arm is an interventiondependent Markov Decision Process. However, the existing literature assumes all intervention resources belong to a single uniform pool, limiting their applicability to real-world settings where interventions are carried out by a set of workers, each with their own costs, budgets, and intervention effects. In this work, we consider a novel RMAB setting, called multi-worker restless bandits (MWRMAB) with heterogeneous workers. The goal is to plan an intervention schedule that maximizes the expected reward while satisfying budget constraints on each worker as well as fairness in terms of the load assigned to each worker. Our contributions are two-fold: (1) we provide a multi-worker extension of the Whittle index to tackle heterogeneous costs and per-worker budget and (2) we develop an index-based scheduling policy to achieve fairness. Further, we evaluate our method on various cost structures and show that our method significantly outperforms other baselines in terms of fairness without sacrificing much in reward accumulated.

PDF

AAAI Conference 2023 Conference Paper

Robust Planning over Restless Groups: Engagement Interventions for a Large-Scale Maternal Telehealth Program

Jackson A. Killian
Arpita Biswas
Lily Xu
Shresth Verma
Vineet Nair
Aparna Taneja
Aparna Hegde
Neha Madhiwalla

In 2020, maternal mortality in India was estimated to be as high as 130 deaths per 100K live births, nearly twice the UN's target. To improve health outcomes, the non-profit ARMMAN sends automated voice messages to expecting and new mothers across India. However, 38% of mothers stop listening to these calls, missing critical preventative care information. To improve engagement, ARMMAN employs health workers to intervene by making service calls, but workers can only call a fraction of the 100K enrolled mothers. Partnering with ARMMAN, we model the problem of allocating limited interventions across mothers as a restless multi-armed bandit (RMAB), where the realities of large scale and model uncertainty present key new technical challenges. We address these with GROUPS, a double oracle–based algorithm for robust planning in RMABs with scalable grouped arms. Robustness over grouped arms requires several methodological advances. First, to adversarially select stochastic group dynamics, we develop a new method to optimize Whittle indices over transition probability intervals. Second, to learn group-level RMAB policy best responses to these adversarial environments, we introduce a weighted index heuristic. Third, we prove a key theoretical result that planning over grouped arms achieves the same minimax regret--optimal strategy as planning over individual arms, under a technical condition. Finally, using real-world data from ARMMAN, we show that GROUPS produces robust policies that reduce minimax regret by up to 50%, halving the number of preventable missed voice messages to connect more mothers with life-saving maternal health information.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems

Aditya S. Mate
Arpita Biswas
Christoph Siebenbrunner
Susobhan Ghosh
Milind Tambe

We propose Streaming Bandits, a Restless Multi-Armed Bandit (RMAB) framework in which heterogeneous arms may arrive and leave the system after staying on for a finite lifetime. Streaming Bandits naturally capture the health-intervention planning problem, where health workers must manage the health outcomes of a patient cohort while new patients join and existing patients leave the cohort each day. Our contributions are as follows: (1) We derive conditions under which our problem satisfies indexability, a precondition that guarantees the existence and asymptotic optimality of the Whittle Index solution for RMABs. We establish the conditions using a polytime reduction of the Streaming Bandit setup to regular RMABs. (2) We further prove a phenomenon that we call index decay — whereby the Whittle index values are low for short residual lifetimes — driving the intuition underpinning our algorithm. (3) We propose a novel and efficient algorithm to compute the index-based solution for Streaming Bandits. Unlike previous methods, our algorithm does not rely on solving the costly finite horizon problem on each arm of the RMAB, thereby lowering the computational complexity compared to existing methods. (4) Finally, we evaluate our approach via simulations run on real-world data sets from a tuberculosis patient monitoring task and an intervention planning task for improving maternal healthcare, in addition to other synthetic domains. Across the board, our algorithm achieves a 2-orders-of-magnitude speed-up over existing methods while maintaining the same solution quality. The full paper is available at: https: //arxiv. org/pdf/2103. 04730. pdf

PDF

AAMAS Conference 2022 Conference Paper

On Achieving Leximin Fairness and Stability in Many-to-One Matchings

Shivika Narang
Arpita Biswas
Yadati Narahari

The past few years have seen a surge of work on fairness in allocation problems where items must be fairly divided among agents having individual preferences. In comparison, fairness in matching settings with preferences on both sides, that is, where agents have to be matched to other agents, has received much less attention. Moreover, the two-sided matching literature has largely focused on ordinal preferences. We study leximin optimality over stable many-to-one matchings under cardinal preferences. We first investigate matching problems with ranked valuations for which we give efficient algorithms to find the leximin optimal matching over the space of stable matchings. We complement these results by showing that relaxing the ranked valuations condition in any way, makes finding the leximin optimal stable matching intractable.

PDF

IJCAI Conference 2022 Conference Paper

Ranked Prioritization of Groups in Combinatorial Bandit Allocation

Lily Xu
Arpita Biswas
Fei Fang
Milind Tambe

Preventing poaching through ranger patrols protects endangered wildlife, directly contributing to the UN Sustainable Development Goal 15 of life on land. Combinatorial bandits have been used to allocate limited patrol resources, but existing approaches overlook the fact that each location is home to multiple species in varying proportions, so a patrol benefits each species to differing degrees. When some species are more vulnerable, we ought to offer more protection to these animals; unfortunately, existing combinatorial bandit approaches do not offer a way to prioritize important species. To bridge this gap, (1) We propose a novel combinatorial bandit objective that trades off between reward maximization and also accounts for prioritization over species, which we call ranked prioritization. We show this objective can be expressed as a weighted linear sum of Lipschitz-continuous reward functions. (2) We provide RankedCUCB, an algorithm to select combinatorial actions that optimize our prioritization-based objective, and prove that it achieves asymptotic no-regret. (3) We demonstrate empirically that RankedCUCB leads to up to 38% improvement in outcomes for endangered species using real-world wildlife conservation data. Along with adapting to other challenges such as preventing illegal logging and overfishing, our no-regret algorithm addresses the general combinatorial bandit problem with a weighted linear objective.

PDF Details DOI

UAI Conference 2022 Conference Paper

Restless and uncertain: Robust policies for restless bandits via deep multi-agent reinforcement learning

Jackson A. Killian
Lily Xu
Arpita Biswas
Milind Tambe

We introduce robustness in \textit{restless multi-armed bandits} (RMABs), a popular model for constrained resource allocation among independent stochastic processes (arms). Nearly all RMAB techniques assume stochastic dynamics are precisely known. However, in many real-world settings, dynamics are estimated with significant uncertainty, e. g. , via historical data, which can lead to bad outcomes if ignored. To address this, we develop an algorithm to compute minimax regret–robust policies for RMABs. Our approach uses a double oracle framework (oracles for \textit{agent} and \textit{nature}), which is often used for single-process robust planning but requires significant new techniques to accommodate the combinatorial nature of RMABs. Specifically, we design a deep reinforcement learning (RL) algorithm, DDLPO, which tackles the combinatorial challenge by learning an auxiliary “$\lambda$-network” in tandem with policy networks per arm, greatly reducing sample complexity, with guarantees on convergence. DDLPO, of general interest, implements our reward-maximizing agent oracle. We then tackle the challenging regret-maximizing nature oracle, a non-stationary RL challenge, by formulating it as a multi-agent RL problem between a policy optimizer and adversarial nature. This formulation is of general interest—we solve it for RMABs by creating a multi-agent extension of DDLPO with a shared critic. We show our approaches work well in three experimental domains.

Details

IJCAI Conference 2021 Conference Paper

Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare

Arpita Biswas
Gaurav Aggarwal
Pradeep Varakantham
Milind Tambe

In many public health settings, it is important for patients to adhere to health programs, such as taking medications and periodic health checks. Unfortunately, beneficiaries may gradually disengage from such programs, which is detrimental to their health. A concrete example of gradual disengagement has been observed by an organization that carries out a free automated call-based program for spreading preventive care information among pregnant women. Many women stop picking up calls after being enrolled for a few months. To avoid such disengagements, it is important to provide timely interventions. Such interventions are often expensive and can be provided to only a small fraction of the beneficiaries. We model this scenario as a restless multi-armed bandit (RMAB) problem, where each beneficiary is assumed to transition from one state to another depending on the intervention. Moreover, since the transition probabilities are unknown a priori, we propose a Whittle index based Q-Learning mechanism and show that it converges to the optimal solution. Our method improves over existing learning-based methods for RMABs on multiple benchmarks from literature and also on the maternal healthcare dataset.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Learning Index Policies for Restless Bandits with Application to Maternal Healthcare

Arpita Biswas
Gaurav Aggarwal
Pradeep Varakantham
Milind Tambe

In many community health settings, it is crucial to have a systematic monitoring and intervention process to ensure that the patients adhere to healthcare programs, such as periodic health checks or taking medications. When these interventions are expensive, they can be provided to only a fixed small fraction of the patients at any period of time. Hence, it is important to carefully choose the beneficiaries who should be provided with interventions and when. We model this scenario as a restless multi-armed bandit (RMAB) problem, where each beneficiary is assumed to transition from one state to another depending on the intervention provided to them. In practice, the transition probabilities are unknown a priori, and hence, we propose a mechanism for the problem of balancing the explore-exploit trade-off. Empirically, we find that our proposed mechanism outperforms the baseline intervention scheme maternal healthcare dataset.

PDF

AAMAS Conference 2019 Conference Paper

Fairness Through the Lens of Proportional Equality

Arpita Biswas
Suvam Mukherjee

Today, automated algorithms, such as machine learning classifiers, are playing an increasingly pivotal role in important societal decisions such as hiring, loan allocation, and criminal risk assessment. This motivates the need to probe the outcomes of a prediction model for discriminatory traits towards specific groups of individuals. In this context, one of the crucial challenges is to formally define a satisfactory notion of fairness. Our contribution in this paper is to formalize Proportional Equality (PE) as a fairness notion. We additionally show that it is a more appropriate criterion than the existing popular notion called Disparate Impact (DI), which is used for evaluating the fairness of a classifier’s outcomes.

PDF

AAAI Conference 2019 Short Paper

Matroid Constrained Fair Allocation Problem

Arpita Biswas
Siddharth Barman

We consider the problem of allocating a set of indivisible goods among a group of homogeneous agents under matroid constraints and additive valuations, in a fair manner. We propose a novel algorithm that computes a fair allocation for instances with additive and identical valuations, even under matroid constraints. Our result provides a computational anchor to the existential result of the fairness notion, called EF1 (envy-free up to one good) by Biswas and Barman in this setting. We further provide examples to show that the fairness notions stronger than EF1 does not always exist in this setting.

PDF Details

IJCAI Conference 2018 Conference Paper

Fair Division Under Cardinality Constraints

Arpita Biswas
Siddharth Barman

We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i. e. , the goods are categorized---and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied unconstrained fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist even under matroid constraints.

PDF Details

AAAI Conference 2018 Conference Paper

Groupwise Maximin Fair Allocation of Indivisible Goods

Siddharth Barman
Arpita Biswas
Sanath Krishnamurthy
Yadati Narahari

We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Speciﬁcally, maximin share is deﬁned as the minimum utility that an agent can guarantee for herself when asked to partition the set of goods into n bundles such that the remaining (n−1) agents pick their bundles adversarially. An allocation is deemed to be fair if every agent gets a bundle whose valuation is at least her maximin share. Even though maximin shares provide a natural benchmark for fairness, it has its own drawbacks and, in particular, it is not sufﬁcient to rule out unsatisfactory allocations. Motivated by these considerations, in this work we deﬁne a stronger notion of fairness, called groupwise maximin share guarantee (GMMS). In GMMS, we require that the maximin share guarantee is achieved not just with respect to the grand bundle, but also among all the subgroups of agents. Hence, this solution concept strengthens MMS and provides an ex-post fairness guarantee. We show that in speciﬁc settings, GMMS allocations always exist. We also establish the existence of approximate GMMS allocations under additive valuations, and develop a polynomial-time algorithm to ﬁnd such allocations. Moreover, we establish a scale of fairness wherein we show that GMMS implies approximate envy freeness. Finally, we empirically demonstrate the existence of GMMS allocations in a large set of randomly generated instances. For the same set of instances, we additionally show that our algorithm achieves an approximation factor better than the established, worst-case bound.

PDF Details

AAMAS Conference 2017 Conference Paper

Profit Optimization in Commercial Ridesharing

Arpita Biswas
Ragavendran Gopalakrishnan
Theja Tulabandhula
Koyel Mukherjee
Asmita Metrewar
Raja Subramaniam Thangaraj

Ridesharing is undoubtedly appealing from a sustainability perspective; however, profit optimization is very important for commercial providers. As such, ridesharing offers a valuable opportunity to garner profit by reducing the number of driver-miles that need to be paid for in order to serve the same set of passengers. In this paper, we study profit optimization for commercial ridesharing service providers such as UberPool and LyftLine. CCS Concepts •Applied computing → Transportation; Economics; Multi-criterion optimization and decision-making;

PDF

IJCAI Conference 2016 Conference Paper

Demand Prediction and Placement Optimization for Electric Vehicle Charging Stations

Ragavendran Gopalakrishnan
Arpita Biswas
Alefiya Lightwala
Skanda Vasudevan
Partha Dutta
Abhishek Tripathi

Effective placement of charging stations plays a key role in Electric Vehicle (EV) adoption. In the placement problem, given a set of candidate sites, an optimal subset needs to be selected with respect to the concerns of both (a) the charging station service provider, such as the demand at the candidate sites and the budget for deployment, and (b) the EV user, such as charging station reachability and short waiting times at the station. This work addresses these concerns, making the following three novel contributions: (i) a supervised multi-view learning framework using Canonical Correlation Analysis (CCA) for demand prediction at candidate sites, using multiple datasets such as points of interest information, traffic density, and the historical usage at existing charging stations; (ii) a mixed-packing-and-covering optimization framework that models competing concerns of the service provider and EV users; (iii) an iterative heuristic to solve these problems by alternately invoking knapsack and setcover algorithms. The performance of the demand prediction model and the placement optimization heuristic are evaluated using real world data.

PDF Details

IJCAI Conference 2016 Conference Paper

Managing Overstaying Electric Vehicles in Park-and-Charge Facilities

Arpita Biswas
Ragavendran Gopalakrishnan
Partha Dutta

With the increase in adoption of Electric Vehicles (EVs), proper utilization of the charging infrastructure is an emerging challenge for service providers. Overstaying of an EV after a charging event is a key contributor to low utilization. Since overstaying is easily detectable by monitoring the power drawn from the charger, managing this problem primarily involves designing an appropriate penalty during the overstaying period. Higher penalties do discourage overstaying; however, due to uncertainty in parking duration, less people would find such penalties acceptable, leading to decreased utilization (and revenue). To analyze this central tradeoff, we develop a novel framework that integrates models for realistic user behavior into queueing dynamics to locate the optimal penalty from the points of view of utilization and revenue, for different values of the external charging demand. Next, when the model parameters are unknown, we show how an online learning algorithm, such as UCB, can be adapted to learn the optimal penalty. Our experimental validation, based on charging data from London, shows that an appropriate penalty can increase both utilization and revenue while significantly reducing overstaying.

PDF Details