Key points are not available for this paper at this time.
우리는 소비자 측 효용을 극대화하면서 생산자 측 개별 노출의 불공정을 최소화하는 순서의 등급을 계산하는 문제를 고려합니다. 이전 연구는 이 문제를 비스토카틱 행렬에 대한 선형 또는 이차 프로그래밍을 사용하여 해결했지만, Birkhoff-von Neumann (BvN) 분해를 기반으로 하는 이러한 접근 방식은 대규모로 구현하기에는 너무 느립니다. 본 논문에서는 위치 기반 모델 (PBM)을 위한 항목의 모든 달성 가능한 노출을 나타내는 점을 가진 기하학적 객체, 엑스포헤드론이라는 다면체를 소개합니다. 우리는 그 일부 속성을 설명하고, n개의 정점을 최대한으로 사용하는 볼록 합으로 엑스포헤드론 내부의 모든 점을 표현할 수 있는 복잡도 O(n²log(n))의 카라테오도리 분해 알고리즘을 제시합니다. 이러한 분해를 통해 가능한 모든 목표 노출을 최대 n개의 순서에서 분포로 표현할 수 있습니다. 게다가, 우리는 이 다면체를 사용하여 다목적 공정성-효용 최적화 문제의 전체 파레토 경계를 복구할 수 있음을 보여주며, 복잡도 O(n²log(n))의 간단한 기하학적 절차를 사용합니다. 우리의 접근 방식은 알고리즘 복잡성과 경험적 실행 시간 측면에서 선형 또는 이차 프로그래밍 기준선보다 유리하며 항목 관련성의 비감소 함수인 모든 장점에 적용 가능합니다. 더욱이 우리의 솔루션은 BvN 분해로 달성된 (n-1)² + 1 대신 오직 순열에 대한 분포로 표현될 수 있습니다. 우리는 이론적 결과를 확인하는 합성 및 실제 데이터 세트에서 실험을 수행합니다.
Kletti 외 (Fri,)는 이 질문을 연구했습니다.