Guido Schäfer

Approval-based multiwinner voting, one of the central topics in computational social choice, addresses collective decision-making scenarios in which n voters select a committee of k candidates from a larger pool of alternatives. A fundamental aim is to ensure that the elected committee proportionately represents the preferences of the electorate. Consequently, much effort has gone into exploring various proportionality notions and developing voting rules to achieve them. A key intuition underlying many fairness axioms and voting rules is that an optimal outcome is attained when no subset of voters can improve their position by reallocating their endorsements. In this paper, we formalize this intuition by defining a new class of games, which we call budgeting games, where committees occur as a result of voters' decisions about how to allocate a given budget. Our primary contribution lies in introducing this new class of normal-form games and showing that key notions in multiwinner voting theory, such as priceability, the core and EJR (Extended Justified Representation) can be thought of as equilibria of budgeting games. Remarkably, our budgeting games do not just capture existing concepts, but also give rise to entirely new families of voting rules. These rules, which are guaranteed to satisfy desirable fairness axioms, are based on improving-move dynamics in the respective budgeting games, and include the well-known Method of Equal Shares. Finally, we showcase the applicability of our game-theoretic perspective by proving existence of strong equilibria in a restricted version of our budgeting games, which implies that the core in a novel special case of multiwinner elections is non-empty.

The realm of algorithms with predictions has led to the development of several new algorithms that leverage predictions to enhance their performance guarantees. The challenge is to devise algorithms that achieve optimal approximation guarantees as the prediction quality varies from perfect (consistency) to imperfect (robustness). This framework is particularly appealing in mechanism design contexts, where predictions might convey private information about the agents. In this paper, we design strategyproof mechanisms that leverage predictions to achieve improved approximation guarantees for several variants of the Generalized Assignment Problem (GAP) in the private graph model. In this model, first introduced by Dughmi & Ghosh (2010), the set of resources that an agent is compatible with is private information. For the Bipartite Matching Problem (BMP), we give a deterministic group-strategyproof (GSP) mechanism that is (1 + ¹/γ)-consistent and (1 + γ)-robust, where γ ≥ 1 is some confidence parameter. We also prove that this is best possible. Remarkably, our mechanism draws inspiration from the renowned Gale-Shapley algorithm, incorporating predictions as a crucial element. Additionally, we give a randomized mechanism that is universally GSP and improves on the guarantees in expectation. The other GAP variants that we consider all make use of a unified greedy mechanism that adds edges to the assignment according to a specific order. For a special case of Restricted Multiple Knapsack, this results in a deterministic strategyproof mechanism that is (1 + ¹/γ)-consistent and (2 + γ)-robust. We then focus on two variants: Agent Size GAP (where each agent has one size) and Value Consensus GAP (where all agents have the same preference order over resources). For both variants, our universally GSP mechanisms randomize over the greedy mechanism, our mechanism for BMP and the predicted assignment, leading to (1 + ³/γ)-consistency and (3 + γ)-robustness in expectation. All our mechanisms also provide more fine-grained approximation guarantees that interpolate between the consistency and robustness guarantees, depending on some natural error measure of the prediction.

Large Neighborhood Search (LNS) is a universal approach that is broadly applicable and has proven to be highly efficient in practice for solving optimization problems. We propose to integrate machine learning (ML) into LNS to assist in deciding which parts of the solution should be destroyed and repaired in each iteration of LNS. We refer to our new approach as Learning-Enhanced Neighborhood Selection (LENS for short). Our approach is universally applicable, i.e., it can be applied to any LNS algorithm to amplify the workings of the destroy algorithm. In this paper, we demonstrate the potential of LENS on the fundamental Vehicle Routing Problem with Time Windows (VRPTW). We implemented an LNS algorithm for VRPTW and collected data on generated novel training instances derived from well-known, extensively utilized benchmark datasets. We trained our LENS approach with this data and compared the experimental results of our approach with two benchmark algorithms: a random neighborhood selection method to show that LENS learns to make informed choices and an oracle neighborhood selection method to demonstrate the potential of our LENS approach. With LENS, we obtain results that significantly improve the quality of the solutions.

We consider clustering games in which the players are embedded into a network and want to coordinate (or anti-coordinate) their strategy with their neighbors. The goal of a player is to choose a strategy that maximizes her utility given the strategies of her neighbors. Recent studies show that even very basic variants of these games exhibit a large Price of Anarchy: A large inefficiency between the total utility generated in centralized outcomes and equilibrium outcomes in which players selfishly maximize their utility. Our main goal is to understand how structural properties of the network topology impact the inefficiency of these games. We derive topological bounds on the Price of Anarchy for different classes of clustering games. These topological bounds provide a more informative assessment of the inefficiency of these games than the corresponding worst-case Price of Anarchy bounds. More specifically, depending on the type of clustering game, our bounds reveal that the Price of Anarchy depends on the maximum subgraph density or the maximum degree of the graph. Among others, these bounds enable us to derive bounds on the Price of Anarchy for clustering games on Erdős-Rényi random graphs. Depending on the graph density, these bounds stand in stark contrast to the known worst-case Price of Anarchy bounds. Additionally, we characterize the set of distribution rules that guarantee the existence of a pure Nash equilibrium or the convergence of best-response dynamics. These results are of a similar spirit as the work of Gopalakrishnan et al. [ 19 ] and complement work of Anshelevich and Sekar [ 4 ].