Britta Dorn
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Britta Dorn has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
Dominikus Krüger
Ulm University
2 shared publications- Ildikó Schlotter
ELTE Centre for Economic and Regional Studies
2 shared publications - Marjeta Kramar Fijavž
Faculty of Civil and Geodetic Engineering, University of Ljubljana, Ljubljana, Slovenia
2 shared publications - Andreas Darmann
Department of Operations and Information Systems, University of Graz, Graz, Austria
1 shared publication - Dominikus Krüger
Dominikus Krüger Institute of Theoretical Computer Science Ulm University Germany
1 shared publication Fatih Bayazit
1 shared publication
Latest Publications
- Open Access
- 23 March 2022
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 90 (4) , 339-371
Minimising inequality in multiagent resource allocation
We analyse the problem of finding an allocation of resources in a multiagent system that is as fair as possible in terms of minimising inequality between the utility levels enjoyed by the individual agents. We use the well-known Atkinson index to measure inequality and we focus on the distributed approach to multiagent resource allocation, where new allocations emerge as the result of a sequence of local deals between groups of agents who agree on an exchange of some of the items in their possession. Our results show that it is possible to design systems that provide theoretical guarantees for optimal outcomes that minimise inequality, but also that there are significant computational hurdles to be overcome in the worst case. In particular, finding an optimal allocation is computationally intractable and under the distributed approach a large number of structurally complex deals, possibly involving many agents and items, may be required before convergence to a socially optimal allocation. This remains true even in severely restricted resource allocation scenarios where all agents have the same utility function. From a methodological point of view, while much work in multiagent resource allocation relies on combinatorial arguments, here we instead use insights from basic calculus.
- 23 March 2022
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 90 (4) , 339-371
Open AccessMinimising inequality in multiagent resource allocation
We analyse the problem of finding an allocation of resources in a multiagent system that is as fair as possible in terms of minimising inequality between the utility levels enjoyed by the individual agents. We use the well-known Atkinson index to measure inequality and we focus on the distributed approach to multiagent resource allocation, where new allocations emerge as the result of a sequence of local deals between groups of agents who agree on an exchange of some of the items in their possession. Our results show that it is possible to design systems that provide theoretical guarantees for optimal outcomes that minimise inequality, but also that there are significant computational hurdles to be overcome in the worst case. In particular, finding an optimal allocation is computationally intractable and under the distributed approach a large number of structurally complex deals, possibly involving many agents and items, may be required before convergence to a socially optimal allocation. This remains true even in severely restricted resource allocation scenarios where all agents have the same utility function. From a methodological point of view, while much work in multiagent resource allocation relies on combinatorial arguments, here we instead use insights from basic calculus.
- Open Access
- 13 September 2021
- Published by Springer Nature in International Journal of Game Theory
- Vol. 51 (1) , 169-212
Simplified group activity selection with group size constraints
Several real-world situations can be represented in terms of agents that have preferences over activities in which they may participate. Often, the agents can take part in at most one activity (for instance, since these take place simultaneously), and there are additional constraints on the number of agents that can participate in an activity. In such a setting, we consider the task of assigning agents to activities in a reasonable way. We introduce the simplified group activity selection problem providing a general yet simple model for a broad variety of settings, and start investigating its special case where upper and lower bounds of the groups have to be taken into account. We apply different solution concepts such as envy-freeness and core stability to our setting and provide a computational complexity study for the problem of finding such solutions.
- 13 September 2021
- Published by Springer Nature in International Journal of Game Theory
- Vol. 51 (1) , 169-212
Open AccessSimplified group activity selection with group size constraints
Several real-world situations can be represented in terms of agents that have preferences over activities in which they may participate. Often, the agents can take part in at most one activity (for instance, since these take place simultaneously), and there are additional constraints on the number of agents that can participate in an activity. In such a setting, we consider the task of assigning agents to activities in a reasonable way. We introduce the simplified group activity selection problem providing a general yet simple model for a broad variety of settings, and start investigating its special case where upper and lower bounds of the groups have to be taken into account. We apply different solution concepts such as envy-freeness and core stability to our setting and provide a computational complexity study for the problem of finding such solutions.
- Open Access
- 26 March 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (5) , 1559-1603
Obtaining a Proportional Allocation by Deleting Items
We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number k of item deletions allowed is small—we show that the problem is $${\mathsf {W}}[3]$$ -hard with respect to the parameter k. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of |I| and k. Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation $$\pi $$ in advance as part of the input, and our aim is to delete a minimum number of items such that $$\pi $$ is proportional in the remainder; this variant turns out to be $${{\mathsf {N}}}{{\mathsf {P}}}$$ -hard for six agents, but polynomial-time solvable for two agents, and we show that it is $$\mathsf {W[2]}$$ -hard when parameterized by the number k of- 26 March 2021
- Published by Springer Nature in Algorithmica
- Vol. 83 (5) , 1559-1603
Open AccessObtaining a Proportional Allocation by Deleting Items
We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number k of item deletions allowed is small—we show that the problem is $${\mathsf {W}}[3]$$ -hard with respect to the parameter k. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of |I| and k. Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation $$\pi $$ in advance as part of the input, and our aim is to delete a minimum number of items such that $$\pi $$ is proportional in the remainder; this variant turns out to be $${{\mathsf {N}}}{{\mathsf {P}}}$$ -hard for six agents, but polynomial-time solvable for two agents, and we show that it is $$\mathsf {W[2]}$$ -hard when parameterized by the number k of - Open Access
Obtaining a Proportional Allocation by Deleting Items
We consider the following control problem on fair allocation of indivisible goods. Given a set $I$ of items and a set of agents, each having strict linear preference over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number $k$ of item deletions allowed is small, since the problem turns out to be W[3]-hard with respect to the parameter $k$. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of $|I|$ and $k$.Open AccessObtaining a Proportional Allocation by Deleting Items
We consider the following control problem on fair allocation of indivisible goods. Given a set $I$ of items and a set of agents, each having strict linear preference over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number $k$ of item deletions allowed is small, since the problem turns out to be W[3]-hard with respect to the parameter $k$. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of $|I|$ and $k$. - Open Access
- 30 December 2015
- Published by Springer Nature
- p. 314-327
Often Harder than in the Constructive Case: Destructive Bribery in CP-nets
- 30 December 2015
- Published by Springer Nature
- p. 314-327
Open AccessOften Harder than in the Constructive Case: Destructive Bribery in CP-nets
- Open Access
Often harder than in the Constructive Case: Destructive Bribery in CP-nets
We study the complexity of the destructive bribery problem---an external agent tries to prevent a disliked candidate from winning by bribery actions---in voting over combinatorial domains, where the set of candidates is the Cartesian product of several issues. This problem is related to the concept of the margin of victory of an election which constitutes a measure of robustness of the election outcome and plays an important role in the context of electronic voting. In our setting, voters have conditional preferences over assignments to these issues, modelled by CP-nets. We settle the complexity of all combinations of this problem based on distinctions of four voting rules, five cost schemes, three bribery actions, weighted and unweighted voters, as well as the negative and the non-negative scenario. We show that almost all of these cases are NP-complete or NP-hard for weighted votes while approximately half of the cases can be solved in polynomial time for unweighted votes.
Open AccessOften harder than in the Constructive Case: Destructive Bribery in CP-nets
We study the complexity of the destructive bribery problem---an external agent tries to prevent a disliked candidate from winning by bribery actions---in voting over combinatorial domains, where the set of candidates is the Cartesian product of several issues. This problem is related to the concept of the margin of victory of an election which constitutes a measure of robustness of the election outcome and plays an important role in the context of electronic voting. In our setting, voters have conditional preferences over assignments to these issues, modelled by CP-nets. We settle the complexity of all combinations of this problem based on distinctions of four voting rules, five cost schemes, three bribery actions, weighted and unweighted voters, as well as the negative and the non-negative scenario. We show that almost all of these cases are NP-complete or NP-hard for weighted votes while approximately half of the cases can be solved in polynomial time for unweighted votes.
- 18 July 2015
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 77 (3-4) , 251-279
On the hardness of bribery variants in voting with CP-nets
- 18 July 2015
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 77 (3-4) , 251-279
On the hardness of bribery variants in voting with CP-nets
- Open Access
Asymptotic periodicity of flows in time-depending networks
We consider a linear transport equation on the edges of a network with time-varying coefficients. Using methods for non-autonomous abstract Cauchy problems, we obtain well-posedness of the problem and describe the asymptotic profile of the solutions under certain natural conditions on the network. We further apply our theory to a model used for air traffic flow management.
Open AccessAsymptotic periodicity of flows in time-depending networks
We consider a linear transport equation on the edges of a network with time-varying coefficients. Using methods for non-autonomous abstract Cauchy problems, we obtain well-posedness of the problem and describe the asymptotic profile of the solutions under certain natural conditions on the network. We further apply our theory to a model used for air traffic flow management.
- Open Access
- 1 January 2013
- Published by American Institute of Mathematical Sciences (AIMS) in Networks and Heterogeneous Media
- Vol. 8 (4) , 843-855
Asymptotic periodicity of flows in time-depending networks
We consider a linear transport equation on the edges of a network with time-varying coefficients. Using methods for non-autonomous abstract Cauchy problems, we obtain well-posedness of the problem and describe the asymptotic profile of the solutions under certain natural conditions on the network. We further apply our theory to a model used for air traffic flow management.
- 1 January 2013
- Published by American Institute of Mathematical Sciences (AIMS) in Networks and Heterogeneous Media
- Vol. 8 (4) , 843-855
Open AccessAsymptotic periodicity of flows in time-depending networks
We consider a linear transport equation on the edges of a network with time-varying coefficients. Using methods for non-autonomous abstract Cauchy problems, we obtain well-posedness of the problem and describe the asymptotic profile of the solutions under certain natural conditions on the network. We further apply our theory to a model used for air traffic flow management.