Collective discrete optimisation as judgment aggregation

• URL: http://arxiv.org/abs/2112.00574v1
• Date: Wed, 1 Dec 2021 15:40:23 GMT
• Title: Collective discrete optimisation as judgment aggregation
• Authors: Linus Boes and Rachael Colley and Umberto Grandi and Jerome Lang and Arianna Novaro
• Abstract summary: Participatory budgeting, for instance, is the collective version of the knapsack problem. Other examples include collective scheduling, and collective spanning trees. We propose to represent and solve them in the unifying framework of judgment aggregation with weighted issues.
• Score: 5.4903333042180495
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many important collective decision-making problems can be seen as multi-agent versions of discrete optimisation problems. Participatory budgeting, for instance, is the collective version of the knapsack problem; other examples include collective scheduling, and collective spanning trees. Rather than developing a specific model, as well as specific algorithmic techniques, for each of these problems, we propose to represent and solve them in the unifying framework of judgment aggregation with weighted issues. We provide a modular definition of collective discrete optimisation (CDO) rules based on coupling a set scoring function with an operator, and we show how they generalise several existing procedures developed for specific CDO problems. We also give an implementation based on integer linear programming (ILP) and test it on the problem of collective spanning trees.

Related papers

• Error Diversity Matters: An Error-Resistant Ensemble Method for Unsupervised Dependency Parsing [49.60415088899208]
  We propose an efficient ensemble-selection approach that considers error diversity and avoids error accumulation. Results demonstrate that our approach outperforms each individual model as well as previous ensemble techniques.
  arXiv  Detail & Related papers  (2024-12-16T08:23:50Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Consistent Multiclass Algorithms for Complex Metrics and Constraints [38.6998359999636]
  This setting includes many common performance metrics such as the multiclass G-mean and micro F1-measure. We give a general framework for consistent algorithms for such complex design goals. Experiments on a variety of multiclass classification tasks and fairness-constrained problems show that our algorithms compare favorably to the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2022-10-18T09:09:29Z)
• An attention model for the formation of collectives in real-world domains [78.1526027174326]
  We consider the problem of forming collectives of agents for real-world applications aligned with Sustainable Development Goals. We propose a general approach for the formation of collectives based on a novel combination of an attention model and an integer linear program.
  arXiv  Detail & Related papers  (2022-04-30T09:15:36Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  We propose a family of algorithms for personalized federated learning with locally convex user costs. The proposed framework is based on a generalization of convex clustering in which the differences between different users' models are penalized.
  arXiv  Detail & Related papers  (2022-02-01T19:25:31Z)
• Joint Continuous and Discrete Model Selection via Submodularity [1.332560004325655]
  In model selection problems for machine learning, the desire for a well-performing model with meaningful structure is typically expressed through a regularized optimization problem. In many scenarios, however, numerically meaningful structure is specified in some discrete space leading to difficult non optimization problems. We show how simple continuous or discrete constraints can also be handled for certain problem classes, motivated by robust optimization.
  arXiv  Detail & Related papers  (2021-02-17T21:14:47Z)
• Population-Based Methods: PARTICLE SWARM OPTIMIZATION -- Development of a General-Purpose Optimizer and Applications [0.0]
  This thesis is concerned with continuous, static, and single-objective optimization problems subject to inequality constraints. The particle swarm optimization paradigm was inspired by previous simulations of the cooperative behaviour observed in social beings.
  arXiv  Detail & Related papers  (2021-01-25T09:36:25Z)
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits [15.609414012418043]
  Cooperative multi-agent decision making involves a group of agents cooperatively solving learning problems while communicating over a network with delays. We consider the kernelised contextual bandit problem, where the reward obtained by an agent is an arbitrary linear function of the contexts' images in the related kernel reproducing Hilbert space (RKHS) We propose textscCoop- KernelUCB, an algorithm that provides near-optimal bounds on the per-agent regret.
  arXiv  Detail & Related papers  (2020-08-14T07:37:44Z)
• Bayesian preference elicitation for multiobjective combinatorial optimization [12.96855751244076]
  We introduce a new incremental preference elicitation procedure able to deal with noisy responses of a Decision Maker (DM) We assume that the preferences of the DM are represented by an aggregation function whose parameters are unknown and that the uncertainty about them is represented by a density function on the parameter space.
  arXiv  Detail & Related papers  (2020-07-29T12:28:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.