Pure Nash Equilibria in Online Fair Division

1 Introduction

Fair division is a fundamental problem our society faces today. It is even more challenging when the fair division decisions are made online often with only partial knowledge. For example, a food bank allocates food as it is donated. As a second example, an organ matching program allocates newly donated organs of deceased patients to transplant recipients within a few hours of their arrival. We cannot wait for more items to arrive before allocating existing items to agents. We focus here on a simple online fair division model introduced in [Walsh, 2014] where a new item arrives at each time step.

Fair division of indivisible items without monetary transfers is a particularly difficult case because items cannot be divided to satisfy multiple agents and because we cannot use money to compensate agents receiving less utility. Competing agents are then likely to behave strategically, especially if they have some information about what items remain to be allocated. We study here such strategic behavior for two promising mechanisms for online fair division: LIKE and BALANCED LIKE [Walsh, 2015]. Since our fair division problem is online, we typically have some uncertainty about items yet to arrive. This limits strategic behavior. However, even with limited information, agents may still be able to act strategically. For instance, with LIKE strategic behavior depends just on the items to arrive and not their arrival order.

Toby Walsh UNSW Sydney Data61, CSIRO TU Berlin toby.walsh@data61.csiro.au

We look at these two simple mechanisms for multiple reasons. They satisfy many nice axiomatic properties [Aleksandrov et al., 2015]. For example, they are randomized and this helps them achieve properties such as fairness, anonymity and equal treatment of equals. The LIKE mechanism is strategyproof, envy-free ex ante but is not fair ex post. In particular, one agent can have unbounded envy for another or even not receive a single item. LIKE characterizes envy-freeness ex ante in general and is one of the few strategy-proof mechanisms. On the other hand, BALANCED LIKE bounds the envy and guarantees that agents will be allocated similar numbers of items but it is not strategy-proof. Neither mechanism is Pareto efficient in general but both become so with binary utilities. Moreover, both LIKE and BALANCED LIKE are the most competitive mechanisms possible from an egalitarian and worst-case perspective. We, therefore, turn attention to questions around their Nash equilibria.

Nash equilibrium is a game-theoretic concept commonly used to understand the behavior of competing agents. If there is a unique pure Nash equilibrium, the main focus is usually around computational questions. One may also be interested in what the "best" equilibrium of the game is, or whether a given pure strategy is played in any equilibrium [Gilboa and Zemel, 1989]. If there are multiple pure Nash equilibria, the focus is then shifted to counting questions. One may argue that it is impossible to have a good overview of all the Nash equilibria of a game if one cannot even count them. This, however, does not preclude us from making predictions about equilibria. In our work, we look at both types of questions. For example, we compute pure Nash equilibria of both LIKE and BALANCED LIKE as well as count them.

There are several reasons why we study Nash equilibria of the one-shot game rather than the subgame perfect Nash equilibria of the repeated game. From a practical perspective, these games are typically played as one-shot. It is impractical to query agents repeatedly as every item arrives so we often collect their preferences in advance. For example, hundreds of items arrive in the food bank problem and, for this reason, charities request food only a few times per day when they reveal their utilities.

In addition, we may force agents to play the one-shot game to reduce their strategic options. Nevertheless, the problem remains online because the items arrive over time, they need to be allocated promptly and as we do not know in advance what items actually will be donated. Our results also suppose we know utilities. Again, this is often reasonable even though mechanisms like LIKE and BALANCED LIKE are ordinal. For instance, in the food bank problem, the utility of liked items might simply be their retail price. This is public information. In the organ matching problem, doctors have a function to compute the utility of a matching based on age and medical history. This is again public information.

Computing equilibria is more relevant for agent control when agents behave strategically. Counting equilibria is more relevant for chair control when the chair wants to enforce a Pareto efficient and envy-free equilibrium once the items start to arrive. To achieve this, we show that the chair might have to choose amongst exponentially many such equilibria. Counting complexity is also important if the chair wants to limit say the envy-freeness of the equilibrium outcome. For example, at Harvard Business School, students submit their sincere preferences for courses and a "proxy draft" mechanism allocates courses to them by using a Pareto efficient equilibrium strategy [Budish and Cantillon, 2012].

