New Frontiers in Computational Social Choice
Project goals
Fixed-parameter tractability and approximation algorithms are nowadays standard tools for design of algorithms for hard problems in the area of Computational Social Choice. Surprisingly, kernelization, a prominent technique in FPT algorithmics, is not used as often to tackle social choice problems. Kernelization is a formalism of safe data reduction which we believe does have its place in all research disciplines dealing with large and complex datasets. The most recent approach is the so-called lossy kernelization which on the one hand cooperates with approximation algorithms (unlike kernelization which can only be pipelined with exact algorithms) and on the other hand, allows circumventing hardness results (in exchange for introducing a possible loss in the quality of the solution). This project aims on filling this gap of usage of these tools in computational social choice. The suggested line of research continues our current studies in this area and the new proposed directions will need novel algorithmic approaches as they focus on the boundaries of tractability.
Keywords
parameterized complexitycomputational social choiceapproximation algorithmskernelization
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202200004
Main participants
České vysoké učení technické v Praze / Fakulta informačních technologií
Contest type
VS - Public tender
Contract ID
22-19557S
Alternative language
Project name in Czech
Nové výzvy ve výpočetní socální volbě
Annotation in Czech
Pro návrh algoritmů na řešení těžkých problémů v oblasti výpočetní sociální volby jsou dnes standardem jak parametrizované tak aproximační algoritmy. Kernelizace, jedna z hlavních technik v parametrizované složitosti, je překvapivě málo používána pro řešení problémů sociální volby. Jsme přesvědčeni, že kernelizace - formalismus pro bezpečnou redukci vstupních dat - má své místo ve všech výzkumných odvětvích týkajících se velkých vstupních dat. Nejnovějšı́ koncept je tzv. ztrátová kernelizace, která je jednak použitelná v kombinaci s aproximačními algoritmy (narozdíl od normální kernelizace, kterou lze kombinovat pouze s exaktními algoritmy), a druhak dokáže obejít těžkostní výsledky za cenu zavedení mírné nepřesnosti do výsledku. Navrhujeme aplikovat tyto moderní nástroje - ztrátovou kernelizaci - ve výpočetní sociální volbě. Projekt se zaměřuje přenesení a využití těchto technik ve výpočetní sociální volby. Navrhovaný projekt navazuje na naši předchozí práci v tomto oboru a uvažované směřování výzkumu bude vyžadovat nové algoritmické přı́stupy.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Apr 1, 2022
Realization period - end
Dec 31, 2024
Project status
—
Latest support payment
Feb 29, 2024
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP25-GA0-GA-R
Data delivery date
Mar 12, 2025
Finance
Total approved costs
5,819 thou. CZK
Public financial support
5,819 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
5 819 CZK thou.
Public support
5 819 CZK thou.
100%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 04. 2022 - 31. 12. 2024