Recently, the problem of allocating one resource per agent with initial endowments () has seen a renewed interest: indeed, while in the general domain Top Trading Cycle is known to be the only procedure guaranteeing Pareto-optimality, individual rationality, and strategy proofness, the situation differs in single-peaked domains. Bade (2019) presented the Crawler, an alternative procedure enjoying the same properties (with the additional advantage of being implementable in obviously dominant strategies); while (2015) showed that allowing mutually beneficial swap-deals among the agents was already enough to guarantee Pareto-optimality. In this paper we significantly deepen our understanding of this decentralized procedures: we show in particular that the single-peaked domains happen to be maximal'' if one wishes to guarantee this convergence property. Interestingly, we also observe that the set of allocations reachable by swap-deals always contains the outcome of the Crawler. To further investigate how these different mechanisms compare, we pay special attention to the average and minimum rank of the resource obtained by the agents in the outcome allocation. We provide theoretical bounds on the loss potentially induced by these procedures with respect to these criteria, and complement these results with an extensive experimental study which shows how different variants of swap dynamics behave. In fact, even the simplest dynamics exhibit very good results, and it is possible to further guide the process towards our objectives, if one is ready to sacrifice a bit in terms of decentralization. On our way, we also show that a simple variant of the Crawler allows to check efficiently that an allocation is Pareto-optimal in single-peaked domains.
Most of the procedures we talked about, among which the TTC algorithm, are centralized procedures which rely on a benevolent entity to proceed. Of particular interest for us are the decentralized procedures. A growing literature exists on such procedures. @cite_21 and @cite_14 respectively introduced the and the , two semi-decentralized procedures where the agents announce their preferred resources to a referee. These procedures return envy-free and balanced allocations when there are two agents. Another semi-decentralized procedure is the in which agents come in turn to pick one of the remaining resource .
@cite_14 @cite_21
2156641215 2063574089
We propose a procedure for dividing indivisible items between two players in which each player ranks the items from best to worst. It ensures that each player receives a subset of items that it values more than the other player's complementary subset, given that such an envy-free division is possible. We show that the possibility of one player's undercutting the other's proposal, and implementing the reduced subset for himself or herself, makes the proposer "reasonable" and generally leads to an envy-free division, even when the players rank items exactly the same. Although the undercut procedure is manipulable, each player's maximin strategy is to be truthful. Applications of the undercut procedure are briefly discussed. The paper investigates how far a particular procedure, called the “descending demand procedure,” can take us in finding equitable allocations of indivisible goods. Both interpersonal and intrapersonal criteria of equitability are considered. It is shown that the procedure generally fares well on an interpersonal criterion of “balancedness”; specifically, the resulting allocations are Pareto-optimal and maximize the well-being of the worst-off individual. As a criterion of intrapersonal equitability, the property of envy-freeness is considered. To accommodate envy-freeness, a modification of the basic procedure is suggested. With two individuals, the modified procedure is shown to select the envy-free allocations that are balanced, i.e. the allocations that maximize the well-being of the worse-off individual among all envy-free allocations.