Thèse Année : 2025

Vote mechanisms and solution of inequation systems with real variables

Mécanismes de votes et résolutions de systèmes d'inéquations à variables réelles

Résumé

Numerous mechanisms exist for collective decision-making. Among them, Social Choice Functions, which have been extensively explored in various works. However, some systems do not fall within the scope of Social Choice Functions. Our first contribution is the design of a unified framework that accommodates a wide range of voting systems, enabling a systematic analysis of different mechanisms through slight modifications in the representation of voter preferences. We also investigate the notion of strategyproofness. A mechanism is strategyproof if voters are always incentivized to report their true preferences, meaning no voter can achieve a better outcome by changing their vote. In the first part of the document, we aim to establish a unified framework that allows for the systematic study of various voting mechanisms previously introduced. We will study several types of voting mechanisms through the lens of strategyproofness. To this end, we introduce a specific class of mechanisms called "score votings," as well as a key condition, the "Constrained Change Property." We then prove that, within the class of score votings, strategyproofness is equivalent to the satisfaction of this property. In the second part, we focus on problems related to systems of inequalities with real-valued variables. Many problems involving real-valued functions are expressed as decision problems. For example, given a polynomial, one may ask whether it has a root. Matiyasevich's theorem implies that deciding whether a polynomial has an integer root is undecidable. However, according to Tarski's theorem, it is possible to determine whether a polynomial has a real root. In this part, we will develop an algorithm that, given an existential property, produces a certificate when an instance is satisfiable. This framework raises two challenges regarding the complexity of the algorithm. First, the certificate must be small, as its length contributes to the overall complexity; thus, if it is not polynomial in size, the algorithm cannot run in polynomial time. Second, the certificate must be efficiently verifiable, meaning the verification process must also be achievable in polynomial time. Delta-decidability provides a complementary approach to handling undecidability and numerical imprecision. Delta-decidability allows for a grey area in which instances may not yield clear answers. However, delta-decidability is not a tool used to design decision problems: the instances in the grey area are present in the input of a delta-decidability problem. In this document, we will use delta-decidability to solve systems of inequalities in polynomial time with access to an oracle in NP. We introduce a class of functions called "Lipschitz ultimately affine approximable functions" and show that as long as all the involved functions belong to this class, inequality systems can be solved approximately within a small margin of error. While the problems we consider are not standard decision problems (and thus not classifiable in traditional complexity classes like NP), we prove that they can be solved in polynomial time with an oracle in NP.

Une première partie de ce document se concentre sur la résistance à la tricherie en théorie du choix social. De nombreux mécanismes existent pour la prise de décision collective. Parmi eux, les Fonctions de Choix Social, largement explorées dans divers ouvrages. Cependant, certains systèmes ne relèvent pas du cadre des Fonctions de Choix Social. Notre première contribution est la conception d'un cadre unifié qui accueille une large gamme de systèmes de vote, permettant une analyse systématique des différents mécanismes grâce à de légères modifications dans la représentation des préférences des électeurs. Nous investiguons également la notion de résistance à la tricherie. Un mécanisme est résistant à la tricherie si les électeurs sont toujours incités à rapporter leurs véritables préférences, c'est-à-dire qu'aucun électeur ne peut obtenir un meilleur résultat en modifiant son vote. Dans cette première partie du document, nous cherchons à établir un cadre unifié qui permet l'étude systématique de divers mécanismes de vote précédemment introduits. Nous étudierons plusieurs types de mécanismes de vote sous l'angle de la résistance à la tricherie. À cette fin, nous introduisons une classe spécifique de mécanismes appelés votes à scores, ainsi qu'une condition clé, la « Constrained Change Property ». Nous prouvons ensuite que, dans la classe des votes à scores, la résistance à la tricherie est équivalente à la satisfaction de cette propriété. Dans une seconde partie, nous nous intéressons à des problèmes liés à des systèmes d'inéquations de la variable réelle. De nombreux problèmes utilisant des fonctions à valeurs réelles sont exprimés sous forme de problèmes de décision. Par exemple, étant donné un polynôme, on peut se demander s'il a une racine. Le théorème de Matiyasevich implique que décider si un polynôme a une racine entière est indécidable. Cependant, d'après le théorème de Tarski, il est possible de déterminer si un polynôme a une racine réelle. Dans cette partie nous allons produire un algorithme qui, étant donné une propriété existentielle, produit un certificat lorsqu'une instance est satisfaisable. Ce cadre soulève deux défis en ce qui concerne la complexité de l'algorithme. Premièrement, le certificat doit être petit, car sa longueur contribue à la complexité globale ; ainsi, s'il n'est pas de taille polynomiale, l'algorithme ne peut pas s'exécuter en temps polynomial. Deuxièmement, le certificat doit être vérifiable de manière efficace, ce qui signifie que la vérification doit également être réalisable en temps polynomial. La delta-décidabilité nous donne une approche complémentaire pour traiter l'indécidabilité et l'imprécision numérique. La delta-décidabilité autorise une zone grise dans laquelle les instances peuvent ne pas donner de réponses claires. Cependant, la delta-décidabilité n'est pas un outil utilisé pour concevoir des problèmes de décision : les instances de la zone grise sont présentes dans l'entrée d'un problème de delta-décidabilité. Dans ce document, nous utiliserons la delta-décidabilité pour résoudre des systèmes d'inéquations en temps polynomial avec accès à un oracle dans NP. Nous introduisons une classe de fonctions appelées “Fonctions Lipschitz ultimement affines approximables” et montrons que tant que toutes les fonctions impliquées appartiennent à cette classe, les systèmes d'inéquations peuvent être résolus approximativement avec une petite marge d'erreur. Bien que les problèmes que nous considérons ne soient pas des problèmes de décision standard (et donc pas classifiables dans des classes de complexité traditionnelles comme NP), nous prouvons qu'ils peuvent être résolus en temps polynomial avec un oracle dans NP.

Fichier principal
Vignette du fichier
150607_DARDILHAC_2025_archivage.pdf (1.1 Mo) Télécharger le fichier
Origine Version validée par le jury (STAR)

Dates et versions

tel-05300167 , version 1 (06-10-2025)

Identifiants

  • HAL Id : tel-05300167 , version 1

Citer

Valentin Dardilhac. Vote mechanisms and solution of inequation systems with real variables. Computational Complexity [cs.CC]. Université Paris-Saclay, 2025. English. ⟨NNT : 2025UPASG045⟩. ⟨tel-05300167⟩
567 Consultations
61 Téléchargements

Partager

  • More