Schelling's model considers k types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighboring agents of the same type. We are motivated by a recent line of work ...
详细信息
ISBN:
(纸本)9798400704864
Schelling's model considers k types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers neighboring agents of the same type. We are motivated by a recent line of work that studies solutions that are optimal with respect to notions related to the welfare of the agents. We explore the parameterized complexity of computing such solutions. We focus on the well-studied notions of social welfare (WO) and Pareto optimality (PO), alongside the recently proposed notions of group-welfare optimality (GWO) and utility-vector optimality (UVO), both of which lie between WO and ¶O. Firstly, we focus on the fundamental case where k=2 and there are r red agents and b blue agents. We show that all solution-notions we consider are intractable even when b=1 and that they do not admit an FPT algorithm when parameterized by r and b, unless FPT = W[1]. In addition, we show that WO and GWO remain intractable even on cubic graphs. We complement these negative results with an FPT algorithm parameterized by r, b and the maximum degree of the graph. For the general case with k types of agents, we prove that for any of the notions we consider the problem remains hard when parameterized by k for a large family of graphs that includes trees. We accompany these negative results with an XP algorithm parameterized by k and the treewidth of the graph.
We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at...
详细信息
ISBN:
(纸本)9781450392136
We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios, such as district-based elections, where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting: We study its parameterized complexity with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts, and its complexity on graphs from different classes (such as paths, stars, and trees).
Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might a...
详细信息
ISBN:
(纸本)9781450392136
Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: Given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.
暂无评论