Online Fair Division

1 Introduction

Hunger is a major problem even in developed countries like Australia. We are working with a social startup, Foodbank Local, and local charities at distributing donated food more efficiently. This food must first be allocated to these charities and then delivered to the end customers. This fair division problem is interesting as it combines traditional features with a number of dimensions that are scarcely considered or combined in the literature. For example, the food arrives online as the day progresses. We must start allocating it almost immediately, possibly anticipating more donations later the same day. We assume the products are packaged and therefore indivisible. How do we then allocate them? Also, the problem the food banks face today is likely to repeat tomorrow. Can we then improve the allocation tomorrow by using the experience learned today? As a very first step, we focus on designing simple mechanisms allocating the food more efficiently (see Aleksandrov et al. [2015a]). In future, we also plan on investigating more closely the frontier between the allocation and the transportation frameworks within this mixed setting. For instance, shall we dispatch the items as soon as they arrive? Or, shall we first gather some more of them and then dispatch these together in order to guarantee the efficiency of the driver's shift?

2 Background

A greatly investigated topic in resource allocation is fair division. Pioneered by Steinhaus [1948], the theoretical models of fair division are typically simplistic and inadequate in addressing complex features encountered in many practical settings. As a response, Walsh [2015], for example, develops more sophisticated and realistic models and mechanisms. In addition, most abstractions assume that the entire resource is available a priori, an assumption often being disregarded in practice. Despite the limited work in online fair division, there are a few works considering features of the problem in isolation. Walsh [2011] cuts cake by adapting existing fair division procedures to an online setting. By comparison, the agents in this model arrive over time, not the resource. Also, Kash et al. [2014] have proposed a related model in which there are multiple, homogeneous divisible goods and not indivisible goods as in here. In this work, we report some initial results fromAleksandrov et al. [2015a].

Online Fair Division

Martin Aleksandrov

University of New South Wales and NICTA, Australia Martin.Aleksandrov@nicta.com.au

3 Online model

Inspired by our work with Foodbank Local, we have formulated a simple online model in which each agent merely declare which items they like or not. We suppose there are k agents and m items. Each agent has some (private) utility for each item. One item appears at each time step. We say that an agent bids for the item if they declare that they like it. Then an allocation mechanism must assign the item to one of the bidders. The next item is then revealed. This continues for m steps.

We consider 2 simple bidding mechanisms. The LIKE mechanism allocates the next item uniformly at random amongst those agents that bid for the item. A benefit of using LIKE is that it maximizes the welfare from an utilitarian perspective whenever the agents bid their utilities. However, a major drawback of it is that an agent can get lucky and be allocated all the items they bid for. This might be highly unfair with respect to the remaining agents (i.e. charities or sectors of the community). We therefore consider a slightly more sophisticated mechanism that helps tackle this problem by achieving more balanced allocations. The BALANCED LIKE mechanism allocates the next item uniformly at random amongst those agents that bid for the item and have so far received the fewest items. BALANCED LIKE is less likely to leave agents empty handed than LIKE .

4 Validation

In order to characterize our mechanisms we study axiomatic properties such as strategy proofness and fairness. We say that an agent bids sincerely for an item if they report their private utility for that item. Otherwise, they bid insincerely. Thus, a mechanism for online fair division is strategy-proof if no agent can improve their expected utility by bidding insincerely. There are several notions of fairness quantifying the random outcomes of our mechanisms, both in ex post and ex ante contexts. One such notion is envy-freeness (e.g. Brams and Taylor [1996]) describing how much each agent envies each other. A mechanism is envy free ex post/ex ante if no agent envies another ex post/ex ante. We also consider a weaker notion of envy-freeness that allows the agents to envy each other but in a bounded sense. Another notion of fairness is proportionality. A mechanism is proportional ex post/ex ante if each of the k agents receives/receives in expectation at least 1k of their total utility in any possible allocation. Besides the analytical properties of our mechanisms, we are also interested in their empirical competitiveness with respect to the optimal (offline) allocation. For this purpose, we compute the loss in efficiency due to the data arriving online and supposing the agents act both sincerely (i.e. competitive ratio) and strategically (i.e. price of anarchy). In the next section, we present some of the results (see more in Aleksandrov et al. [2015b]).

5 Results

When using LIKE , each agent bidding for a given item gets an equal chance of receiving it. As a result, no agent has an incentive to bid for items that they do not value or not to bid for items that they value. In both cases, their expected utility will not increase. Consequently, LIKE is strategy-proof. This is not the case if were using BALANCED LIKE .

Proposition 1 The BALANCED LIKE mechanism is not strategy proof even with only 0/1 utilities.

Proof 1 Suppose we are allocating the items a, b and c in alphabetical order between the agents 1, 2 and 3. Also, let agent 1 values all items, agent 2 values only b and agent 3 values a and c. By bidding sincerely, agent 1 receives an expected utility of 98 but this increases to 54 if she bids strategically only for items b and c and supposing the other agents bid sincerely ✷.

BALANCED LIKE may not be strategy proof, however, it is bounded envy-free ex post and ex ante (see Aleksandrov et al. [2015a]). On the contrary, LIKE can imply unbounded unfairness as confirmed by the following example.

Example 1 Suppose the fair division of m items and 2 agents valuing all items. Also, suppose that agent 1 gets lucky at each random draw and is thus assigned all items. In this case, agent 2 assigns a utility of at least m units greater to the allocation of agent 1 than to their own (empty) allocation.

The mechanisms we consider are online and thus are expected to achieve allocations that are more or less sub-optimal from welfare perspective. Thus, we report in Figure 1 the impact our mechanisms have on egalitarian social welfare supposing only 0/1 utilities. Note that in this setting both mechanisms optimise the utilitarian welfare as each agent receives items they sincerely value in each possible allocation.

Within this experimental setting, we sampled 100 instances at random. Figure 1 contains two graphs. In the left graph, we fix the number of agents to 5 and vary the number of items from 2 to 10. In the right graph, we fix the number of items to 10 and vary the number of agents from 2 to 5. Both graphs show the competitive ratios ("like" and "balanced") and the prices of anarchy ("balanced+" and "balanced-") of the worst and the best strategic play of the agents. The experiment confirms that BALANCED LIKE improves the egalitarian welfare supposing sincere ("balanced" compared to "like") or strategic ("balanced+" and "balanced-" compared to "like") play of the agents. For 5 agents and 10 items, the competitive ratio increases from around 0.7 to 0.85 on average (≈ 21% higher value) supposing that instead of LIKE we run BALANCED LIKE . Indeed, the strategic play of the agents often increases the welfare even in the worst case ("balanced" compared to "balanced"), though the effect is small. At the same data point, its value is approximately 6% higher supposing strategic ("balanced+" or "balanced-") versus sincere ("balanced") play (i.e reaches ≈ 0.9 from ≈ 0.85).

In conclusion, BALANCED LIKE achieves fairer allocations than LIKE with 0/1 utilities from egalitarian perspective.

6 Conclusion

We considered a model of fair division capturing features of a real-world problem in which charities bid for items in an online manner. We designed two mechanisms, LIKE and BALANCED LIKE , allocating the items and studied their axiomatic properties. Also, we showed empirically that BALANCED LIKE achieves more egalitarian allocations than LIKE and even competes with the optimal (offline) allocation. As a next step, we are about to add more complex features to this basic setting. For instance, different charities have unequal entitlements and the allocation must reflect this. It would be interesting to see how the axiomatic properties change as the mechanisms grow.