06443nam 2200409 450 991055869550332120230516083859.010.14279/depositonce-12056(CKB)5580000000302866(NjHacI)995580000000302866(EXLCZ)99558000000030286620230516d2021 uy 0engur|||||||||||txtrdacontentcrdamediacrrdacarrierAlgorithmic aspects of resource allocation and multiwinner voting theory and experiments /Andrzej KaczmarczykBerlin :Universitätsverlag der Technischen Universität Berlin,2021.1 online resource (228 pages)Foundations of Computing ;153-7983-3216-9 This thesis is concerned with investigating elements of computational social choice in the light of real-world applications. We contribute to a better understanding of the areas of fair allocation and multiwinner voting. For both areas, inspired by real-world scenarios, we propose several new notions and extensions of existing models. Then, we analyze the complexity of answering the computational questions raised by the introduced concepts. To this end, we look through the lens of parameterized complexity. We identify different parameters which describe natural features specific to the computational problems we investigate. Exploiting the parameters, we successfully develop efficient algorithms for spe- cific cases of the studied problems. We complement our analysis by showing which parameters presumably cannot be utilized for seeking efficient algorithms. Thereby, we provide comprehensive pictures of the computational complexity of the studied problems. Specifically, we concentrate on four topics that we present below, grouped by our two areas of interest. For all but one topic, we present experimental studies based on implementations of newly developed algorithms. We first focus on fair allocation of indivisible resources. In this setting, we consider a collection of indivisible resources and a group of agents. Each agent reports its utility evaluation of every resource and the task is to "fairly" allocate the resources such that each resource is allocated to at most one agent. We concentrate on the two following issues regarding this scenario. The social context in fair allocation of indivisible resources. In many fair allocation settings, it is unlikely that every agent knows all other agents. For example, consider a scenario where the agents represent employees of a large corporation. It is highly unlikely that every employee knows every other employee. Motivated by such settings, we come up with a new model of graph envy-freeness by adapting the classical envy-freeness notion to account for social relations of agents modeled as social networks. We show that if the given social network of agents is simple (for example, if it is a directed acyclic graph), then indeed we can sometimes find fair allocations efficiently. However, we contrast tractability results with showing NP-hardness for several cases, including those in which the given social network has a constant degree. Fair allocations among few agents with bounded rationality. Bounded rationality is the idea that humans, due to cognitive limitations, tend to simplify problems that they face. One of its emanations is that human agents usually tend to report simple utilities over the resources that they want to allocate; for example, agents may categorize the available resources only into two groups of desirable and undesirable ones. Applying techniques for solving integer linear programs, we show that exploiting bounded rationality leads to efficient algorithms for finding envy-free and Pareto-efficient allocations, assuming a small number of agents. Further, we demonstrate that our result actually forms a framework that can be applied to a number of different fairness concepts like envy-freeness up to one good or envy-freeness up to any good. This way, we obtain efficient algorithms for a number of fair allocation problems (assuming few agents with bounded rationality). We also empirically show that our technique is applicable in practice. Further, we study multiwinner voting, where we are given a collection of voters and their preferences over a set of candidates. The outcome of a multiwinner voting rule is a group (or a set of groups in case of ties) of candidates that reflect the voters' preferences best according to some objective. In this context, we investigate the following themes. The robustness of election outcomes. We study how robust outcomes of multiwinner elections are against possible mistakes made by voters. Assuming that each voter casts a ballot in a form of a ranking of candidates, we represent a mistake by a swap of adjacent candidates in a ballot. We find that for rules such as SNTV, k-Approval, and k-Borda, it is computationally easy to find the minimum number of swaps resulting in a change of an outcome. This task is, however, NP-hard for STV and the Chamberlin-Courant rule. We conclude our study of robustness with experimentally studying the average number of random swaps leading to a change of an outcome for several rules. Strategic voting in multiwinner elections. We ask whether a given group of cooperating voters can manipulate an election outcome in a favorable way. We focus on the k-Approval voting rule and we show that the computational complexity of answering the posed question has a rich structure. We spot several cases for which our problem is polynomial-time solvable. However, we also identify NP-hard cases. For several of them, we show how to circumvent the hardness by fixed-parameter tractability. We also present experimental studies indicating that our algorithms are applicable in practice.Foundations of computing ;15.Algorithmic aspects of resource allocation and multiwinner votingElectronic data processingSocial choiceElectronic data processing.Social choice.004Kaczmarczyk Andrzej859250NjHacINjHaclBOOK9910558695503321Algorithmic aspects of resource allocation and multiwinner voting3013778UNINA02995nam 2200493 450 991053697330332120230808200343.0(CKB)3710000000929269(Au-PeEL)EBL4522420(CaPaEBR)ebr11294750(CaONFJC)MIL968697(OCoLC)962411291(ScCtBLL)b9bd1199-b2df-4698-8676-e270bd57ce0e(MiAaPQ)EBC4522420(EXLCZ)99371000000092926920161114h20162016 uy 0engurcnu||||||||rdacontentrdamediardacarrierSmart water utilities complexity made simple /Pernille Ingildsen and Gustaf OlssonLondon, England :IWA Publishing,2016.©20161 online resource (307 pages)1-78040-757-2 1-78040-758-0 Today there is increasing pressure on the water infrastructure and although unsustainable water extraction and wastewater handling can continue for a while, at some point water needs to be managed in a way that is sustainable in the long-term. We need to handle water utilities "smarter". New and effective tools and technologies are becoming available at an affordable cost and these technologies are steadily changing water infrastructure options. The quality and robustness of sensors are increasing rapidly and their reliability makes the automatic handling of critical processes viable. Online and real-time control means safer and more effective operation. The combination of better sensors and new water treatment technologies is a strong enabler for decentralised and diversified water treatment. Plants can be run with a minimum of personnel attendance. In the future, thousands of sensors in the water utility cycle will handle all the complexity in an effective way. Smart Water Utilities: Complexity Made Simple provides a framework for Smart Water Utilities based on an M-A-D (Measurement-Analysis-Decision). This enables the organisation and implementation of "Smart" in a water utility by providing an overview of supporting technologies and methods. The book presents an introduction to methods and tools, providing a perspective of what can and could be achieved. It provides a toolbox for all water challenges and is essential reading for the Water Utility Manager, Engineer and Director and for Consultants, Designers and Researchers.WaterPurificationSustainable developmentWater treatment plantsManagementWaterPurification.Sustainable development.Water treatment plantsManagement.628.162Ingildsen Pernille940730Olsson GustafMiAaPQMiAaPQMiAaPQBOOK9910536973303321Smart water utilities2776469UNINA