Neidminimierung - Envy minimization

In der Informatik und Operations Research , das Neid Minimierung Problem das Problem der Zuordnung von einzelnen Elementen unter Agenten mit unterschiedlichen Bewertungen über die Elemente ist, so dass die Menge von Neid ist so klein wie möglich.

Aus Fairness-Perspektive möchte man idealerweise eine neidfreie Artikelzuordnung finden – eine Zuteilung, bei der kein Agent einen anderen Agenten beneidet. Das heißt: Kein Agent bevorzugt das Bündel, das einem anderen Agenten zugewiesen ist. Bei unteilbaren Gegenständen kann dies jedoch unmöglich sein. Ein Ansatz zur Bewältigung dieser Unmöglichkeit besteht darin, das Problem in ein Optimierungsproblem umzuwandeln , bei dem die Verlustfunktion eine Funktion ist, die den Neidbetrag beschreibt. Im Allgemeinen ist dieses Optimierungsproblem NP-schwer , da selbst die Entscheidung, ob eine neidfreie Zuweisung vorliegt, dem Partitionsproblem äquivalent ist . Es gibt jedoch Optimierungsalgorithmen, die in der Praxis gute Ergebnisse liefern können.

Definieren Sie die Menge an Neid

Es gibt mehrere Möglichkeiten, die Zielfunktion (das Ausmaß des Neids) für die Minimierung zu definieren. Einige von ihnen sind:

Die Zahl der neidischen Agenten ;
Die Anzahl der Neid-Beziehungen (-Kanten im Neid-Graphen );
Das maximale Neidverhältnis , wobei das Neidverhältnis von i in j in der Zuordnung X definiert ist als: ; das Verhältnis ist also 1, wenn ich j nicht beneidet , und es ist größer, wenn ich j
beneidet . ${\text{EnvyRatio}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})} \Recht)$ ${\text{EnvyRatio}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})} \Recht)$
- Ebenso kann man die Summe der Neid-Verhältnisse oder ihr Produkt betrachten.
Das Maximum, die Summe oder das Produkt der Neid-Differenz .

Minimierung des Neid-Verhältnisses

Bei allgemeinen Bewertungen erfordert jeder deterministische Algorithmus, der das maximale Neidverhältnis minimiert, eine Anzahl von Abfragen, die im schlimmsten Fall exponentiell in der Anzahl der Güter ist.

Bei additiven und identischen Bewertungen :

Der folgende Greedy-Algorithmus findet eine Allokation, deren maximales Neid-Verhältnis höchstens das 1,4-fache des Optimums beträgt:
1. Sortieren Sie die Artikel nach absteigendem Wert;
2. Wenn es mehr Artikel gibt, geben Sie den nächsten Artikel an einen Agenten mit dem kleinsten Gesamtwert.
Es gibt ein PTAS für die Minimierung des maximalen Neid-Verhältnisses. Außerdem gibt es bei konstanter Spielerzahl ein FPTAS .

Mit additiven und unterschiedlichen Bewertungen :

Wenn die Anzahl der Agenten Teil der Eingabe ist, ist es unmöglich, in polynomieller Zeit einen Näherungsfaktor besser als 1,5 zu erhalten, es sei denn, P = NP.
Wenn die Anzahl der Agenten konstant ist (kein Teil der Eingabe), gibt es einen FPTAS zum Minimieren des maximalen Neid-Verhältnisses und des Produkts der Neid-Verhältnisse.
Wenn die Anzahl der Agenten der Anzahl der Elemente entspricht, gibt es einen Polynomialzeitalgorithmus.

Verteilte Neidminimierung

In manchen Fällen ist es erforderlich, eine neidminimierende Zuordnung verteilt zu berechnen, dh jeder Agent sollte seine eigene Zuordnung so berechnen, dass die resultierende Zuordnung konsistent ist. Dieses Problem kann gelöst werden, indem es wie folgt als asymmetrisches verteiltes Beschränkungsoptimierungsproblem (ADCOP) dargestellt wird.