Our contributions: LIKE is strategy-proof whereas BALANCED LIKE is not. Our first result is that no mechanism is group strategy-proof. These results motivate why we look at competitive pure Nash equilibria for BALANCED LIKE and group pure Nash equilibria for LIKE. Our second result is that computing a pure Nash equilibrium is tractable for LIKE and intractable for BALANCED LIKE. Our third result is that there could be multiple such profiles and counting them is also intractable in the worst-case. Our intractability results have many interesting consequences. For example, we show that deciding whether an equilibrium with egalitarian welfare (i.e. minimum expected utility) of at least k is intractable. As a second example, we show that counting envy-free pure Nash equilibria is also computationally hard.

2 Preliminaries

An instance I of an online allocation problem has (1) agents a1, . . . , an, (2) indivisible items o1, . . . , om, (3) private utility uij for each agent ai and each item oj and (4) ordering o of the items. We consider binary utilities and general rational utilities. We say that agent ai likes item oj if uij > 0.

Online setting: The allocation proceeds in rounds. At round j, we suppose that item oj when each agent ai places a rational bid vij for item oj . A mechanism now allocates item oj to an agent supposing no information about future items.

We consider the LIKE and BALANCED LIKE from [Aleksandrov et al., 2015]. Each of them allocates item oj uniformly at random to a feasible agent. With LIKE, agent ai is feasible for item oj if vij > 0. With BALANCED LIKE, agent ai is feasible for item oj if vij > 0 and ai has fewest items amongst those agents that bid positively for item oj.

Pure Nash equilibria: Let vi = (vi1, . . . , vim) denote the vector of bids that agent ai report for all items and vi,-j the sub-vector of vi without bid vij. Also, let V denote the bid matrix (i.e. bidding profile) and V-i the bid sub-matrix of V without vi. Further, let ui(vi, V-i, o) denote the expected utility of agent ai for all items. We say that v1 i is a strict best response vector of agent ai to V-i if ui(v1 i , V-i, o) > ui(v2 i , V-i, o) for each vector v2 i ̸= v1 i . We say that v1 i is a weak best response vector of agent ai to V-i if ui(v1 i , V-i, o) = ui(v2 i , V-i, o) for some vector v2 i ̸= v1 i and ui(v1 i , V-i, o) ≥ ui(v3 i , V-i, o) for each vector v3 i ̸= v1 i . We next define pure Nash equilibria. A bidding matrix V is a strict pure Nash equilibrium if all bidding vectors in V are strict pure best responses, and V is a weak pure Nash equilibrium if some vectors in V are weak best responses and the other vectors in V are strict best responses. Throughout the paper, we consider monotone pure Nash equilibria in which each agent bids their positively or zero for each item they like, and bids zero for each item they dislike.

Agent a envies (ex ante) ex post agent b if a's (expected) utility of b's (expected) allocation is greater than a's (expected) utility of a's (expected) allocation. A bidding profile is envy-free (ex ante) ex post for a mechanism if no agent envies (ex ante) ex post another one given the (expected) allocation returned by the mechanism on this profile. A bidding profile is (ex ante) ex post Pareto efficient for a mechanism if the (expected) allocation returned by the mechanism on this profile is Pareto optimal. A mechanism is strategyproof if, with complete information, no agent can misreport their sincere utilities for items and thus strictly increase their (expected) utility. A mechanism is group strategy-proof if, with complete information, no set (or no group) of agents can misreport their sincere utilities and thus strictly increase their group expected outcome (i.e. the sum of the expected utilities of the agents in the group).

We show our hardness results using notions from computational complexity and graph theory.

Computational complexity: We use complexity classes such as P, NP, coNP and #P as well as mappings such as Karp, Turing and parsimonious reductions [Garey and Johnson, 1979; Turing, 1936; Valiant, 1979].

Graph theory: Let G be a bipartite graph. A matching in G is a set of vertex-disjoint edges. We say that it matches a vertex if there is an edge in it that is incident with the vertex. A matching is perfect if it matches all vertices in G.

We report our results for strategy-proofness in Section 3. We then study how to compute equilibria in Section 4. In Section 5 and Section 6, we show non-uniqueness of equilibria and hardness of counting them. We conclude in Section 7.

