Fair allocation of items and money
Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below. Two agents and one item With two agents and one item, it is possible to attain fairness using the following simple algorithm (which is a variant of cut and choose): Alice says a price p that she is willing to pay for the item. George chooses whether to take the item and pay p, or leave the item to Alice so that Alice pays p. This algorithm assumes that the agents have quasilinear utilities, that is, their utility is the value of items plus the amount of money that they have. If George thinks that Alice's price is low (he is willing to pay more than p), then he takes the item and pay p, and his utility is positive, so he does not envy Alice. Alice, too, does not envy George since his utility - in her eyes - is 0. Similarly, if George thinks that Alice's price is high (he is willing to pay p or more), then he leaves the item to Alice and does not envy, since Alice's utility in his eyes is negative. The paid money p can later be divided equally between the players, since an equal monetary transfer does not affect the relative utilities. Then, effectively, the buying agent pays p/2 to the selling agent. The total utility of each agent is at least 1/2 of his/her utility for the item. If the agents have different entitlements, then the paid money p should be divided between the partners in proportion to their entitlements. There are various works extending this simple idea to more than two players and more complex settings. The main fairness criteria in these works is envy-freeness. In addition, some works consider a setting in which a benevolent third-party is willing to subsidize the allocation, but wants to minimize the amount of subsidy subject to envy-freeness. This problem is called the minimum-subsidy envy-free allocation. Unit-demand agents Unit-demand agents are interested in at most a single item. Rental harmony A special case of this setting is when dividing rooms in an apartment between tenants. It is characterized by three requirements: (a) the number of agents equals the number of items, (b) each agent must get exactly one item (room), (c) the total amount of money paid by the agents must equal a fixed constant, which represents the total apartment rent. This is known as the Rental Harmony problem. More general settings In general, in the economics literature, it is common to assume that each agent has a