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.
@cite_35 renewed the interest for the assignment problem in the economic literature by investigating randomized procedures. Subsequent work by @cite_32 introduced single-peaked preferences in their setting. @cite_15 later considered deterministic and probabilistic solutions under single-peaked preferences.
@cite_35 @cite_15 @cite_32
2027956524 2088605609 2088903596 2141499077
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. 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. Abstract We consider the problem of fairly allocating an infinitely divisible commodity among agents with single-peaked preferences. We search for methods of performing this division, or solutions , that satisfy the following property of consistency : any recommendation made for any economy is in agreement with the recommendation made for any "reduced" economy obtained by imagining the departure of some of the agents with their allotted consumptions. Our main result is that essentially all efficient subsolutions of the no-envy solution satisfying consistency must contain a certain solution known as the uniform rule. We also characterize the uniform rule on the basis of a "converse" of consistency and the distributional requirement of individual rationality from equal division. Journal of Economic Literature Classification Numbers: D63, D71. The random assignment problem asks for the minimum-cost perfect matching in the complete n × n bipartite graph Knn with i.i.d. edge weights, say uniform on [0, 1]. In a remarkable work by Aldous [Aldous, D. 2001. The ζ(2) limit in the random assignment problem. RSA18 381--418], the optimal cost was shown to converge to ζ(2) as n → ∞, as conjectured by Mezard and Parisi [Mezard, M., G. Parisi. 1987. On the solution of the random link matching problem. J. Phys.48 1451--1459] through the so-called cavity method. The latter also suggested a nonrigorous decentralized strategy for finding the optimum, which turned out to be an instance of the belief propagation (BP) heuristic discussed by Pearl [Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco]. In this paper we use the objective method to analyze the performance of BP as the size of the underlying graph becomes large. Specifically, we establish that the dynamic of BP on Knn converges in distribution as n → ∞ to an appropriately defined dynamic on the Poisson weighted infinite tree, and we then prove correlation decay for this limiting dynamic. As a consequence, we obtain that BP finds an asymptotically correct assignment in O(n2) time only. This contrasts with both the worst-case upper bound for convergence of BP derived by [Bayati, M., D. Shah, M. Sharma. 2008. Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Trans. Inform. Theory54(3) 1241--1251.] and the best-known computational cost of Θ(n3) achieved by Edmonds and Karp's algorithm [Edmonds, J., R. Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM19 248--264].