Siddharth Barman

JAIR Journal 2026 Journal Article

Nearly Equitable Allocations Beyond Additivity and Monotonicity

• Siddharth Barman
• Umang Bhaskar
• Yeshwant Pandit
• Soumyajit Pyne

Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, equitability is not guaranteed when the allocation is complete. We hence consider a meaningful analog: equitability up to any item (EQX). EQX allocations exist for monotone, additive valuations. However, if (1) the agents’ valuations are not additive, or (2) the set of indivisible items includes both goods and chores (positively and negatively valued items), then prior to this work, it was not known whether EQX allocations exist or not. We study both the existence and efficient computation of EQX allocations. (1) For monotone valuations (not necessarily additive), we show that EQX allocations always exist, and for the large class of weakly well-layered valuations, these allocations can be found in polynomial time. Further, we prove that approximately EQX allocations can be computed efficiently under general monotone valuations. (2) For nonmonotone valuations, we show that an EQX allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we establish the existence and efficient computability of EQX allocations. This includes the case of two agents with additive valuations where each item is either a good or a chore, and there are no mixed items. In general, we show that, under additive nonmonotone valuations, determining the existence of EQX allocations is weakly NP-hard for two agents and strongly NP-hard for more agents. We also give a pseudo-polynomial time algorithm for this problem for a constant number of agents.

AAAI Conference 2025 Conference Paper

Fair Division with Market Values

• Siddharth Barman
• Soroush Ebadian
• Mohamad Latifian
• Nisarg Shah

We introduce a model of fair division with market values, where indivisible goods must be partitioned among agents with (additive) subjective valuations, and each good additionally has a market value. The market valuation can be viewed as a separate additive valuation that holds identically across all the agents. We seek allocations that are simultaneously fair with respect to the subjective valuations and under the market valuation. We show that an allocation that satisfies stochastically-dominant envy-freeness up to one good (SD-EF1) with respect to both the subjective valuations and the market valuation does not always exist, but the weaker guarantee of EF1 with respect to the subjective valuations along with SD-EF1 with respect to the market valuation can be guaranteed. We also study a number of other guarantees such as Pareto optimality, EFX, and MMS. In addition, we explore non-additive valuations and extend our model to cake-cutting. Along the way, we identify several tantalizing open questions.

RLC Conference 2024 Conference Paper

Causal Contextual Bandits with Adaptive Context

• Rahul Madhavan
• Aurghya Maiti
• Gaurav Sinha
• Siddharth Barman

