Athens University Economics and Business (AUEB)
Optimisation under preferences for matchings and circulations: combinatorial and polyhedral aspects
Abstract
dc:descriptionThis thesis examines different optimisation problems under preferences defined in terms of Graph Theory. We are interested in studying them from both combinatorial, polyhedral and algorithmic view. What we call preferences represent expressed options or possible decisions for an individual in an ordinal scale that answers which is better than the other. Many of the problems we study have been used to represent real life decision making situations for individuals or organizations. Firstly, the Stable Matching problem (SM), the many-to-many Stable Matching problem (MM) and the Stable Allocation (SA) are presented alongside with some important combinatorial and polyhedral results about them. A minimal polyhedral description is provided for SM, MM and the unconstrained case of SA via an affine transformation of the order polytope of their rotation-poset. For the unconstrained case of SA it is the first time that a minimal description is provided. To establish this affine transformation some necessary structure results for these problems have been proved. Then, this thesis proposes a novel setting of relaxing stability in SM, called Unstable Matching problem, where each pair has a value for participating in the matching and a cost of blocking it. Finding a matching of that maximizes the function of value minus the blocking cost is NP-hard. If the value and the cost function are identical the cases where either this function is restricted to (0, 1) or satisfies the preference-concordancy property are solved in polynomial time. In contrast, if the function is restricted to two general values (α, β) the problem remains NP-hard. Another variation that is proved to be polynomially solvable is when the set of pairs is partitioned into those that can be part of the output matching but are not allowed to block it (their cost is +∞) and those that can block at a cost, but cannot be part of it (their value is −∞). This thesis also examines a novel one-to-many generalization of House Allocation problem where there is no upper bound of how many agents can receive a specific good but there are pairs of agents who cannot receive the same good. From another perspective this variation of House Allocation problem can be viewed as a list coloring under preferences problem. Even though Serial Dictatorship mechanism still returns a Pareto optimal allocation, a simple counter example shows that there are Pareto optimal allocations not obtainable by SD. Interestingly, the problem of verifying whether a given assignment is Pareto optimal is no longer easy but becomes coNP-complete. Some special cases where the verification problem remains easy are shown. The last problem studied in this thesis is an exchange market under preferences variation with agent-specific indivisible goods where the central criterion is Pareto optimality. A solution is returned by Top Trading Cycle Mechanism and also a combinatorial characterization of the Pareto optimal solutions is provided. This characterization leads directly to an easy way of recognising whether a given exchange is Pareto optimal. Moreover, it is proved that if there is a weight function for the possible exchange finding the maximum weight exchange is NP-hard. If the weight satisfies the preference-concordancy property then the problem is solved in polynomial time.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2023
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Samaris, Michail
- Σάμαρης, Μιχαήλ
Subjects
dc:subject × 21- Συνδυαστική βελτιστοποίηση
- Προτιμήσεις
- Ταιριάσματα
- Χρωματισμοί
- COMBINATORIAL OPTIMIZATION
- Preferences
- Matching
- Coloring
- Circulation
- Μαθηματικά
- Φυσικές Επιστήμες
- Διακριτά μαθηματικά και Συνδυαστική
- Έλεγχος και Βελτιστοποίηση
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Mathematics
- Natural Sciences
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computer and Information Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/55011