EFX Allocation to Chores over Small Graph

When allocating indivisible items among agents, achieving envy-free (EF) allocation is not always feasible. Hence a specific area of interest lies in determining whether envy-freeness up to any item (EFX) allocation is feasible for indivisible items. The existence of EFX allocations poses a significant open problem in the field of fair division, even when considering additive valuations. However, while there is a wealth of research on the allocation of goods, relatively little is known about the allocation of chores. Notably, for instances involving bi-valued valuations, existence results have only been established for cases involving three agents. Therefore, we study a natural relaxation of these two fairness constraints, where agents are located on the node of a linear graph and the envy is only possible between adjacent agents. Our main contribution lies in determining the impact of the number of special agents and the presence of arrows in scenarios involving four agents, finding the algorithm that guarantees an EFX allocation when allocating m indivisible bi-valued chores among four linearly structured agents.