Fair Division of Indivisible Goods with and without Money

This work is devoted to the study of the existence and analysis of the mechanisms for finding envy-free solutions in the fair division problems with indivisible goods with and without money. The first part examines the issue of the existence of envy-free allocations in fair division problems without money. It is shown that for a class of problems without money where the utility of agents from goods is simulated by independent random variables, envy-free allocations exist with a high probability. This property was already noted, but it was based on a different approach and without an explicit estimation of probability. In this paper, a universal method is proposed for analyzing typical properties, which leads to the explicit estimate based on the approach using the apparatus of the theory of measure concentration - a universal approach that allows to investigate the typical properties of large problems. In the case of fair division problem of indivisible goods with money the opposite problem arises - there are too many envy-free solutions and we need the mechanism that will choose the most "fair" solution. In the second part of this work, the problem of distributing indivisible goods where transfers are allowed is considered by the example of the rooms allocation problem and dividing the rent between several tenants. In the classical formulation of the problem, each room goes to one agent, and it is known that there is a mechanism that always constructs an effective envy-free solution which maximizes the utility of the least satisfied agent. We consider the extension of the classical problem, where agents can be roommates, and it is proved that there is a solution without envy, but now maximizing the minimum utility can lead to ineffective solution. The work consists of six parts and includes an introduction, the main part, three chapters, conclusion and a list of references.