The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Jorg Rothe - One of the best experts on this subject based on the ideXlab platform.
-
The price to pay for forgoing normalization in fair division of Indivisible Goods
Annals of Mathematics and Artificial Intelligence, 2019Co-Authors: Pascal Lange, Nhan-tam Nguyen, Jorg RotheAbstract:We study the complexity of fair division of Indivisible Goods and consider settings where agents can have nonzero utility for the empty bundle. This is a deviation from a common normalization assumption in the literature, and we show that this inconspicuous change can lead to an increase in complexity: In particular, while an allocation maximizing social welfare by the Nash product is known to be easy to detect in the normalized setting whenever there are as many agents as there are resources, without normalization it can no longer be found in polynomial time, unless P = NP. The same statement also holds for egalitarian social welfare. Moreover, we show that it is NP-complete to decide whether there is an allocation whose Nash product social welfare is above a certain threshold if the number of resources is a multiple of the number of agents. Finally, we consider elitist social welfare and prove that the increase in expressive power by allowing negative coefficients again yields NP-completeness.
-
Approximation and complexity of the optimization and existence problems for maximin share, proportional share, and minimax share allocation of Indivisible Goods
Autonomous Agents and Multi-Agent Systems, 2018Co-Authors: Tobias Heinen, Nhan-tam Nguyen, Trung Thanh Nguyen, Jorg RotheAbstract:This paper is concerned with various types of allocation problems in fair division of Indivisible Goods, aiming at maximin share, proportional share, and minimax share allocations. However, such allocations do not always exist, not even in very simple settings with two or three agents. A natural question is to ask, given a problem instance, what is the largest value c for which there is an allocation such that every agent has utility of at least c times her fair share. We first prove that the decision problem of checking if there exists a minimax share allocation for a given problem instance is $$\mathrm {NP}$$ NP -hard when the agents’ utility functions are additive. We then show that, for each of the three fairness notions, one can approximate c by a polynomial-time approximation scheme, assuming that the number of agents is fixed. Next, we investigate the restricted cases when utility functions have values in $$\{0,1\}$$ { 0 , 1 } only or are defined based on scoring vectors (Borda and lexicographic vectors), and we obtain several tractability results for these cases. Interestingly, we show that maximin share allocations can always be found efficiently with Borda utilities, which cannot be guaranteed for general additive utilities. In the nonadditive setting, we show that there exists a problem instance for which there is no c -maximin share allocation, for any constant c . We explore a class of symmetric submodular utilities for which there exists a tight $$\frac{1}{2}$$ 1 2 -maximin share allocation, and show how it can be approximated to within a factor of $$\nicefrac {1}{4}$$ 1 4 .
-
sequential allocation rules are separable refuting a conjecture on scoring based allocation of Indivisible Goods
Adaptive Agents and Multi-Agents Systems, 2018Co-Authors: Benno Kuckuck, Jorg RotheAbstract:Baumeister et al. (2017) introduced scoring allocation correspondences and rules, parameterized by an aggregation function * (such as + and min) and a scoring vector s. Among the properties they studied is separability, a.k.a. consistency (Thomson, 2011), a central property important in many social decision contexts. Baumeister et al. (2017) show that some common scoring allocation rules fail to be separable and conjecture that "(perhaps under mild conditions on s and *), no positional scoring allocation rule is separable.'' We refute this conjecture by showing that (1) the family of sequential allocation rules---an elicitation-free protocol for allocating Indivisible Goods based on picking sequences (Kohler and Chandrasekaran, 1971)---is separable for each coherent collection of picking sequences, and (2) every sequential allocation rule can be expressed as a scoring allocation rule for a suitable choice of scoring vector and social welfare ordering.
-
strategy proofness of scoring allocation correspondences for Indivisible Goods
Social Choice and Welfare, 2018Co-Authors: Nhan-tam Nguyen, Dorothea Baumeister, Jorg RotheAbstract:We study strategy-proofness in a model of resource allocation due to Brams and King (Ration Soc 17:387–421, 2005) and Brams et al. (Theory Decis 55:147–180, 2003), further developed by Baumeister et al. (J Auton Agents Multi Agent Syst 31(3):628–655, 2017). We assume resources to be Indivisible and nonshareable and that agents have responsive preferences over the power set of the resources, but only submit ordinal preferences over single resources to the social planner. Using scoring vectors, these ordinal preferences induce additive utility functions. We then focus on allocation correspondences that maximize utilitarian social welfare, and we use extension principles (from social choice theory, such as the Kelly and the Gardenfors extension) for preferences to study manipulation of allocation correspondences. We characterize strategy-proofness of the utilitarian allocation correspondence: It is Gardenfors/Kelly-strategy-proof if and only if the number of different values in the scoring vector is at most two or the number of occurrences of the greatest value in the scoring vector is larger than half the number of resources.
-
approximate solutions to max min fair and proportionally fair allocations of Indivisible Goods
Adaptive Agents and Multi-Agents Systems, 2017Co-Authors: Nhan-tam Nguyen, Trung Thanh Nguyen, Jorg RotheAbstract:Max-min fair allocations and proportionally fair allocations are desirable outcomes in a fair division of Indivisible Goods. Unfortunately, such allocations do not always exist, not even in very simple settings with few agents. A natural question is to ask about the largest value c for which there is an allocation such that every agent has utility of at least c times her fair share. Our goal is to approximate this value c. For additive utilities, we show that when the number of agents is fixed, one can approximate c by a polynomial-time approximation scheme. We show that the case when utility functions are defined based on scoring vectors (binary, Borda, and lexicographic vectors) is tractable. For 2-additive functions, we show that a bounded constant for max-min fair allocations does not exist, not even when there are only two agents. We explore a class of symmetric submodular functions for which a tight 1/2-max-min fair allocation exists and show how it can be approximated within a factor of 1/4.
Lirong Xia - One of the best experts on this subject based on the ideXlab platform.
-
welfare of sequential allocation mechanisms for Indivisible Goods
European Conference on Artificial Intelligence, 2015Co-Authors: Haris Aziz, Toby Walsh, Thomas Kalinowski, Lirong XiaAbstract:Sequential allocation is a simple and attractive mechanism for the allocation of Indivisible Goods. Agents take turns, according to a policy, to pick items. Sequential allocation is guaranteed to return an allocation which is efficient but may not have an optimal social welfare. We consider therefore the relation between welfare and efficiency. We study the (computational) questions of what welfare is possible or necessary depending on the choice of policy. We also consider a novel control problem in which the chair chooses a policy to improve social
-
welfare of sequential allocation mechanisms for Indivisible Goods
arXiv: Artificial Intelligence, 2015Co-Authors: Haris Aziz, Toby Walsh, Thomas Kalinowski, Lirong XiaAbstract:Sequential allocation is a simple and attractive mechanism for the allocation of Indivisible Goods. Agents take turns, according to a policy, to pick items. Sequential allocation is guaranteed to return an allocation which is efficient but may not have an optimal social welfare. We consider therefore the relation between welfare and efficiency. We study the (computational) questions of what welfare is possible or necessary depending on the choice of policy. We also consider a novel control problem in which the chair chooses a policy to improve social welfare.
-
strategic behavior when allocating Indivisible Goods sequentially
National Conference on Artificial Intelligence, 2013Co-Authors: Thomas Kalinowski, Toby Walsh, Nina Narodytska, Lirong XiaAbstract:We study a simple sequential allocation mechanism for allocating Indivisible Goods between agents in which agents take turns to pick items.We focus on agents behaving strategically. We view the allocation procedure as a finite repeated game with perfect information. We show that with just two agents, we can compute the unique subgame perfect Nash equilibrium in linear time. With more agents, computing the subgame perfect Nash equilibria is more difficult. There can be an exponential number of equilibria and computing even one of them is PSPACE-hard. We identify a special case, when agents value many of the items identically, where we can efficiently compute the subgame perfect Nash equilibria. We also consider the effect of externalities and modifications to the mechanism that make it strategy proof.
Sylvain Bouveret - One of the best experts on this subject based on the ideXlab platform.
-
efficiency sequenceability and deal optimality in fair division of Indivisible Goods
Adaptive Agents and Multi-Agents Systems, 2019Co-Authors: Aurelie Beynier, Sylvain Bouveret, Nicolas Maudet, Michel Lemaitre, Simon Rey, Parham ShamsAbstract:In fair division of Indivisible Goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is as follows: at each stage, a designated agent picks one object among those that remain. Another intuitive way to obtain an allocation is to give objects to agents in the first place, and to let agents exchange them as long as such "deals" are beneficial. This paper investigates these notions, when agents have additive preferences over objects, and unveils surprising connections between them, and with other efficiency and fairness notions. In particular, we show that an allocation is sequenceable if and only if it is optimal for a certain type of deals, namely cycle deals involving a single object. Furthermore, any Pareto-optimal allocation is sequenceable, but not the converse. Regarding fairness, we show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. To complete the picture, we show how some domain restrictions may affect the relations between these notions. Finally, we experimentally explore the links between the scales of efficiency and fairness.
-
positional scoring based allocation of Indivisible Goods
Autonomous Agents and Multi-Agent Systems, 2017Co-Authors: Dorothea Baumeister, Nhan-tam Nguyen, Jorg Rothe, Trung Thanh Nguyen, Sylvain Bouveret, Jerome Lang, Abdallah SaffidineAbstract:We define a family of rules for dividing m Indivisible Goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of Goods are additive, but that the input is ordinal: each agent reports her preferences simply by ranking single Goods. Similarly to positional scoring rules in voting, a scoring vector $$s = (s_1, \ldots , s_m)$$s=(s1,ź,sm) consists of m nonincreasing, nonnegative weights, where $$s_i$$si is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the Goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function $$\star $$ź such as, typically, $$+$$+ or $$\min $$min. The rule associated with s and $$\star $$ź maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.
-
Efficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences
2016Co-Authors: Sylvain Bouveret, Michel LemaitreAbstract:In fair division of Indivisible Goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is the following: at each stage, a designated agent picks one object among those that remain. This paper, restricted to the case where the agents have numerical additive preferences over objects, revisits to some extent the seminal paper by Brams and King [9] which was specific to ordinal and linear order preferences over items. We point out similarities and differences with this latter context. In particular, we show that any Pareto-optimal allocation (under additive preferences) is sequenceable, but that the converse is not true anymore. This asymmetry leads naturally to the definition of a " scale of efficiency " having three steps: Pareto-optimality, sequenceability without Pareto-optimality, and non-sequenceability. Finally, we investigate the links between these efficiency properties and the " scale of fairness " we have described in an earlier work [7]: we first show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. Then we experimentally explore the links between the scales of efficiency and fairness.
-
scoring rules for the allocation of Indivisible Goods
European Conference on Artificial Intelligence, 2014Co-Authors: Dorothea Baumeister, Nhan-tam Nguyen, Trung Thanh Nguyen, Sylvain Bouveret, Jerome Lang, Jorg RotheAbstract:We define a family of rules for dividing m Indivisible Goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of Goods are additive, but that the input is ordinal: each agent simply ranks single Goods. Similarly to (positional) scoring rules in voting, a scoring vector s = (s1,...,sm) consists of m nonincreasing nonnegative weights, where si is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the Goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function * such as, typically, + or min. The rule associated with s and * maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.
-
characterizing conflicts in fair division of Indivisible Goods using a scale of criteria
Adaptive Agents and Multi-Agents Systems, 2014Co-Authors: Sylvain Bouveret, Michel LemaitreAbstract:We investigate five different fairness criteria in a simple model of fair resource allocation of Indivisible Goods based on additive preferences. We show how these criteria are connected to each other, forming an ordered scale that can be used to characterize how conflicting the agents' preferences are: the less conflicting the preferences are, the more demanding criterion this instance will be able to satisfy, and the more satisfactory the allocation will be. We analyze the computational properties of the five criteria, give some experimental results about them, and further investigate a slightly richer model with k-additive preferences.
Joachim Schauer - One of the best experts on this subject based on the ideXlab platform.
-
maximizing nash product social welfare in allocating Indivisible Goods
European Journal of Operational Research, 2015Co-Authors: Andreas Darmann, Joachim SchauerAbstract:Abstract We consider the problem of allocating Indivisible Goods to agents who have preferences over the Goods. In such a setting, a central task is to maximize social welfare. In this paper, we assume the preferences to be additive and measure social welfare by means of the Nash product. We focus on the computational complexity involved in maximizing Nash product social welfare when scores inherent in classical voting procedures such as approval or Borda voting are used to associate utilities with the agents’ preferences. In particular, we show that the maximum Nash product social welfare can be computed efficiently when approval scores are used, while for Borda and lexicographic scores the corresponding decision problem becomes NP -complete.
-
maximizing nash product social welfare in allocating Indivisible Goods
Social Science Research Network, 2014Co-Authors: Andreas Darmann, Joachim SchauerAbstract:We consider the problem of allocating Indivisible Goods to agents who have preferences over the Goods. In such a setting, a central task is to maximize social welfare. In this paper, we assume the preferences to be additive, and measure social welfare by means of the Nash product. We focus on the computational complexity involved in maximizing Nash product social welfare when scores inherent in classical voting procedures such as Approval or Borda voting are used to associate utilities with the agents' preferences. In particular, we show that the maximum Nash product social welfare can be computed efficiently when Approval scores are used, while for Borda and Lexicographic scores the problem becomes NP-complete.
Jerome Lang - One of the best experts on this subject based on the ideXlab platform.
-
positional scoring based allocation of Indivisible Goods
Autonomous Agents and Multi-Agent Systems, 2017Co-Authors: Dorothea Baumeister, Nhan-tam Nguyen, Jorg Rothe, Trung Thanh Nguyen, Sylvain Bouveret, Jerome Lang, Abdallah SaffidineAbstract:We define a family of rules for dividing m Indivisible Goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of Goods are additive, but that the input is ordinal: each agent reports her preferences simply by ranking single Goods. Similarly to positional scoring rules in voting, a scoring vector $$s = (s_1, \ldots , s_m)$$s=(s1,ź,sm) consists of m nonincreasing, nonnegative weights, where $$s_i$$si is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the Goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function $$\star $$ź such as, typically, $$+$$+ or $$\min $$min. The rule associated with s and $$\star $$ź maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.
-
fair division of Indivisible Goods
Economics and Computation, 2016Co-Authors: Jerome Lang, Jorg RotheAbstract:Chapters 4, 5, and 6 focused on collective decision making problems (especially, voting) with the default assumption that all agents are concerned with the outcome as a whole, and therefore, all agents are expected to have, and to express, preferences over all alternatives.
-
scoring rules for the allocation of Indivisible Goods
European Conference on Artificial Intelligence, 2014Co-Authors: Dorothea Baumeister, Nhan-tam Nguyen, Trung Thanh Nguyen, Sylvain Bouveret, Jerome Lang, Jorg RotheAbstract:We define a family of rules for dividing m Indivisible Goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of Goods are additive, but that the input is ordinal: each agent simply ranks single Goods. Similarly to (positional) scoring rules in voting, a scoring vector s = (s1,...,sm) consists of m nonincreasing nonnegative weights, where si is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the Goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function * such as, typically, + or min. The rule associated with s and * maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.
-
a general elicitation free protocol for allocating Indivisible Goods
International Joint Conference on Artificial Intelligence, 2011Co-Authors: Sylvain Bouveret, Jerome LangAbstract:We consider the following sequential allocation process. A benevolent central authority has to allocate a set of Indivisible Goods to a set of agents whose preferences it is totally ignorant of. We consider the process of allocating objects one after the other by designating an agent and asking her to pick one of the objects among those that remain. The problem consists in choosing the "best" sequence of agents, according to some optimality criterion. We assume that agents have additive preferences over objects. The choice of an optimality criterion depends on three parameters: how utilities of objects are related to their ranking in an agent's preference relation; how the preferences of different agents are correlated; and how social welfare is defined from the agents' utilities. We address the computation of a sequence maximizing expected social welfare under several assumptions. We also address strategical issues.
-
efficiency and envy freeness in fair division of Indivisible Goods logical representation and complexity
Journal of Artificial Intelligence Research, 2008Co-Authors: Sylvain Bouveret, Jerome LangAbstract:We consider the problem of allocating fairly a set of Indivisible Goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case.
