Online EFX Allocations with Predictions

We study an online fair division problem where a fixed, but unknown number of goods arrive sequentially and must be allocated immediately and irrevocably to a given set of agents. The objective is to ensure (approximate) envy-freeness up to any good (EFX), that is, after the allocation, no agent should prefer another agent's bundle once any single good is removed from it. Unfortunately, we show that approximate EFX is impossible to guarantee, even under restrictive valuation assumptions. To overcome this barrier, we follow the emerging trend of algorithms with predictions, assuming access to a vector of predicted valuations. Predictions may be inaccurate, and we measure their error using the total variation distance from the true valuations. For additive valuations, we prove impossibility results for algorithms that either ignore predictions or rely solely on them, and we establish lower bounds on the prediction accuracy required by any algorithm to compute approximate EFX. Finally, we provide a positive result: for two agents with identical valuations, we design an algorithm that uses predictions to achieve approximate EFX, with guarantees improving smoothly in prediction accuracy.