3 Manipulable Mechanisms

We know that the LIKE mechanism is strategy-proof and the BALANCED LIKE mechanism is not strategy-proof [Aleksandrov et al., 2015]. We, therefore, proceed with group manipulations. In our food allocation problem, charities in the same region might decide to bid together for all items they like in common because they might exchange these items post the allocation. In our organ matching problem, hospitals in the same city might decide to report common patients multiple times on a national level and thus bias the national matching of organs in their favor. Group strategy-proof mechanisms exist and are successfully characterized in many domains [Mart´ınez et al., 2004; Pountourakis and Vidali, 2012]. Unfortunately, in online fair division, no mechanism is group strategy-proof in general.

Theorem 1 With general utilities, no mechanism is group strategy-proof.

Proof. Consider two agents and one item. Suppose the item is not always allocated deterministically to the agent bidding most for it. Then, from a group strategy perspective, the two agents can improve the group outcome by having only the agent with greatest utility bidding for the item. Hence, to be group strategy-proof, the item must be deterministically allocated to agent bidding most for it. However, the underbidder can now improve their individual outcome by increasing their bid to exceed the current winner's bid. Thus, deterministically allocating item to agent bidding most for it is not strategy-proof and thus not group strategy-proof.✷

If we use LIKE in the proof of Theorem 1, we immediately conclude that this mechanism is not group strategyproof even with 0/1/2 utilities. Surprisingly, however, it becomes group strategy-proof with 0/1 utilities.

Theorem 2 With 0/1 utilities, the LIKE mechanism is group strategy-proof.

Proof. Consider a group of agents. Note that the expected outcome of the group for each item oj is independent of their bidding strategies for items o1 to oj-1. Each joint bidding strategy of the agents from the group can be represented as a sequence of individual agent strategies. There are multiple such sequences that correspond to a given joint bidding strategy. The group outcome increases with LIKE if the next two conditions hold. For each such sequence and each individual bidding strategy in it, we have that the group expected outcome does not decrease. For each such sequence and some individual bidding strategy in it, we have that the group expected outcome increases. We show that no such strictly increasing individual strategy could exist. Let us pick an agent from the group and an item, say a1 and o1. WLOG, suppose that o1 is liked by k agents from the group, and by l agents in total. If a1 sincerely dislikes item o1 and strategically bids 1 for it, l is in [k, n-1] and the decrease from the sincere group outcome is k/[l · (l + 1)]. If a1 sincerely likes item o1 and strategically bids 0 for it, l is in [k, n] and the decrease from the sincere group outcome is (l - k)/[l · (l - 1)]. Both deviations are non-negative. Hence, sincere bidding dominates.✷

By Theorem 2, it quickly follows that the sincere strategy is dominant for a group of agents and for an item if the agents from the group that like the item have the same utility for it.

Corollary 1 With general utilities, the LIKE mechanism is group strategy-proof if, for each group G and item oj, each agent fromG that likes oj has utility uGj for it.

We next report one interesting observation about group strategy-proofness. Envy-freeness ex ante is incompatible with ex ante Pareto efficiency in general.

Observation 1 With general utilities, no mechanism is group strategy-proof and envy-free ex ante, or group strategy-proof and ex ante Pareto efficient even with randomisation.

The LIKE mechanism is group strategy-proof and envyfree ex ante with 0/1 utilities but not even bounded envy-free ex post. In contrast, BALANCED LIKE is envy-free ex ante and bounded envy-free ex post but not even strategy-proof. Both of them are Pareto efficient with 0/1 utilities.

4 Computing Pure Nash Equilibria

We show that there could be a unique weak or strict pure Nash equilibrium and then that computing one is intractable.

Example 1 (Unique weak pure Nash equilibrium) Consider items o1 and o2 and agents a1 and a2. Suppose that a1 likes o1 with 1 and o2 with 2, and a2 likes o1 with 2 and o2 with 1. Let us run the BALANCED LIKE mechanism. The sincere profile is not a pure Nash equilibrium. By bidding sincerely, each agent receives expected utility of 3/2. By bidding strategically 0 for item o1, each agent receives strictly higher expected utility of 2. This is the only pure Nash equilibrium which happens to be weak because the agents receive the same outcomes if a2 reports 0 for o2 in it. ✷

