Το πρόβλημα της δίκαιης κατανομής είναι ένα πολύ σημαντικό πρόβλημα που έχει ανακύψει στον τομέα της επιστήμης των υπολογιστών και όχι μόνο. Κάποιες από τις μορφές που έχει εμφανιστεί είναι π.χ. στην κατανομή πόρων σε δίκτυα υπολογιστών, στο διακανονισμό συνόρων σε διεθνείς διαφωνίες, στο οικογενειακό δίκαιο και ως πρόβλημα της μείωσης των εκπομπών αερίων του θερμοκηπίου. Θεωρούμε προβλήματα αναθέσεων στα οποία ένα σύνολο αγαθών είτε αγγαρειών πρέπει να ανατεθεί σε κάποιους παίκτες. Κάθε παίκτης έχει μία συνάρτηση κέρδους (κόστους) που δείχνει πόσο εκτιμά κάθε αγαθό (αγγαρεία, αντίστοιχα) και το κέρδος (κόστος) του παίκτη για κάθε πιθανό σύνολο αντικειμένων προκύπτει αθροιστικά. Στόχος του προβλήματος είναι, φυσικά, η αποδοτικότητα και η δικαιοσύνη της ανάθεσης, περιορισμοί όμως, όπως η εγωιστική συμπεριφορά των παικτών οδηγούν σε πολύ ενδιαφέρουσες παραλλαγές του προβλήματος. Το πρώτο αποτέλεσμα της εργασίας προκύπτει από τη μελέτη του προβλήματος ανάθεσης ενός συνόλου αδιαίρετων αγαθών σε παίκτες όταν μας ενδιαφέρει να μην υπάρχει μεγάλη ζήλεια μεταξύ των παικτών. Αδιαίρετα λέγονται τα αντικείμενα που δεν μπορούν να κοπούν σε κομμάτια και πρέπει να ανατεθούν ακέραια σε κάποιο παίκτη, ενώ ζήλεια, διαισθητικά, είναι η προτίμηση που έχει κάποιος παίκτης για το σύνολο αγαθών που ανατέθηκαν σε κάποιον άλλον σε σχέση με τα αγαθά που ανατέθηκαν στον ίδιο. Όπως έχουμε αναφέρει, στην πράξη οι παίκτες έχουν εγωιστική συμπεριφορά, υπό την έννοια ότι προσπαθούν να μεγιστοποιήσουν το κέρδος τους. Για αυτό το λόγο, μπορεί να αναφέρουν εσφαλμένες συναρτήσεις κέρδους για να πετύχουν μία καλύτερη ανάθεση. Ως ειλικρινής χαρακτηρίζεται ένας μηχανισμός ανάθεσης ο οποίος εγγυάται ότι η ανάθεση των αντικειμένων βασίζεται στις σωστές συναρτήσεις κέρδους των παικτών. Υπό μία έννοια, ένας ειλικρινής μηχανισμός ανάθεσης αναγκάζει τους παίκτες να πουν την αλήθεια για τις συναρτήσεις κέρδους τους, ή αλλιώς, εγγυάται πως το κέρδος ενός παίκτη από την ανάθεση που βασίζεται σε εσφαλμένη συνάρτηση κέρδους δεν είναι μεγαλύτερο από το κέρδος που θα είχε αν η ανάθεση είχε βασιστεί στην πραγματική συνάρτηση κέρδους του, δεδομένου του ότι οι υπόλοιποι παίκτες λένε την αλήθεια. Παρουσιάζουμε μία απλή απόδειξη ότι ειλικρινείς ντετερμινιστικοί μηχανισμοί ανάθεσης δεν ελαχιστοποιούν τη ζήλεια, χαρακτηρίζοντας τέτοιους μηχανισμούς για δύο παίκτες και δύο αντικείμενα. Συγκεκριμένα, στην απόδειξη μας φαίνεται ότι για κάθε τέτοιο ειλικρινή μηχανισμό υπάρχουν στιγμιότυπα για τα οποία η ζήλεια σχεδόν μεγιστοποιείται. Επίσης, παρουσιάζουμε μία ανάλυση για ομοιόμορφα τυχαίες αναθέσεις οι οποίες είναι ειλικρινείς μηχανισμοί κατά μέσο όρο. Τα αποτελέσματα αυτά απλοποιούν και βελτιώνουν προηγούμενα αποτελέσματα των Lipton, Markakis, Mossel και Saberi. Συγκεκριμένα, δείχνουμε ότι η ζήλεια φράσσεται εκ των άνω από την ποσότητα O(a√(m ln n)) με μεγάλη πιθανότητα, όπου a είναι το μέγιστο κέρδος για κάθε αντικείμενο για κάθε παίκτη, n είναι ο αριθμός των παικτών και m ο αριθμός των αντικειμένων. Για την περίπτωση που το κέρδος κάθε παίκτη στο σύνολο των αντικειμένων είναι 1, το φράγμα γίνεται O(√(a ln n)). Στη συνέχεια μελετούμε την επίπτωση της δικαιοσύνης στην αποδοτικότητα των αναθέσεων. Στα ακόλουθα θα θεωρούμε ότι όντως είναι γνωστές οι πραγματικές συναρτήσεις κέρδους των παικτών. Επίσης, θεωρούμε και αναθέσεις αγγαρειών εκτός από αγαθών, καθώς επίσης και αναθέσεις διαιρετών εκτός από αδιαίρετων αντικειμένων. Ασχολούμαστε με τρείς διαφορετικές έννοιες δικαιοσύνης ανάμεσα στους παίκτες, συγκεκριμένα την αναλογικότητα, τη μη ύπαρξη ζήλειας και την ισοτιμία για αναθέσεις διαιρετών και αδιαίρετων αγαθών και αγγαρειών. Γενικά, μία ανάθεση αντικειμένων σε n παίκτες είναι αναλογική εάν σε κάθε παίκτη δίνεται η εντύπωση ότι παίρνει ένα σύνολο αντικειμένων “καλύτερο” από ποσοστό 1/n του συνόλου των αντικειμένων προς ανάθεση. Μία ανάθεση είναι χωρίς-ζήλεια εάν κάε παίκτης προτιμά όσα του έχουν ανατεθεί σε σύγκριση με το τι έχει πάρει οποιοσδήποτε άλλος παίκτης, ενώ μία ανάθεση είναι ισότιμη όταν όλοι οι παίκτες είναι εξ'ίσου ικανοποιημένοι με αυτά που τους έχουν ανατεθεί. Τέλος, μία ανάθεση είναι βέλτιστη εάν μεγιστοποιεί το κέρδος (ελαχιστοποιεί το κόστος, αντίστοιχα) του συνόλου των παικτών, δηλ. κάθε αντικείμενο ανατίθεται σε εκείνον τον παίκτη που το εκτιμά περισσότερο (του κοστίζει λιγότερο, αντίστοιχα). Παρουσιάζουμε μία σειρά αποτελεσμάτων για το κόστος της δικαιοσύνης όσον αφορά σε κάθε μία από τις τρείς έννοιες δικαιοσύνης που αναφέρθηκαν παραπάνω, πάνω σε διαιρετά και αδιαίρετα αντικείμενα αγαθών και αγγαρειών και ποσοτικοποιούμε την απώλεια αποδοτικότητας σε δίκαιες αναθέσεις σε σύγκριση με τις βέλτιστες. Παρουσιάζουμε άνω και κάτω φράγματα για κάθε περίπτωση, τα περισσότερα από τα οποία είτε συμπίπτουν είτε απέχουν κατά σταθερούς πολλαπλασιαστικούς παράγοντες. / Fair division (or fair allocation) dates back to the ancient times and has found applications such as border settlement in international disputes, greenhouse gas emissions reduction, allocation of mineral riches in the ocean bed, inheritance, divorces, etc. In the era of the Internet, it appears regularly in distributed resource allocation and cost sharing in communication networks. We consider allocation problems in which a set of goods or chores has to be allocated among several players. Each player has a utility (disutility) function indicating the happiness (regret) of the player if she is allocated the particular good (chore, respectively); this function is non-negative and additive. The objective of the problem is the efficiency and the fairness of the allocation, but restrictions like the selfish nature of the players lead to very interesting variants of the problem. Our first result stems from the study of the problem where a set of indivisible items has to be allocated to some players and where allocations in which no player envies the bundle of items allocated to the other players too much are considered. Indivisibility implies that an item cannot be broken into parts and must be allocated to a single player, and envy, intuitively implies the preference of a player for the bundle of items allocated to another player compared to that of the items allocated to her. As we stated above, in practice, players are usually selfish in the sense that they aim to increase their benefit, i.e., their total utility on the bundle of items the algorithm allocates to them. In order to do so, they may report false valuations of items to the algorithm (i.e., different than their true utilities). Truthful allocation functions guarantee that the allocation is based on the true utilities of the players. In a sense, a truthful allocation function motivates the players to be truthful, or, put differently, guarantees that the benefit obtained by a player when reporting false valuations on the items is not greater than the benefit she would have obtained by telling the truth, given that the rest of the players are truthful. We present a simple proof that deterministic truthful allocations do not minimize envy by characterizing the truthful mechanisms for two players and two items. Our proof actually shows that for any truthful allocation function, there are instances in which the envy is almost maximized. We also present an improved analysis of uniformly random allocations of m items over n players, which are truthful in expectation. We show that the envy is at most O(a√(mln n)) with high probability, where a is the maximum utility per item over all players and items. For the case where the sum of utilities of each player is 1, we prove a bound of O(√(aln n)). This improves the previous bound of O(√a n^{1/2+e}) for any e>0. We also study the impact of fairness on the efficiency of allocations. For this part of the paper, we assume that the true utility functions of the players are public knowledge. We consider both goods and chores, as well as divisible and indivisible items. Furthermore, we consider three different notions of fairness, namely proportionality, envy-freeness, and equitability. Informally, an allocation among n players is proportional if each player has the impression that she gets a better share than a fraction of 1/n of the items to be allocated. An allocation is envy-free if no player envies some other player, whereas an allocation is equitable when all players are equally happy with their shares. Finally, an allocation is optimal when it maximizes the total utility (minimizes the total disutility, respectively) of the set of players, i.e., each item is allocated to the player that values it the most (costs her the least). We present a series of results on the price of fairness under the three aforementioned different notions of fairness, for the cases of divisible and indivisible goods and chores, and quantify the efficiency loss in fair allocations compared to optimal ones. We present upper and lower bounds on each case, most of which are either exact or tight within constant factors.

