Gewichtete EF1- und PO-Zuweisungen mit wenigen Typen von Agenten oder Aufgaben

Wir untersuchen die Existenz fairer und effizienter Zuweisungen von unteilbaren Aufgaben an asymmetrische Agenten, die ungleiche Ansprüche oder Gewichte haben. Wir betrachten das Fairnesskonzept der gewichteten Neidfreiheit bis zu einer Aufgabe (wEF1) und das Effizienzkonzept der Pareto-Optimalität (PO). Die Existenz von EF1- und PO-Zuweisungen von Aufgaben an symmetrische Agenten ist ein wichtiges offenes Problem in der diskreten fairen Teilung, und positive Ergebnisse sind nur für bestimmte strukturierte Fälle bekannt. In diesem Papier untersuchen wir dieses Problem in einem allgemeineren Rahmen asymmetrischer Agenten und zeigen, dass eine Zuweisung existiert, die wEF1 und PO ist und in polynomialer Zeit für Instanzen mit: - Drei Typen von Agenten, wobei Agenten des gleichen Typs identische Präferenzen haben, aber unterschiedliche Gewichte haben können. - Zwei Typen von Aufgaben, wobei die Aufgaben in zwei Mengen partitioniert werden können, wobei jede Menge Kopien derselben Aufgabe enthält. Für symmetrische Agenten etablieren unsere Ergebnisse, dass EF1- und PO-Zuweisungen für drei Typen von Agenten existieren und auch bekannte Ergebnisse für drei Agenten, zwei Typen von Agenten und zwei Typen von Aufgaben verallgemeinern. Unsere Algorithmen verwenden einen gewichteten Auswahlsequenzalgorithmus als Unterroutine; wir erwarten, dass diese Idee und unsere Analyse von unabhängigem Interesse sind.