A set of indivisible goods, e.g., a car, a house, a toothbrush, . . . , has to be split among a set of agents in a fair manner. Each agent has its own valuation function for sets of goods. What constitutes a fair allocation? When does a fair allocation exist? If it exists, can we compute it efficiently? Can we approximate fair allocations?

There are three main notions of fairness: envy-based, share-based, and welfare-based. In the first part of the talk, I will discuss all three notions.

In the second part, I will concentrate on envy-freeness: Nobody should get more than I do. For indivisible goods, envy-freeness cannot be achieved in general. Think of two persons and one good which both persons like. The good has to be given to one of the persons, and the other person will envy. Envy-freeness up to any good (EFX) is a relaxation. One person may envy another person, but upon removal of any good from the other person’s bundle, the envy goes away.

Imagine the following hypothetical dialogue. Two brothers inherit the property of their parents. One says to the other. You are getting a house, a car, and a toothbrush. I envy you, because I prefer what you get over what I get. But this is OK, because, if I discard the toothbrush, I do not envy you anymore.

I will mainly discuss two results:

• For three agents and additive valuations, an EFX-allocation always exists. A valuation is additive, if the value of a bundle of items is the sum of the values of the items in the bundle (JACM ’24 , Operations Research ’24).
• For general valuations, EFX-allocations do not always exist. (arXiv ’26).