Constraint satisfaction problems: probabilistic approach and applications to social choice theory

Abstract

In this Ph.D thesis, we work in one of the most well studied class of problems in Computer Science, that of Constraint Satisfaction Problems (CSPs). In one of their usual formulations, CSPs consist of a set of variables that take values in a common domain set. Groups of variables are tied by constraints that restrict the possible combinations of values that the variables can have in a solution. In such a setting, there are many objectives that one might be interested in: checking if there is a solution, finding or approximating one, or considering how fast an algorithmic procedure can do all that. The framework of CSPs is broad enough to model a great number of interesting problems in computer science, like the satisfiability of propositional formulas and graph coloring problems. It is also a very developed field on its own accord, with a lot of interesting results that classify the computational complexity of classes of CSPs and delineate the bounds between tractability and NP-hardness. The machinery used to tackle such problems is broad, including polynomial-time algorithms that solve classes of CSPs, randomized ones that find or approximate solutions given some conditions that the CSP in question must satisfy and algebraic manipulations that allow us to relate their computational complexity with structural properties of their sets of constraints. We begin with an overview of various approaches to CSPs: defining them in the language of Propositional, First or Second Order Logic and via homo-morphisms and we consider the subclass of multi-sorted CSPs, that is CSPs whose variables are divided in different sorts and take values in independent domains. Some of these variations are discussed to show the versatility of CSPs and provide some context to our work, while others are utilized to prove our results. The first part of our results concerns what is known as the probabilistic approach. Here, we devise randomized algorithms that (i) prove conditions56that guarantee the existence of solutions to a given instance of a CSP and (ii) in case a solution exists, find it efficiently. A solution in this setting is usually expressed as a point in a probability space such that no event, from a set of events that are deemed as “undesirable”, occurs. We work with the seminal Lovász Local Lemma (LLL) and its variation, Shearer’s Lemma, which, given some bounds concerning the probabilities of undesirable events and the way these events depend on each other, provide conditions that imply all the events can be avoided with positive probability. A solution in this setting, is a point in a probability space such that none of the events occur. All our work is situated in the variable framework of Moser and Tardos, where the events are assumed to be defined upon independent random variables. Although this is a restriction of the general setting, it is a broad framework that easily translates to the language of CSPs and that is particularly handy for algorithmic purposes. Specifically, we define two new notions of dependency between the events, the variable-directed lopsi dependency (VDL) and the directed dependency (d-dependency), which are specifically tailored to facilitate the algorithmic manipulation of events that are negatively correlated. It is quite common in practice to depict dependencies between the events by a dependency graph, where the nodes correspond to the events and unconnected events are considered independent. We thus discuss how the directed dependency graphs that our notions give rise to, relate with other such graphs in the bibliography. Furthermore, we show that the d-dependency condition gives rise to as parser dependency graph than other known such conditions in the variable framework, thus allowing for stronger versions of the LLL to be proven. We then proceed to prove the simple version of the LLL of the VDL condition. That is, we design an algorithm which, if the probabilities of the events are upper bounded by a common number p ∈ [0, 1), the VDL graph has maximum degree d and epd ≤ 1, efficiently finds a point in the probability space such that none of the events occur, thus showing at the same time that such a point must exist in the first place. We also prove the more general asymmetric version of the LLL for the d-dependency graph, where the probability of each event is bounded by a number relating to the probabilities of the events depending on it. We then prove the even stronger Shearer’s lemma for the underlying undirected graph of the d-dependency one, which bounds the probabilities of the events by polynomials defined over the independent sets of the graph. The proofs for these versions of the LLL and Shearer’s lemma employ a7direct probabilistic approach, in which we show that the probability that our algorithms last for at least n steps is inverse exponential to n, by expressing it by a recurrence relation which we subsequently solve using advanced analytic tools, such as Bender and Richmond’s Lagrange Inversion Formula and Gelfand’s Formula for the spectral radius of matrices. In contrast, most extant work bounds only the expectation of the steps performed by such algorithms. We believe that this fact is interesting in each own accord. Nevertheless, we have applied our method in two interesting combinatorial problems. First, we show that 2∆ − 1 colors suffice to a cyclicaly color the edges of a graph with maximum degree ∆, that is, we want the resulting coloring to contain neither incident edges with the same color, nor bichromatic cycles. We thus match the best possible bound for Moser-like algorithms, as observed by Cai et al. [Acyclic edge colourings of graphs with large girth. Random Structures & Algorithms, 50(4):511–533, 2017]. We also show how to explicitly construct binary c-separating codes whose rate matches the optimal known one. c-separating codes are M × n matrices over some alphabet Q, where, in any two sets U and V of at most c rows, there is at least one column such that the set of elements in U is disjoint with that in V . Al-though such codes are very useful for applications, explicit constructions arescarce. The second part of our results lies in Social Choice Theory and, specifically, in Judgment Aggregation, where a group of agents collectively decides a set of issues and where, both the individual positions of each agent and the aggregated positions (the social outcome) needs to adhere to some restrictions that reflect logical consistency requirements. The aim is to find aggregating procedures that preserve these requirements and do not degenerate to dictatorships, that is aggregators that always output the positions of a specific agent. Firstly, we consider the case where these restrictions are expressed by a set of m ary vectors X over some finite domain D, where m is the number of issues to be decided. That is, m contains the allowed combinations of votes over the issues and a vector not in X is deemed “irrational”. In this setting, we characterize possibility domains, that is sets X where non-dictatorial aggregation is possible, via the types of aggregators they admit. Furthermore, we provide an analogous characterization for a subclass of possibility domains we named uniform possibility domains, which are domains that admitaggregators that are not dictatorial even when restricted to any issue and any binary subset of allowed positions. We also show that uniform possi-8bility domains give rise to tractable multi-sorted CSPs, while any domain that is not uniform, gives rise to NP-complete multi-sorted CSPs, thus tying the possibility of non-dictatorial aggregation with a dichotomy result in the complexity of multi-sorted CSPs. We then proceed to consider Boolean such domains, that are given as the sets of models of propositional formulas, which, in the bibliography, are called integrity constraints. We provide syntactic characterizations for integrity constraints that give rise to (uniform) possibility domains and also to domains admitting a variety of non-dictatorial aggregators with specific properties that have appeared in the bibliography. We also show how to efficiently identify integrity constraints of these types and how to efficiently construct such constraints given a Boolean domain X of the corresponding type. Finally, we turn our attention to the problem of recognizing if a domain admits a (uniform) non-dictatorial aggregator. In case X is provided explicitly, as a set of m-ary vectors, we design polynomial-time algorithms that solve this problem. In case X is Boolean and provided either via an integrity constraint, or, as in the original framework of Judgment Aggregation, as the set of consistent evaluations of a set of propositional formulas, called an agenda, we provide upper and lower complexity bounds in the polynomial hierarchy. We extend these results to include the cases where X admits non-dictatorial aggregators with desirable properties.