Many e-voting techniques have been proposed but not widely used in reality. One of the problems associated with most of existing e-voting techniques is the lack of transparency, leading to a failure to deliver voter assurance. In this work, we propose a transparent, auditable, end-to-end verifiable, and mutual restraining e-voting protocol that exploits the existing multi-party political dynamics such as in the US. The new e-voting protocol consists of three original technical contributions -- universal verifiable voting vector, forward and backward mutual lock voting, and in-process check and enforcement -- that, along with a public real time bulletin board, resolves the apparent conflicts in voting such as anonymity vs. accountability and privacy vs. verifiability. Especially, the trust is split equally among tallying authorities who have conflicting interests and will technically restrain each other. The voting and tallying processes are transparent to voters and any third party, which allow any voter to verify that his vote is indeed counted and also allow any third party to audit the tally. For the environment requiring receipt-freeness and coercion-resistance, we introduce additional approaches to counter vote-selling and voter-coercion issues. Our interactive voting protocol is suitable for small number of voters like boardroom voting where interaction between voters is encouraged and self-tallying is necessary; while our non-interactive protocol is for the scenario of large number of voters where interaction is prohibitively expensive. Equipped with a hierarchical voting structure, our protocols can enable open and fair elections at any scale.

La théorie des champs de vecteurs logarithmiques et des formes différentielles logarithmiques d’une hypersurface singulière réduite est développée par K.Saito. Ces notions apparaissent dans l’étude de la connexion de Gauss-Manin de certaines familles de singularités et de leur déploiement semi-universel.Lorsque le module des champs de vecteurs logarithmiques est libre, l’hypersurface est appelée diviseur libre. A.G. Aleksandrov et A. Tsikh généralisent les notions de formes différentielles logarithmiques et de résidus logarithmiques aux intersections complètes et aux espaces de Cohen-Macaulay réduits.Nous étudions dans ce travail les formes différentielles logarithmiques d’un espace singulier réduit de codimension quelconque plongé dans une variété lisse, et nous développons une notion de singularités libres qui étend la notion de diviseurs libres. Les résidus des formes différentielles logarithmiques d’une hypersurface ainsi que leur généralisation aux espaces de codimension supérieure interviennent de façon cruciale dans ce travail de thèse. Notre premier objectif est de donner des caractérisations de la liberté pour les intersections complètes et les espaces de Cohen-Macaulay qui généralisent le cas des hypersurfaces. Nous accordons ensuite une attention particulière à une famille de singularités libres, à savoir les courbes, pour lesquelles nous décrivons le module des résidus logarithmiques en termes de multi-valuations. / The theory of logarithmic vector fields and logarithmic differential forms along a reduced singular hypersurface is developed by K. Saito. These notions appear in the study of the Gauss-Manin connection of some families of singularities and their semi-universal unfolding. If the module of logarithmic vector fields is free, the hypersurface is called a free divisor. A.G. Aleksandrov and A. Tsikh generalize the notions of logarithmic differential forms and logarithmic residues to reduced complete intersections and Cohen-Macaulay spaces. In this work, we study the logarithmic differential forms of a reduced singular space of any codimension embedded in a smooth manifold, and we develop a notion of free singularity which extend the notion of free divisor. The residues of logarithmic differential forms as well as theirgeneralization to higher codimension spaces are crucial in this thesis. Our first purpose is to give characterizations of freeness for complete intersections and Cohen-Macaulay spaces which generalize the case of hypersurfaces. We then give a particular attention to a family of free singularities, namely the curves, for which we describe the module of logarithmic residues thanks to their set of values.