Fügen Sie für jeden Agenten i und jedes Element j eine binäre Variable v _{ij hinzu} . Der Variablenwert ist "1", wenn der Agent das Element erhält, andernfalls "0". Die Variable gehört dem Agenten i .
Um die Einschränkung auszudrücken, dass jedes Element höchstens einem Agenten gegeben wird, fügen Sie binäre Einschränkungen für jeweils zwei verschiedene Variablen hinzu, die sich auf dasselbe Element beziehen, mit unendlichen Kosten, wenn die beiden Variablen gleichzeitig "1" sind, andernfalls mit null Kosten.
Um die Einschränkung auszudrücken, dass alle Elemente zugewiesen werden müssen, fügen Sie für jedes Element eine n- äre Einschränkung hinzu (wobei n die Anzahl der Agenten ist), mit unendlichen Kosten, wenn keine Variable, die sich auf dieses Element bezieht, "1" ist.

Das Problem kann mit dem folgenden lokalen Suchalgorithmus gelöst werden .

Alle Agenten sind lexikographisch geordnet (zB nach ihrem Namen oder Index).
Jeder Agent ordnet seine Variablen auch lexikographisch.
Jeder Agent beansprucht seinerseits alle Posten, die keinem Agenten mit einer höheren Priorität zugeordnet wurden ("Ansprüche" bedeutet, dass der Agent der entsprechenden Variablen "1" zuweist).
Nachdem ein Agent alle seine Variablen zugewiesen hat (entweder 1 oder 0), sendet er die resultierende Zuweisung an den nächsten Agenten in der lexikografischen Reihenfolge.
Die Agenten senden sich mit ihrer neidischen Bewertung des aktuellen Einsatzes gegenseitig Nachrichten.
Missgunst Auswertungen von anderen Agenten nach dem Empfang kann das Mittel entscheiden Rückzieher auf eine Variable; Wenn keine Variablen mehr zum Zurückverfolgen vorhanden sind, kann der Agent zu einem vorherigen Agenten zurückverfolgen. Sobald der erste Agent seine erste Variable zurückverfolgt, ist die Suche beendet und die optimale Zuordnung gefunden.

Online-Minimierung des Neid-Unterschieds

Manchmal sind die zuzuweisenden Artikel nicht alle auf einmal verfügbar, sondern kommen im Laufe der Zeit online an. Jeder ankommende Artikel muss sofort zugeordnet werden. Ein Anwendungsbeispiel ist die Problematik einer Tafel , die Lebensmittelspenden entgegennimmt und diese umgehend karitativen Zwecken zuordnen muss.

Benade, Kazachkov, Procaccia und Psomas betrachten das Problem der Minimierung der maximalen Neid-Differenz , wobei die Bewertungen so normalisiert werden, dass der Wert jedes Elements in [0,1] liegt. Beachten Sie, dass es in der Offline-Variante dieser Einstellung leicht ist, eine Zuordnung zu finden, bei der die maximale Neid-Differenz 1 beträgt (eine solche Zuordnung wird EF1 genannt; für weitere Details siehe neidfreie Artikelzuordnung ). Bei der Online-Variante nimmt der Neid-Unterschied jedoch mit der Stückzahl zu. Sie zeigen einen Algorithmus, bei dem der Neid nach T Items in ist . Jiang, Kulkarni und Singla verbessern ihren Neid einen Algorithmus zur gebunden mit Online zweidimensionaler Diskrepanz Minimierung . $O({\sqrt {T/n}})$

Andere Einstellungen

Andere Umgebungen, in denen Neidminimierung untersucht wurde, sind:

Optimale Steuer .
Wahl der Schule .

Verweise

