Siddharth Barman

Siddharth Barman

Auto-generated profile, based on publicly available information

Siddharth Barman

Indian Institute of Science Bangalore

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
17 July 2019 in Proceedings of the AAAI Conference on Artificial Intelligence
Verified
Journal Article
Open access
PDF file
SBSiddharth Barman
Siddharth Barman
SKSanath Kumar Krishnamurthy
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.

6 December 2020
Verified
Book Chapter
Closed access
PDF file
SBSiddharth Barman
Siddharth Barman
UBUmang Bhaskar
Umang Bhaskar
NSNisarg Shah
Nisarg Shah

26 June 2023 in Proceedings of the AAAI Conference on Artificial Intelligence
Verified
Journal Article
Open access
PDF file
SBSiddharth Barman
Siddharth Barman
AKArindam Khan
Arindam Khan
SSSudarshan Shyam
Sudarshan Shyam
KSK. V. N. Sreenivas
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.

1 July 2021 in Mathematical Programming
Verified
Journal Article
Closed access
PDF file
SBSiddharth Barman
Siddharth Barman
OFOmar Fawzi
Omar Fawzi
SGSuprovat Ghoshal
Suprovat Ghoshal
EGEmirhan Gürpınar
Emirhan Gürpınar

14 April 2020
Verified
Book Chapter
Open access
PDF file
SBSiddharth Barman
Siddharth Barman
OFOmar Fawzi
Omar Fawzi
SGSuprovat Ghoshal
Suprovat Ghoshal
EGEmirhan Gürpınar
Emirhan Gürpınar
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| \le 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\pi \ell }}\). We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture. This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as combinatorial auctions.

7 July 2023
Verified
Conference Paper
Open access
SBSiddharth Barman
Siddharth Barman
AKArindam Khan
Arindam Khan
SSSudarshan Shyam
Sudarshan Shyam
KSK. V. N. Sreenivas
K. V. N. Sreenivas
We study fair division of goods under the broad class of generalized assignment constraints. In this constraint framework, the sizes and values of the goods are agent-specific, and one needs to allocate the goods among the agents fairly while further ensuring that each agent receives a bundle of total size at most the corresponding budget of the agent. Since, in such a constraint setting, it may not always be feasible to partition all the goods among the agents, we conform---as in recent works---to the construct of charity to designate the set of unassigned goods. For this allocation framework, we obtain existential and computational guarantees for envy-free (appropriately defined) allocation of divisible and indivisible goods, respectively, among agents with individual, additive valuations for the goods. We deem allocations to be fair by evaluating envy only with respect to feasible subsets. In particular, an allocation is said to be feasibly envy-free (FEF) iff each agent prefers its bundle over every (budget) feasible subset within any other agent's bundle (and within the charity). The current work establishes that, for divisible goods, FEF allocations are guaranteed to exist and can be computed efficiently under generalized assignment constraints. Note that, in the presence of generalized assignment constraints, even the existence of such fair allocations of divisible goods is nonobvious, a priori. Our existential and computational guarantee for FEF allocations is built upon an incongruity property satisfied across a family of linear programs. This novel proof template is interesting in its own right. In the context of indivisible goods, FEF allocations do not necessarily exist, and hence, we consider the fairness notion of feasible envy-freeness up to any good (FEFx). Under this notion, an allocation of indivisible goods is declared to be fair iff for each pair of agents, a and b, envy-freeness holds for agent a against every feasible and strict subset of b's bundle; a similar guarantee is required with respect to the charity. We show that, under generalized assignment constraints, an FEFx allocation of indivisible goods always exists. In fact, our FEFx result resolves open problems posed in prior works, which provide existence guarantees under weaker fairness notions and more specialized constraints. Further, for indivisible goods and under generalized assignment constraints, we provide a pseudo-polynomial time algorithm for computing FEFx allocations, and a fully polynomial-time approximation scheme (FPTAS) for computing approximate FEFx allocations.