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.
Following this line of work, we assume single-peaked preferences in this paper. This domain of preferences has been introduced by @cite_36 and @cite_16 . It has been more specifically studied in voting theory and now are a very common domain of preferences . Numerous works have used single-peaked preferences in the context of fair division. @cite_23 studied the fair division problem with single-peaked preferences and divisible objects. He defines and characterizes the , the unique strategy-proof, efficient and anonymous allocation rule in this setting. The fairness properties of this rule have been subsequently explored by @cite_17 and @cite_6 @cite_2 who showed that it is envy-free, one-sided resource monotonic and consistent. As already mentioned, @cite_15 extended this research area to indivisible resources and considered the problem of assigning objects to a line under single-peaked preferences. Subsequently, @cite_18 investigated the computational aspects of this assignment problem.
@cite_18 @cite_36 @cite_6 @cite_23 @cite_2 @cite_15 @cite_16 @cite_17
2165733306 2088605609 2123389191 2027956524
We define a general notion of single-peaked preferences based on abstract betweenness relations. Special cases are the classical example of single-peaked preferences on a line, the separable preferences on the hypercube, the “multi-dimensionally single-peaked” preferences on the product of lines, but also the unrestricted preference domain. Generalizing and unifying the existing literature, we show that a social choice function is strategy-proof on a sufficiently rich domain of generalized single-peaked preferences if and only if it takes the form of voting by issues (“voting by committees”) satisfying a simple condition called the “Intersection Property.” Based on the Intersection Property, we show that the class of preference domains associated with “median spaces” gives rise to the strongest possibility results; in particular, we show that the existence of strategyproof social choice rules that are non-dictatorial and neutral requires an underlying median space. A space is a median space if, for every triple of elements, there is a fourth element that is between each pair of the triple; numerous examples are given (some well-known, some novel), and the structure of median spaces and the associated preference domains is analysed. We consider the problem of assigning indivisible goods among a group of agents with lotteries when the preference profile is single-peaked. Unfortunately, even on this restricted domain of preferences, equal treatment of equals, stochastic dominance efficiency, and stochastic dominance strategy-proofness are incompatible. This paper is devoted to the proportional representation (PR) problem when the preferences are clustered single-peaked. PR is a "multi-winner" election problem, that we study in Chamberlin and Courant's scheme [6]. We define clustered single-peakedness as a form of single-peakedness with respect to clusters of candidates, i.e. subsets of candidates that are consecutive (in arbitrary order) in the preferences of all voters. We show that the PR problem becomes polynomial when the size of the largest cluster of candidates (width) is bounded. Furthermore, we establish the polynomiality of determining the single-peaked width of a preference profile (minimum width for a partition of candidates into clusters compatible with clustered single-peakedness) when the preferences are narcissistic (i.e., every candidate is the most preferred one for some voter). Our objective is to investigate the implications of the “replacement principle” for the fair allocation of an infinitely divisible commodity among agents with single-peaked preferences. The principle says that when one of the components of the data entering the description of the problem to be solved changes, all of the relevant agents should be affected in the same direction: they all gain or they all lose. We apply it to situations in which the preferences of one of the agents may change, under the name ofwelfare-domination under preference-replacement. We show that there is no selection from the no-envy and Pareto solution satisfying it. Then, we weaken it by limiting its application to situations in which the change is not so disruptive that it turns the economy from one in which there is “too little” of the commodity to one in which there is “too much,” or conversely. We show that there is only one selection from the no-envy and Pareto solution satisfying this property andreplication-invariance. It is the “uniform rule,” a solution that has played a central role in previous analyses of the problem.Journal of Economic LiteratureClassification Numbers: D51, D63, D70.