In this paper, the problem of the evaluation of the uncertainties that originate in the complex design process of a new system is analyzed, paying particular attention to multibody mechanical ...systems. To this end, the Wiener-Shannon’s axioms are extended to non-probabilistic events and a theory of information for non-repetitive events is used as a measure of the reliability of data. The selection of the solutions consistent with the values of the design constraints is performed by analyzing the complexity of the relation matrix and using the idea of information in the metric space. Comparing the alternatives in terms of the amount of entropy resulting from the various distribution, this method is capable of finding the optimal solution that can be obtained with the available resources. In the paper, the algorithmic steps of the proposed method are discussed and an illustrative numerical example is provided.
Fair division of indivisible items is a well-studied topic in Economics and Computer Science. The objective is to allocate items to agents in a fair manner, where each agent has a valuation for each ...subset of items. Envy-freeness is one of the most widely studied notions of fairness. Since complete envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling one is envy-freeness up to any item (EFX), where no agent envies another agent after the removal of any single item from the other agent’s bundle. However, despite significant efforts by many researchers for several years, it is known that a complete EFX allocation always exists only in limited cases. In this paper, we show that a complete EFX allocation always exists when each agent is of one of two given types, where agents of the same type have identical additive valuations. This is the first such existence result for non-identical valuations when there are any number of agents and items and no limit on the number of distinct values an agent can have for individual items. We give a constructive proof, in which we iteratively obtain a Pareto dominating (partial) EFX allocation from an existing partial EFX allocation.
We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition ...government. Our focus is on picking sequences derived from common apportionment methods, including five traditional divisor methods and the quota method. We paint a complete picture of these methods in relation to known envy-freeness and proportionality relaxations for indivisible items as well as monotonicity properties with respect to the resource, population, and weights. In addition, we provide characterizations of picking sequences satisfying each of the fairness notions, and show that the well-studied maximum Nash welfare solution fails resource- and population-monotonicity even in the unweighted setting. Our results serve as an argument in favor of using picking sequences in weighted fair division problems.
Mind the gap: Cake cutting with separation Elkind, Edith; Segal-Halevi, Erel; Suksompong, Warut
Artificial intelligence,
December 2022, 2022-12-00, 20221201, Volume:
313
Journal Article
Peer reviewed
Open access
We study the problem of fairly allocating a divisible resource, also known as cake cutting, with an additional requirement that the shares that different agents receive should be sufficiently ...separated from one another. This captures, for example, constraints arising from social distancing guidelines. While it is sometimes impossible to allocate a proportional share to every agent under the separation requirement, we show that the well-known criterion of maximin share fairness can always be attained. We then provide algorithmic analysis of maximin share fairness in this setting—for instance, the maximin share of an agent cannot be computed exactly by any finite algorithm, but can be approximated with an arbitrarily small error. In addition, we consider the division of a pie (i.e., a circular cake) and show that an ordinal relaxation of maximin share fairness can be achieved. We also prove that an envy-free or equitable allocation that allocates the maximum amount of resource exists under separation.
We present a study of a few graph-based problems motivated by fair allocation of resources in a social network. The central role in the paper is played by the following problem: What is the largest ...number of items we can allocate to the agents in the given social network so that each agent hides at most one item and overall at most k items are hidden, and no one envies its neighbors? We show that the problem admits an XP algorithm and is W1-hard parameterized by k. Moreover, within the running time, we can identify agents that should hide its items and can construct an ordering in which agents should pick items into its bundles to get a desired allocation. Besides this problem, we also consider the existence and verification versions of this problem. In the existence problem, we are given a social network, valuations, a budget, and the goal is to find an allocation without envy. In the verification problem, we are additionally given an allocation, and the goal is to determine if the allocation satisfies the required property.
This paper studies the allocation of indivisible items to agents, when each agent’s preferences are expressed by means of a directed acyclic graph. The vertices of each preference graph represent the ...subset of items approved of by the respective agent. An arc (a,b) in such a graph means that the respective agent prefers item a over item b. We introduce a new measure of dissatisfaction of an agent by counting the number of non-assigned items which are approved of by the agent and for which no more preferred item is allocated to the agent. Considering two problem variants, we seek an allocation of the items to the agents in a way that minimizes (i) the total dissatisfaction over all agents or (ii) the maximum dissatisfaction among the agents. For both optimization problems we study the status of computational complexity and obtain NP-hardness results as well as polynomial algorithms with respect to natural underlying graph structures, such as stars, trees, paths, and matchings. We also analyze the parameterized complexity of the two problems with respect to various parameters related to the number of agents, the dissatisfaction threshold, the vertex degrees of the preference graphs, and the treewidth.
PDF
