📊 statistics

Data-Driven Dynamic Assortment in Online Platforms: Learning about Two Sides

이 논문은 양측 모두의 선택 파라미터가 알려지지 않은 양면 동적 어소트먼트 문제에 대해 데이터 기반 알고리즘을 소개하며, 고객과 판매자의 선호도를 동시에 학습하는 동시에 플랫폼 수익을 극대화함으로써 최적의 속도인 폴리로그(polylogarithmic) 회귀를 달성한다.

원저자: Rahul Roy, Nur Sunar, Jayashankar M. Swaminathan

게시일 2026-06-10

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Rahul Roy, Nur Sunar, Jayashankar M. Swaminathan

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 고도의 기술이 접목된 농부 시장이나 데이팅 앱과 같은 활기찬 디지털 마켓플레이스를 운영하고 있다고 상상해 보십시오. 당신에게는 두 그룹의 사람들이 있습니다: 고객(서비스를 구매하고자 함)과 판매자(서비스를 제공하고자 함). 당신의 임任务는 문을 열고 들어오는 각 고객에게 어떤 판매자를 보여줄지 결정하는 것입니다.

이 논문은 매우 까다로운 문제를 다룹니다: 당신은 아무도 무엇을 좋아하는지 모릅니다.

핵심 문제: "블라인드 데이트" 마켓플레이스

대부분의 온라인 플랫폼은 고객이 무엇을 원하는지 추측하려고 노력합니다. 하지만 이 논문의 시나리오에서 플랫폼는 두 가지 측면에서 눈이 멀어 있습니다:

고객이 무엇을 원하는지 모릅니다: 어떤 고객은 태양광 설치업자를 좋아하고, 다른 고객은 프리랜서 작가를 선호할 수 있습니다. 플랫폼은 다음에 어떤 유형의 고객이 도착할지 모릅니다.
판매자가 무엇을 원하는지 모릅니다: 설령 고객이 한 판매자를 선택하더라도, 그 판매자가 "정중히 거절"할 수도 있습니다. 예를 들어, 그 판매자가 특정 유형의 고객과 일하는 것을 싫어할 수도 있습니다. 플랫폼은 이러한 선호도 또한 알지 못합니다.

이것은 마치 매치메이커(중매인)가 남자가 무엇을 좋아하는지도 모르고, 여자가 무엇을 좋아하는지도 모르는 상태에서 진행되는 블라인드 데이트 설정과 같습니다. 만약 남자가 여자를 선택하더라도, 여자는 여전히 그를 거절할 수 있습니다. 만약 매치메이커가 남자가 무엇을 좋아하는지만 배우고 여자가 무엇을 좋아하는지는 무시한다면, 그들은 계속해서 잘못된 데이트를 설정하게 될 것입니다.

사건의 순환

논문은 이 마켓플레이스가 작동하는 특정한 리듬을 설명합니다:

도착: 고객이 도착합니다.
메뉴: 플랫폼은 그들에게 작은 목록(어쏘트먼트, assortment)을 보여줍니다.
제안: 고객은 목록 중 한 명의 판매자를 선택하거나, 아무도 선택하지 않습니다.
검토: 판매자는 제안들을 한 묶음으로 받습니다. 몇 일마다(사이클), 판매자는 그들을 검토하고 최대 한 명의 고객과 일하기로 선택합니다.
보상: 고객이 판매자를 선택하고 동시에 판매자가 고객을 선택했을 때만 플랫폼은 수익을 얻거나(또는 "매치"를 얻거나) 합니다.

과제: 실행하며 배우기

플랫폼 관리자는 미래를 알지 못하는 상태에서 '지금' 결정을 내려야 합니다. 그들은 다음과 같은 문제를 해결해야 합니다:

"고객 유형 A는 어떤 판매자를 좋아하는가?"
"판매자 유형 B는 어떤 고객 유형을 수용하는가?"

만약 플랫폼이 인기 있는 판매자들만 계속 보여준다면, 새로운 판매자가 특정 고객 유형에게 실제로 훌륭한 매치인지 결코 배울 수 없습니다. 하지만 너무 많은 무작위 판매자를 보여준다면, 잘못된 매치에 시간과 돈을 낭비하게 됩니다. 이것이 바로 전형적인 "탐색(Exploration) 대 활용(Exploitation)"의 딜레마입니다.

