비정상 매칭 시장에서의 경쟁적 유인물

수요 측 에이전트가 공급 측(유인물)과 매칭하기 위해 경쟁하는 양측 온라인 매칭 시장의 복잡한 역학을 이해하는 것이 최근 상당한 관심을 받아왔습니다. 이를 위해 본 논문에서는 비정상(동적) 환경에서의 분산 양측 매칭 시장의 프레임워크를 도입합니다. 우리는 수요 측 에이전트가 공급 측(유인물)에 대해 알 수 없고 서로 다른 선호도를 갖는 연속 독재 설정을 고수하되, 유인물은 에이전트에 대해 고정되고 알려진 선호도를 갖는 것을 따릅니다. 우리는 에이전트가 유인물에 대한 자신의 선호도를 배우기 위해 (제한적인) 연속 제거형 학습 알고리즘을 수행하는 비동기식 분산 학습 알고리즘인 비정상 경쟁적 유인물(NSCB)을 제안하고 분석합니다. 이러한 시스템을 이해하는 데 있어 복잡성은 경쟁적 유인물이 비동기식으로 행동을 선택하고, 하위 등급 에이전트만이 상위 등급 에이전트에 의해 지배되지 않는 유인물 집합에서 배울 수 있다는 사실에서 기인합니다. 이는 강제 탐색으로 이어집니다. 신중하게 정의된 복잡성 매개변수를 통해 이 강제 탐색을 특징짓고 NSCB의 서브 선형(로그형) 후회를 도출합니다. 또한, 실험을 통해 우리의 이론적 발견을 검증합니다.