- PII
- S30346444S0002338825050066-1
- DOI
- 10.7868/S3034644425050066
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume / Issue number 5
- Pages
- 78-85
- Abstract
- The paper considers the problem of finding the number of dominant voters in two-level voting procedures. At the first stage, voting is conducted among local groups of voters, and at the second stage, the results are aggregated to form a final decision. The goal is to determine the minimum proportion of voters supporting a proposal for it to be accepted. The paper uses the method of pairwise comparisons to analyze the structure of the problem and develop heuristic algorithms with guaranteed accuracy. Special cases are considered, including the agent communication graph as a tree, complete graph, or regular graph with an odd number of vertices. New heuristic algorithms are proposed for each case, along with pairwise comparison functions to estimate the accuracy of the solution. Results extend the use of polynomial algorithms to a broader class of problems, providing criteria for selecting the optimal algorithm during the post-processing stage.
- Keywords
- метод попарного сходства двухуровневое голосование эвристический алгоритм регулярный граф полный граф граф дерево
- Date of publication
- 09.12.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 26
References
- 1. Breer V.V., Novikov D.A., Rogatkin A.D. Mob Control: Models of Threshold Collective Behavior // 1st Edn. Cham: Springer International Publishing, 2017.
- 2. Chebotarev P., Peleg D. The Power of Small Coalitions Under Two-tier Majority on Regular Graphs // Discrete Applied Mathematics. 2023. V. 340. P. 239–258.
- 3. Broere I., Hattingh J.H., Henning M.A., McRae A.A. Majority Domination in Graphs // Discrete Mathematics. 1995. V. 138. №. 1–3. P. 125–135.
- 4. Yeh H.G., Chang G.J. Algorithmic Aspects of Majority Domination // Taiwanese J. Mathematics. 1997. V. 1. №. 3. P. 343–350.
- 5. Holm T.S. On Majority Domination in Graphs // Discrete Mathematics. 2001. V. 239. №. 1–3. P. 1–12.
- 6. Lemtyuzhnikova D., Chebotarev P., Goubko M., Shushko N. Pairwise Similarity Estimation for Discrete Optimization Problems // Advances in Systems Science and Applications. 2023. V. 23. №. 2. P. 164–177.
- 7. Шушко Н.Н. Метод попарного сходства для задачи двухровневого голосования // Интеллектуализация обработки информации: тез. локл. 15-й междунар. конф. Гродно. ГрГУ Беларусь, 2024.
- 8. Lazarev A.A., Lemtyuzhnikova D.V., Werner F. A Metric Approach for Scheduling Problems with Minimizing the Maximum Penalty // Applied Mathematical Modelling. 2021. V. 89. P. 1163–1176.
- 9. Lazarev A., Lemtyuzhnikova D., Providivets N., Werner F. Polynomially Solvable Subcases for the Approximate Solution of Multi-machine Scheduling Problems // Intern. Conf. on Optimization and Applications. Cham: Springer International Publishing, 2020. P. 211–223.
- 10. Lazarev A.A., Lemtyuzhnikova D.V., Providivets N.A. Metric Approach for Finding Approximate Solutions of Scheduling Problems // Computational Mathematics and Mathematical Physics. 2021. V. 61. P. 1169–1180.
- 11. Bukueva E., Kudinov I., Lemtyuzhnikova D. Analysis of the Feasibility to Use Metric Approach for NP-hard Makespan Minimization Problem // IFAC-PapersOnLine. 2022. V. 55. №. 10. P. 2898–2901.
- 12. Cheng T.C.E., Lazarev A., Lemtyuzhnikova D. A Metric Approach for the Two-station Single-track Railway Scheduling Problem // IFAC-PapersOnLine. 2022. V. 55. №. 10. P. 2875–2880.
