Author name cluster

Luca Kreisel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

AAMAS Conference 2026 Conference Paper

Fair Allocation with Initial Utilities

Niclas Boehmer
Luca Kreisel

The problem of allocating indivisible resources to agents arises in a wide range of domains, including treatment distribution and social support programs. An important goal in algorithm design for this problem is fairness, where the focus in previous work has been on ensuring that the computed allocation provides equal treatment to everyone. However, this perspective disregards that agents may start from unequal initial positions, which is crucial to consider in settings where fairness isunderstoodas equality ofoutcome. In such settings, the goal is to create an equal final outcome for everyone by leveling initial inequalities through the allocated resources. To close this gap, focusing on agents with additive utilities, we extend the classic model by assigning each agent an initial utility and study the existence and computational complexity of several new fairness notions following the principle of equality of outcome. Among others, we show that complete allocations satisfying a direct analog of envy-freeness up to one resource (EF1) may fail to exist and are computationally hard to find, forming a contrast to the classic setting without initial utilities. We propose a new, always satisfiable fairness notion, called minimum-EF1-init and design a polynomialtime algorithm based on an extended round-robin procedure to compute complete allocations satisfying this notion.

PDF

JAAMAS Journal 2024 Journal Article

Equilibria in schelling games: computational hardness and robustness

Luca Kreisel
Niclas Boehmer
Rolf Niedermeier

Abstract In the simplest game-theoretic formulation of Schelling’s model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI ’20] and Elkind et al. [IJCAI ’19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.

Details DOI

AAMAS Conference 2022 Conference Paper

Equilibria in Schelling Games: Computational Hardness and Robustness

Luca Kreisel
Niclas Boehmer
Vincent Froese
Rolf Niedermeier

In the simplest game-theoretic formulation of Schelling’s model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex. The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jumpequilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI ’20] and Elkind et al. [IJCAI ’19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.

PDF