Σε αυτήν την διδακτορική διατριβή δουλεύουμε σε Προβλήματα Ικανοποίησης Περιορισμών (Π.Ι.Π.), τα οποία αποτελούν μία από τις πιο καλά μελετημένες κατηγορίες προβλημάτων στην Επιστήμη της Πληροφορικής. Στην συνήθη τους μορφή, τα Π.Ι.Π. αποτελούνται από ένα σύνολο μεταβλητών που παίρνουν τιμές από ένα κοινό πεδίο ορισμού. Οι μεταβλητές αυτές υπόκεινται σε διάφορους περιορισμούς, που ορίζουν τους αποδεκτούς συνδυασμούς τιμών μίας λύσης. Σε αυτό το πλαίσιο, υπάρχουν διάφορα ζητήματα που μπορούν να μας απασχολήσουν: ο έλεγχος για το αν υπάρχει λύση, το να βρούμε ή να προσεγγίσουμε μία λύση, ή το πόσο γρήγορα μπορεί να κάνει τα προηγούμενα μία αλγοριθμική διαδικασία. Πολλά ενδιαφέροντα προβλήματα στην περιοχή της Επιστήμης των Υπολογιστών μπορούν να αναπαρασταθούν ως Π.Ι.Π., όπως αυτό της ικανοποιησιμότητας προτασιακών τύπων ή του χρωματισμού γραφημάτων. Ως αυτόνομο ερευνητικό πεδίο, τα Π.Ι.Π. έχουν μελετηθεί εκτεταμένα, με αποτέλεσμα να υπάρχει ένα μεγάλο πλήθος ερευνών που τα κατηγοριοποιούν με βάση την υπολογιστική πολυπλοκότητά τους και που διαχωρίζουν τα (πολυωνυμικώς) επιλύσιμα από τα NP-δύσκολα. Πέραν τούτου, έχουν αναπτυχθεί πολλά εργαλεία γι' αυτά τα προβλήματα, όπως πολυωνυμικού χρόνου αλγόριθμοι για συγκεκριμένες κατηγορίες Π.Ι.Π., πιθανοτικοί αλγόριθμοι που βρίσκουν ή προσεγγίζουν λύσεις σε Π.Ι.Π. που ικανοποιούν ορισμένες συνθήκες και αλγεβρικές προσεγγίσεις μέσω των οποίων συσχετίζουμε την υπολογιστική τους πολυπλοκότητα με την δομή του συνόλου των περιορισμών τους. Στην παρούσα εργασία, ξεκινάμε με την παρουσίαση διαφόρων προσεγγίσεων στα Π.Ι.Π.: μέσω Προτασιακής, Πρωτοβάθμιας ή Δευτεροβάθμιας Λογικής και μέσω ομομορφισμών. Μελετούμε επίσης την παραλλαγή των Πολυειδών Π.Ι.Π., των οποίων οι μεταβλητές χωρίζονται σε διαφορετικά είδη και παίρνουν τιμές από διακριτά και ανεξάρτητα πεδία ορισμών. Κάποιες από αυτές τις παραλλαγές και προσεγγίσεις δίνονται ώστε να φανεί η ευρύτητα του πλαισίου μέσα 910 στο οποίο δουλεύουμε, ενώ άλλες χρησιμοποιούνται στα ίδια τα αποτελέσματά μας. Το πρώτο μέρος των αποτελεσμάτων μας αφορά την λεγόμενη πιθανοτική προσέγγιση. Σχεδιάζουμε αλγορίθμους που (ι) αποδεικνύουν συνθήκες οι οποίες εγγυώνται την ύπαρξη λύσης σε στιγμιότυπα ενός Π.Ι.Π. και (ιι) σε περίπτωση που υπάρχει λύση, την βρίσκουν σε πολυωνυμικό χρόνο. Οι λίσεις αυτές συνήθως αναπαριστόνται από σημεία ενός πιθανοτικού χώρου στα οποία δεν ισχύει κανένα από μία σειρά γεγονότα τα οποία κρίνονται ως ‘ανεπιθύμητα’. Δουλεύουμε με το Τοπικό Λήμμα του Lovász (Lovász Local Lemma) και την παραλλαγή του, το Λήμμα του Shearer. Αυτά τα λήμματα, δοθέντων κάποιων άνω φραγμάτων στην πιθανότητα μη-επιθυμητών γεγονότων να συμβούν, καθώς και στο πλήθος των μεταξύ τους συσχετισμών και εξαρτήσεων, μας δίνουν συνθήκες κάτω από τις οποίες υπάρχει λύση. Ακολουθώντας τους Moser και Tardos, υποθέτουμε ότι όλα τα γεγονότα ορίζονται μέσω ανεξάρτητων τυχαίων μεταβλητών. Παρόλο που αυτό είναι ένα πιο περιορισμένο πεδίο σε σχέση με το να δουλεύαμε με γενικούς πιθανοτικούς χώρους, είναι ένα ευρύ πλαίσιο που ταιριάζει με αυτό των Π.Ι.Π. και στο οποίο μπορούμε εύκολα να σχεδιάσουμε αλγορίθμους. Συγκεκριμένα, εισάγουμε δύο νέες έννοιες εξάρτησης μεταξύ των γεγονότων, την κατευθυνόμενη ασύμμετρη εξάρτηση μεταβλητής (variable - di-rected lopsidependency - VDL) και την κατευθυνόμενη εξάρτηση. Και οι δύο αυτές έννοιες είναι σχεδιασμένες ώστε να επιτρέπουν την αλγοριθμική επεξεργασία αρνητικά συσχετισμένων γεγονότων. Είναι σύνηθες οι εξαρτήσεις μεταξύ των γεγονότων να αποτυπώνονται στα λεγόμενα γραφήματα εξάρτησης, των οποίων οι κορυφές αντιστοιχούν στα γεγονότα και τα γεγονότα που δεν ενώνονται με ακμές θεωρούνται ανεξάρτητα. Ως εκ τούτου, συγκρίνουμε τα κατευθυνόμενα γραφήματα εξάρτησης που προκύπτουν από τις δύο παραπάνω έννοιες που εισαγάγαμε, με άλλα τέτοιου είδους γραφήματα που χρησιμοποιούνται στην βιβλιογραφία. Ειδικότερα, δείχνουμε ότι το γράφημα της κατευθυνόμενης εξάρτησης είναι πιο αραιό από τα περισσότερα τέτοια γραφήματα, κάτι που επιτρέπει να αποδειχθούν πιο ισχυρές μορφές του Τοπικού Λήμματος. Στην συνέχεια, αποδεικνύουμε την απλή μορφή του λήμματος αυτού για την VDL. Συγκεκριμένα, σχεδιάζουμε έναν αλγόριθμο ο οποίος, δεδομένου ότι η πιθανότητα των γεγονότων φράσσεται από έναν αριθμό p ∈ [0, 1), ότι το VDL γράφημα έχει μέγιστο βαθμό d και ότι epd ≤ 1, βρίσκει σε πολυωνυμικό χρόνο ένα σημείο στον πιθανοτικό χώρο τέτοιο ώστε κανένα από τα μη επιθυμητά γεγονότα να μην ισχύει. Αυτό φυσικά συνεπάγεται και την ύπαρξη τέτοιου σημείου. Στην συνέχεια, αποδεικνύουμε την μη-συμμετρική εκδοχή του λήμματος για το γράφημα κατευθυνόμενης εξάρτησης. Σε αυτήν την εκδοχή, η πιθανότητα κάθε γεγονότος φράσσεται από έναν αριθμό που σχετίζεται με την πιθανότητα όλων των εξαρτωμένων από αυτό γεγονότων. Τέλος, αποδεικνύουμε και το πιο ισχυρό Λήμμα του Shearer για το μη-κατευθυνόμενο γράφημα που προκύπτει αν αγνοήσουμε τις κατευθύνσεις στο γράφημα κατευθυνόμενης εξάρτησης. Σε αυτό το λήμμα, οι πιθανότητες των γεγονότων φράσσονται από πολυώνυμα επί των ανεξάρτητων συνόλων του γραφήματος. Οι αποδείξεις αυτών των εκδοχών των λημμάτων αυτών γίνονται μέσω μίας απευθείας πιθανοτικής ανάλυσης του πλήθους των βημάτων που κάνουν οι αλγόριθμοι μας. Για να το επιτύχουμε αυτό, φράσσουμε την πιθανότητα να εκτελέσουν τουλάχιστον n βήματα από μια σχέση αναδρομής, την οποία στην συνέχεια επιλύουμε με αναλυτικά εργαλεία, όπως την εκδοχή της Φόρμουλας Αντιστροφής του Lagrange που έχουν αποδείξει οι Bender και Richmond, ή την Φόρμουλα του Gelfand για την φασματική νόρμα πινάκων. Αντίθετα, οι μέχρι τώρα αλγοριθμικές προσεγγίσεις υπολογίζουν την αναμενόμενη τιμή των βημάτων των αλγορίθμων. Θεωρούμε πως αυτό το γεγονός από μόνο του κάνει την παραπάνω προσέγγισή ενδιαφέρουσα. Παρόλα αυτά, εφαρμόσαμε τις μεθόδους μας σε δύο ενδιαφέροντα υπολογιστικά προβλήματα. Αρχικά, δείχνουμε ότι 2∆ − 1 χρώματα αρκούν για να βάψουμε τις ακμές ενός γραφήματος με τέτοιων τρόπο ώστε, πρώτον, να μην υπάρχουν προσπίπτουσες ακμές ίδιου χρώματος και, δεύτερον, να μην υπάρχουν διχρωματικοί κύκλοι. Το αποτέλεσμα αυτό είναι βέλτιστο για αλγορίθμους τύπου Moser, όπως παρατήρησαν οι Cai etal. [Acyclic edge colourings of graphs with large girth. Random Structures & Algorithms, 50(4):511–533, 2017]. Ακόμη, δείχνουμε πως να κατασκευάσουμε c-διαχωριστικούς κώδικες των οποίων η πληροφορία σε κάθε ψηφίο είναι η βέλτιστη που έχει βρεθεί στην βιβλιογραφία. Οι c-διαχωριστικοί κώδικες είναι πίνακες διάστασης M ×n, με στοιχεία από ένα αλφάβητο Q, ώστε, για κάθε δύο υποσύνολα U , V το πολύ c γραμμών τους, να υπάρχει τουλάχιστον μία στήλη της οποίας τα σύνολα των στοιχείων στο U και αυτά του V να είναι ξένα. Παρ ́ ότι αυτοί οι κώδικες είναι πολύ χρήσιμοι στις εφαρμογές, οι κατασκευές τους είναι πολύ σπάνιες. Το δεύτερο μέρος της δουλειάς μας είναι στην Θεωρία Κοινωνικών Προτιμήσεων και, πιο συγκεκριμένα, στον Συμψηφισμό Κρίσεων, όπου ένα σύνολο ατόμων θέλει να αποφασίσει συλλογικά ένα σύνολο ζητημάτων, και που οι δυνατοί συνδυασμοί ψήφων, τόσο για το κάθε άτομο ξεχωριστά, όσο και για την συλλογική απόφαση υπακούν σε κάποιους περιορισμούς, οι οποίοι επιβάλουν κάποια έννοια λογικής συνέπειας. Στόχος είναι να βρεθούν κανόνες συμψηφισμού που διατηρούν αυτούς τους περιορισμούς και που δεν εκφυλίζονται σε 12 δικτατορίες, δηλαδή σε κανόνες που καταλήγουν πάντα στις επιλογές ενός συγκεκριμένου ατόμου. Αρχικά, εξετάζουμε την περίπτωση που οι περιορισμοί αυτοί μας δίνονται ως ένα σύνολο X m-αδικών διανυσμάτων με στοιχεία από ένα πεδίο ορισμού D,όπου m είναι το πλήθος των ζητημάτων επί των οποίων ψηφίζουν τα άτομα. Το X λοιπόν περιέχει τους επιτρεπόμενους συνδυασμούς ψήφων επί των θεμάτων και κάθε διάνυσμα εκτός του X θεωρείται μη λογικά συνεπές. Σε αυτό το πλαίσιο, χαρακτηρίζουμε τα πεδία δυνατότητας, τα σύνολα X δηλαδή όπου μπορούμε να βρούμε μη-δικτατορικούς συμψηφιστές, μέσω των ειδών των συμψηφιστών που δέχονται. Στην συνέχεια, χαρακτηρίζουμε με αντίστοιχο τρόπο τα ομοιόμορφα πεδία δυνατότητας, τα οποία δέχονται συμψηφιστές οι οποίοι δεν είναι δικτατορικοί ακόμη κι όταν περιορίζονται σε οποιοδήποτε θέμα και δυαδικό υποσύνολο δυνατών θέσεων ως προς το θέμα αυτό. Δείχνουμε επίσης ότι τα πολυειδή Π.Ι.Π. που ορίζονται πάνω σε ομοιόμορφα πεδία δυνατότητας είναι πολυωνυμικώς επιλύσιμα, ενώ τα Π.Ι.Π. που ορίζονται σε σύνολα που δεν είναι τέτοια, είναι NP-δύσκολα, συνδέοντας έτσι την δυνατότητα μη δικτατορικού συμψηφισμού με μια διχοτομία στην πολυπλοκότητα των πολυειδών Π.Ι.Π. Στην συνέχεια, ασχολούμαστε με την περίπτωση που το X ορίζεται πάνω σε δυαδικό πεδίο ορισμού και μας δίνεται ως το σύνολο αληθοτιμών μιας προτασιακής φόρμουλας. Στην βιβλιογραφία, τέτοιες φόρμουλες ονομάζονται περιορισμοί ακεραιότητας. Αποδεικνύουμε συντακτικούς χαρακτηρισμούς για φόρμουλες που μας δίνουν (ομοιόμορφα) πεδία δυνατότητας, καθώς και πεδίων που δέχονται ένα πλήθος από μη-δικτατορικούς συμψηφιστές με ενδιαφέρουσες ιδιότητες, που έχουν εμφανιστεί στην βιβλιογραφία. Δείχνουμε επίσης πως να αναγνωρίζουμε αποδοτικά τέτοιους συντακτικούς τύπους αλλά και πως να τους κατασκευάζουμε μέσω ενός πεδίου με τις κατάλληλες ιδιότητες. Τέλος, ασχολούμαστε με το πρόβλημα της αναγνώρισης ενός πεδίου που δέχεται (ομοιόμορφους) μη δικτατορικούς συμψηφιστές. Στην περίπτωση που το X μας έχει δοθεί ως σύνολο διανυσμάτων, σχεδιάζουμε πολυωνυμικούς αλγορίθμους που το επιλύουν. Αν το X δίνεται είτε ως το σύνολο αληθείας μιας προτασιακής φόρμουλας, είτε ως ένα σύνολο λογικά συνεπών κρίσεων ενός συνόλου τέτοιων τύπων, δηλαδή μιας αντζέντας, όπως ήταν κι ο αρχικός τρόπος μελέτης της συγκεκριμένης περιοχής, δίνουμε άνω και κάτω φράγματα στην υπολογιστική πολυπλοκότητα αυτών των προβλημάτων, μέσω της πολυωνυμικής ιεραρχίας. Αντίστοιχα αποτελέσματα βρίσκουμε και στις περιπτώσεις που ελέγχουμε για μη δικτατορικούς συμψηφιστές με επιθυμητές ιδιότητες που έχουν μελετηθεί στην βιβλιογραφία.