WP1: Computation, approximation, verification

Coordinator: Olivier Spanjaard

This work package focuses on the computational difficulties of the various multiagent optimization problems considered in the project. The specificity of the problems studied in the project is that each agent has her own individual preferences and one aims at producing a feasible solution that complies with these preferences. The problems investigated fall within three main categories:

  • finding a collective solution (jointly used by a group of agents) to a problem where the set of possible solutions has a combinatorial structure. Examples of such problems studied in the project:
    • picking a set of movies to put on a plane as entertainment system
    • selecting a subset of projects to fund under a budget constraint
    • implementing multiple referenda and committee elections
    • compounding a balanced recruiting committee
    • coordinating the actions of a set of agents in a network determining a common itinerary for a group of agents
  • determining a fair allocation of indivisible goods to agents Examples of such problems studiedin the project:
    • reallocation of resources to achieve mutually better outcomes
    • the Santa Claus problem, where one looks for a max-min allocation of objects among agents
    • the assignment of papers to reviewers according to the bids made by the reviewers in a conference management system
    • the robust assignment of tasks to agents
    • object allocation problems under constraints
    • designing the scientific program of a conference with multiple parallel sessions
  • taking into account coalitions in games and elections. Examples of such problems studied in the project:
    • include the partitioning of a set of agents into subsets of agents who perform coordinate actions
    • elections in a plurality-voting setting where the candidates are split between parties, and each party nominates exactly one candidate for the final election

The issues tackled in the undertaken research works include the followings:

  • giving synthetic studies of complexity results for the various multiagent optimization problems considered in the project
  • designing algorithms able to handle ordered aggregation operators or Lorenz-dominance relations in order to compute fair solutions to multiagent optimization problems
  • studying the complexity of computing and verifying Pareto optimal committees (given a rule to lift each individual preference relation over candidates to a preference relation over committees)
  • defining formal models expressive enough to capture various group decision problems where the set of possible solutions has a combinatorial structure
  • taking advantage of a specific combinatorial structure to obtain positive computational results.

For all these issues, the different tasks put forward in the proposal have been tackled:

  • analysis of the computational complexity and identification of tractable instances
  • design of polynomial approximation algorithms and approximability studies
  • practical computation of solutions and experiments