Dokument: Approximierbarkeit und Unapproximierbarkeit der Optimierung der sozialen Wohlfahrt im Bereich der Multiagenten-Systeme

Titel:	Approximierbarkeit und Unapproximierbarkeit der Optimierung der sozialen Wohlfahrt im Bereich der Multiagenten-Systeme
Weiterer Titel:	Approximability and Inapproximability of Social Welfare Optimization in Multiagent Resource Allocation
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=27747
URN (NBN):	urn:nbn:de:hbz:061-20131125-154145-2
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Nguyen, Trung Thanh [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 644 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 25.11.2013 / geändert 25.11.2013
Beitragende:	Prof. Dr. Rothe, Jörg [Gutachter] Prof. Dr. Wanke, Egon [Gutachter]
Stichwörter:	optimization, multiagent system, social welfare, approximation algorithm
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	Das Aufteilen von G\"utern ist ein fundamentales Problem im Bereich der Multiagenten-Systeme, bei dem eine Menge von G\"utern unter einer Gruppe von Agenten aufgeteilt werden soll, sodass die soziale Wohlfahrt dabei optimiert wird. In den letzten Jahren wurde diesem Problem viel Aufmerksamkeit gewidmet, gerade weil es viele Anwendungen hat (siehe die \"Ubersicht von Chevaleyre et al. \cite{che-etal:j:multiagent-resource-allocation})). Diese Arbeit behandelt die Approximierbarkeit und die Unapproximierbarkeit von verschiedenen, wichtigen Optimierungsproblemen im Bereich der G\"uteraufteilung mit mehreren Agenten, wobei der Fokus auf zwei zentralen Formen liegt, die Pr\"aferenzen der Agenten zu repr\"asentieren: die B\"undel-Form und die $k$-additive Form. Weiterhin werden verschiedene Formen der sozialen Wohlfahrt untersucht, diese reichen von quantitativen Ma\ss en (utilitarische, egalitarische und Nash-Produkt soziale Wohlfahrt) bis hin zu qualitativen Ma\ss en (Neidfreiheit). Am Anfang widmen wir uns Probleme, die die soziale Wohlfahrt maximieren, dabei behandeln wir utilitarische und egalitarische soziale Wohlfahrt und soziale Wohlfahrt in Hinblick auf das Nash-Produkt (f\"ur die totale und die durchschnittliche Version). Wir erhalten verschiedene Approximierbarkeits- und Unapproximierbarkeits-Resultate. F\"ur utilitarische soziale Wohlfahrt mit $2$-additiven N\"utzlichkeitsfunktionen zeigen wir, dass es unm\"oglich ist einen Approximationsfaktor besser als $\nicefrac{21}{22}$ zu erhalten, solange nicht $\p=\np$ gilt. Weiterhin zeigen wir, dass die egalitarische soziale Wohlfahrt und die soziale Wohlfahrt in Hinblick auf das Nash-Produkt f\"ur jeden Faktor $\np$-hart zu approximieren sind. Beides gilt sowohl f\"ur die B\"undel-Form als auch f\"ur die 3-additive Form. Sind die N\"utzlichkeitsfunktionen additiv gegeben, erhalten wir einen H\"artefaktor von $(\nicefrac{8}{9})+\varepsilon$ f\"ur die Optimierung der totalen sozialen Wohlfahrt in Hinblick auf das Nash-Produkt und einen weiteren H\"artefaktor von $(\nicefrac{2\sqrt{2}}{3})+\varepsilon$ f\"ur die durchschnittliche Version. Alle unseren positiven Ergebnisse werden f\"ur die additive Form erreicht. Wir geben einen schnellen Greedy-Algorithmus an, der ein Ergebnis innerhalb eines Faktors von $\nicefrac{1}{(m-n+1)}$ f\"ur die Optimierung der durchschnittlichen sozialen Wohlfahrt in Hinblick auf das Nash-Produkt liefert. Dabei ist $n$ die Anzahl der Agenten und $m$ die Anzahl der G\"uter. Ausserdem beweisen wir, dass es f\"ur den Fall von identischen Agenten ein PTAS gibt. Genau genommen erhalten wir ein FPTAS f\"ur die Optimierung der egalitarischen sozialen Wohlfahrt und derer mit Hinblick auf das Nash-Produkt, falls die Anzal der Agenten nicht Teil der Eingabe ist. Am Ende betrachten wir den Spezialfall, dass $n=m$ gilt und wir geben einen Polynomialzeit-Algorithmus an, der die Optimall\"osung sowohl f\"ur das totale als auch f\"ur das durchschnittliche Problem die soziale Wohlfahrt in Hinblick auf das Nash-Produkt zu optimieren liefert. Dann betrachten wir das Problem, eine Menge von unteilbaren G\"utern zwischen Agenten mit additiven M\"utzlichkeitsfunktionen aufzuteilen, wobei auf Neidfreiheit und ihre schw\"acheren Bedeutungen geachtet wird. Anstatt uns auf neidfreie Aufteilungen zu konzentrieren (die nicht immer existieren), versuchen wir Aufteilungen zu finden, bei denen der Neid minimiert wird. Basierend auf Begriffen, die Chevaylere u.a. ~\cite{che-end-est-mau:c:reaching-envy-free-state-distribute-setting} eingef\"uhrt haben, definieren wir verschiedene Probleme um den Grad des Neides zu minimieren und betrachten deren Approximierbarkeit. Dann widmen mir uns der Frage, ob es einen wahrhaftigen Mechanismus gibt, um die (totale und durchschnittliche) soziale Wohlfahrt in Hinblick auf das Nash-Product zu maximieren, sowie dem Problem den Grad des Neides zu minimieren. Wir beweisen, dass dies sowohl f\"ur exakte als auch f\"ur approximative Mechanismen unm\"oglich ist. Zum Schluss f\"uhren wir ein Modell ein, dass es uns erlaubt, positionelle Punktregeln zum Aufteilen von unteilbaren G\"utern zu nutzen, wobei die Agenten ihre Pr\"aferenzen nur dadurch zum Ausdruck bringen, dass sie die einzelnen G\"uter nach ihrer Wertigkeit anordnen, von wertvoll bis wertlos. Wir definieren dann verschiedene Probleme, entweder in der Entscheidungsversion oder in der Optimierungsversion, und betrachten sie aus der Sicht der Berechenbarkeit. Resource allocation is a fundamental problem in the field of multiagent systems, where a set of resources need to be allocated to a group of agents in a way so as to optimizing social welfare. In the last few years this problem has received much attention, especially due to its wide applicability domain (see the survey of Chevaleyre et al. 2006). This thesis studies the approximability and inapproximability of several important optimization problems addressed in the area of multiagent resource allocation, focusing on two central representations of preferences, the bundle form and the $k$-additive form, and on various types of social welfare, ranging from quantitative measures (utilitarian, egalitarian and Nash product social welfare) to qualitative measures (envy-freeness). First of all, we study the social welfare maximization problems, where we consider utilitarian and egalitarian social welfare and social welfare by the Nash product (for both total and average versions). We obtain several approximability and inapproximability results. For the utilitarian social welfare maximization with $2$-additive utilities, we show that unless $\p=\np$, it is impossible to achieve an approximation factor better than $\nicefrac{21}{22}$. In addition, we prove that both egalitarian and Nash product social welfare maximization are $\np$-hard to approximate to within any factor, each for both the bundle form and the $3$-additive form. For utility functions represented as additive form, we establish a hardness factor of $(\nicefrac{8}{9})+\varepsilon$ for total Nash product social welfare maximization and another hardness factor of $(\nicefrac{2\sqrt{2}}{3})+\varepsilon$ for the average version. Our positive results have all been achieved regarding the additive form. We provide a fast greedy approximation algorithm to within a factor of ($\nicefrac{1}{m-n+1}$) for average Nash social welfare maximization, where $n$ and $m$ are the number of agents and the number of resources, respectively. We also prove that this problem admits a PTAS for the case of identical agents. Particularly, we obtain an FPTAS for maximization problems with respect to egalitarian and Nash product social welfare when the number of agents is not the part of input. Finally, we consider a special case when $n=m$ and present a polynomial-time algorithm that produces optimal solutions for both total and average Nash social welfare problems. We then consider the problem of fairly distributing a number of indivisible goods among agents with additive utility functions, focusing on envy-freeness and its weaker notions. Instead of concentrating on envy-free allocations (which might not always exist), we seek to find an allocation with minimum envy. Based on a notion introduced by Chevaleyre et al. 2007, we define several problems of minimizing the degree of envy and study their approximability. We next concern the question of whether there exist truthful mechanisms for the problem of maximizing (total and average) Nash product social welfare and the problem of minimizing the degree of envy. We show that this is impossible for both exact and approximation mechanisms. Finally we introduce a model of using the positional scoring rules for allocating indivisible resources, where agents express their preferences only by ranking single resources from the most preferred to the least preferred. We then define several problems, either in their decision or optimization version, and study them from a computational point of view.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät
Dokument erstellt am:	25.11.2013
Dateien geändert am:	25.11.2013
Promotionsantrag am:	18.07.2013
Datum der Promotion:	21.11.2013