본 논문은 에이전트들에게 나눌 수 없는 재화를 순차적으로 할당하는 온라인 환경에서의 공정한 할당 문제를 연구합니다. 부러움 없는 공정성, 비례성, 최대-최소 공유 공정성(및 그 근사값)과 같은 널리 알려진 공정성 개념에 초점을 맞춰, 미래 재화에 대한 정보의 가용성이 공정한 할당의 존재와 근사 가능성에 어떤 영향을 미치는지 질문합니다. 어떠한 정보도 없는 경우, 본 논문은 심지어 근사적인 공정성 보장을 달성하는 것의 고유한 어려움을 보여주는 강력한 불가능성 결과를 확립합니다. 반대로, 각 에이전트의 총 평가액(또는 정규화된 평가액)의 집계 또는 미래 재화 가치의 다중집합(빈도 예측)과 같은 추가 정보의 지식은 더 공정한 온라인 알고리즘 설계를 가능하게 함을 보여줍니다. 정규화 정보가 주어지면, 기존 결과보다 강력한 공정성 보장을 달성하는 알고리즘을 제안합니다. 빈도 예측이 주어지면, 광범위한 "공유 기반" 공정성 개념에 대해 최고의 오프라인 보장을 활용하는 메타 알고리즘을 소개합니다. 각 설정에서 상호 보완적인 불가능성 결과는 미래 재화에 대한 불확실성에 의해 부과되는 한계와 온라인 공정 분할에서 더 공정한 결과를 달성하기 위해 구조화된 정보를 활용하는 잠재력을 모두 강조합니다.
