Pairwise Similarity Method for Majority Domination Problem

The paper addresses the problem of determining the domination number in two-level voting procedures, where the first stage involves voting within local groups of agents, and the second stage aggregates the results into a final decision. The main objective is to identify the minimum proportion of agents supporting a proposal required for its acceptance. The study applies the pairwise similarity method to analyze the structure of the problem and to design heuristic algorithms with guaranteed accuracy. Three specific cases are examined: the agent connection graph as a tree, a complete graph, and a regular graph with an odd number of vertices. For each case, the authors propose new heuristic algorithms and pairwise similarity functions that enable the estimation of solution error. The results extend the applicability of polynomial algorithms to a broader class of problems and offer criteria for selecting the optimal algorithm during postprocessing.