Binary valuations

Working with Foodbank Australia, Aleksandrov, Aziz, Gaspers and Walsh^[9] have initiated the study of the food bank problem when all agents have binary valuations {0,1}, that is, for each arriving item, every agent states whether he likes the item or not. The mechanism should decide which of the agents who like the item should receive it. They study two simple mechanisms for this setting:

• LIKE: each item is given uniformly at random to one of the agents who likes it. It is strategyproof and envy-free ex-ante, but does not guarantee even approximate envy-free ex-post. With binary valuations, it attains the optimal egalitarian and utilitarian social welfare. With additive valuations, its expected egalitarian and utilitarian social welfare are least 1/n of the optimal values attainable by an offline algorithm. The same is true whether the agents are sincere or strategic (i.e., its price of anarchy is n).
• BALANCED-LIKE: each item is given uniformly at random to one of the agents who likes it, from among those who received the least number of items so far. It is envy-free ex-ante, and guarantees EF1 ex-post when all agents have binary valuations. It is strategyproof for two agents with binary valuations, but not strategyproof for three or more agents even with binary valuations. When agents bid sincerely, with binary valuations, it attains the optimal egalitarian and utilitarian social welfare. With additive valuations, its expected egalitarian and utilitarian social welfare do not attain any constant-factor approximation of the offline optimal values, even with two agents. When agents bid strategically, even with binary valuations, its price of anarchy is n.

Additive valuations

In a more general case of the food bank problem, agents can have additive valuations, which are normalized to [0,1].

Due to the online nature of the problem, it may be impossible to attain some fairness and efficiency guarantees that are possible in the offline setting. In particular, Kahana and Hazon^[10] prove that no online algorithm always finds a PROP1 (proportional up to at most one good) allocation, even for two agents with additive valuations. Moreover, no online algorithm always finds any positive approximation of RRS (round-robin share).

To explain this, define the envy of agent i at agent j as the amount by which i believes that j's bundle is better, that is, ${\displaystyle \max(0,V_{i}(X_{j})-V_{i}(X_{i}))}$. The max-envy of an allocation is the maximum of the envy among all ordered agent pairs. Suppose the values of all items are normalized to [0,1]. Then, in the offline setting, it is easy to attain an allocation in which the max-envy is at most 1, for example, by the round-robin item allocation (this condition is called EF1). However, in the online setting, the envy might grow with the number of items (T). Therefore, instead of EF1, some algorithms aim to attain vanishing envy—the expected value of the max-envy of the allocation of T items should be sublinear in T (assuming the value of every item is between 0 and 1).

Benade, Kazachkov, Procaccia and Psomas^[11] show that the LIKE algorithm (allocating each item uniformly at random) attains vanishing envy - the envy after T items is in ${\displaystyle O({\sqrt {T/n}})}$. They also present a deterministic algorithm with a similar envy-bound, using the method of pessimistic estimators. They show that this envy-bound is asymptotically optimal (up to logarithmic factors) in the worst case, when the valuations are chosen by an adaptive adversary (an adversary who chooses an item after seeing the allocation at time T-1). In particular, in contrast to the case of binary valuations, no algorithm can guarantee EF1. They also study a more general setting in which the items come in batches of m each time, rather than 1 at a time. In this case, there is a deterministic algorithm with envy in ${\displaystyle O({\sqrt {T/(mn)}})}$.

Jiang, Kulkarni and Singla^[12] improve their envy bound using an algorithm for online two-dimensional discrepancy minimization.

Zeng and Psomas^[13] study the trade-off between efficiency and fairness under five adversary models, from weak to strong. Below, v_it denotes the value of the item arriving at time t to agent i.

1. Identical independent agents: the adversary picks a probability distribution D₀. On each round t, v_it is drawn independently from D₀.
2. Different independent agents: The adversary picks a probability distribution D_i for each agent i. On each round t, v_it is drawn independently from D_i.
3. Correlated agents: The adversary picks a joint probability distribution D. On each round t, the vector (v_1t, ..., v_nt) is drawn independently from D.
4. Non-adaptive adversary: After seeing the algorithm code, the adversary picks the valuations of all n agents to all T items.
5. Adaptive adversary: After seeing the algorithm code, and after seeing the allocation of the first t-1 items, the adversary picks the valuations of item t (In ^[13] this is the model).

For adversary 3 (hence also 2 and 1), they show an allocation strategy that guarantees, to each pair of agents, either EF1, or EF with high probability, and in addition, guarantees ex-post Pareto efficiency. They show that the "EF1 or EF w.h.p." guarantee cannot be improved even for adversary 1 (hence also for 2 and 3). For adversary 4 (hence also 5), they show that every algorithm attaining vanishing envy can be at most 1/n ex-ante Pareto-efficient.

Sinclair, Bannerjee and Yu^[14] present an algorithm that attains the optimal fairness-efficiency threshold.