Sortierung, Seitengrössen und algorithmische Ungerechtigkeit

Angenommen wir hätten ein System, dass Suchresultate paginiert (d.h. die Resultate werden in mehrere Seiten aufgeteilt) und nach Anzahl Interaktionen sortiert auflistet. Ein solches System könnte zum Beispiel ein Online Shop (Käufe), eine Suchmaschine (Clicks), ein Social Media Feed (Clicks) oder ein News-Aggregator (Clicks) sein. Hat die Darstellung der Resultate einen Einfluss auf die resultierende Verteilung der Interaktionen? Führt dies zu einer durch den Algorithmus eingeführte Ungerechtigkeit, d.h. werden einige Resultate mit der Zeit ungerechtfertigt bevorzugt behandelt? Eine erste Idee der Auswirkungen eines solches Systems kann durch Simulation gewonnen werden!

Modell

Für die Simulation wird eine agentenbasierte Modellierung verwendet. Jeder Agent durchstöbert eine paginierte, sortierte Liste von Elementen und interagiert mit einem zufällig ausgewählten Element. Es besteht die Möglichkeit, dass der Verbraucher nur die erste Seite durchblättert. Nach einigen Interaktionen wird die Liste absteigend nach Anzahl Interaktionen sortiert.

Zur Bestimmung der Ungleichverteilung wird der Hoover Index (der normierten mittleren absoluten Abweichung) berechnet:

Resultat

Eine Simulation mit 100 Elementen und 50 Interaktionen / Agenten pro Sortierung zeigt, dass je kleiner die Seitengrösse und je grösser die Wahrscheinlichkeit, nur die erste Seite zu durchstöbern, desto grösser die resultierende Ungleichverteilung. Überraschend ist dabei, dass bereits sehr geringe Wahrscheinlichkeiten zu einer merkbaren Ungleichverteilung führen.

Abbildung 1: Ungleichverteilung in Abhängigkeit der Seitengrösse und Wahrscheinlichkeit.

Weiter ist zu sehen, dass die Ungleichverteilung bereits nach wenigen Neusortierungen entsteht und relativ konstant bleibt (100 Items, Seitengrösse 20). Das Histogramm zeigt eine bimodale Verteilung: Einige wenige Elemente besitzen viele Interaktionen, viele Elemente haben nur sehr wenige Interaktionen.

Abbildung 2: Entwicklung der Ungleichverteilung und finale Verteilung.

Moderierende Faktoren

In einem solchen System kann es weitere moderierende Faktoren geben, welche zum Beispiel den Effekt der Ungleichverteilung abschwächen. Ein solcher Faktor könnte zum Beispiel ein maximales Alter der Elemente sein, z.B. in einem Shop Artikel, welche nicht mehr geliefert werden.

Das Modell wird so angepasst, dass jedes Element ein Alter in Anzahl Sortierungszyklen besitzt und nach einer bestimmten Anzahl Zyklen durch ein neues (mit Alter 0) ersetzt wird. Die initialen Elemente werden mit zufälligem Alter initialisiert.

Eine Simulation mit 100 Elementen, 50 Interaktionen / Agenten pro Neusortierung und einer Seitengrösse von 20 zeigt, dass die Ungleichverteilung dadurch bereits zu Beginn höher ist. Allgemein ist die Ungleichverteilung grösser, je kleiner das maximale Alter.

Abbildung 3: Ungleichverteilung in Abhängigkeit der Seitengrösse und Wahrscheinlichkeit, mit rotierendem Bestand.

Ein Blick auf die zeitliche Entwicklung (100 Items, Seitengrösse 20) zeigt den Unterschied zu vorher: Zwar gibt es auch hier bereits nach wenigen Neusortierungen bereits eine Ungleichverteilung, diese variiert mit der Zeit aber stärker. Zudem gibt nun eine unimodale Verteilung statt einer bimodalen Verteilung: die meisten Elemente besitzen nur wenige Interaktionen. Die Verteilung scheint ein kleines Bisschen fairer.

Abbildung 4: Entwicklung der Ungleichverteilung und finale Verteilung, mit rotierendem Bestand.

Weiterführende Informationen