8 papers
Equitable Colorings of Vertex-Weighted Graphs
Siddharth Barman, Vignesh Viswanathan
We study a generalization of the classical Hajnal-Szemerédi theorem to vertex-weighted graphs. Given a graph with nonnegative vertex weights, a coloring is called -approximate…
Existence and Computation of Fair Allocations under Constraints
Siddharth Barman, Ioannis Caragiannis, Sudarshan Shyam
We study fair division of divisible goods under generalized assignment constraints. Here, each good has an agent-specific value and size, and every agent has a budget constraint th…
Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning
Siddharth Barman, Paritosh Verma
This paper studies fair division of divisible and indivisible items among agents whose cardinal preferences are not necessarily monotone. We establish the existence of fair divisio…
Introspectively Envy-Free and Efficient Allocation of Indivisible Mixed Manna
Siddharth Barman, Paritosh Verma
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…
Compatibility of Fairness and Nash Welfare under Subadditive Valuations
Siddharth Barman, Mashbat Suzuki
We establish a compatibility between fairness and efficiency, captured via Nash Social Welfare (NSW), under the broad class of subadditive valuations. We prove that, for subadditiv…
Fair and Efficient Allocation of Indivisible Mixed Manna
Siddharth Barman, Vishwa Prakash HV, Aditi Sethia +1
We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness --…