02/02/2021

Welfare Guarantees in Schelling Segregation

Martin Bullinger, Warut Suksompong, Alexandros A. Voudouris

Keywords:

Abstract Paper Similar Papers

Abstract: Schelling's model is an influential model that reveals how individual perceptions and incentives can lead to racial segregation. Inspired by a recent stream of work, we study welfare guarantees and complexity in this model with respect to several welfare measures. First, we show that while maximizing the social welfare is NP-hard, computing an assignment with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality and introduce two new optimality notions, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions. In addition, we show that for trees, it is possible to decide whether there exists an assignment that gives every agent a positive utility in polynomial time; moreover, when every node in the topology has degree at least 2, such an assignment always exists and can be found efficiently.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38947907
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 12:51 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 12:52 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 3:13 
 0
 0
 0
 0
 14:03 
 0
 0
 0
 0
 24:22 
 0
 0
 0
 0
 16:52 
 0
 0
 0
 0
 13:39 
 0
 0
 0
 0
 3:25 
 0
 0
 0
 0
 11:20 
 0
 0
 0
 0
 14:51 
 0
 0
 0
 0
 19:43 
 0
 0
 0
 0
 4:55 
 0
 0
 0
 0
 16:11 
 0
 0
 0
 0
 17:38 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 23:08 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 13:50 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 15:58 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 8:11 
 0
 0
 0
 0
 14:38 
 0
 0
 0
 0
 3:14 
 0
 0
 0
 0
 15:16 
 0
 0
 0
 0
 27:27 
 0
 0
 0
 0
 15:26 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 5:19 
 0
 0
 0
 0
 2:50 
 0
 0
 0
 0
 14:43 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 14:25 
 0
 0
 0
 0
 3:02