Assortment Planning with Sponsored Products

기술 요약: 스폰서 제품을 포함한 어소트먼트 플래닝(Assortment Planning)

문제 정의
본 논문은 이커머스 및 추천 시스템에서의 어소트먼트 플래닝 문제를 다루며, 특히 전통적인 유기적(organic) 제품과 함께 **스폰서 제품(sponsored products)**을 포함하도록 범위를 확장한다. 기존 연구(예: Talluri and Van Ryzin 2004)는 주로 유기적 제품에 초점을 맞추어 왔으나, 스폰서 배치(예: 아마존, 페이스북, 구글에서의 배치)의 부상은 복잡한 최적화 과제를 야기한다. 플랫폼은 광고주의 특정 요구사항을 준수하면서 기대 수익을 극대화하기 위해 $k$개의 제품 세트를 선택하고 배치해야 한다.

핵심적인 어려움은 플랫폼의 수익 목표와 스폰서 제품의 필수 요구사항 사이의 균형을 맞추는 데 있다. 위치를 임의로 지정할 수 있는 유기적 제품과 달리, 스폰서 제품은 종종 경매 메커니즘(예: 특정 품질 점수에 기반하여 "상위-$m$" 위치나 특정 슬롯을 입찰하는 광고주)에서 파생된 엄격한 배치 제약을 동반한다. 이 문제는 다항 로짓(Multinomial Logit, MNL) 선택 모델 하에서 기대 수익을 극대화하는 실행 가능한 제품 시퀀스를 찾는 조합 최적화 작업으로 정식화된다.

방법론
저자들은 소비자의 선택 행동을 MNL 모델로 모델링하며, 여기서 소비자 $i$가 특정 위치에서 제품을 선택할 확률은 해당 제품의 고유 효용과 표시된 다른 모든 제품의 효용에 따라 결정된다. 선택 확률의 분모에 모든 선택된 아이템의 효용 합계가 포함되기 때문에 수익 함수는 비선형적이다.

본 논문은 제약 조건에 따라 두 가지 알고리즘 접근 방식을 제안한다:

1. 기본 제약 조건에 대한 엄밀해(Exact Solution):
   스폰서 제품의 필수 배치(각 스폰서 제품 $i$가 유효한 위치 $t \in R_i$에 할당되어야 함)만이 제약 조건일 때, 이 문제는 할당 문제(assignment problem)로 정식화된다. 저자들은 이 제약 행렬이 **전단사 정수성(totally unimodular)**을 가짐을 입증한다. 결과적으로, 이 문제는 정수 제약을 선형 계획법(LP) 정식화로 완화하여 해결할 수 있으며, 이는 정수 해를 산출한다는 것이 보장된다.

2. 확장된 제약 조건에 대한 근사 알고리즘:
   본 논문은 유기적 제품의 선택에 대한 추가적인 제약(예: 총 비용 $\le C$인 용량(knapsack) 제약 또는 특정 그룹 내 아이템 수의 제한인 파티션 매트로이드(partition matroid) 제약)을 포함하도록 문제를 확장한다.

   • 분해 전략(Decomposition Strategy): 최적해는 두 부분, 즉 스폰서 제품으로부터의 수익과 유기적 제품으로부터의 수익으로 분해된다. 저자들은 두 가지 후보 어소트먼트를 구성한다:
     • 후보 I: 유기적 제품을 무시하고 오직 스폰서 제품만을 고려하여 수익을 최적화한다.
     • 후보 II: 유기적 제품 선택을 위한 효용을 "저축"하기 위해 스폰서 제품의 총 가중치(효용)를 먼저 최소화한 후, 고정된 스폰서 선택을 바탕으로 유기적 제품의 어소트먼트를 최적화한다.
   • 무작위 선택(Randomized Selection): 최종 솔루션은 더 나은 두 후보 중 하나를 선택한다. 이론적 분석에 따르면, 만약 유기적 하위 문제(P.5)가 $\beta$ 비율 내에서 근사될 수 있다면, 전체 알고리즘은 $\frac{\beta}{\beta+1}$의 근사 비율을 달enc한다.
   • 부가적 최적화(Submodular Optimization): 복잡한 제약 조건 하에서 유기적 하위 문제(P.5)를 해결하기 위해, 저자들은 시퀀싱 문제를 제품-위치 쌍의 그라운드 셋(ground set)에 대한 부분 집합 선택 문제로 변환한다. 이들은 결과적인 효용 함수가 **단조성(monotone)과 부가성(submodularity)**을 가짐을 증명한다. 이를 통해 최첨단 부가적 최대화 알고리즘을 적용할 수 있다:
     • 용량(knapsack) 제약의 경우, $\beta = 1/(1+\epsilon)^3$의 비율을 달성하는 알고리즘을 활용한다.
     • 파티션 매트로이드 제약의 경우, $\beta = 1/(2+\epsilon)$의 비율을 달성하는 알고리즘을 활용한다.

