A Quick Algorithm to Determine 2-Optimality Consensus for Collectives

Abstract

Nowadays, to solve a problem, people/systems typically use knowledge from different sources. A binary vector is a useful structure to represent knowledge states, and determining the consensus for a binary vector collective is helpful in many areas. However, determining a consensus that satisfies postulate 2-Optimality is an NP-hard problem; therefore, many heuristic algorithms have been proposed. The basic heuristic algorithm is the fastest in the literature, and most widely used to solve this problem. The computational complexity of the basic heuristic algorithm is O(m2n). In this study, we propose a quick algorithm (called QADC) to determine the 2-Optimality consensus. The QADC algorithm is developed based on a new approach for calculating the distances from a candidate consensus to the collective members. The computational complexity of the QADC algorithm has been reduced to O(mn), and the consensus quality of QADC algorithm and the basic heuristic algorithm is the same.

Keywords

• Collective intelligence
• collective knowledge
• consensus
• heuristic algorithm
• 2-optimality consensus