해결책: "양방향 학습" 알고리즘

저자들은 TWL-UCB라고 불리는 스마트한 컴퓨터 프로그램(알고리즘)을 만들었습니다. 이것을 모든 가능한 쌍에 대해 "신뢰 점수"를 유지하는 초정밀 관찰자 매치메이커라고 생각하십시오.

추측 게임: 알고리즘은 고객과 판매자가 서로를 얼마나 좋아하는지 추측하며 시작합니다.
"만약에" 테스트: 알고리즘은 "상한 신뢰 구간(Upper Confidence Bound, UCB)"이라는 수학적 트릭을 사용합니다. 알고리즘이 안전하게 가면서도 계산된 위험을 감수하는 모습을 상상해 보십시오. 알고리즘은 이렇게 생각합니다: "나는 고객 A가 판매자 X를 좋아한다고 90% 확신하지만, 판매자 Y에 대해서는 50%만 확신해. 하지만 만약 내 생각이 맞다면 엄청난 승리가 될 수 있으니, 그냥 한번 Y를 시도해 보자!"
이중 확인: 기존의 방법들이 고객의 행동만을 관찰했던 것과 달리, 이 알고리즘은 양쪽 모두를 관찰합니다.
- 고객이 선택을 할 때마다 알고리즘은 고객이 무엇을 좋아하는지에 대한 추측을 업데이트합니다.
- 판매자가 제안을 수락하거나 거절할 때마다 알고리즘은 판매자가 무엇을 좋아하는지에 대한 추측을 업데이트합니다.
결과: 시간이 지남에 따라 알고-리즘은 완벽한 매치를 예측하는 데 매우 능숙해집니다. 실패한 데이트(후회)를 최소화합니다.

주요 발견

저자들은 수학과 컴퓨터 시뮬레이션을 사용하여 세 가지 주요 사항을 증명했습니다:

1. 빠르게 발전함 ("다항 로그"의 승리)
저자들은 자신들의 알고리즘이 매우 효율적으로 학습하여, 발생하는 "실수"가 시간이 흐름에 따라 매우 느리게 증가한다는 것을 증명했습니다. 수학적으로, 오차는 로그의 제곱처럼(매우 느린 곡선) 증가합니다.

비유: 학생이 시험을 치르는 상황을 상상해 보십시오. 대부분의 학습 방법은 실수가 가파른 언덕처럼 쌓여갑니다. 이 알고리즘은 실수가 완만한 경사처럼 쌓입니다. 즉, 이 알고리즘은 다른 누구보다 훨씬 빠르게 규칙을 배웁니다.

2. 이보다 더 잘할 수는 없음 ("하한선")
저자들은 또한 어떤 다른 전략도 자신들의 방식보다 유의미하게 빠르게 학습할 수 없음을 증명했습니다. 그들은 최악의 시나리오에서도 심지어 "완벽한" 알고리즘이라 할지라도 자신들과 유사한 횟수의 실수를 저지를 것이라는 점을 보여주었습니다.

비유: 그들은 자신들의 알고리즘이 "금메달리스트"임을 증명했습니다. 트랙 자체가 이미 그만큼 빠르기 때문에 더 빨리 달릴 수는 없습니다.

3. 크다고 항상 좋은 것은 아님 ("메뉴 크기"의 놀라움)
그들은 큰 메뉴(많은 판매자)를 보여주는 것과 작은 메뉴를 보여주는 것 사이에 어떤 차이가 있는지 알아보기 위해 시뮬레이션을 실행했습니다.

발견: 메뉴가 특정 크기(시뮬레이션에서는 약 30명의 판매자)에 도달하면, 메뉴를 더 크게 만드는 것이 큰 도움이 되지 않는다는 것을 발견했습니다.
비유: 레스토랑 메뉴를 생각해 보십시오. 5개의 훌륭한 요리가 있다면, 여기에 평범한 요리 50개를 더 추가한다고 해서 고객이 더 행복해지지는 않습니다. 그것은 단지 고객을 혼란스럽게 할 뿐입니다. 플랫폼은 거대한 메뉴를 가질 때와 마찬가지로 중간 크기의 메뉴를 통해서도 동일한 횟수의 성공적인 매치를 얻습니다.

이것이 왜 중요한가

이 논문은 양쪽 모두가 무엇을 원하는지 모르는 상태에서, 양쪽 시장의 양상을 동시에 학습하는 퍼즐을 처음으로 해결했습니다. 이는 플랫폼이 단순히 "고객의 선택" 문제로 접근하는 대신, 이를 "양방향" 학습 과제로 다룸으로써 훨씬 더 스마트하고, 빠르고, 수익성 있는 결정을 내릴 수 있음을 보여줍니다.

요약하자면: 성공적인 양면 마켓플레이스를 운영하려면, 구매자가 무엇을 원하는지 추측하는 것뿐만 아니라, 판매자가 무엇을 원하는지도 배워야 합니다. 그리고 적절한 수학을 통해 이 두 가지를 동시에 수행한다면, 승리할 수 있습니다.

기술 요약: 온라인 플랫폼에서의 데이터 기반 동적 어소트먼트(Assortment): 양면 학습에 관한 연구

문제 정의
본 논문은 불완전한 정보 하에서 운영되는 양면 서비스 플랫폼에서의 동적 어소트먼트 선택 문제를 다룹다. 고객 선호도만을 바탕으로 수익을 극대화하기 위해 제품을 선택하는 전통적인 어소트먼트 문제와 달리, 이 설정에는 수요 측(고객)과 공급 측(판매자) 모두에 "능동적인" 참여자가 존재한다.

시스템은 $T$ 기간의 호라이즌 동안 이산 시간 단위로 작동한다. 플랫폼은 $N$ 개의 판매자를 관리하며, 이질적인 유형을 가진 일련의 고객들을 마주한다. 각 기간마다 플랫폼 매니저는 도착하는 고객에게 보여줄 어소트メント(최대 $B$ 개의 판매자로 구성된 부분집합)를 선택한다. 고객은 제시된 어소트먼트 내에서 최대 하나의 판매자를 선택하며, 이는 미지의 선호 파라미터 $v_{z,i}$ ( $z$ 는 고객 유형, $i$ 는 판매자)에 의해 제어되는 다항 로짓(Multinomial Logit, MNL) 선택 모델을 따른다.

결정적인 점은, 고객의 선택이 이루어진다고 해서 거래가 즉시 확정되지 않는다는 것이다. 고객의 제안은 $K$ 기간 동안 고정된 기간 동안 유지된다. 각 에포크(epoch, $K$ 기간의 블록)가 끝날 때, 판매자들은 자신들이 받은 제안을 검토하고, 자신들의 미지 MNL 선호 파라미터 $u_{i,z}$ 에 기초하여 최대 하나의 고객을 수락할지 여부를 결정한다. 거래(및 그에 따른 보상)는 판매자가 제안을 수락했을 때만 발생한다. 플랫폼 매니저의 목표는 계획 호라이즌 동안 총 기대 보상을 극대화하는 것이다.

핵심 과제는 **양방향 학습(Two-Way Learning)**이다. 플랫폼은 고객( $V$ )과 판매자( $U$ ) 양측의 선택 파라미터를 모두 알지 못하며, 어소트먼트 결정을 내리는 동시에 이들을 동적으로 학습해야 한다. 이는 기존 문헌(주로 고객 선호도만 미지수인 경우나 즉각적인 보상 실현을 가정하는 경우)과 차별화되는 지점이다.

방법론
저자들은 TWL-UCB(Two-Way Learning via Upper Confidence Bound)라고 명명된 데이터 기반 온라인 알고리즘을 제안한다. 이 알고리즘은 양면 시장의 비동기적 피드백 구조를 처리하면서 탐색(exploration)과 활용(exploitation) 사이의 균형을 맞추도록 설계되었다.

상한 신뢰 구간(UCB) 추정치: 알고즘은 고객 선호 파라미터( $v_{z,i}$ $v_{z, i}$ )와 판매자 선호 파라미터( $u_{i,z}$ $u_{i, z}$ ) 모두에 대한 UCB 추정치를 유지한다.
- 고객 업데이트 (단계 II): 매 기간마다 플랫폼은 제공된 어소트먼트 내에서 관찰된 고객의 선택(제안)을 바탕으로 고객 추정치를 업데이트한다.
- 판매자 업데이트 (단계 III): 판매자 추정치는 관찰된 매칭 결정(수락/거절)을 바탕으로 각 에포크( $K$ 기간)가 끝날 때만 업데이트된다.
어소트먼트 최적화 (단계 I): 각 기간마다 플랫폼은 추정된 기대 매칭 증가량의 한계치를 극대화하는 어소트먼트를 선택한다. 이 지표인 $\Delta_M$ 은 현재 제안 상태와 고객 및 판매자 선호도의 UCB 추정치를 고려할 때 현재 에포크에서 기대되는 매칭 이득을 포착한다.
후회(Regret) 최소화: 성능은 클레어보이언트 정책(모든 파라미터와 도착 시퀀스를 알고 있는 정책)이 달성한 보상과 제안된 알고리즘이 달성한 보상 간의 차이로 정의되는 *후회(regret)*를 사용하여 평가된다.

