# Finding an algorithm EF[1,1] and PO division for more than two agents

From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents.

We consider the problem of fairly and efficiently allocating indivisible items (goods or bads) under capacity constraints. In this setting, we are given a set of categorized items. Each category has a capacity constraint (the same for all agents), that is an upper bound on the number of items an agent can receive from each category. Our main result is a polynomial-time algorithm that solves the problem for two agents with additive utilities over the items. When each category contains items that are all goods (positively evaluated) or all chores (negatively evaluated) for each of the agents, our algorithm finds a feasible allocation of the items, which is both Pareto-optimal and envy-free up to one item. In the general case, when each item can be a good or a chore arbitrarily, our algorithm finds an allocation that is Pareto-optimal and envy-free up to one good and one chore.

Two important considerations in item allocation are efficiency and fairness. As an efficiency criterion, we use Pareto optimality (PO), which means that no other feasible allocation is at least as good for all agents and strictly better for some agent. As fairness criteria, we use two relaxations of envy-freeness (EF).

With capacity constraints, an EF1 allocation may not exist. For example, consider a scenario with one category with two items, $$o_1$$ and $$o_2$$, and capacity constraint of 1. $$o_1$$ is a good for both agents (e.g., $$u_1(o_1) = u_2(o_1) = 1$$), and $$o_2$$ is a chore for both agents (e.g., $$u_1(o_2) = u_2(o_2) = -1$$). Clearly, in every feasible allocation, one agent must receive the good and the other agent must receive the chore (due to the capacity constraint), and thus the allocation is not EF1. Therefore, we introduce a natural relaxation of it, which we call envy-freeness up to one good and one chore (EF[1,1]). It means that, for each pair of agents 𝑖, 𝑗, there exists a chore in 𝑖’s bundle, and a good in 𝑗’s bundle, such that both are in the same category, and after removing them, 𝑖 would not be jealous of 𝑗. In the special case in which, for each agent and category, either all items are goods or all items are chores (as in the student project example above), EF[1,1] is equivalent to EF1. We call this special case a samesign instance; note that it is still more general than only-goods or only-chores settings. More details are in above link.

Algorithm 1 Finding an EF[1,1] and PO division for two agents according to the above research paper at page number 8


// Step 1: Find a 𝑤-maximal feasible allocation that is EF for
some agent.

1: 𝐴 = (𝐴1,𝐴2) <-- a 𝑤-maximal allocation, for w1 = w2 = 0.5.

2: if 𝐴 is EF[1,1] then

3:    return 𝐴

4: end if

5: if 𝐴 is EF for agent 2 then

6:     replace the names of agent 1 and agent 2

7: end if

// We can now assume that agent 2 is jealous.

// Step 2: Build a set of item-pairs whose replacement increases
agent 2’s utility:

8: item-pairs <-- all the exchangeable pairs o1, o2 ∈ 𝐴1,𝐴2, for
which u2(o1) > u2(o2)

9: current-pair <-- (o1, o2) where 𝑟_{2/1} (o1, o2) is maximal.

// Step 3: Switch items in order until an EF[1,1] allocation is
found:

10: while 𝐴 = (𝐴1,𝐴2) is not EF[1,1] do

11:     Switch current-pair between the agents.

12:     Update item-pairs list and current-pair (Steps 8, 9).

13: end while

14: return A


My Question

My question is how to write the algorithm for more than two agents,proof of the correctness of the algorithm,and complexity analysis of the algorithm?

My try

To extend the algorithm for more than two agents, we can start with a weighted allocation where each agent initially has equal weight and perform item swaps to increase the weights of envious agents while preserving feasibility. Here's the algorithm:

Algorithm 2 (for n agents)

Finding an EF[1,1] and PO division for n agents:
// Step 1: Initialize weights and build an initial allocation.

1: Initialize weights 𝑤 = (1/n, 1/n, ..., 1/n).

2: 𝐴 <-- a 𝑤-maximal allocation for weights 𝑤.

// Step 2: Perform item swaps to improve envious agents' utilities.

3: while 𝐴 is not EF[1,1] do

4:     Find the envious agent 𝑖 with the lowest weight.

5:      Find an item-pair (o1, o2) that benefits agent 𝑖 when swapped.

6:     Perform the swap (o1, o2) between agents to increase 𝑤𝑖.

7:     Update the allocation 𝐴 and weights 𝑤 accordingly.

8: end while

// Step 3: Return the final allocation.

9: return 𝐴



Complexity Analysis for More Than Two Agents:

The complexity analysis for this extended algorithm depends on the number of iterations in the while loop and the time required for each iteration. Here's the complexity analysis:

Finding the initial 𝑤-maximal allocation: This step involves finding a maximum weighted matching in a bipartite graph, similar to the two-agent case. The time complexity remains 𝑂(𝑚^3), where 𝑚 is the number of items.

Iterations in the while loop: In each iteration, we identify the envious agent with the lowest weight and find an item-pair to swap. The number of iterations depends on the complexity of finding these item-pairs.

Finding item-pairs: This step involves scanning through items in the allocation and considering potential swaps. For each agent, there can be at most 𝑚 item-pairs to consider. Therefore, the complexity of finding item-pairs is 𝑂(𝑚^2).

Performing a swap: Performing a swap between two agents and updating the allocation and weights can be done in 𝑂(𝑚) time.

Overall, the number of iterations in the while loop can vary, but in the worst case, it can be 𝑂(𝑚) iterations. Therefore, the time complexity of the algorithm for more than two agents is 𝑂(𝑚^3 + 𝑚^2 * 𝑚) = 𝑂(𝑚^4).

Proof of Correctness (for More Than Two Agents):

To prove the correctness of the algorithm for more than two agents, we need to show that it terminates with an EF[1,1] and Pareto-optimal allocation.

Termination: The algorithm will terminate because in each iteration, we select the envious agent with the lowest weight, and we perform item swaps that benefit this agent, which increases their weight. The weights of agents are non-negative and sum to 1, so the weights cannot keep increasing indefinitely.

EF[1,1] Guarantee: In each iteration, we ensure that the allocation remains EF[1,1] because we select item-pairs that benefit the envious agent without making other agents worse off. This guarantees that the final allocation is EF[1,1].

Pareto-Optimality (PO): The algorithm starts with a 𝑤-maximal allocation, which is already PO for the initial weights 𝑤. In each iteration, we improve the utilities of envious agents without reducing the utility of others. Therefore, the final allocation remains PO.

Thus, the algorithm terminates with an EF[1,1] and Pareto-optimal allocation for more than two agents.

References

Hila Shoshan,Noam Hazon, Erel Segal-Halevi "Efficient Nearly-Fair Division with Capacity Constraints".

Cap