Approximation and complexity of the optimization and existence problems for maximin share,proportional share,and minimax share allocation of indivisible goods

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}\)-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\}\) 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}\)-maximin share allocation, and show how it can be approximated to within a factor of \(\nicefrac {1}{4}\).     

Majority bargaining for resource division

We address the problem of how a set of agents can decide to share a resource, represented as a unit-sized pie. The pie can be generated by the entire set but also by some of its subsets. We investigate a finite horizon non-cooperative bargaining game, in which the players take it in turns to make proposals on how the resource should for this purpose be allocated, and the other players vote on whether or not to accept the allocation. Voting is modelled as a Bayesian weighted voting game with uncertainty about the players’ weights. The agenda, (i.e., the order in which the players are called to make offers), is defined exogenously. We focus on impatient players with heterogeneous discount factors. In the case of a conflict, (i.e., no agreement by the deadline), no player receives anything. We provide a Bayesian subgame perfect equilibrium for the bargaining game and conduct an ex-ante analysis of the resulting outcome. We show that the equilibrium is unique, computable in polynomial time, results in an instant Pareto optimal outcome, and, under certain conditions provides a foundation for the core and also the nucleolus of the Bayesian voting game. In addition, our analysis leads to insights on how an individual’s bargained share is influenced by his position on the agenda. Finally, we show that, if the conflict point of the bargaining game changes, then the problem of determining the non-cooperative equilibrium becomes NP-hard even under the perfect information assumption. Our research also reveals how this change in conflict point impacts on the above mentioned results.     

Approximate solutions of moral dilemmas in multiple agent system

Moral dilemmas are one of the major issues of current research in ethical reasoning. In particular, it is well known that admitting moral dilemmas in Standard Deontic Logic generates a family of inconsistencies that are intrinsically unsolvable. Since managing dilemmas means performing preferential reasoning, we argue that one simple approach to both types of problems is by ordering actions. We notice that in general, more than local orderings between two actions, agents have intrinsic preferences based on classification issues, like the action type, and that, once we have discharged the dilemma as it is intrinsically, preferential reasoning is performed by using a second-level choice approach. Decision theory has dealt with the problem of making decisions in presence of conflicting decision criteria, and some researcher has pointed out that this is the case of moral dilemmas as well. In practice, the choice of preferences in presence of conflicting criteria can be seen as a form of preferential-ethical reasoning. Although this is certainly an important topic in multiple agent investigations, it is definitely neglected in the current investigations. It is well known that humans are quite clever in solving moral dilemmas, and the usage they make of preferential reasoning is very complex. In this paper we address the problems of preferential-ethical reasoning in a combinatorial fashion and provide an algorithm for making decisions on moral dilemmas in presence of conflicting decision criteria. We then evaluate the complexity of the algorithm and prove that this approach can be applied in practice.

---

Embedding domain-specific modelling languages in Maude specifications

We propose a formal approach for the definition and analysis of domain-specific modelling languages (dsml). The approach uses standard model-driven engineering artifacts for defining a language’s syntax (using metamodels) and its operational semantics (using model transformations). We give formal meanings to these artifacts by translating them to the Maude language: metamodels and models are mapped to equational specifications, and model transformations are mapped to rewrite rules between such specifications, which are also expressible in Maude due to Maude’s reflective capabilities. These mappings provide us, on the one hand, with abstract definitions of the mde concepts used for defining dsml, which naturally capture their intended meanings; and, on the other hand, with equivalent executable definitions, which can be directly used by Maude for formal verification. We also study a notion of operational semantics-preserving model transformations, which are model transformations between two dsml that ensure that each execution of a transformed instance is matched by an execution of the original instance. We propose a semi-decision procedure, implemented in Maude, for checking the semantics-preserving property. We also show how the procedure can be adapted for tracing finite executions of the transformed instance back to matching executions of the original one. The approach is illustrated on xspem, a language for describing the execution of activities constrained by time, precedence, and resource availability.     

Positional scoring-based allocation of indivisible goods

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)\) consists of m nonincreasing, nonnegative weights, where \(s_i\) 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 \). 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.     

A framework for organization-aware agents