Example 2 (Unique strict pure Nash equilibrium) Consider the instance in the proof of Theorem 2 from [Aleksandrov et al., 2015]. It has a unique pure Nash equilibrium which happens to be strict.✷

We further study the following computational problem for an instance and a mechanism.

PURE NASH EQUILIBRIUM

Input: instance A and mechanismM

Output: a pure Nash equilibrium of A with M

If we can solve this problem in polynomial time, then we can solve its decision version in polynomial time. The decision version asks whether there is a pure Nash equilibrium of the given instance with the given mechanism. We show that the decision version is intractable for BALANCED LIKE and therefore the computational problem is intractable as well. Our Reduction 1 is a Karp mapping from the minimum size maximal matching problem in 3-regular bipartite graphs which is NP-complete [Demange and Ekim, 2008].

Reduction 1 Let R be a 3-regular bipartite graph with vertices u1, . . . , uN and v1, . . . , vN. For each vertex ui, let vi1, vi2, vi3 denote the vertices connected to it and e3·(i-1)+1 = (ui, vi1), e3·(i-1)+2 = (ui, vi2), e3·(i-1)+3 = (ui, vi3) the edges incident with it. Each edge ek can be represented as (ui, vj) for some ui ∈ {u1, . . . , uN} and vj ∈ {vi1, vi2, vi3}. We construct instance IR as follows:

• Agents: 1 agent ak per edge ek, agents b and c and agents d1 to d2·(N-r) (i.e. 5 · N - 2 · r + 2 agents),
• Items: 1 item per vertex vj, 2 items ui1 and ui2 per vertex ui, 2 more items wi1 and wi2 per vertex ui and items x1 to xN-r, y (i.e. 6 · N - r + 1 items),
• Non-zero Utilities each agent ak has utility of 1 for items vj, ui1, ui2,wi1,wi2 and x1 to xN-r; agent b has utility of 1 for items xN-r and y; agent c has utility of 1 for item y only; each agent dk has utility of 1 for u11, u12 to uN1, uN2, and
• Ordering: o = (u11u12 . . . uN1uN2v1 . . . vNw11w12 . . . wN1wN2x1 . . . xN-ry).

The completely detailed proofs of the next technical Lemmas 1 and 2 are omitted for reasons of space.

Lemma 1 There is a maximal matching in R of cardinality at most r iff, with the BALANCED LIKE mechanism, agent b receives item y in IR with probability greater than zero.

Lemma 2 With the BALANCED LIKE mechanism, the sincere profile of IR is a pure Nash equilibrium.

Proof sketch. Suppose the sincere profile is not a pure Nash equilibrium. Consequently, there is an agent that receives strictly higher expected utility by reporting zeros for items they sincerely like supposing the other agent strategies are the sincere ones. We consider four cases. In the first one, suppose this is agent a1. There is a symmetry in the preferences of agents a1, a2, a3, and each other triplet of a's agents. There is another symmetry in the preferences of agents ai, aj, ak such that all like item vh for each h. Based on these symmetries, we obtained that agent ak is sincere iff agent ai is sincere, and that agent a1 is strictly sincere. In the second case, suppose this is agent b. They receive outcome of p+(1-p) · (1/2) if they bid 1 for xN-r, y, 1/2 if they bid 1 only for y, p > 0 if they bid 1 only for xN-r, and 0 if they do not bid for items. Sincerity dominates. In the third case, suppose this is agent c. They receive p + (1 - p) · (1/2) if they bid 1 for y, and 0 otherwise. Sincerity dominates. In the fourth case, suppose this is agent d1. There is a symmetry in the preferences of agents d1 to d2·(N-r). Based on it, we obtained that agent dk is sincere iff agent di is sincere, and that agent d1 is strictly sincere. ✷

Lemma 3 With the BALANCED LIKE mechanism, there is at least one more pure Nash equilibria of IR besides the sincere profile iff agent b receives item y in IR with probability zero.