Tato disertační práce představuje derivační stromy několika různých typů gramatik ve zobecněné Kurodově normální formě; jmenovitě obecné a regulárně řízené gramatiky, gramatiky s rozptýleným kontextem a spolupracující distribuované gramatické systémy. Definuje jednoduché stromové rysy založené na kontextových vlastnostech jednotlivých diskutovaných gramatik a dokazuje, že pokud existuje limitující konstanta k taková, že každá věta generovaného jazyka L odpovídá řetězci listových uzlů derivačního stromu, ve kterém je výskyt definovaných stromových rysů omezen konstantou k, jazyk L je ve skutečnosti bezkontextový. Tato práce dále ukazuje, že dosažený výsledek představuje silný nástroj důkazu bezkontextovosti jazyka. Vše je doplněno příklady praktického využití nástroje.

Cette thèse s'inscrit dans la théorie des matrices aléatoires, à l'intersection avec la théorie des probabilités libres et des algèbres d'opérateurs. Elle s'insère dans une démarche générale qui a fait ses preuves ces dernières décennies : importer les techniques et les concepts de la théorie des probabilités non commutatives pour l'étude du spectre de grandes matrices aléatoires. On s'intéresse ici à des généralisations du théorème de liberté asymptotique de Voiculescu. Dans les Chapitres 1 et 2, nous montrons des résultats de liberté asymptotique forte pour des matrices gaussiennes, unitaires aléatoires et déterministes. Dans les Chapitres 3 et 4, nous introduisons la notion de fausse liberté asymptotique pour des matrices déterministes et certaines matrices hermitiennes à entrées sous diagonales indépendantes, interpolant les modèles de matrices de Wigner et de Lévy. / The thesis fits into the random matrix theory, in intersection with free probability and operator algebra. It is part of a general approach which is common since the last decades: using tools and concepts of non commutative probability in order to get general results about the spectrum of large random matrices. Where are interested here in generalization of Voiculescu's asymptotic freeness theorem. In Chapter 1 and 2, we show some results of strong asymptotic freeness for gaussian, random unitary and deterministic matrices. In Chapter 3 and 4, we introduce the notion of asymptotic false freeness for deterministic matrices and certain random matrices, Hermitian with independent sub-diagonal entries, interpolating Wigner and Lévy models.