Open systems are characterized by the presence of a diversity of heterogeneous and autonomous agents that act according to private goals. Organizations, such as those used in real-life to structure human activities such as task allocation, coordination and supervision, can regulate the agents’ behavior space and describe the expected behavior of the agents. Assuming an open environment, where agents are developed independently of the Organizational structures, agents need to be able to reason about the structure, so that they can deliberate about their actions and act within the expected boundaries and work towards the objectives of the organization. In this paper, we present the AORTA reasoning framework and show how it can be integrated into typical BDI-agents. We provide operational semantics that enables agents to make organizational decisions in order to coordinate and cooperate without explicit coordination mechanisms within the agents. The organizational model is independent of that of the agents, and the approach is not tied to a specific organizational model, but uses an organizational metamodel. We show how AORTA helps agents work together in a system with an organization for choosing the best tender for a building project.     

Facility location with double-peaked preferences

We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations. We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. As a motivating example, assume that the government plans to build a primary school along a street; an agent with single-peaked preferences would prefer having the school built exactly next to her house. However, while that would make it very easy for her children to go to school, it would also introduce several problems, such as noise or parking congestion in the morning. A 5-min walking distance would be sufficiently far for such problems to no longer be much of a factor and at the same time sufficiently close for the school to be easily accessible by the children on foot. There are two positions (symmetrically) in each direction and those would be the agent’s two peaks of her double-peaked preference. Motivated by natural scenarios like the one described above, we mainly focus on the case where peaks are equidistant from the agents’ locations and discuss how our results extend to more general settings. We show that most of the results for single-peaked preferences do not directly apply to this setting, which makes the problem more challenging. As our main contribution, we present a simple truthful-in-expectation mechanism that achieves an approximation ratio of \(1+b/c\) for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3 / 2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable strategyproof mechanisms, there is no deterministic mechanism that outperforms our truthful-in-expectation mechanism. In order to obtain this result, we first characterize mechanisms for two agents that satisfy two simple properties; we use the same characterization to prove that no mechanism in this class can be group-strategyproof.     

On the structure and complexity of worst-case equilibria

In the resource allocation game introduced by Koutsoupias and Papadimitriou, n$n$ jobs of different weights are assigned to m$m$ identical machines by selfish agents. For this game, it has been conjectured by several authors that the fully mixed Nash equilibrium (FMNE) is the worst possible w.r.t. the expected maximum load over all machines. Assuming the validity of this conjecture, computing a worst-case Nash equilibrium for a given instance was trivial, and approximating the Price of Anarchy for this instance would be possible by approximating the expected social cost of the FMNE by applying a known FPRAS.     

On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

We study the efficiency of the proportional allocation mechanism that is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the Price of Anarchy (PoA) of the induced game under complete and incomplete information. When agents’ valuations are concave, we show that the Bayesian Nash equilibria can be arbitrarily inefficient, in contrast to the well-known 4/3 bound for pure equilibria Johari and Tsitsiklis (Math. Oper. Res. 29(3), 407–435 2004). Next, we upper bound the PoA over Bayesian equilibria by 2 when agents’ valuations are subadditive, generalizing and strengthening previous bounds on lattice submodular valuations. Furthermore, we show that this bound is tight and cannot be improved by any simple or scale-free mechanism. Then we switch to settings with budget constraints, and we show an improved upper bound on the PoA over coarse-correlated equilibria. Finally, we prove that the PoA is exactly 2 for pure equilibria in the polyhedral environment.     

The analytic hierarchy process: task scheduling and resource allocation in cloud computing environment

Resource allocation is a complicated task in cloud computing environment because there are many alternative computers with varying capacities. The goal of this paper is to propose a model for task-oriented resource allocation in a cloud computing environment. Resource allocation task is ranked by the pairwise comparison matrix technique and the Analytic Hierarchy Process giving the available resources and user preferences. The computing resources can be allocated according to the rank of tasks. Furthermore, an induced bias matrix is further used to identify the inconsistent elements and improve the consistency ratio when conflicting weights in various tasks are assigned. Two illustrative examples are introduced to validate the proposed method.     

The resource allocation model for multi-process instances based on particle swarm optimization