Proof. If agent b receives item y in IR with probability 0, then let us substitute their sincere bid of 1 for item y with their strategic bid of 0 for this item. The new profile is another pure Nash equilibrium in which all agents receive exactly the same outcomes as in the sincere profile. If there is at least one more pure Nash equilibrium of IR besides the sincere profile, then it must be the case that agent b receives item y with zero probability in the sincere profile. This follows because each other agent is strictly sincere by Lemma 2.✷

There are many hardness implications under Turing reductions from Lemmas 1, 2 and 3. There is a strict pure Nash equilibrium of IR iff the sincere profile is a strict pure Nash equilibrium. There is a weak pure Nash equilibrium of IR iff the sincere profile is not a strict pure Nash equilibrium. Hence, there is a weak pure Nash equilibrium of IR iff there is not a strict pure Nash equilibrium of IR. Further, there is a pure Nash equilibrium of IR iff there is a weak or a strict pure Nash equilibrium of IR iff agent b receives item y with zero or positive probability. Further, there is a unique pure Nash equilibrium of IR iff the sincere profile is a strict pure Nash equilibrium. There is a pure Nash equilibrium of IR with egalitarian welfare at least 1 (achieved by agent c for item y) iff the sincere profile is a weak pure Nash equilibrium. Even more, there is a (weak) strict pure Nash equilibrium of IR in which agent b bids 1 for item y iff the sincere profile is a (weak) strict pure Nash equilibrium. These problems have indirect implications to the problem of finding a Nash equilibrium in general [Dickhaut and Kaplan, 1993; Porter et al., 2008; Sandholm et al., 2005].

Corollary 2 With 0/1 utilities and the BALANCED LIKE mechanism, problem PURE NASH EQUILIBRIUM is NPhard.

We next study group pure Nash equilibria for the LIKE mechanism. We can view the allocation process with this mechanism as a repeated game [Tomala, 1998]. This follows from the fact that this mechanism is Markovian. In each round j of this repeated game, there is a group pure Nash equilibrium for the current item oj. The group pure Nash equilibrium of a game played m rounds is a collection that has a group pure Nash equilibrium for each item.

Theorem 3 With general utilities and the LIKE mechanism, problem PURE NASH EQUILIBRIUM is P.

Proof. WLOG, we show that computing a group pure Nash equilibrium for say item oj is tractable. At step 1, let us pick a group of agents G. WLOG, suppose that all agents from G (no agent that dislikes oj can increase the group outcome of G by bidding positively for oj ), and k other agents not from G like item oj. We need to compute a set H ⊆ G such that H = argmaxJ⊆G[(∑ai∈J uij)/(|J| + k)]. Note that maxJ⊆G[(∑ai∈J uij)/(|J| + k)] is equal to maxl∈[0,|G|] maxJl⊆G[(∑ai∈Jl uij)/(l + k)] where l agents are in Jl. But, then maxJl⊆G[(∑ai∈Jl uij)/(l + k)] is equal to (maxJl⊆G ∑ai∈Jl uij)/(l + k). Finally, the value of maxJl⊆G ∑ai∈Jl uij can be computed in O(n) space and time for each l. To do so, we just pick l different agents from G with the first l greatest utilities for item oj. Hence, the set of agents H can be computed in O(n2 ) time. This result holds for any value of k. The "best" strategy for the agents from G is that the agents from H bid positively for item oj and the agents fromG\H bid zero for oj . At step 2, consider next the set of k agents not fromG that like item oj and another group F that contains at least one of these agents. Similarly, compute the "best" strategy of the agents from F that like item oj and are not from G. Repeat step 2 with the remaining agents not from G and F but that like oj till not more such agents are left. The "best" strategies converge to a group pure Nash equilibrium. Interestingly, even though there might be an exponential number of not necessarily disjoint groups of agents, our procedure terminates in O(n3 ) space and time. Hence, a group pure Nash equilibrium can be computed in O(n3 · m) space and time.✷

5 Multiple Pure Nash Equilibria

In general, there could be multiple pure Nash equilibria. Some of these could be strict and some others could be weak. There also could be payoff equivalent or payoff different pure Nash equilibria. In fact, the number of weak pure Nash equilibria with equal outcomes could be exponential in the number of agents.