In diese Dissertation, betrachte ich das Problem der Aufteilung der unteilbaren Objekte unter Agenten, ihren Vorlieben entsprechend, und die Transfers fehlen. In Kapitel 1 studiere ich den Kompromiss zwischen Fairness und Effizienz in der Klasse der strategy-proof Aufteilungsmechanismen. Das wichtigste Ergebnis ist, dass für die strategy-proof Mechanismen folgende Effizienz- und Fairness-Kriterien nicht miteinander vereinbar sind: (1) Ex-post-Effizienz und Neidfreiheit, (2) Ordnung-Effizienz und schwache Neidfreiheit und (3) Ordnung-Effizienz und gleiche-Teilung-untere-Grenze. In Kapitel 2 ist der Fokus auf zwei Darstellungen einer Zuteilung: als probabilistische Zuordnung und als Lotterie über deterministische Zuordnungen. Um die Gestaltung der praktischen Lotterie-Mechanismen zu erleichtern schlagen wir neue Werkzeuge für den Erhalt der stochastischen Verbesserungen bei Lotterien vor. Als Anwendungen schlagen wir Lotterie Mechanismen, die die weit verbreiteten Random serial dictatorship Mechanismus verbessern, und eine Lotterie-Darstellung seiner Konkurrent, die Probabilistic serial Mechanismus, vor. In Kapitel 3 schlage ich einen neuen Mechanismus vor, der Schüler an Grundschulen zuweist: Adaptive Acceptance (AA). AA sammelt von Neumann-Morgenstern Präferenzen von Studenten über Schulen und implementiert die Zuordnung unter Verwendung eines iterativen Verfahrens, das ähnlich der vorherrschenden Immediate Acceptance (IA) ist. AA verfügt über eine starke Kombination von Anreize und Effizienzeigenschaften im Vergleich zu IA und sein Rivale, Deferred Acceptance (DA). / I consider the problem of allocating indivisible objects among agents according to their preferences when transfers are absent. In Chapter 1, I study the tradeoff between fairness and efficiency in the class of strategy-proof allocation mechanisms. The main finding is that for strategy-proof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) Ex-post efficiency and envy-freeness, (2) ordinal efficiency and weak envy-freeness and (3) ordinal efficiency and equal division lower bound. In Chapter 2, the focus is on two representations of an allocation when randomization is used: as a probabilistic assignment and as a lottery over deterministic assignments. To help facilitate the design of practical lottery mechanisms, we provide new tools for obtaining stochastic improvements in lotteries. As applications, we propose lottery mechanisms that improve upon the widely-used random serial dictatorship mechanism, and a lottery representation of its competitor, the probabilistic serial mechanism. In Chapter 3, I propose a new mechanism to assign students to primary schools: the Adaptive Acceptance rule (AA). AA collects von Neumann-Morgenstern utilities of students over schools and implements the assignment using an iterative procedure similar to the prevalent Immediate Acceptance rule (IA). AA enjoys a strong combination of incentive and efficiency properties compared to IA and its rival, the Deferred Acceptance rule (DA). In case of strict priorities, AA implements the student-optimal stable matching in dominant strategies, which dominates each equilibrium outcome of IA. In case of no priorities, AA is ex-post efficient while some equilibrium outcomes of IA are not; also, AA causes loss of ex-ante efficiency less often than DA. If, in addition, students have common ordinal preferences, AA is approximately strategy-proof and ex-ante dominates DA.