Resource allocation in process management focuses on how to maximize process performance via proper resource allocation since the quality of resource allocation determines process outcome. In order to improve resource allocation, this paper proposes a resource allocation method, which is based on the improved hybrid particle swarm optimization (PSO) in the multi-process instance environment. Meanwhile, a new resource allocation model is put forward, which can optimize the resource allocation problem reasonably. Furthermore, some improvements are made to streamline the effectiveness of the method, so as to enhance resource scheduling results. In the end, experiments are conducted to demonstrate the effectiveness of the proposed method.     

Simple negotiation schemes for agents with simple preferences: sufficiency,necessity and maximality

We investigate the properties of an abstract negotiation framework where agents autonomously negotiate over allocations of indivisible resources. In this framework, reaching an allocation that is optimal may require very complex multilateral deals. Therefore, we are interested in identifying classes of valuation functions such that any negotiation conducted by means of deals involving only a single resource at a time is bound to converge to an optimal allocation whenever all agents model their preferences using these functions. In the case of negotiation with monetary side payments amongst self-interested but myopic agents, the class of modular valuation functions turns out to be such a class. That is, modularity is a sufficient condition for convergence in this framework. We also show that modularity is not a necessary condition. Indeed, there can be no condition on individual valuation functions that would be both necessary and sufficient in this sense. Evaluating conditions formulated with respect to the whole profile of valuation functions used by the agents in the system would be possible in theory, but turns out to be computationally intractable in practice. Our main result shows that the class of modular functions is maximal in the sense that no strictly larger class of valuation functions would still guarantee an optimal outcome of negotiation, even when we permit more general bilateral deals. We also establish similar results in the context of negotiation without side payments.     

Computing leximin-optimal solutions in constraint networks