Example 3 (Weak pure Nash equilibria) We consider the fair division of items o1 to on between agents a1 to an. Suppose that a1 likes each item with utility 1 and each other agent ai likes only oi with utility 1. With BALANCED LIKE, the sincere bidding strategy is dominant for each agent. However, agent a1 receives the same expected outcome of 1 if they bid 1 for o1 with probability 1 and, for each of the other n - 1 items, they bid 1 with probability 1 or bid 0 with probability 1. Hence, there are 2n-1 weak pure Nash equilibria that give the same output as the sincere profile. ✷

Moreover, there could also be exponentially many strict pure Nash equilibria with unequal outcomes.

Example 4 (Strict pureNash equilibria)We use n gadgets, each of 4 agents and 4 items, to construct instance A with 4n agents and 4n items that have 2n different strict pure Nash equilibria. The ith gadget has agents ai1 to ai4 and items oi1 to oi4. Agent ai1 likes items oi1 and oi4 with 1, item oi2 with 1 + 2i · ϵ and dislikes item oi3. Agent ai2 likes only item oi2 with 1. Agent ai3 likes items oi1 and oi4 with 1, item oi3 with 1 + (2i + 1) · ϵ and dislikes item oi2. Agent ai4 likes only item oi3 with 1. The items are revealed in ordering oi = (oi1oi2oi3oi4). Suppose that ϵ < 1 4·n and we use BALANCED LIKE mechanism. There are two strict pure Nash equilibria of this gadget if we consider it as an online instance by itself: (1) agent ai1 bids 0 for item oi1 and all other agents are sincere, and (2) agent ai3 bids 0 for item oi1 and all other agents are sincere. These two profiles are different as their expected allocations are different. The instance A contains n such gadgets: for i ∈ [1, n], agents ai1 to ai4 and items oi1 to oi4. The entire ordering of A is (o1 . . . on). The two strict pure Nash equilibria of each gadget are independent and different than the two strict pure Nash equilibria of each other gadget. Hence, A admits 2n different equilibria.✷

6 Counting Pure Nash Equilibria

Computing pure Nash equilibria is intractable in general. Even if we compute a single pure Nash equilibrium, we cannot be sure that the agents will play according to it simply because there might be multiple pure Nash equilibria. As a result, the task of counting (or enumerating) pure Nash equilibria becomes more relevant than simply computing such profiles. We hence show that counting equilibria (and therefore enumerating them) is intractable even when computing a single pure Nash equilibrium is tractable.

In particular, we ask questions around counting pure Nash equilibria with some specific property. For example, how many profiles are there whose outcome is equal to the outcome of the sincere profile or to the one of some equilibrium? Or, how many equilibria are Pareto efficient or envyfree? Further, strategic behavior might increase or decrease the welfare value [Aleksandrov et al., 2015]. But, how many equilibria maximize the egalitarian welfare e, the utilitarian welfare u or the Nash n welfare (i.e. the minimum expected utility of an agent, the sum or the product of the expected utilities of the agents, respectively)?

We give a single parsimonious reduction from the popular #P-complete counting perfect matchings problem that output the number of perfect matchings in a given undirected bipartite graph G. Counting perfect matchings problem is shown to be #P-hard on 3-regular bipartite graphs in [Dagum and Luby, 1992]. Our Reduction 2 is very simple but also insightful because it provides a very tight bound on the complexity of counting, parameterizing or approximating pure Nash equilibria (i.e. as many items as agents, 0/1 utilities, each agent likes 3 items, each item is liked by 3 agents, each pair of agents like at most 2 items in common, the ordering is fixed, etc.) [Jerrum and Sinclair, 1989; Downey and Fellows, 2013].

Reduction 2 Let R be a 3-regular bipartite graph with vertices u1, . . . , uN and v1, . . . , vN. For each vertex ui, let vi1, vi2, vi3 denote the vertices connected to it and e3·(i-1)+1 = (ui, vi1), e3·(i-1)+2 = (ui, vi2), e3·(i-1)+3 = (ui, vi3) the edges incident with it. Each edge ek can be represented as (ui, vj) for some ui ∈ {u1, . . . , uN} and vj ∈ {vi1, vi2, vi3}. The allocation instance ER is as follows:

