Researcher profile

Siddharth Barman

Siddharth Barman contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Computer Science and Game Theory Data Structures and Algorithms Information Theory Machine Learning math.IT math.OC

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author

18works

0followers

6topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

preprint2026arXiv

Introspectively Envy-Free and Efficient Allocation of Indivisible Mixed Manna

The existence of allocations that are fair and efficient, simultaneously, is a central inquiry in fair division literature. A prominent result in discrete fair division shows that the complementary desiderata of fairness and efficiency can be achieved together when allocating indivisible items with nonnegative values; specifically, for indivisible goods and among agents with additive valuations, there always exists an allocation that is both envy-free up to one item (EF1) and Pareto efficient (PO). While a recent breakthrough extends the EF1 and PO guarantee to indivisible chores (items with negative values), the question remains open for indivisible mixed manna, i.e., for indivisible items whose values can be positive, negative, or zero. The current work makes notable progress in resolving this central question. For indivisible mixed manna and additive valuations, we establish the existence of allocations that are PO and introspectively envy-free up to one item (IEF1). In an IEF1 allocation, each agent can eliminate its envy towards all the other agents by either adding an item or removing an item from its own bundle. The notion of IEF1 coincides with EF1 for indivisible chores, and hence, our result generalizes the aforementioned existence guarantee for chores. Our techniques can be adopted to obtain an alternative proof for the existence of EF1 and PO allocations of indivisible goods. Hence, along with the result for mixed manna, we provide a unified approach for establishing the EF1 and PO guarantee for indivisible goods and indivisible chores. We also utilize our result for indivisible items to develop a distinct proof of the noted EF and PO guarantee for divisible mixed manna. Our work highlights an interesting application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division and develops multiple, novel structural insights and algorithmic ideas.

preprint2022arXiv

Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations

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.

preprint2022arXiv

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits

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 \left( \sqrt{\frac{k \log T}{T}} \right)$, 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 \left( \sqrt{\frac{k\log T}{T}} \log T \right)$.

preprint2022arXiv

Nash Welfare Guarantees for Fair and Efficient Coverage

We study coverage problems in which, for a set of agents and a given threshold $T$, the goal is to select $T$ subsets (of the agents) that, while satisfying combinatorial constraints, achieve fair and efficient coverage among the agents. In this setting, the valuation of each agent is equated to the number of selected subsets that contain it, plus one. The current work utilizes the Nash social welfare function to quantify the extent of fairness and collective efficiency. We develop a polynomial-time $\left(18 + o(1) \right)$-approximation algorithm for maximizing Nash social welfare in coverage instances. Our algorithm applies to all instances wherein, for the underlying combinatorial constraints, there exists an FPTAS for weight maximization. We complement the algorithmic result by proving that Nash social welfare maximization is APX-hard in coverage instances.

preprint2022arXiv

Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations

We study the problem of allocating indivisible goods among $n$ agents with the objective of maximizing Nash social welfare (NSW). This welfare function is defined as the geometric mean of the agents' valuations and, hence, it strikes a balance between the extremes of social welfare (arithmetic mean) and egalitarian welfare (max-min value). Nash social welfare has been extensively studied in recent years for various valuation classes. In particular, a notable negative result is known when the agents' valuations are complement-free and are specified via value queries: for XOS valuations, one necessarily requires exponentially many value queries to find any sublinear (in $n$) approximation for NSW. Indeed, this lower bound implies that stronger query models are needed for finding better approximations. Towards this, we utilize demand oracles and XOS oracles; both of these query models are standard and have been used in prior work on social welfare maximization with XOS valuations. We develop the first sublinear approximation algorithm for maximizing Nash social welfare under XOS valuations, specified via demand and XOS oracles. Hence, this work breaks the $O(n)$-approximation barrier for NSW maximization under XOS valuations. We obtain this result by developing a novel connection between NSW and social welfare under a capped version of the agents' valuations. In addition to this insight, which might be of independent interest, this work relies on an intricate combination of multiple technical ideas, including the use of repeated matchings and the discrete moving knife method. In addition, we partially complement the algorithmic result by showing that, under XOS valuations, an exponential number of demand and XOS queries are necessarily required to approximate NSW within a factor of $\left(1 - \frac{1}{e}\right)$.

