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.
The idea of using swap deals was explored for instance by @cite_31 , who studied barter exchange networks. @cite_34 and @cite_12 studied dynamics of swap-deals by considering an underlying social network constraining the possible interactions of the agents, and focusing on complexity issues. These results were recently extended by @cite_19 .
@cite_19 @cite_31 @cite_34 @cite_12
2064109654 2296489440 2741643477 2888333077
Of late online social networks have become popular, with interest spanning various aspects including search, analysis mining, and their potential use for item barter exchange markets. The idea is that users can leverage their social network for exchanging items they possess with other users. The problem of generating recommendations for item exchanges between users, consisting of synchronous exchange cycles has been investigated[2]. In this paper, we identify the shortcomings of the above exchange model and propose an asynchronous model that makes use of credit points. Rather than insist on exchanging items synchronously, we award points to users whenever they give items to other users, which can be redeemed later. Points and their redemption raise an issue of fairness which intuitively means users who contribute more should have a greater priority over others for receiving items they wish for. We focus on fairness maximization and prove that it is NPhard and cannot be approximated within any factor in polynomial time unless P=NP. We then develop efficient heuristic algorithms, and experimentally demonstrate their effectiveness and scalability on both synthetic data and a real dataset from readitswapit.co.uk. This article deals with object allocation where each agent receives a single item. Starting from an initial endowment, the agents can be better off by exchanging their objects. However, not all trades are likely because some participants are unable to communicate. By considering that the agents are embedded in a social network, we propose to study the allocations emerging from a sequence of simple swaps between pairs of neighbors in the network. This model raises natural questions regarding (i) the reachability of a given assignment, (ii) the ability of an agent to obtain a given object, and (iii) the search of Pareto-efficient allocations. We investigate the complexity of these problems by providing, according to the structure of the social network, polynomial and NP-complete cases. We examine a resource allocation problem where each agent is to be assigned exactly one object. Agents are initially endowed with a resource that they can swap with one another. However, not all exchanges are plausible: we represent required connections between agents with a social network. Agents may only perform pairwise exchanges with their neighbors and only if it brings them preferred objects. We analyze this distributed process through two dual questions. Could an agent obtain a certain object if the swaps occurred favourably? Can an agent be guaranteed a certain level of satisfaction regardless of the actual exchanges? These questions are investigated through parameterized complexity, focusing on budget constraints such as the number of exchanges an agent may be involved in or the total duration of the process.