주요 결과 및 이론적 기여
본 논문은 후회의 상한과 하한을 일치시킴으로써 TWL-UCB 알고리즘의 이론적 최적성을 입증한다:

상한 (정리 1): 저자들은 TWL-UCB 알고리즘의 최악의 경우 후회가 시간( $T$ )에 대해 폴리로그(polylogarithmically) 형태로 증가함을 증명하였다: $O(\log^2(NT))$ . 이는 단방향 학습에 초점을 맞춘 기존의 동적 어소트먼트 문헌에서 발견되는 $\tilde{O}(\sqrt{T})$ 후회 경계보다 유의미한 개선이다.
하한 (정리 2): 논문은 어떤 허용 가능한 정책에 대해서도 최악의 경우 후개가 적어도 $\tilde{\Omega}(\log^2(NT))$ 임을 보여주는 일치하는 하한을 도출한다.
속도 최적성: 상한과 하한의 일치는 TWL-UCB 알고리즘이 양방향 학습 문제에 대해 속도 최적(rate-optimal)임을 확립한다.
시뮬레이션 결과:
- TWL-UCB 알고리즘은 양면 설정에서 적응된 단방향 학습 알고리즘(구체적으로 Agrawal et al., 2019의 UCB 알고리즘)보다 일관되게 우수한 성능을 보인다. 후자의 경우 지연된 피드백과 판매자 측의 불확실성을 고려하지 못하기 때문에 실패한다.
- 연구는 어소트먼트 크기에 관한 임계 효과를 식별한다: 어ソ트먼트 최대 크기( $B$ )를 특정 지점(시뮬레이션에서 약 30으로 관찰됨) 이상으로 늘리는 것은 플랫폼 총 보상 측면에서 수확 체감의 법칙을 보인다.

확장 및 강건성
저자들은 알고리즘의 강건성을 입증하기 위해 두 가지 확장을 분석한다:

정보 투명성: 플랫폼 매니저가 판매자에게 고객별 정보를 부분적으로만 공유하더라도 알고리즘은 $O(\log^2(NT))$ 후회 경계를 유지한다 (정리 3).
고객 의존적 보상: 성공적인 매칭에 대한 보상이 에포크당 고정된 값이 아니라 매칭된 특정 고객 유형에 따라 달라지는 경우에도 후회 경계는 성립한다 (정리 4).

의의 및 주장
저자들은 이것이 결정자가 양방향 시장의 양측 선택 파라미터를 동시에 학습해야 하는 동적 어소트먼트 문제를 공식화하고 분석한 첫 번째 연구라고 주장한다.

본 연구의 의의는 다음과 같다:

문제의 참신함: 현대 서비스 플랫폼(예: Airbnb, Upwork, HomeAdvisor)의 능동적인 참여자 특성을 반영하여, 단방향 학습을 넘어 "양방향 학습" 프레임워크로 나아갔다.
알고리즘적 발전: 지연된 피드백이 존재하는 이 복잡한 설정에서도 폴리로그(polylogarithmic) 후회가 달성 가능하다는 것을 입증하였으며, 이는 단방향 학습 문제가 일반적으로 제곱근(square-root) 후제를 겪는 것과 대조적이다.
실무적 통찰: 단방향 학습용 알고리즘은 양방향 환경에서 효과적이지 않으며, 플랫폼 매니저는 수확 체감을 고려하여 어소트먼트 크기를 확장하는 데 주의해야 함을 강조한다.

결론적으로, 제안된 TWL-UCB 알고리즘은 양방향 시장에서 불완전한 정보 하에 운영되는 플랫폼 매니저를 위한 이론적으로 최적이며 강건한 솔루션을 제공한다.