Research map / Learning theory and algorithms / Submodular and game algorithms
Welfare Guarantees in Schelling Segregation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Assign agents uniformly at random to topology nodes | Schelling instances with n agents · General Schelling instances | social welfare: g(n) | Helped |
| Derandomize assignment by choosing each next type to maximize conditional expected welfare | Schelling instances with n agents · General Schelling instances | social welfare: at least g(n); g(n) ≥ n/2 - 1 | Helped |
| Require a topology with minimum degree at least 2 and equal numbers of agents and nodes | Schelling instances with at least two agents of each type · Topology with minimum degree at least 2 | positive-utility agents: every agent | Helped |
| Use depth-first search to place agents of the majority type first | Schelling instances with n≥3 · General connected topologies | number of positive-utility agents: at least ceil n/2 | Helped |
| Restrict the topology to a tree | Pareto-optimal assignments · Tree topologies, n≥3 | social welfare lower bound: 1/sqrt{n} -> n/(n-1) | Helped |
Closest papers by meaning
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.85)
- The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective (AAAI 2025 · similarity 0.85)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.85)
- Maxileximin Envy Allocations and Connected Goods (AAAI 2024 · similarity 0.84)
- Maximizing Nash Social Welfare under Two-Sided Preferences (AAAI 2024 · similarity 0.84)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.