In many real-world multiobjective optimization problems one needs to find solutions or alternatives that provide a fair compromise between different conflicting objective functions—which could be criteria in a multicriteria context, or agent utilities in a multiagent context—while being efficient (i.e. informally, ensuring the greatest possible overall agents' satisfaction). This is typically the case in problems implying human agents, where fairness and efficiency requirements must be met. Preference handling, resource allocation problems are another examples of the need for balanced compromises between several conflicting objectives. A way to characterize good solutions in such problems is to use the leximin preorder to compare the vectors of objective values, and to select the solutions which maximize this preorder. In this article, we describe five algorithms for finding leximin-optimal solutions using constraint programming. Three of these algorithms are original. Other ones are adapted, in constraint programming settings, from existing works. The algorithms are compared experimentally on three benchmark problems.     

Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs

We consider the scheduling problem in which two agents (agents A and B), each having its own job set (containing the A-jobs and B-jobs, respectively), compete to process their own jobs in a two-machine flowshop. Each agent wants to maximize a certain criterion depending on the completion times of its jobs only. Specifically, agent A desires to maximize either the weighted number of just-in-time (JIT) A-jobs that are completed exactly on their due dates or the maximum weight of the JIT A-jobs, while agent B wishes to maximize the weighted number of JIT B-jobs. Evidently four optimization problems can be formulated by treating the two agents’ criteria as objectives and constraints of the corresponding optimization problems. We focus on the problem of finding the Pareto-optimal schedules and present a bicriterion analysis of the problem. Solving this problem also solves the other three problems of bicriterion scheduling as a by-product. We show that the problems under consideration are either polynomially or pseudo-polynomially solvable. In addition, for each pseudo-polynomial-time solution algorithm, we show how to convert it into a two-dimensional fully polynomial-time approximation scheme for determining an approximate Pareto-optimal schedule. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.     

Power and welfare in bargaining for coalition structure formation

We investigate a noncooperative bargaining game for partitioning n agents into non-overlapping coalitions. The game has n time periods during which the players are called according to an exogenous agenda to propose offers. With probability \(\delta \), the game ends during any time period \(t<n\). If it does, the first t players on the agenda get a chance to propose but the others do not. Thus, \(\delta \) is a measure of the degree of democracy within the game (ranging from democracy for \(\delta =0\), through increasing levels of authoritarianism as \(\delta \) approaches 1, to dictatorship for \(\delta =1\)). We determine the subgame perfect equilibrium (SPE) and study how a player’s position on the agenda affects his bargaining power. We analyze the relation between the distribution of power of individual players, the level of democracy, and the welfare efficiency of the game. We find that purely democratic games are welfare inefficient and that introducing a degree of authoritarianism into the game makes the distribution of power more equitable and also maximizes welfare. These results remain invariant under two types of player preferences: one where each player’s preference is a total order on the space of possible coalition structures and the other where each player either likes or dislikes a coalition structure. Finally, we show that the SPE partition may or may not be core stable.     

Supporting inconsistent rules in database systems

When a set of rules generates (conflicting) values for a virtual attribute of some tuple, the system must resolve the inconsistency and decide on a unique value that is assigned to that attribute. In most current systems, the conflict is resolved based on criteria that choose one of the rules in the conflicting set and use the value that it generated. There are several applications, however, where inconsistencies of the above form arise, whose semantics demand a different form of resolution. We propose a general framework for the study of the conflict resolution problem, and suggest a variety of resolution criteria, which collectively subsume all previously known solutions. With several new criteria being introduced, the semantics of several applications are captured more accurately than in the past. We discuss how conflict resolution criteria can be specified at the schema or the rule-module level. Finally, we suggest some implementation techniques based on rule indexing, which allow conflicts to be resolved efficiently at compile time, so that at run time only a single rule is processed.An earlier version of this work appeared under the title Conflict Resolution of Rules Assigning Values to Virtual Attributes inProceedings of the 1989 ACM-Sigmod Conference, Portland, OR, June 1989, pp. 205–214.Partially supported by the National Science Foundation under Grant IRI-9157368 (PYI Award) and by grants from DEC, HP, and AT&T.Partially supported by the National Science Foundation under Grant IRI-9057573 (PYI Award), IBM, DEC, and the University of Maryland Institute for Advanced Computer Studies (UMIACS).     

An agent-based model of the emergence and evolution of a language system for boolean coordination

This paper presents an agent-based model of the emergence and evolution of a language system for Boolean coordination. The model assumes the agents have cognitive capacities for invention, adoption, abstraction, repair and adaptation, a common lexicon for basic concepts, and the ability to construct complex concepts using recursive combinations of basic concepts and logical operations such as negation, conjunction or disjunction. It also supposes the agents initially have neither a lexicon for logical operations nor the ability to express logical combinations of basic concepts through language. The results of the experiments we have performed show that a language system for Boolean coordination emerges as a result of a process of self-organisation of the agents’ linguistic interactions when these agents adapt their preferences for vocabulary, syntactic categories and word order to those they observe are used more often by other agents. Such a language system allows the unambiguous communication of higher-order logic terms representing logical combinations of basic properties with non-trivial recursive structure, and it can be reliably transmitted across generations according to the results of our experiments. Furthermore, the conceptual and linguistic systems, and simplification and repair operations of the agent-based model proposed are more general than those defined in previous works, because they not only allow the simulation of the emergence and evolution of a language system for the Boolean coordination of basic properties, but also for the Boolean coordination of higher-order logic terms of any Boolean type which can represent the meaning of nouns, sentences, verbs, adjectives, adverbs, prepositions, prepositional phrases and subexpressions not traditionally analysed as forming constituents, using linguistic devices such as syntactic categories, word order and function words.     

Reducing Early Retirement in Europe: Do Working Conditions Matter?

The paper argues that the existing literature, based on the Survey of Health, Ageing and Retirement in Europe (SHARE) data, on how working conditions impact on early retirement preferences/plans is hampered by the fact that the approach adopted to capture individuals’ early retirement plans fails to acknowledge that these preferences/plans are defined by reference to the rules that regulate the entitlement to pension benefits. In doing so, these studies risk overestimating the impact of working conditions on early retirement plans. We put forward a more accurate way of capturing individuals’ early retirement preferences/plans, which consists in using information on the age at which respondents plan to start collecting the basic pension benefits, and then computing whether the respondent plans to retire before the official age of retirement in his country of residence. Using SHARE microdata, wave 4, we show that individuals exposed to an imbalance between effort and rewards at work (Siegriest Journal Journal of Occupational Health Psychology, 1(1), 27–41, 1996 ) are more likely to plan to take-up early retirement. We also show that the effect of poor working conditions is smaller than one would find using the previous approach to the measurement of early retirement preferences/plans.