Sensing God's Will is Fixed Parameter Tractable

Michael Fellows, Frances Rosamond and Arkadii Slinko

Abstract

One of the goals of Artificial Intelligence is to create autonomous software agents which exhibit social intelligence, i.e are capable to act as a group member in various groups and, in particular, to participate in group decision making. For such agents to be programmed we need protocols which are formalizable. In this paper we are suggesting such a protocol based on one of the most famous and controversial social choice rules - Dodgson's rule. We prove that the problem of implementation of this protocol is fixed parameter tractable.








Keywords
consensus, protocol, Dodgson rule, complexity

Math Review Classification
Primary 91B10, 91B14 ; Secondary 91-08

Last Updated
03/03/2008

Length
9 pages

Availability
This article is available in: