Logo Oapen
  • Search
  • Join
    • Deposit
    • For Librarians
    • For Publishers
    • For Researchers
    • Funders
    • Resources
    • OAPEN
    • For Librarians
    • For Publishers
    • For Researchers
    • Funders
    • Resources
    • OAPEN
    View Item 
    •   OAPEN Home
    • View Item
    •   OAPEN Home
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Algorithmic aspects of resource allocation and multiwinner voting: theory and experiments

    Thumbnail
    Download PDF Viewer
    Web Shop
    Author(s)
    Kaczmarczyk, Andrzej
    Collection
    AG Universitätsverlage
    Language
    English
    Show full item record
    Abstract
    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.
    URI
    https://library.oapen.org/handle/20.500.12657/54062
    DOI
    10.14279/depositonce-12056
    ISBN
    9783798332157, 9783798332164, 9783798332157
    Publisher
    Universitätsverlag der Technischen Universität Berlin
    Publisher website
    https://verlag.tu-berlin.de/
    Publication date and place
    Berlin, 2021
    Grantor
    • Deutsche Forschungsgemeinschaft - 284041127 - Algorithms for Fair Allocations (AFFA)
    Series
    Foundations of computing, 15
    Classification
    Applied mathematics
    Algorithms and data structures
    Pages
    241
    Rights
    https://creativecommons.org/licenses/by/4.0/
    • Imported or submitted locally

    Browse

    All of OAPENSubjectsPublishersLanguagesCollections

    My Account

    LoginRegister

    Export

    Repository metadata
    Logo Oapen
    • For Librarians
    • For Publishers
    • For Researchers
    • Funders
    • Resources
    • OAPEN

    Newsletter

    • Subscribe to our newsletter
    • view our news archive

    Follow us on

    License

    • If not noted otherwise all contents are available under Attribution 4.0 International (CC BY 4.0)

    Credits

    • logo EU
    • This project received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 683680, 810640, 871069 and 964352.

    OAPEN is based in the Netherlands, with its registered office in the National Library in The Hague.

    Director: Niels Stern

    Address:
    OAPEN Foundation
    Prins Willem-Alexanderhof 5
    2595 BE The Hague
    Postal address:
    OAPEN Foundation
    P.O. Box 90407
    2509 LK The Hague

    Websites:
    OAPEN Home: www.oapen.org
    OAPEN Library: library.oapen.org
    DOAB: www.doabooks.org

     

     

    Export search results

    The export option will allow you to export the current search results of the entered query to a file. Differen formats are available for download. To export the items, click on the button corresponding with the preferred download format.

    A logged-in user can export up to 15000 items. If you're not logged in, you can export no more than 500 items.

    To select a subset of the search results, click "Selective Export" button and make a selection of the items you want to export. The amount of items that can be exported at once is similarly restricted as the full export.

    After making a selection, click one of the export format buttons. The amount of items that will be exported is indicated in the bubble next to export format.