We study a variant of causal contextual bandits where the context is chosen based on an initial intervention chosen by the learner. At the beginning of each round, the learner selects an initial action, depending on which a stochastic context is revealed by the environment. Following this, the learner then selects a final action and receives a reward. Given $T$ rounds of interactions with the environment, the objective of the learner is to learn a policy (of selecting the initial and the final action) with maximum expected reward. In this paper we study the specific situation where every action corresponds to intervening on a node in some known causal graph. We extend prior work from the deterministic context setting to obtain simple regret minimization guarantees. This is achieved through an instance-dependent causal parameter, $\lambda$, which characterizes our upper bound. Furthermore, we prove that our simple regret is essentially tight for a large class of instances. A key feature of our work is that we use convex optimization to address the bandit exploration problem. We also conduct experiments to validate our theoretical results, and release our code at [github. com/adaptiveContextualCausalBandits/aCCB](https: //github. com/adaptiveContextualCausalBandits/aCCB).

RLJ Journal 2024 Journal Article

Causal Contextual Bandits with Adaptive Context

• Rahul Madhavan
• Aurghya Maiti
• Gaurav Sinha
• Siddharth Barman

We study a variant of causal contextual bandits where the context is chosen based on an initial intervention chosen by the learner. At the beginning of each round, the learner selects an initial action, depending on which a stochastic context is revealed by the environment. Following this, the learner then selects a final action and receives a reward. Given $T$ rounds of interactions with the environment, the objective of the learner is to learn a policy (of selecting the initial and the final action) with maximum expected reward. In this paper we study the specific situation where every action corresponds to intervening on a node in some known causal graph. We extend prior work from the deterministic context setting to obtain simple regret minimization guarantees. This is achieved through an instance-dependent causal parameter, $\lambda$, which characterizes our upper bound. Furthermore, we prove that our simple regret is essentially tight for a large class of instances. A key feature of our work is that we use convex optimization to address the bandit exploration problem. We also conduct experiments to validate our theoretical results, and release our code at [github.com/adaptiveContextualCausalBandits/aCCB](https://github.com/adaptiveContextualCausalBandits/aCCB).

NeurIPS Conference 2024 Conference Paper

Generalized Linear Bandits with Limited Adaptivity

• Ayush Sawarni
• Nirjhar Das
• Siddharth Barman
• Gaurav Sinha

We study the generalized linear contextual bandit problem within the constraints of limited adaptivity. In this paper, we present two algorithms, B-GLinCB and RS-GLinCB, that address, respectively, two prevalent limited adaptivity settings. Given a budget $M$ on the number of policy updates, in the first setting, the algorithm needs to decide upfront $M$ rounds at which it will update its policy, while in the second setting it can adaptively perform $M$ policy updates during its course. For the first setting, we design an algorithm B-GLinCB, that incurs $\tilde{O}(\sqrt{T})$ regret when $M = \Omega( \log{\log T} )$ and the arm feature vectors are generated stochastically. For the second setting, we design an algorithm RS-GLinCB that updates its policy $\tilde{O}(\log^2 T)$ times and achieves a regret of $\tilde{O}(\sqrt{T})$ even when the arm feature vectors are adversarially generated. Notably, in these bounds, we manage to eliminate the dependence on a key instance dependent parameter $\kappa$, that captures non-linearity of the underlying reward model. Our novel approach for removing this dependence for generalized linear contextual bandits might be of independent interest.

AAAI Conference 2024 Conference Paper

Nearly Equitable Allocations beyond Additivity and Monotonicity

• Siddharth Barman
• Umang Bhaskar
• Yeshwant Pandit
• Soumyajit Pyne

Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, an equitable allocation may not exist, and hence we instead consider a meaningful analog, EQx, that requires equitability up to any item. EQx allocations exist for monotone, additive valuations. However, if (1) the agents' valuations are not additive or (2) the set of indivisible items includes both goods and chores (positively and negatively valued items), then prior to the current work it was not known whether EQx allocations exist or not. We study both the existence and efficient computation of EQx allocations. (1) For monotone valuations (not necessarily additive), we show that EQx allocations always exist. Also, for the large class of weakly well-layered valuations, EQx allocations can be found in polynomial time. Further, we prove that approximately EQx allocations can be computed efficiently under general monotone valuations. (2) For non-monotone valuations, we show that an EQx allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we show existence and efficient computability of EQx allocations. This includes the case of two agents with additive valuations where each item is either a good or a chore, and there are no mixed items.

AAMAS Conference 2024 Conference Paper

Parameterized Guarantees for Almost Envy-Free Allocations

• Siddharth Barman
• Debajyoti Kar
• Shraddha Pathak

We study fair allocation of indivisible goods among agents with additive valuations. We obtain novel approximation guarantees for two of the strongest fairness notions in discrete fair division, namely envy-free up to the removal of any positively-valued good (EFx) and pairwise maximin shares (PMMS). Our approximation guarantees are in terms of an instance-dependent parameter 𝛾 ∈ (0, 1] that upper bounds, for each indivisible good in the given instance, the multiplicative range of nonzero values for the good across the agents. First, we consider allocations wherein, between any pair of agents and up to the removal of any positively-valued good, the envy is multiplicatively bounded. Specifically, the current work develops a polynomial-time algorithm that computes a 2𝛾 √ 5+4𝛾−1 approximately EFx allocation for any given fair division instance with range parameter 𝛾 ∈ (0, 1]. For instances with 𝛾 ≥ 0. 511, the obtained approximation guarantee for EFx surpasses the previously best-known approximation bound of (𝜙−1) ≈ 0. 618, here 𝜙 denotes the golden ratio. Furthermore, we study multiplicative approximations for PMMS. For fair division instances with range parameter 𝛾 ∈ (0, 1], the current paper develops a polynomial-time algorithm for finding allocations wherein the PMMS requirement is satisfied, between every pair of agents, within a multiplicative factor of 5 6𝛾. En route to this result, we obtain novel existential and computational guarantees for 5 6 -approximately PMMS allocations under restricted additive valuations.

AAMAS Conference 2023 Conference Paper

Fair Chore Division under Binary Supermodular Costs

• Siddharth Barman
• Vishnu Narayan
• Paritosh Verma

We study the problem of dividing indivisible chores among agents whose costs (for the chores) are supermodular set functions with binary marginals. Such functions capture complementarity among chores, i. e. , they constitute an expressive class wherein the marginal disutility of each chore is either one or zero, and the marginals increase with respect to supersets. In this setting, we study the broad landscape of finding fair and efficient chore allocations. In particular, we establish the existence of (𝑖) EF1 and Pareto efficient chore allocations, (𝑖𝑖) MMS-fair and Pareto efficient allocations, and (𝑖𝑖𝑖) Lorenz dominating chore allocations. Furthermore, we develop polynomial-time algorithms—in the value oracle model—for computing the chore allocations for each of these fairness and efficiency criteria. Complementing these existential and algorithmic results, we show that in this chore division setting, the aforementioned fairness notions, namely EF1, MMS, and Lorenz domination are incomparable: an allocation that satisfies any one of these notions does not necessarily satisfy the others. Additionally, we study EFX chore division. In contrast to the above-mentioned positive results, we show that, for binary supermodular costs, Pareto efficient allocations that are even approximately EFX do not exist, for any arbitrarily small approximation constant.

AAAI Conference 2023 Conference Paper

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits

• Siddharth Barman
• Arindam Khan
• Arnab Maiti
• Ayush Sawarni

We extend the notion of regret with a welfarist perspective. Focussing on the classic multi-armed bandit (MAB) framework, the current work quantifies the performance of bandit algorithms by applying a fundamental welfare function, namely the Nash social welfare (NSW) function. This corresponds to equating algorithm's performance to the geometric mean of its expected rewards and leads us to the study of Nash regret, defined as the difference between the - a priori unknown - optimal mean (among the arms) and the algorithm's performance. Since NSW is known to satisfy fairness axioms, our approach complements the utilitarian considerations of average (cumulative) regret, wherein the algorithm is evaluated via the arithmetic mean of its expected rewards. This work develops an algorithm that, given the horizon of play T, achieves a Nash regret of O ( sqrt{(k log T)/T} ), here k denotes the number of arms in the MAB instance. Since, for any algorithm, the Nash regret is at least as much as its average regret (the AM-GM inequality), the known lower bound on average regret holds for Nash regret as well. Therefore, our Nash regret guarantee is essentially tight. In addition, we develop an anytime algorithm with a Nash regret guarantee of O( sqrt{(k log T)/T} log T ).

AAAI Conference 2023 Conference Paper

Finding Fair Allocations under Budget Constraints

• Siddharth Barman
• Arindam Khan
• Sudarshan Shyam
• K. V. N. Sreenivas

We study the fair allocation of indivisible goods among agents with identical, additive valuations but individual budget constraints. Here, the indivisible goods--each with a specific size and value--need to be allocated such that the bundle assigned to each agent is of total size at most the agent's budget. Since envy-free allocations do not necessarily exist in the indivisible goods context, compelling relaxations--in particular, the notion of envy-freeness up to k goods (EFk)--have received significant attention in recent years. In an EFk allocation, each agent prefers its own bundle over that of any other agent, up to the removal of k goods, and the agents have similarly bounded envy against the charity (which corresponds to the set of all unallocated goods). It has been shown in prior work that an allocation that satisfies the budget constraints and maximizes the Nash social welfare is 1/4-approximately EF1. However, the computation (or even existence) of exact EFk allocations remained an intriguing open problem. We make notable progress towards this by proposing a simple, greedy, polynomial-time algorithm that computes EF2 allocations under budget constraints. Our algorithmic result implies the universal existence of EF2 allocations in this fair division context. The analysis of the algorithm exploits intricate structural properties of envy-freeness. Interestingly, the same algorithm also provides EF1 guarantees for important special cases. Specifically, we settle the existence of EF1 allocations for instances in which: (i) the value of each good is proportional to its size, (ii) all the goods have the same size, or (iii) all the goods have the same value. Our EF2 result even extends to the setting wherein the goods' sizes are agent specific.

UAI Conference 2023 Conference Paper

Learning good interventions in causal graphs via covering

• Ayush Sawarni
• Rahul Madhavan
• Gaurav Sinha 0001
• Siddharth Barman

We study the causal bandit problem that entails identifying a near-optimal intervention from a specified set A of (possibly non-atomic) interventions over a given causal graph. Here, an optimal intervention in A is one that maximizes the expected value for a designated reward variable in the graph, and we use the standard notion of simple regret to quantify near optimality. Considering Bernoulli random variables and for causal graphs on N vertices with constant in-degree, prior work has achieved a worst case guarantee of O(N/sqrt(T)) for simple regret. The current work utilizes the idea of covering interventions (which are not necessarily contained within A) and establishes a simple regret guarantee of O(sqrt(N/T)). Notably, and in contrast to prior work, our simple regret bound depends only on explicit parameters of the problem instance. We also go beyond prior work and achieve a simple regret guarantee for causal graphs with unobserved variables. Further, we perform experiments to show improvements over baselines in this setting.

NeurIPS Conference 2023 Conference Paper

Nash Regret Guarantees for Linear Bandits

• Ayush Sawarni
• Soumyabrata Pal
• Siddharth Barman

We obtain essentially tight upper bounds for a strengthened notion of regret in the stochastic linear bandits framework. The strengthening---referred to as Nash regret---is defined as the difference between the (a priori unknown) optimum and the geometric mean of expected rewards accumulated by the linear bandit algorithm. Since the geometric mean corresponds to the well-studied Nash social welfare (NSW) function, this formulation quantifies the performance of a bandit algorithm as the collective welfare it generates across rounds. NSW is known to satisfy fairness axioms and, hence, an upper bound on Nash regret provides a principled fairness guarantee. We consider the stochastic linear bandits problem over a horizon of $\mathsf{T}$ rounds and with a set of arms ${\cal X}$ in ambient dimension $d$. Furthermore, we focus on settings in which the stochastic reward---associated with each arm in ${\cal X}$---is a non-negative, sub-Poisson random variable. For this setting, we develop an algorithm that achieves a Nash regret of $O\left( \sqrt{\frac{d}{\mathsf{T}}} \log(\mathsf{T} |{\cal X}|)\right)$. In addition, addressing linear bandit instances in which the set of arms ${\cal X}$ is not necessarily finite, we obtain a Nash regret upper bound of $O\left( \frac{d^\frac{5}{4}}{\sqrt{\mathsf{T}}} \log(\mathsf{T})\right)$. Since bounded random variables are sub-Poisson, these results hold for bounded, non-negative rewards. Our linear bandit algorithm is built upon the successive elimination method with novel technical insights, including tailored concentration bounds and the use of sampling via John ellipsoid in conjunction with the Kiefer–Wolfowitz optimal design.

IJCAI Conference 2022 Conference Paper

Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations

• Siddharth Barman
• Anand Krishna
• Yadati Narahari
• Soumyarup Sadhukhan

We study the problem of allocating indivisible goods among agents in a fair manner. While envy-free allocations of indivisible goods are not guaranteed to exist, envy-freeness can be achieved by additionally providing some subsidy to the agents. These subsidies can be alternatively viewed as a divisible good (money) that is fractionally assigned among the agents to realize an envy-free outcome. In this setup, we bound the subsidy required to attain envy-freeness among agents with dichotomous valuations, i. e. , among agents whose marginal value for any good is either zero or one. We prove that, under dichotomous valuations, there exists an allocation that achieves envy-freeness with a per-agent subsidy of either 0 or 1. Furthermore, such an envy-free solution can be computed efficiently in the standard value-oracle model. Notably, our results hold for general dichotomous valuations and, in particular, do not require the (dichotomous) valuations to be additive, submodular, or even subadditive. Also, our subsidy bounds are tight and provide a linear (in the number of agents) factor improvement over the bounds known for general monotone valuations.

AAAI Conference 2022 Conference Paper

Truthful and Fair Mechanisms for Matroid-Rank Valuations

• Siddharth Barman
• Paritosh Verma

We study the problem of allocating indivisible goods among strategic agents. We focus on settings wherein monetary transfers are not available and each agent’s private valuation is a submodular function with binary marginals, i. e. , the agents’ valuations are matroid-rank functions. In this setup, we establish a notable dichotomy between two of the most well-studied fairness notions in discrete fair division; specifically, between envy-freeness up to one good (EF1) and maximin shares (MMS). First, we show that a known Pareto-efficient mechanism is group strategy-proof for finding EF1 allocations, under matroid-rank valuations. The group strategy-proofness guarantee strengthens an existing result that establishes truthfulness (individually for each agent) in the same context. Our result also generalizes prior work from binary additive valuations to the matroid-rank case. Next, we establish that an analogous positive result cannot be achieved for MMS, even when considering truthfulness on an individual level. Specifically, we prove that, for matroid-rank valuations, there does not exist a truthful mechanism that is index oblivious, Pareto efficient, and maximin fair. For establishing our results, we develop a characterization of truthful mechanisms for matroid-rank functions. This characterization in fact holds for a broader class of valuations (specifically, holds for binary XOS functions) and might be of independent interest.

AAAI Conference 2022 Conference Paper

Universal and Tight Online Algorithms for Generalized-Mean Welfare

• Siddharth Barman
• Arindam Khan
• Arnab Maiti

We study fair and efficient allocation of divisible goods, in an online manner, among n agents. The goods arrive online in a sequence of T time periods. The agents’ values for a good are revealed only after its arrival, and the online algorithm needs to fractionally allocate the good, immediately and irrevocably, among the agents. Towards a unifying treatment of fairness and economic efficiency objectives, we develop an algorithmic framework for finding online allocations to maximize the generalized mean of the values received by the agents. In particular, working with the assumption that each agent’s value for the grand bundle of goods is appropriately scaled, we address online maximization of p-mean welfare. Parameterized by an exponent term p ∈ (−∞, 1], these means encapsulate a range of welfare functions, including social welfare (p = 1), egalitarian welfare (p → −∞), and Nash social welfare (p → 0). We present a simple algorithmic template that takes a threshold as input and, with judicious choices for this threshold, leads to both universal and tailored competitive guarantees. First, we show that one can compute online a single allocation that O( √ n log n)-approximates the optimal p-mean welfare for all p ≤ 1. The existence of such a universal allocation is interesting in and of itself. Moreover, this universal guarantee achieves essentially tight competitive ratios for specific values of p. Next, we obtain improved competitive ratios for different ranges of p by executing our algorithm with p-specific thresholds, e. g. , we provide O(log3 n)-competitive ratio for all p ∈ ( −1 log 2n, 1). We complement our positive results by establishing lower bounds to show that our guarantees are essentially tight for a wide range of the exponent parameter.

AAMAS Conference 2021 Conference Paper

Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations

• Siddharth Barman
• Paritosh Verma

We study fair and economically efficient allocation of indivisible goods among agents whose valuations are rank functions of matroids. Such valuations constitute a well-studied class of submodular functions (i. e. , they exhibit a diminishing returns property) and model preferences in several resource-allocation settings. We prove that, for matroid-rank valuations, a social welfare-maximizing allocation that gives each agent her maximin share always exists. Furthermore, such an allocation can be computed in polynomial time. We establish similar existential and algorithmic results for the pairwise maximin share guarantee as well. To complement these results, we show that if the agents have binary XOS valuations or weighted-rank valuations, then maximin fair allocations are not guaranteed to exist. Both of these valuation classes are immediate generalizations of matroid-rank functions.

IJCAI Conference 2021 Conference Paper

Optimal Algorithms for Range Searching over Multi-Armed Bandits

• Siddharth Barman
• Ramakrishnan Krishnamurthy
• Saladi Rahul

This paper studies a multi-armed bandit (MAB) version of the range-searching problem. In its basic form, range searching considers as input a set of points (on the real line) and a collection of (real) intervals. Here, with each specified point, we have an associated weight, and the problem objective is to find a maximum-weight point within every given interval. The current work addresses range searching with stochastic weights: each point corresponds to an arm (that admits sample access) and the point's weight is the (unknown) mean of the underlying distribution. In this MAB setup, we develop sample-efficient algorithms that find, with high probability, near-optimal arms within the given intervals, i. e. , we obtain PAC (probably approximately correct) guarantees. We also provide an algorithm for a generalization wherein the weight of each point is a multi-dimensional vector. The sample complexities of our algorithms depend, in particular, on the size of the {optimal hitting set} of the given intervals. Finally, we establish lower bounds proving that the obtained sample complexities are essentially tight. Our results highlight the significance of geometric constructs (specifically, hitting sets) in our MAB setting.

IJCAI Conference 2020 Conference Paper

Uniform Welfare Guarantees Under Identical Subadditive Valuations

• Siddharth Barman
• Ranjani G. Sundaram

We study the problem of allocating indivisible goods among agents that have an identical subadditive valuation over the goods. The extent of fair- ness and efficiency of allocations is measured by the generalized means of the values that the alloca- tions generate among the agents. Parameterized by an exponent term p, generalized-mean welfares en- compass multiple well-studied objectives, such as social welfare, Nash social welfare, and egalitarian welfare. We establish that, under identical subadditive valu- ations and in the demand oracle model, one can efficiently find a single allocation that approximates the optimal generalized-mean welfare—to within a factor of 40—uniformly for all p ∈ (−∞, 1]. Hence, by way of a constant-factor approximation algorithm, we obtain novel results for maximizing Nash social welfare and egalitarian welfare for identical subadditive valuations.

AAMAS Conference 2019 Conference Paper

Fair Division of Indivisible Goods Among Strategic Agents

• Siddharth Barman
• Ganesh Ghalme
• Shweta Jain
• Pooja Kulkarni
• Shivika Narang

We study fair division of indivisible goods among strategic agents in a single-parameter environment. This work specifically considers fairness in terms of envy freeness up to one good (EF1) and maximin share guarantee (MMS). We show that (in a single-parameter environment) the problem of maximizing welfare, subject to the constraint that the allocation of the indivisible goods is EF1, admits a polynomial-time, 1/2-approximate, truthful auction. Under MMS setup, we develop a truthful auction which efficiently finds an allocation wherein each agent gets a bundle of value at least (1/2 − ε) times her maximin share and the welfare of the computed allocation is at least the optimal, here ε > 0 is a fixed constant. Our results for EF1 and MMS are based on establishing interesting majorization inequalities.

AAAI Conference 2019 Conference Paper

Fair Division with a Secretive Agent

• Eshwar Ram Arunachaleswaran
• Siddharth Barman
• Nidhi Rathi

We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with cardinal preferences. We will show that, for all of these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n − 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation. For the rent-division setting we prove that well-behaved utilities of n − 1 agents suffice to find a rent division among n rooms such that, for every possible room selection of the secretive agent, there exists an allocation (of the remaining n − 1 rooms among the n − 1 agents) which ensures overall envy freeness (fairness). We complement this existential result by developing a polynomial-time algorithm for the case of quasilinear utilities. In this partial information setting, we also develop efficient algorithms to compute allocations that are envy-free up to one good (EF1) and ε-approximate envy free. These two notions of fairness are applicable in the context of indivisible goods and divisible goods (cake cutting), respectively. One of the main technical contributions of this paper is the development of novel connections between different fairdivision paradigms, e. g. , we use our existential results for envy-free rent-division to develop an efficient EF1 algorithm.

SODA Conference 2019 Conference Paper

Fully Polynomial-Time Approximation Schemes for Fair Rent Division

• Eshwar Ram Arunachaleswaran
• Siddharth Barman
• Nidhi Rathi

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.

AAAI Conference 2019 Conference Paper

On the Proximity of Markets with Integral Equilibria

• Siddharth Barman
• Sanath Kumar Krishnamurthy

We study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with additive valuations (Eisenberg and Gale 1959; Orlin 2010), such equilibria, in general, assign goods fractionally to agents. Hence, Fisher markets are not directly applicable in the context of indivisible goods. In this work we show that one can always bypass this hurdle and, up to a bounded change in agents’ budgets, obtain markets that admit an integral equilibrium. We refer to such markets as pure markets and show that, for any given Fisher market (with additive valuations), one can efficiently compute a “near-by, ” pure market with an accompanying integral equilibrium. Our work on pure markets leads to novel algorithmic results for fair division of indivisible goods. Prior work in discrete fair division has shown that, under additive valuations, there always exist allocations that simultaneously achieve the seemingly incompatible properties of fairness and efficiency (Caragiannis et al. 2016); here fairness refers to envyfreeness up to one good (EF1) and efficiency corresponds to Pareto efficiency. However, polynomial-time algorithms are not known for finding such allocations. Considering relaxations of proportionality and EF1, respectively, as our notions of fairness, we show that fair and Pareto efficient allocations can be computed in strongly polynomial time.

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.

AAMAS Conference 2018 Conference Paper

Greedy Algorithms for Maximizing Nash Social Welfare

• Siddharth Barman
• Sanath Kumar Krishnamurthy
• Rohit Vaish

We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean of the valuations of the agents for their bundles. While the problem of maximizing Nash social welfare is known to be APX-hard in general, we study the effectiveness of simple, greedy algorithms in solving this problem in two interesting special cases. First, we show that a simple, greedy algorithm provides a 1. 061approximation guarantee when agents have identical valuations, even though the problem of maximizing Nash social welfare remains NP-hard for this setting. Second, we show that when agents have binary valuations over the goods, an exact solution (i. e. , a Nash optimal allocation) can be found in polynomial time via a greedy algorithm. Our results in the binary setting extend to provide novel, exact algorithms for optimizing Nash social welfare under concave valuations. Notably, for the above mentioned scenarios, our techniques provide a simple alternative to several of the existing, more sophisticated techniques for this problem such as constructing equilibria of Fisher markets or using real stable polynomials.

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. Specifically, maximin share is defined 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 sufficient to rule out unsatisfactory allocations. Motivated by these considerations, in this work we define 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 specific settings, GMMS allocations always exist. We also establish the existence of approximate GMMS allocations under additive valuations, and develop a polynomial-time algorithm to find 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.

AAAI Conference 2018 Conference Paper

Online Learning for Structured Loss Spaces

• Siddharth Barman
• Aditya Gopalan
• Aadirupa Saha

We consider prediction with expert advice when the loss vectors are assumed to lie in a set described by the sum of atomic norm balls. We derive a regret bound for a general version of the online mirror descent (OMD) algorithm that uses a combination of regularizers, each adapted to the constituent atomic norms. The general result recovers standard OMD regret bounds, and yields regret bounds for new structured settings where the loss vectors are (i) noisy versions of vectors from a low-dimensional subspace, (ii) sparse vectors corrupted with noise, and (iii) sparse perturbations of low-rank vectors. For the problem of online learning with structured losses, we also show lower bounds on regret in terms of rank and sparsity of the loss vectors, which implies lower bounds for the above additive loss settings as well.

ICML Conference 2018 Conference Paper

Testing Sparsity over Known and Unknown Bases

• Siddharth Barman
• Arnab Bhattacharyya 0001
• Suprovat Ghoshal

Sparsity is a basic property of real vectors that is exploited in a wide variety of machine learning applications. In this work, we describe property testing algorithms for sparsity that observe a low-dimensional projec- tion of the input. We consider two settings. In the first setting, we test sparsity with respect to an unknown basis: given input vectors $y_1, .. ., y_p \in R^d$ whose concatenation as columns forms $Y \in R^{d \times p}$, does $Y = AX$ for matrices $A \in R^{d\times m}$ and $X \in R^{m \times p}$ such that each column of $X$ is $k$-sparse, or is $Y$ “far” from having such a decomposition? In the second setting, we test sparsity with respect to a known basis: for a fixed design ma- trix $A \in R^{d \times m}$, given input vector $y \in R^d$, is $y = Ax$ for some $k$-sparse vector $x$ or is $y$ “far” from having such a decomposition? We analyze our algorithms using tools from high-dimensional geometry and probability.

STOC Conference 2015 Conference Paper

Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

• Siddharth Barman

We present algorithmic applications of an approximate version of Caratheodory's theorem. The theorem states that given a set of vectors X in R d , for every vector in the convex hull of X there exists an ε-close (under the p-norm distance, for 2 ≤ p < ∞) vector that can be expressed as a convex combination of at most b vectors of X, where the bound b depends on ε and the norm p and is independent of the dimension d. This theorem can be derived by instantiating Maurey's lemma, early references to which can be found in the work of Pisier (1981) and Carl (1985). However, in this paper we present a self-contained proof of this result. Using this theorem we establish that in a bimatrix game with n x n payoff matrices A, B, if the number of non-zero entries in any column of A+B is at most s then an ε-Nash equilibrium of the game can be computed in time n O(log s/ε 2 }) . This, in particular, gives us a polynomial-time approximation scheme for Nash equilibrium in games with fixed column sparsity s. Moreover, for arbitrary bimatrix games---since s can be at most n---the running time of our algorithm matches the best-known upper bound, which was obtained by Lipton, Markakis, and Mehta (2003). The approximate Carathéodory's theorem also leads to an additive approximation algorithm for the densest k -bipartite subgraph problem. Given a graph with n vertices and maximum degree d , the developed algorithm determines a k x k bipartite subgraph with density within ε (in the additive sense) of the optimal density in time n O (log d/ε 2 ).

SODA Conference 2012 Conference Paper

Traffic-redundancy aware network design

• Siddharth Barman
• Shuchi Chawla 0001

SODA Conference 2010 Conference Paper

Region Growing for Multi-Route Cuts

• Siddharth Barman
• Shuchi Chawla 0001

SODA Conference 2009 Conference Paper

Packing multiway cuts in capacitated graphs

• Siddharth Barman
• Shuchi Chawla 0001