본 논문은 순차적으로 도착하는 불가분의 재화를 대리인들에게 즉각적이고 돌이킬 수 없이 할당하는 온라인 공정 분배 문제를 연구합니다. 기존 연구는 이러한 설정에서 부러움 없는 공정성 및 최대 공유 공정성과 같은 고전적인 공정성 개념을 근사하는 것에 대한 강력한 불가능성 결과를 확립했습니다. 이와는 대조적으로, 본 논문은 비례성의 자연스러운 완화인 비례성 최대 한 개의 재화 (PROP1)에 초점을 맞춥니다. 먼저, 세 가지 자연스러운 탐욕 알고리즘이 적응형 적대자에 대해 일반적으로 PROP1에 대한 어떠한 양의 근사도 보장하지 못함을 보여줍니다. 이는 탐욕 알고리즘이 공정 분배에서 일반적으로 사용되고 추가적인 정보 가정 하에 자연스러운 탐욕 알고리즘이 PROP1을 달성할 수 있는 것으로 알려져 있기 때문에 놀라운 결과입니다. 이러한 어려움 결과는 학습 증강 알고리즘의 정신에 따라 비적응형 적대자와 부가 정보의 사용에 대한 연구를 동기화합니다. 비적응형 적대자의 경우, 단순한 균일 랜덤 할당이 높은 확률로 의미있는 PROP1 근사를 달성할 수 있음을 보여줍니다. 한편, 최대 항목 값 (MIV) 예측이 주어졌을 때 PROP1에 대해 강력한 근사 비율을 얻는 알고리즘을 제시합니다. 흥미롭게도, EF1, MMS 및 PROPX와 같은 더 강력한 공정성 개념은 완벽한 MIV 예측에서도 근사할 수 없음을 보여줍니다.
