Konkurrenzierende Banditen in nicht-stationären Matching-Märkten

Das Verständnis der komplexen Dynamik von zweiseitigen Online-Matching-Märkten, in denen die Nachfrageseite mit der Angebotsseite (Arme) konkurriert, hat in letzter Zeit erhebliches Interesse geweckt. Zu diesem Zweck führen wir in diesem Papier den Rahmen eines dezentralen zweiseitigen Matching-Marktes unter nicht-stationären (dynamischen) Bedingungen ein. Wir halten uns an das Konzept der seriellen Diktatur, bei dem die Agenten auf der Nachfrageseite unbekannte und unterschiedliche Präferenzen gegenüber der Angebotsseite (Arme) haben, die Arme jedoch feste und bekannte Präferenzen gegenüber den Agenten haben. Wir schlagen einen asynchronen und dezentralen Lernalgorithmus vor und analysieren diesen, nämlich nicht-stationäre konkurrierende Banditen (NSCB), bei dem die Agenten (restrictive) sukzessive Eliminations-Lernalgorithmen spielen, um ihre Präferenzen gegenüber den Armen zu lernen. Die Komplexität des Verständnisses eines solchen Systems resultiert aus der Tatsache, dass die konkurrierenden Banditen ihre Aktionen auf asynchrone Weise wählen und die niedriger eingestuften Agenten nur von einer Menge von Armen lernen können, die nicht von den höher eingestuften Agenten dominiert wird, was zu einer erzwungenen Exploration führt. Mit sorgfältig definierten Komplexitätsparametern charakterisieren wir diese erzwungene Exploration und erzielen sub-lineare (logarithmische) Reue von NSCB. Darüber hinaus validieren wir unsere theoretischen Erkenntnisse durch Experimente.