^ ^a ^b Lipton, RJ; Markakis, E.; Mossel, E.; Saberi, A. (2004). „Über ungefähr gerechte Zuteilungen von unteilbaren Gütern“. Tagungsband der 5. ACM-Konferenz zum elektronischen Geschäftsverkehr - EC '04 . s. 125. doi : 10.1145/988772.988792 . ISBN 1-58113-771-0.
^ Graham, RL (1969). "Grenzen bei Multiprocessing-Timing-Anomalien". SIAM Journal für Angewandte Mathematik . 17 (2): 416–429. CiteSeerX 10.1.1.90.8131 . doi : 10.1137/0117039 .
^ Nguyen, Trung Thanh; Rothe, Jörg (2014). "Minimierung von Neid und Maximierung der durchschnittlichen Nash-Sozialwohlfahrt bei der Zuteilung unteilbarer Güter" . Diskrete Angewandte Mathematik . 179 : 54–68. doi : 10.1016/j.dam.2014.09.010 .
^ ^a ^b Netzer, Arnon; Meisels, Amnon; Zivan, Roie (2016-03-01). "Verteilte Neidminimierung für die Ressourcenallokation" . Autonome Agenten und Multi-Agenten-Systeme . 30 (2): 364–402. doi : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .
^ Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Christos-Alexandros (2018-06-11). „Wie man Neid im Laufe der Zeit verschwinden lässt“ . Proceedings of the 2018 ACM Conference on Economics and Computation . EM '18. Ithaca, NY, USA: Association for Computing Machinery: 593–610. doi : 10.1145/3219166.3219179 . ISBN 978-1-4503-5829-3. S2CID 3340196 .
^ Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). „Online Geometrische Diskrepanz für stochastische Ankünfte mit Anwendungen zur Neidminimierung“. arXiv : 1910.01073 [ cs.DS ].
^ Yukihiro, Nishimura (2008). "Neidminimierung im optimalen Steuerkontext" . AgEcon-Suche . doi : 10.22004/ag.econ.273655 .
^ Abdulkadiroglu, Atila; Che, Yeon-Koo; Pathak, Parag A.; Roth, Alvin E.; Tercieux, Olivier (2017-03-27). "Berechtigten Neid bei der Schulwahl minimieren: Das Design von New Orleans' OneApp" . Cite Journal erfordert |journal=( Hilfe )

[lmms04-1] Lipton, RJ; Markakis, E.; Mossel, E.; Saberi, A. (2004). „Über ungefähr gerechte Zuteilungen von unteilbaren Gütern“. Tagungsband der 5. ACM-Konferenz zum elektronischen Geschäftsverkehr - EC '04 . s. 125. doi : 10.1145/988772.988792 . ISBN 1-58113-771-0.

[g69-2] Graham, RL (1969). "Grenzen bei Multiprocessing-Timing-Anomalien". SIAM Journal für Angewandte Mathematik . 17 (2): 416–429. CiteSeerX 10.1.1.90.8131 . doi : 10.1137/0117039 .

[nr15-3] Nguyen, Trung Thanh; Rothe, Jörg (2014). "Minimierung von Neid und Maximierung der durchschnittlichen Nash-Sozialwohlfahrt bei der Zuteilung unteilbarer Güter" . Diskrete Angewandte Mathematik . 179 : 54–68. doi : 10.1016/j.dam.2014.09.010 .

[:2-4] Netzer, Arnon; Meisels, Amnon; Zivan, Roie (2016-03-01). "Verteilte Neidminimierung für die Ressourcenallokation" . Autonome Agenten und Multi-Agenten-Systeme . 30 (2): 364–402. doi : 10.1007/s10458-015-9291-7 . ISSN 1387-2532 . S2CID 13834856 .

[:0-5] Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Christos-Alexandros (2018-06-11). „Wie man Neid im Laufe der Zeit verschwinden lässt“ . Proceedings of the 2018 ACM Conference on Economics and Computation . EM '18. Ithaca, NY, USA: Association for Computing Machinery: 593–610. doi : 10.1145/3219166.3219179 . ISBN 978-1-4503-5829-3. S2CID 3340196 .

[6] Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). „Online Geometrische Diskrepanz für stochastische Ankünfte mit Anwendungen zur Neidminimierung“. arXiv : 1910.01073 [ cs.DS ].

[7] Yukihiro, Nishimura (2008). "Neidminimierung im optimalen Steuerkontext" . AgEcon-Suche . doi : 10.22004/ag.econ.273655 .

[8] Abdulkadiroglu, Atila; Che, Yeon-Koo; Pathak, Parag A.; Roth, Alvin E.; Tercieux, Olivier (2017-03-27). "Berechtigten Neid bei der Schulwahl minimieren: Das Design von New Orleans' OneApp" . Cite Journal erfordert |journal=( Hilfe )

Languages

In other projects