Short Term Scientific Mission, COST Action IC0602
Beneficiary: PALACIOS Hector, Universidad Carlos III
Host: Endriss Ulle, ILLC
Place: Amsterdam (Netherlands)
Reference code: COST-STSM-ECOST-STSM-IC0602-231110-003109
In the short visit of Hector Palacios to Ulle Endriss, to Amsterdam, from 8th to 26th of February 2011, we investigated new connections between Combinatorial Voting and Planning. Combinatorial Voting (CV) refers to the case where voters should express their preferences on a subject that can be described in terms of value assignments to variables.
We focused on obtaining effective algorithms for CV to solve in practice problems, trying to scale well as the number of variables describing the problem and the number of voters expressing their preferences grow. We wanted to take advantage of the expertise of the visitor on Planning, and its relation with a language called CP-nets (Boutilier et al, JAIR 2004) for expressing combinatorial preferences of an agent.
During the visit we sketched basic formulations for solving a fundamental question for many voting rules: to determine if for a majority of voters, an option O is less preferred than an option O'. Such a formulation is suited for problems described using CP-nets and other related languages. Being able to determine dominance of O by O' will allow us to compute the winner for some well known voting rules. We also obtained a basic formulation for determining when all the voters prefer an option O less than O'.
Our main idea is to transform dominance queries into planning under incomplete information problems, where actions are to be applied to a set of possible configurations. We expect that this line of work will allow us to obtain an algorithm for determining the winner without having to enumerate explicitly all the possible options.
Besides working with Dr. Ulle Endriss, I talked with the rest of the members of the Computational Social Choice group and gave a talk in their seminar about this work in progress.