Fair-Share-Zuweisungen für Agenten mit willkürlichen Ansprüchen

Wir betrachten das Problem der fairen Zuteilung von unteilbaren Gütern an n Agenten ohne Transfers. Wenn die Agenten gleiche Ansprüche haben, dient das gut etablierte Konzept des Maximinanteils (MMS) als attraktives Fairnesskriterium, wobei eine Zuteilung, um als fair zu gelten, jedem Agenten mindestens einen wesentlichen Bruchteil ihres MMS geben muss. In diesem Papier betrachten wir den Fall willkürlicher (ungleicher) Ansprüche. Wir erklären die Mängel in früheren Versuchen, den MMS auf ungleiche Ansprüche zu erweitern. Unser konzeptioneller Beitrag ist die Einführung eines neuen Begriffs für einen Anteil, den AnyPrice-Anteil (APS), der für Einstellungen mit willkürlichen Ansprüchen geeignet ist. Der AnyPrice-Anteil eines Agenten ist der Wert, den sie sich selbst garantieren kann, wenn ihr ein Budget gleich ihrem Anspruch gegeben wird, und sie ihr hochpreisigstes, erschwingliches Set kauft, wenn die Artikel feindlich mit einem Gesamtpreis bepreist sind, der dem Gesamtanspruch entspricht. Selbst im Fall der gleichen Ansprüche ist dieses Konzept neu und erfüllt APS ≥ MMS, wobei die Ungleichung manchmal strikt ist. Wir präsentieren auch eine alternative Definition für den APS als ein Maximierungsproblem (eine fraktionale Version des MMS) und bieten Vergleiche zwischen dem APS und früheren Fairnesskonzepten an. Unser Hauptergebnis bezieht sich auf additive Bewertungen und willkürliche Ansprüche, für die wir einen Algorithmus in Polynomialzeit bereitstellen, der jedem Agenten mindestens einen 3/5-Anteil ihres APS gibt. Dieser Algorithmus kann auch als Bereitstellung einer Strategie in einem bestimmten natürlichen Gebots-Spiel betrachtet werden, und diese Strategie sichert jedem Agenten, der sie nutzt, mindestens einen 3/5-Anteil ihres APS, unabhängig von den Strategien, die von anderen Agenten verwendet werden.