• Agents: 1 agent ak per edge ek (i.e. 3 · N agents),
• Items: 1 item per vertex vj, 2 items ui1, ui2 per vertex ui (i.e. 3 · N items),
• Non-zero Utilities each agent ak has utility of 1 for items vj, ui1, and ui2, and
• Ordering: o = (v1 . . . vNu11u12 . . . uN1uN2).

Theorem 4 Even with 0/1 utilities and BALANCED LIKE, counting pure Nash equilibria is #P-hard.

Proof. In the sincere profile, it is easy to show that the expected utility of each agent is equal to 1. In fact, the sincere profile in ER is a pure Nash equilibrium. Let us next consider the following perfect profile for each perfect matching in R. WLOG, for each i ∈ [1,N], suppose the matching matches ui to vj which happens to be vi1. The perfect profile that corresponds to this matching is as follows: for i ∈ [1,N], agent a3·(i-1)+1 bids 1 for items vj , ui1, ui2, and agents a3·(i-1)+2 and a3·(i-1)+3 bid 1 only for items ui1, ui2. There is 1-to-1 correspondence between the perfect matchings in R and the perfect profiles in ER. Therefore, counting such profile is intractable. Note that computing one of them in ER is tractable [Hopcroft and Karp, 1973]. Finally, it is easy to show that each perfect profile is a pure Nash equilibrium in which each agent receives expected utility of 1.✷

Corollary 3 With BALANCED LIKE, counting pure Nash equilibria that maximize the egalitarian, utilitarian or Nash welfare is #P-hard.

Proof. For e, each agent in each perfect profile of ER receives expected utility of 1. Therefore, the value of e in this profile is 1. We argue that this is the maximum value of this welfare. To see this, consider any bidding profile in which some agents receive expected utility more than 1. Hence, there are some other agents that receive expected utility less than 1. This is guaranteed because there are as many items as agents in ER, the utilities are binary, each agent likes at least one item and each item is liked by at least one agent. As a result, the sum of the expected utilities of the agents is equal to n and hence each perfect profile maximizes e. For u, each perfect profile maximizes it because at least one agent bids for each item. For n, we argue that the maximum value of this welfare is 1 and is achieved whenever each agent receives expected outcome of 1. We highlight the key idea. Consider a triplet of agents, say a3·(i-1)+1, a3·(i-1)+2 and a3·(i-1)+3, and a bidding profile in which say a3·(i-1)+1 receives expected utility greater than 1. We showed that a3·(i-1)+2 or a3·(i-1)+3 receives expected utility smaller than 1 in such a profile. The same holds for every triplet of agents. For each such bidding profile, we obtained that n < 1. Finally, each agent receives outcome of 1 in all profiles that n = 1. ✷

Corollary 4 With BALANCED LIKE, counting pure Nash equilibria whose outcome is sincere is #P-hard.

Proof. The result follows immediately because agents in ER receive expected outcomes of 1 in the sincere profile and in each perfect profile.✷

Corollary 5 With BALANCED LIKE, counting pure bidding profiles whose outcome is equilibrium is #P-hard.

Proof. Consider the following profile for each perfect profile. For i ∈ [1,N], agent a3·(i-1)+1 bids 1 for item vj, agent a3·(i-1)+2 bids 1 for item ui1 and agent a3·(i-1)+3 bids 1 for item ui2. We call this profile deterministic because a single agent bids for each item. Each agent receives (expected) utility of 1 in such a deterministic profile. This outcome is equal to their outcome in the sincere profile and in each perfect profile. However, the deterministic profile is not a pure Nash equilibria. Agent a3·(i-1)+3 increases their outcome from 1 to 3 2 by bidding 1 instead of 0 for item ui1 supposing we keep the other bidding strategies fixed.✷

Corollary 6 With BALANCED LIKE, counting pure Nash equilibria whose outcome is Pareto efficient is #P-hard.

Proof. Each perfect profile of ER is Pareto efficient ex post and ex ante. These profiles are pure Nash equilibria.✷

