|
We study the problem of fairly allocating a set of indivisible goods between two agents with additive valuations. Fair distribution has become an emerging research topic in computer science and artificial intelligence, and envy-free is the most widely studied concept of fairness. Envy-free allocation always exists when goods are divisible, but not always for indivisible goods, which motivates us to study envy-free relaxation. In this paper, we introduce a novel solution concept called EFS1, in which envy between two agents can be eliminated by swapping a good in the bundle of the two agents. Furthermore, we propose an efficient algorithm capable of finding such allocations in polynomial time, and we demonstrate the algorithm's execution through an example involving a dummy good. Our research offers promising solutions for addressing envy in allocation scenarios with the introduction of the EFS1 concept and an efficient algorithm.
|