preprint2022arXiv

Tight Approximation Bounds for Maximum Multi-Coverage

In the classic maximum coverage problem, we are given subsets $T_1, \dots, T_m$ of a universe $[n]$ along with an integer $k$ and the objective is to find a subset $S \subseteq [m]$ of size $k$ that maximizes $C(S) := |\cup_{i \in S} T_i|$. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of $(1-e^{-1})$ and there is a matching inapproximability result. We note that in the maximum coverage problem if an element $e \in [n]$ is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element $e$ as many times as it is covered, then we obtain a linear objective function, $C^{(\infty)}(S) = \sum_{i \in S} |T_i|$, which can be easily maximized under a cardinality constraint. We study the maximum $\ell$-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to $\ell$ times but no more; hence, we consider maximizing the function $C^{(\ell)}(S) = \sum_{e \in [n]} \min\{\ell, |\{i \in S : e \in T_i\}| \}$, subject to the constraint $|S| \leq k$. Note that the case of $\ell = 1$ corresponds to the standard maximum coverage setting and $\ell = \infty$ gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of $1 - \frac{\ell^{\ell}e^{-\ell}}{\ell!}$ for the $\ell$-multi-coverage problem. In particular, when $\ell = 2$, this factor is $1-2e^{-2} \approx 0.73$ and as $\ell$ grows the approximation ratio behaves as $1 - \frac{1}{\sqrt{2π\ell}}$. We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture.

preprint2021arXiv

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

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.

preprint2020arXiv

Approximation Algorithms for Maximin Fair Division

We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations. Specifically, we show that when the valuations of the agents are nonnegative, monotone, and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the paper is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions.

preprint2020arXiv

Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations

We develop polynomial-time algorithms for the fair and efficient allocation of indivisible goods among $n$ agents that have subadditive valuations over the goods. We first consider the Nash social welfare as our objective and design a polynomial-time algorithm that, in the value oracle model, finds an $8n$-approximation to the Nash optimal allocation. Subadditive valuations include XOS (fractionally subadditive) and submodular valuations as special cases. Our result, even for the special case of submodular valuations, improves upon the previously best known $O(n \log n)$-approximation ratio of Garg et al. (2020). More generally, we study maximization of $p$-mean welfare. The $p$-mean welfare is parameterized by an exponent term $p \in (-\infty, 1]$ and encompasses a range of welfare functions, such as social welfare ($p = 1$), Nash social welfare ($p \to 0$), and egalitarian welfare ($p \to -\infty$). We give an algorithm that, for subadditive valuations and any given $p \in (-\infty, 1]$, computes (in the value oracle model and in polynomial time) an allocation with $p$-mean welfare at least $\frac{1}{8n}$ times the optimal. Further, we show that our approximation guarantees are essentially tight for XOS and, hence, subadditive valuations. We adapt a result of Dobzinski et al. (2010) to show that, under XOS valuations, an $O \left(n^{1-\varepsilon} \right)$ approximation for the $p$-mean welfare for any $p \in (-\infty,1]$ (including the Nash social welfare) requires exponentially many value queries; here, $\varepsilon>0$ is any fixed constant.

preprint2020arXiv

Uniform Welfare Guarantees Under Identical Subadditive Valuations

