Talk
Talk by Shraddha Pathak
Title: Non-Monotonicity in Fair Division of Graphs
Abstract:
Fairly allocating indivisible resources among agents is a fundamental problem in economics and computer science. In this talk, we will discuss fair division with *non-monotonic valuations*, where the marginal value of an item may be positive or negative depending on the set to which it is added. Specifically, we consider a graph partitioning setting in which items correspond to vertices of a graph, and the value of a bundle is determined by its cut function value in the graph, i.e., the number of edges with exactly one endpoint in the bundle. Such valuations naturally arise in applications where diversity is important, such as team formation scenarios.
We will focus on the fairness notion of envy-freeness up to one item (EF1) and explore its compatibility with several efficiency concepts such as Transfer Stability (TS) that prohibits single-item transfers that benefit one agent without making the other worse-off. For general graphs, our results reveal a non-monotonic relationship between the number of agents and the existence of allocations satisfying EF1 and TS: such allocations always exist for two agents, may fail to exist for three agents, but exist
again for all instances with four or more agents. We further show that
existence can be guaranteed for any number of agents by slightly weakening
the efficiency requirement or by restricting attention to forest graphs.
Speaker Bio:Shraddha Pathak is a PhD student at Penn State University, advised by Dr. Hadi Hosseini. Her research focuses on problems at the intersection of computer science and economics, specifically in computational social choice.
- 03 - 03 July,2026
- 09:30 am - 10:15 am
- Bharti 501