Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems

Abstract

Integer Linear Programming (ILP) has proven to be a powerful tool for solving hard problems, particularly in computational social choice, where it has been used to address variants of the bribery problem. This problem involves finding the smallest change that results in a desired outcome after opinions diffuse through a society. The ILP solution for this problem has been shown to be experimentally limited to small instances of the problem. Research has shown that such problems can be encoded using logical formulas in Presburger Arithmetic (PrA) matching the complexity of the ILP algo- rithm. Therefore, a practical analysis of the PrA-based approach is called for. In this project, we randomly generate instances with prescribed election parameters and model them as ILP instances and PrA formulas. We use solvers such as GUROBI, GLPK, and Z3 to solve these instances and con- duct a comparative study to evaluate the performance of both approaches under different parameters, such as the number of voter types and diffusion steps. Our results show that the ILP approach is more robust than the PrA approach in practice. 1

Celočíselné lineární programování (ILP) se ukázalo být mocným nástro- jem pro řešení obtížných problémů, zejména v oblasti výpočetní sociální volby, kde byl použit k řešení variant problému úplatků. V tomto prob- lému jde o nalezení nejmenší změny, která vede ke kýženému výsledku po- tom, co ve společnosti proběhne proces šíření názorů. Předchozí experimenty ukazují, že řešení tohoto problému pomocí ILP je omezené pouze na malé instance. Novější výsledky ukazují, že tentýž problém lze vyjádřit pomocí logických formulí v Presburgerově aritmetice (PrA) a lze tak dosáhnout složi- tosti podobné algoritmu ILP. Proto se nabízí provést praktickou analýzu přístupu založeného na PrA. V tomto projektu jsme vygenerovali náhodné instance s předepsanými parametry voleb a modelovali je jako instance ILP a PrA. Následně jsme takto získané instance vyřešili pomocí řešičů jako jsou např. GUROBI, GLPK a Z3 a provedli jsme srovnávací studii k vyhodnocení výkonnosti obou přístupů vzhledem k různých parametrům, jako jsou např. počet typů voličů a difúzních kroků. Naše výsledky ukazují, že přístup skrze ILP je v praxi robustnější než přístup PrA. 1