Corollary 7 With BALANCED LIKE, counting pure Nash equilibria whose outcome is envy-free is #P-hard.

Proof. Each perfect profile of ER is envy-free ex ante because each agent receives expected utility of 1. Each such profile is also envy-free ex post because each agent receives exactly one item in each possible allocation. These profiles are pure Nash equilibria.✷

Counting competitive pure Nash equilibria that are Pareto efficient or envy-free or maximize the welfares is intractable. We next count group pure Nash equilibria with these mechanisms. By Theorem 4, we conclude that counting group pure Nash equilibria is #P-hard with BALANCED LIKE even when each agent is alone in a group. This counting problem remains intractable for LIKE even with 0/1/2 utilities.

Reduction 3 Given the 3-regular bipartite graph R in Reduction 2, construct an online allocation instance FR with the same set of agents, the same set of items, the same zero utilities and the same ordering as in ER. Only the non-zero utilities in FR differ from the ones in ER. For i between 1 and N and j ∈ {1, 2, 3}, agent a3·(i-1)+j has utility 2 for item vij if the vertices ui and vij in the graph are matched in some perfect matching in R and 1 otherwise, and utility 2 for items ui1 and ui2. To compute such a "coloring" in polynomial time, we can use a polynomial maximum matching algorithm such as the one from [Hopcroft and Karp, 1973].

Theorem 5 Even with 0/1/2 utilities and LIKE, counting group pure Nash equilibria is #P-hard.

Proof. Consider instance FR and suppose that all agents are in a group. The sincere profile of FR is not a pure Nash equilibrium. Suppose sincere play. Each agent receives expected utility 2 if they have cardinal utility 2 for each of the three items they like, and 5/3 if they have cardinal utility 1 for the first item they like and 2 for each of the remaining two items. Suppose next strategic play. Let the agents bid according to one perfect profile that is defined for FR as for ER in Theorem 4. Each agent receives expected utility 2 given such a profile. Hence, the group outcome can only increase. In fact, such a perfect profile is a group pure Nash equilibrium. ✷

Finally, note that each perfect profile of FR in the proof of Theorem 5 is also Pareto efficient and envy-free whereas the sincere profile is not. We conclude the next immediate result for LIKE (or even for BALANCED LIKE).

Corollary 8 With LIKE, counting group pure Nash equilibria whose outcome is Pareto efficient, envy-free or maximizes the egalitarian, the utilitarian or the Nash welfare is #Phard.

7 RelatedWork and Conclusions

Our work is in-line with many other research works that study equilibria induced by allocation mechanisms. For example, the equilibria of the popular probabilistic serial rule are wellunderstood [Aziz et al., 2015]. We consider weak and strict Nash equilibria as in [Shapley and Rigby, 1959] but we restricted ourselves to pure such profiles. The presentation of our counting results was inspired by the hardness results for two agents presented in [Conitzer and Sandholm, 2008]. Unfortunately, we could not inherit any of these results because manipulations for two agents are tractable for LIKE and BALANCED LIKE. Our decision problems are similar to other such problems in stochastic game-theory [Ummels and Wojtczak, 2009].

To conclude, we studied pure Nash equilibria for two allocation mechanisms in a simple online fair division model: LIKE and BALANCED LIKE. The LIKE mechanism is strategyproof but not group strategy-proof and therefore we studied its group pure Nash equilibria. These profiles always exist and are tractable. But, are they always Pareto efficient or envy-free? The BALANCED LIKE mechanism is not strategyproof and therefore we studied its competitive pure Nash equilibria. These profiles are intractable. It is an interesting future work to consider in more details the case of two agents. Even more, we want to explore possible parameterizations and approximations of these problems. For example, a sampling scheme might exist for our counting problems whose convergence is guaranteed by the Hoeffding's inequality [Sab´an and Sethuraman, 2013]. Finally, as our first next step, we plan to study the induced subgame perfect Nash equilibria of the repeated game. We also left open the question whether there is always a pure Nash equilibrium in such games for BALANCED LIKE.

Acknowledgements

Data61 (formerly NICTA) is supported by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.

Toby Walsh acknowledges support from the European Research Council, as well as the Asian Office of Aerospace Research and Development.