Nous définissons des formes normales géodésiques pour les séries générales des groupes de réflexions complexes G(de,e,n). Ceci nécessite l'élaboration d'une technique combinatoire afin de déterminer des décompositions réduites et de calculer la longueur des éléments de G(de,e,n) sur un ensemble générateur donné. En utilisant ces formes normales géodésiques, nous construisons des intervalles dans G(e,e,n) qui permettent d'obtenir des groupes de Garside. Certains de ces groupes correspondent au groupe de tresses complexe B(e,e,n). Pour les autres groupes de Garside, nous étudions certaines de leurs propriétés et nous calculons leurs groupes d'homologie sur Z d'ordre 2. Inspirés par les formes normales géodésiques, nous définissons aussi de nouvelles présentations et de nouvelles bases pour les algèbres de Hecke associées aux groupes de réflexions complexes G(e,e,n) et G(d,1,n) ce qui permet d'obtenir une nouvelle preuve de la conjecture de liberté de BMR (Broué-Malle-Rouquier) pour ces deux cas. Ensuite, nous définissons des algèbres de BMW (Birman-Murakami-Wenzl) et de Brauer pour le type (e,e,n). Ceci nous permet de construire des représentations de Krammer explicites pour des cas particuliers des groupes de tresses complexes B(e,e,n). Nous conjecturons que ces représentations sont fidèles. Enfin, en se basant sur nos calculs heuristiques, nous proposons une conjecture sur la structure de l'algèbre de BMW. / We define geodesic normal forms for the general series of complex reflection groups G(de,e,n). This requires the elaboration of a combinatorial technique in order to determine minimal word representatives and to compute the length of the elements of G(de,e,n) over some generating set. Using these geodesic normal forms, we construct intervals in G(e,e,n) that give rise to Garside groups. Some of these groups correspond to the complex braid group B(e,e,n). For the other Garside groups that appear, we study some of their properties and compute their second integral homology groups. Inspired by the geodesic normal forms, we also define new presentations and new bases for the Hecke algebras associated to the complex reflection groups G(e,e,n) and G(d,1,n) which lead to a new proof of the BMR (Broué-Malle-Rouquier) freeness conjecture for these two cases. Next, we define a BMW (Birman-Murakami-Wenzl) and Brauer algebras for type (e,e,n). This enables us to construct explicit Krammer's representations for some cases of the complex braid groups B(e,e,n). We conjecture that these representations are faithful. Finally, based on our heuristic computations, we propose a conjecture about the structure of the BMW algebra.