주요 기여

• 문제 정식화: 본 논문은 스폰서 제품의 통합을 명시적으로 모델링함으로써, 기존 문헌(종종 모든 제품이 유기적이거나 스폰서 통합을 무시함)에서 발견된 공백을 메우는 어소트먼트 플래닝 문제를 공식적으로 정의한다.
• 이론적 보장: 이론적 경계 없이 딥러닝 휴리스틱에 의존하는 기존 연구들(예: Liao et al. 2022)과 달리, 본 논문은 엄격한 근사 보장을 제공한다.
• 알고리즘 프레임워크: 저자들은 플랫폼 수익 극대화와 광고주 제약 사이의 간극을 좁히는 프레임워크를 개발한다. 기본 문제는 LP를 통해 다항 시간 내에 해결 가능함을 증명하고, 유기적 제품에 대한 용량 또는 다양성 제약이 포함된 더 복잡한 변형에 대해 상수 인자 근사 알고리즘을 제공한다.
• 부가성 증명: 유기적 제품 선택을 위한 변환된 효용 함수가 부가적(submodular)임을 증명한 것은 중요한 기술적 기여이며, 이를 통해 NP-난해(NP-hard) 제약 조건에 대한 효율적인 근사 알고리즘 사용을 가능하게 한다.

결과
본 논문은 다음과 같은 이론적 결과를 확립한다:

• 기본 문제(스폰서 제약만 있는 경우), 최적해를 효율적으로 계산할 수 있다.
• 확장된 문제(스폰서 제약 + 유기적 용량/매트로이드 제약), 제안된 알고리즘은 다음의 근사 비율을 달성한다:
  • 용량 제약의 경우: $\frac{1}{(1+\epsilon)^3 + 1}$
  • 파티션 매트로이드 제약의 경우: $\frac{1}{(2+\epsilon) + 1}$
  • (참고: 논문은 최종 비율을 하위 문제의 근사 비율인 $\beta$를 사용하여 $\frac{\beta}{\beta+1}$로 도출한다.)

의의 및 주장
저자들은 본 연구가 스폰서 제품의 통합을 명시적으로 모델링함으로써 어소트먼트 플래닝 문헌의 중요한 공백을 해결한다고 주장한다. 이 연구의 의의는 플랫폼(수익 극대화)과 광고주(특정 배치 요구사항)의 상충하는 목표를 조절하는 솔루션에 대한 이론적 보장을 제공하는 데 있다. 본 논문은 자사의 접근 방식이 기업들이 전체적인 수익 전략이나 사용자 경험을 훼mp하지 않으면서도 스폰서 제품을 원활하게 통합할 수 있는 방법을 제공하며, 이것이 단순한 휴리스틱 성능이 아닌 증명 가능한 수학적 경계에 기초하고 있음을 단언한다. 이 작업은 진화하는 이커머스 추천 시스템 분야의 기초적인 단계로 제시된다.