The upper bound is O(n)

by either Round-robin or maximum Nash welfare.

Open the “Price of fairness” section on Wikipedia →

Source: List of unsolved problems in fair division (CC BY-SA 4.0)