Consumers of digital contents are empowered with numerous technologies allowing them to produce perfect copies of these contents and distribute them around the world with little or no cost. To prevent illegal copying and distribution, a technology called Digital Rights Management (DRM) is developed. With this technology, consumers are allowed to access digital contents only if they have purchased the corresponding licenses from license issuers. The problem, however, is that those consumers are not allowed to resell their own licenses- a restriction that goes against the first-sale doctrine. Enabling a consumer to buy a digital license directly from another consumer and allowing the two consumers to fairly exchange the license for a payment are still an open issue in DRM research area. This thesis investigates existing security solutions for achieving digital license reselling and analyses their strengths and weaknesses. The thesis then proposes a novel Reselling Deal Signing (RDS) protocol to achieve fairness in a license reselling. The idea of the protocol is to integrate the features of the concurrent signature scheme with functionalities of a License Issuer (LI). The security properties of this protocol is informally analysed and then formally verified using ATL logic and the model checker MOCHA. To assess its performance, a prototype of the RDS protocol has been developed and a comparison with related protocols has been conducted. The thesis also introduces two novel digital tokens a Reselling Permission (RP) token and a Multiple Reselling Permission (MRP) token. The RP and MRP tokens are used to show whether a given license is single and multiple resalable, respectively. Moreover, the thesis proposes two novel methods supporting fair and secure digital license reselling. The first method is the Reselling Deal (RD) method which allows a license to be resold once. This method makes use of the existing distribution infrastructure, RP, License Revocation List (LRL), and three protocols: RDS protocol RD Activation (RDA) protocol, and RD Completion (RDC) protocol. The second method is a Multiple License Reselling (MLR) method enabling one license to be resold N times by N consumers. The thesis presents two variants of the MLR method: RRP-MR (Repeated RP-based Multi-Reselling) and HC-MR (Hash Chain-based Multi-Reselling). The RRP-MR method is designed such that a buyer can choose to either continue or stop a multi-reselling of a license. Like the RD method, the RRP-MR method makes use of RP, LI, LRL, and the RDS, RDA, and RDC protocols to achieve fair and secure reselling. The HC-MR method allows multiple resellings while keeping the overhead on LI at a minimum level and enable a buyer to check how many times a license can be further resold. To do so, the HC-MR utilises MRP and the hash chain cryptographic primitive along with LRL, LI and the RDS, RDA and RDC protocols. The analysis and the evaluation of these three methods have been conducted. While supporting the license reselling, the two methods are designed to prevent a reseller from (1) continuing using a resold license, (2) reselling a non-resalable license, and (3) reselling one license a unauthorised number of times. In addition, they enable content owners of resold contents to trace a buyer who has violated any of the usage rights of a license bought from a reseller. Moreover, the methods enable a buyer to verify whether a license he is about to buy is legitimate for re-sale. Furthermore, the two methods support market power where a reseller can maximise his profit and a buyer can minimise his cost in a reselling process. In comparison with related works, our solution does not make use of any trusted hardware device, thus it is more cost-effective, while satisfying the interests of both resellers and buyers, and protecting the content owner's rights.