We study the problem of allocating indivisible goods among agents that have an identical subadditive valuation over the goods. The extent of fairness and efficiency of allocations is measured by the generalized means of the values that the allocations generate among the agents. Parameterized by an exponent term $p$, generalized-mean welfares encompass multiple well-studied objectives, such as social welfare, Nash social welfare, and egalitarian welfare. We establish that, under identical subadditive valuations 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 \in (-\infty, 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.

preprint2013arXiv

Decomposition Methods for Large Scale LP Decoding

When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode error-correcting codes at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper we draw on decomposition methods from optimization theory, specifically the Alternating Directions Method of Multipliers (ADMM), to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a "two-slice" characterization of the geometry of the parity polytope, which is the convex hull of all codewords of a single parity check code. This new characterization simplifies the representation of points in the polytope. Using this simplification, we develop an efficient algorithm for Euclidean norm projection onto the parity polytope. This projection is required by ADMM and allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We present numerical results for LDPC codes of lengths more than 1000. The waterfall region of LP decoding is seen to initiate at a slightly higher signal-to-noise ratio than for sum-product BP, however an error floor is not observed for LP decoding, which is not the case for BP. Our implementation of LP decoding using ADMM executes as fast as our baseline sum-product BP decoder, is fully parallelizable, and can be seen to implement a type of message-passing with a particularly simple schedule.

preprint2013arXiv

Network Design with Coverage Costs

We study network design with a cost structure motivated by redundancy in data traffic. We are given a graph, g groups of terminals, and a universe of data packets. Each group of terminals desires a subset of the packets from its respective source. The cost of routing traffic on any edge in the network is proportional to the total size of the distinct packets that the edge carries. Our goal is to find a minimum cost routing. We focus on two settings. In the first, the collection of packet sets desired by source-sink pairs is laminar. For this setting, we present a primal-dual based 2-approximation, improving upon a logarithmic approximation due to Barman and Chawla (2012). In the second setting, packet sets can have non-trivial intersection. We focus on the case where each packet is desired by either a single terminal group or by all of the groups, and the graph is unweighted. For this setting we present an O(log g)-approximation. Our approximation for the second setting is based on a novel spanner-type construction in unweighted graphs that, given a collection of g vertex subsets, finds a subgraph of cost only a constant factor more than the minimum spanning tree of the graph, such that every subset in the collection has a Steiner tree in the subgraph of cost at most O(log g) that of its minimum Steiner tree in the original graph. We call such a subgraph a group spanner.

preprint2013arXiv

Query Complexity of Correlated Equilibrium

We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an n-player game is specified via a black box that returns players' utilities at pure action profiles. In this model we establish that in order to compute a correlated equilibrium any deterministic algorithm must query the black box an exponential (in n) number of times.

preprint2013arXiv

Small-Support Approximate Correlated Equilibria

We prove the existence of approximate correlated equilibrium of support size polylogarithmic in the number of players and the number of actions per player. In particular, using the probabilistic method, we show that there exists a multiset of polylogarithmic size such that the uniform distribution over this multiset forms an approximate correlated equilibrium. Along similar lines, we establish the existence of approximate coarse correlated equilibrium with logarithmic support. We complement these results by considering the computational complexity of determining small-support approximate equilibria. We show that random sampling can be used to efficiently determine an approximate coarse correlated equilibrium with logarithmic support. But, such a tight result does not hold for correlated equilibrium, i.e., sampling might generate an approximate correlated equilibrium of support size Ω(m) where m is the number of actions per player. Finally, we show that finding an exact correlated equilibrium with smallest possible support is NP-hard under Cook reductions, even in the case of two-player zero-sum games.

preprint2013arXiv

The Empirical Implications of Rank in Bimatrix Games

We study the structural complexity of bimatrix games, formalized via rank, from an empirical perspective. We consider a setting where we have data on player behavior in diverse strategic situations, but where we do not observe the relevant payoff functions. We prove that high complexity (high rank) has empirical consequences when arbitrary data is considered. Additionally, we prove that, in more restrictive classes of data (termed laminar), any observation is rationalizable using a low-rank game: specifically a zero-sum game. Hence complexity as a structural property of a game is not always testable. Finally, we prove a general result connecting the structure of the feasible data sets with the highest rank that may be needed to rationalize a set of observations.

preprint2012arXiv

A Bicriteria Approximation for the Reordering Buffer Problem

In the reordering buffer problem (RBP), a server is asked to process a sequence of requests lying in a metric space. To process a request the server must move to the corresponding point in the metric. The requests can be processed slightly out of order; in particular, the server has a buffer of capacity k which can store up to k requests as it reads in the sequence. The goal is to reorder the requests in such a manner that the buffer constraint is satisfied and the total travel cost of the server is minimized. The RBP arises in many applications that require scheduling with a limited buffer capacity, such as scheduling a disk arm in storage systems, switching colors in paint shops of a car manufacturing plant, and rendering 3D images in computer graphics. We study the offline version of RBP and develop bicriteria approximations. When the underlying metric is a tree, we obtain a solution of cost no more than 9OPT using a buffer of capacity 4k + 1 where OPT is the cost of an optimal solution with buffer capacity k. Constant factor approximations were known previously only for the uniform metric (Avigdor-Elgrabli et al., 2012). Via randomized tree embeddings, this implies an O(log n) approximation to cost and O(1) approximation to buffer size for general metrics. Previously the best known algorithm for arbitrary metrics by Englert et al. (2007) provided an O(log^2 k log n) approximation without violating the buffer constraint.

preprint2011arXiv

Secretary Problems with Convex Costs

We consider online resource allocation problems where given a set of requests our goal is to select a subset that maximizes a value minus cost type of objective function. Requests are presented online in random order, and each request possesses an adversarial value and an adversarial size. The online algorithm must make an irrevocable accept/reject decision as soon as it sees each request. The "profit" of a set of accepted requests is its total value minus a convex cost function of its total size. This problem falls within the framework of secretary problems. Unlike previous work in that area, one of the main challenges we face is that the objective function can be positive or negative and we must guard against accepting requests that look good early on but cause the solution to have an arbitrarily large cost as more requests are accepted. This requires designing new techniques. We study this problem under various feasibility constraints and present online algorithms with competitive ratios only a constant factor worse than those known in the absence of costs for the same feasibility constraints. We also consider a multi-dimensional version of the problem that generalizes multi-dimensional knapsack within a secretary framework. In the absence of any feasibility constraints, we present an O(l) competitive algorithm where l is the number of dimensions; this matches within constant factors the best known ratio for multi-dimensional knapsack secretary.

preprint2011arXiv

Traffic-Redundancy Aware Network Design

We consider network design problems for information networks where routers can replicate data but cannot alter it. This functionality allows the network to eliminate data-redundancy in traffic, thereby saving on routing costs. We consider two problems within this framework and design approximation algorithms. The first problem we study is the traffic-redundancy aware network design (RAND) problem. We are given a weighted graph over a single server and many clients. The server owns a number of different data packets and each client desires a subset of the packets; the client demand sets form a laminar set system. Our goal is to connect every client to the source via a single path, such that the collective cost of the resulting network is minimized. Here the transportation cost over an edge is its weight times times the number of distinct packets that it carries. The second problem is a facility location problem that we call RAFL. Here the goal is to find an assignment from clients to facilities such that the total cost of routing packets from the facilities to clients (along unshared paths), plus the total cost of "producing" one copy of each desired packet at each facility is minimized. We present a constant factor approximation for the RAFL and an O(log P) approximation for RAND, where P is the total number of distinct packets. We remark that P is always at most the number of different demand sets desired or the number of clients, and is generally much smaller.

Siddharth Barman

Quick read

Decide how to stay connected

How to connect with this researcher

Open a focused conversation when the fit is right

See the researcher in context

Building this graph slice

18 published item(s)

Introspectively Envy-Free and Efficient Allocation of Indivisible Mixed Manna

Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations

Fairness and Welfare Quantification for Regret in Multi-Armed Bandits

Nash Welfare Guarantees for Fair and Efficient Coverage

Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations

Tight Approximation Bounds for Maximum Multi-Coverage

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

Approximation Algorithms for Maximin Fair Division

Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations

Uniform Welfare Guarantees Under Identical Subadditive Valuations

Decomposition Methods for Large Scale LP Decoding

Network Design with Coverage Costs

Query Complexity of Correlated Equilibrium

Small-Support Approximate Correlated Equilibria

The Empirical Implications of Rank in Bimatrix Games

A Bicriteria Approximation for the Reordering Buffer Problem

Secretary Problems with Convex Costs

Traffic-Redundancy Aware Network Design