# fair_and_truthful_giveaway_lotteries__70c1e448.pdf

Fair and Truthful Giveaway Lotteries

Tal Arbiv,1,2 Yonatan Aumann1

1Bar Ilan University 2The College of Management Academic Studies talarbiv7@gmail.com, aumann@cs.biu.ac.il

We consider a setting where a large number of agents are all interested in attending some public resource of limited capacity. Attendance is thus allotted by lottery. If agents arrive individually, then randomly choosing the agents one by one - is a natural, fair and efficient solution. We consider the case where agents are organized in groups (e.g. families, friends), the members of each of which must all be admitted together. We study the question of how best to design such lotteries. We first establish the desired properties of such lotteries, in terms of fairness and efficiency, and define the appropriate notions of strategy proofness (providing that agents cannot gain by misrepresenting the true groups, e.g. joining or splitting groups). We establish inter-relationships between the different properties, proving properties that cannot be fulfilled simultaneously (e.g. leximin optimality and strong group stratagy proofness). Our main contribution is a polynomial mechanism for the problem, which guarantees many of the desired properties, including: leximin optimality, Paretooptimality, anonymity, group strategy proofness, and adjunctive strategy proofness (which provides that no benefit can be obtained by registering additional - uninterested or bogus - individuals). The mechanism approximates the utilitarian optimum to within a factor of 2, which, we prove, is optimal for any mechanism that guarantees any one of the following properties: egalitarian welfare optimality, leximin optimality, envyfreeness, and adjunctive strategy proofness.

1 Introduction

Each summer, dozens of brown bears descend daily on Mc Neil River State Game Sanctuary and Refuge to feed on the salmon that swim past in their upstream migration. Only ten lucky visitors, chosen by lottery, are admitted (daily) to watch this spectacle. Similar lotteries are administered for entrance permits to dozens of other natural attractions across the US and Canada, as for awarding tickets to the White House Easter Egg Roll, and the National Christmas Tree Lighting Ceremony. In Venice, Italy, a lottery is used to award 15 lucky citizens with prime seats for observing the traditional Regata Storica on the Grand Canal. No official data is available, but it is safe to assume that hundreds such lotteries, if not more, are carried out worldwide each year.

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

How should these lotteries be designed? If people were only interested in attending the events individually, then randomly choosing the entrants - one by one - is the natural, fair and efficient solution. However, many people do not want to enjoy these events alone, but rather with family, friends, and the like. Indeed, some of these lotteries explicitly allow individuals to register in groups, which, if win, are all admitted together. How should such group lotteries be designed? This is the topic of this paper.

Examples. How can/should the lottery be conducted? One option is to choose the individuals at random. However, this means that members of large families are severely disadvantaged; if the probability of a lone person to attend is p, then the probability of a k person family to attend is only pk. Another method, commonly used in practice, is to randomly order the groups, and admit groups in order - so long as the capacity is not exceeded. If a group overfills the resource, then the next in order is considered, until no more groups can be admitted. This method, however, again unduly penalizes large groups. Consider the Mc Neil River park with its 10 person limit, and suppose five couples and two 5-person families have registered. Then, the random order method gives more than 1/2 probability for each of the couples to attend, but less than 0.4 to the families. The reason is that the families can only attend if they are first, second or third in line - and even that not always - while the couples have considerably more options. Furthermore, with probability 2/3, only 9 people end up being admitted. At the same time, by grouping the two families separately, and the five couples separately, it is possible to admit each person with probability 1/2, and also obtain 100% utilization of the resource. Next, consider a mechanism that only aims to maximize utilization, that is, the number of persons admitted. Suppose there is one family of size 5 and two of size 3. Then, the mechanism admits the 5 person family with probability 1, and each of the others with probability 1/2 each. In this case, the smaller families are better off jointly registering as a 6-person family - misrepresenting their true structure - to secure admittance with probability 1 (and - in the course - reducing the utilization). So, such a mechanism promotes cheating.

Contributions. In this paper we study the design of such giveaway lotteries. We seek lotteries that are fair, efficient

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

and strategyproof. The contributions of this paper are three fold. Firstly, we formally define the setting and the relevant properties of interest for such lotteries, in several regards, including: fairness, efficiency, and strategy proofness. Secondly, we establish relationships between the properties, including some properties that imply others, and properties that cannot be obtained simultaneously (e.g. leximin optimality and strong group strategyproofness). Thirdly, and most importantly, we present a polynomial mechanism that simultaneously achieves many of the desired properties, including: leximin optimality, Pareto optimality, anonymity, envy-freeness, and - importantly - group strategy proofness, and also adjunctive strategy proofness (which provides that no benefit can be obtained by registering additional uninterested or bogus individuals). The algorithm also guarantees at least a 1/2 approximation to the optimal utilization of the resource (per instance), which, we prove is optimal for any mechanism that guarantees any one of the following properties: egalitarian welfare optimality, leximin optimality, envyfreeness, and adjunctive strategy proofness.

Organization. Section 2 introduces the model and studies relevant objectives. The relations between the properties are studied in Section 3. The polynomial mechanism is presented in Section 4. Section 5 concludes with future work.

1.1 Related Work

This work is related to a large body of work on fair allocation, and, in particular, randomized allocations of indivisible goods. Due to the limited space we only mention some relevant and foundational works. The early work of (Hylland and Zeckhauser 1979) considers fair many-toone random allocations. (Bogomolnaia and Moulin 2001) study mechanisms for random allocation of n items to n agents with ordinal preferences. (Budish et al. 2013) extend the framework to include many-to-many assignments, and importantly, to allow for quotas and complementarities within preferences over bundles. Complementarities are also considered by (Nguyen, Peivandi, and Vohra 2014) (see also (Gutman and Nisan 2012)). The core difference of our work from this line is that in our setting the utility of the players are not independent, but rather fully depend on the allocation to the other agents. (Aziz, Bogomolnaia, and Moulin 2019) consider voting rules for fractional distribution of public goods, where fractional can also be interpreted probabilistically. Unlike our model, they seek mechanisms that provide larger groups with a bigger share (/probability) of the good. A recent manuscript (Arnosti and Bonet 2021) considers lotteries for distribution of tickets to events, focusing, as we do, on groups that seek to attend together. While the setting is similar to ours, there are major differences, in both the model and the results. Their main concern is with wasted tickets and inflated demand, which is only a minor issue in our model (under the adjunctive strategy proofness - see Section 2.4). On the other hand, we seek and obtain leximin optimality, while they only aim to maximize the least utility, and our major result is group strategy proofness, while they only consider individual strategy proofness.

Strategyproof fair allocation of indivisible goods was considered, among others, by (Svensson 1999; P apai 2000; Pycia and Unver 2017), the last of which also considering group strategy proofness. Strategyproofness in the cakecutting (divisible good) context is considered in (Chen et al. 2013; Mossel and Tamuz 2010; Maya and Nisan 2012; Dall Aglio, Branzei, and Tijs 2009), the last of which considers group strategy proofness. The key difference of our work to the above is that in our setting the possible misrepresentation of the agents is not with regards to their individual utilities but rather of their group structure. Group preferences are considered in the context of matching, mostly for couples (groups of size 2) (Kojima, Pathak, and Roth 2013; Abdulkadiroglu et al. 2006; Ashlagi, Braverman, and Hassidim 2011; Bronfman et al. 2018). Some matching literature, e.g. college admissions, considers preferences over the universe of subsets entrants (Roth 1985; Abizada 2016; Kawase and Iwasaki 2017). Leximin optimality (also called max-min fairness) as a fairness criterion was considered in many works, see (Moulin 2004) for an excellent rewiew. Leximin optimal routing and load balancing algorithms frequently use an iterative algorithm similar to ours, see (Nace, Pioro, and Doan 2006). Our work is also related to fractional bin packing as introduced by (Karmarkar and Karp 1982).

2 Model and Objectives 2.1 Model

We first formally define the problem setting, which we call Giveaway Lottery (Ga L). A Ga L instance is a pair I = (F, c), where F = (F1, F2, . . . , Fn) is a collection of n disjoint sets of individuals, and c is the capacity of the resource the individuals wish to enjoy. We assume that c |Fi| for all i, as a larger Fi s clearly cannot enjoy the resource, and may be omitted. Each Fi is called a family. A set S of individuals is admissible if |S| c and it is a union of families. We denote by A the collection of admissible sets. A solution for a Ga L instance is a distribution D = (p D(S))S A over the admissible sets, with the meaning that set S is chosen to enjoy the resource with probability p D(S). Given a solution distribution D, and a set F of individuals, we denote D(F) = P F S p D(S), which we call the admittance probability of F. Given a Ga L instance, there are several objectives that may be of interest in the solution distribution D. We now list the main objectives of interest.

2.2 Fairness

Fairness can take many meanings. We now review some of the established criteria, and how they relate to our setting.

Egalitarian Welfare. The egalitarian welfare of a distribution D is the least admittance probability of any family: eg(D) = mini{D(Fi)}. We seek to maximize eg(D).1

1Here and throughout, we naturally view the admittance probability of an individual as its utility.

Leximin Fairness. The egalitarian welfare considers only the least probability, but does not discern between distributions that offer the same least probability, but differ in other probabilities. The leximin criterion takes the entire distribution into account. For a multi-set X of reals, let (X1, X2, . . . , ) be the elements of X ordered in non-decreasing order. For such multisets X, Y , we denote X leximin Y , if there exists an i such that, Xj = Yj for j < i, and Xi < Yi. The leximin order naturally induces an order on the solution distributions. We denote D leximin D, if {D(Fi)}n i=1 leximin { D(Fi)}n i=1. We seek to maximize the solution according to this order.

Anonymity. An algorithm/mechanism is anonymous if it only takes into account the sizes of the families, and not the identity of its members. In our case, a mechanism is anonymous if D(Fi) = D(Fj) whenever |Fi| = |Fj|.

Envyfreeness. Envyfreeness is a common fairness criterion in the context of fair division (Brams and Taylor 1996), requiring that no player would prefer to obtain the share of another player. In our context this translates to saying that no family Fi would prefer to be admitted instead of any other family Fj, whenever Fj is admitted. Note, however, that if Fi is larger than Fj, then there may be cases where Fi cannot be admitted in Fj s stance. So, the requirement is only that Fi not prefer to be admitted in Fj s stance, whenever it is possible. Formally, envyfreeness states that for any i, j,

S:Fj S and (S Fj) Fi A p D(S).

2.3 Efficiency Ex-Post Pareto Optimality. Conceptually, ex-post Pareto Optimality says that following the lottery no additional family can be admitted, in addition to those chosen by the lottery. Formally, for any S, if p D(S) > 0 then S is not a strict subset of any other admissible set.

Ex-Ante Pareto Optimality. A distribution D is ex-ante Pareto optimal if there is no other distribution that gives all families at least the same as in D, and strictly increases the probability of some family.

Utilization. The utilization offered by the distribution D is the expected utilization of the resource; that is ut(D) = P S A p D(S) |S|

c . We seek to maximize ut(D).

2.4 Strategy Proofness In our setting, the only information provided by the agents is the list of registrants, and their kinship structure. So, strategy proofness provides that individuals/families cannot gain by falsely reporting this information. A mechanism M for the Ga L problem is an algorithm that, given an instance I produces a distribution D = M(I).

Individual Strategy Proofness. This level of strategy proofness provides that no family alone can gain by misrepresentation; that is, by partitioning itself into several families. Formally,

Definition 2.1 (Individual Strategy Proofness). Mechanism M is individually strategy proof if for any F = {F1, . . . , Fn} and c, any i, and any partition G of Fi, the following holds. Let D = M(F, c), and D = M(F , c), where F = F \ {Fi} G. Then, D(Fi) D (Fi).2

Group Strategy Proofness. Group strategy proofness provides that no collection of families can all gain by collectively misrepresenting their kinship structure. Strong group strategy proofness requires that no one of the misrepresenting families can gain while the other mis-representing families are not harmed. Formally, Definition 2.2 (Group Strategy Proofness). Mechanism M is group strategyproof if for any F = {F1, . . . , Fn} and c, any C F, and any partition G of Fi CFi, the following holds. Let D = M(F, c), and D = M(F , c), where F = F \ C G. Then, D(Fi) D (Fi) for some Fi C. The mechanism is strong group strategyproof if D(Fi) < D (Fi) for some Fi C implies that D(Fj) > D (Fj) for some other Fj C.

Adjunctive Strategy Proofness. The Ga L setting lends itself to another type of misrepresentation. A family, or set of families, may register additional - non-interested - individuals, or even bogus ones. Adjunctive Strategy Proofness provides that this cannot be beneficial. We consider two possibilities as to where the additional, non-interested individuals can be placed. The hybrid version requires that the non-interested individuals are placed in families together with original ones. The apart version allows the formation of families comprising exclusively of non-interested individuals. Formally, Definition 2.3 (Adjunctive Group3 Strategy Proofness). Mechanism M is hybrid adjunctive group strategyproof if for any F = {F1, . . . , Fn} and c, any C F, any S disjoint from all Fj s, and any partition G = {G1, . . . , Gk} of Fj CFj S wherein Gj S for all j, the following holds. Let D = M(F, c), and D = M(F , c), where F = F \ C G. Then, D(Fi) D (Fi) for some Fi C. Apart adjunctive group strategyproofness is defined identically, only not requiring that Gj S for all j. By definition, hybrid adjunctive group strategyproof implies apart hybrid adjunctive group strategyproof, which implies group strategyproof, which implies individual strategy proofness.

3 Relations Among Properties 3.1 Implications We now establish properties that imply others. Proposition 1. Ex-ante Pareto optimality implies ex-post Pareto optimality, but not the opposite.

Proof. If D is not ex-post Pareto optimal, then there exist admissible sets S, S with S S , with p D(S) > 0. So,

2D (Fi) is the probability that all members of Fi are admitted together. It is well defined even though Fi is not a family in F . 3For brevity we defined adjunctive strategyproofness only in the group form.

the distribution D that shifts all the probability of S to S ex-ante Pareto dominates D. For the reverse none-implication consider the setting |F1| = |F2| = |F3| = 2, |F4| = |F5| = 3 and c = 6. Then, the distribution that gives probability 1/6 to each of the 6 combinations of size 5 is ex-post Pareto optimal, but is ex-ante Pareto dominated by the distribution giving probability 5/12 to F1 F2 F3, and 7/12 to F4 F5.

Proposition 2. Envyfreeness implies anonymity.

Proof. Suppose that D is not anonymous. So, D(Fi) < D(Fj), for some |Fi| = |Fj|. So, Fi envies Fj.

Proposition 3. Any distribution that is leximin optimal also: (i) maximizes the egalitarian welfare, (ii) is Pareto optimal (ex-ante and ex-post), and (iii) envyfree.

Proof. Let D be a leximin optimal distribution. If D offers higher egalitarian welfare, then it also dominates D in the leximin order. The same holds if D ex-ante Pareto dominates the D, and ex-post follows from ex-ante. To show that D is envyfree, contrariwise suppose that Fi envies Fj. Let D be wherein Fi is admitted in Fj s stead, whenever possible, and Fj is never admitted. Then, D(Fi) < D (Fi) D(Fj). Set ϵ = D (Fi) D(Fi). Consider the mixture distribution D = (1 ϵ)D + ϵD . Then,

D (Fj) = (1 ϵ)D(Fj) > D(Fj) ϵ D(Fi) D (Fi) = (1 ϵ)D(Fi) + ϵD (Fi) > D(Fi) D (Fℓ) = D(Fℓ) for ℓ = i, j.

So, D leximin dominates D, contrary to the assumption.

3.2 Impossibility Results We now establish properties that cannot be simultaneously guaranteed.

Proposition 4. No mechanism can guarantee both leximin optimality and strong group strategy proofness.

Proof. Consider the setting with the following family sizes:

|F1| = 9, |F2| = 8, |F3| = |F4| = 5, |F5| = |F6| = 4, |F7| = 2, |F8| = 1,

and c = 10. Then, the following is leximin optimal:

Pr[F1 F8] = Pr[F2 F7] = Pr[F3 F4] = 1/4, Pr[F5 F6 F7] = Pr[F5 F6 F8] = 1/8,

giving probability 3/8 to F7 and F8, and 1/4 to the others. However, if F3, F4, F5, and F6 collude with F8, creating two new sets of size 9, F = F3 F5 and F = F4 F6. Then, the leximin optimal solution is:

Pr[F1 F8] = Pr[F2 F7] = Pr[(F3 F5) F8] = Pr[(F4 F6) F8] = 1/4,

giving probability 3/4 to F8 without harming the other colluding families.

Proposition 5. No mechanism can guarantee both leximin optimality and apart adjunctive strategyproofness.

Proof. Consider a setting with two families |F1| = 3 and |F2| = 1, and c = 3. Then, leximin optimality dictates that each get probability 1/2. Now suppose that F2 registers two additional, uninterested families F3, F4 of size 2. Then, the leximin optimal solution to this new instance is

Pr[F1] = Pr[F2 F3] = Pr[F2 F4] = 1/3,

increasing F2 s probability to 2/3.

Proposition 6. Any mechanism that is hybrid group adjunctive strategyproof cannot guarantee to approximate the optimal utilization to any constant greater than 1/2.

Proof. Let M be hybrid group adjunctive strategyproof. Consider any ϵ > 0. Choose c > 2/ϵ, even. Consider the setting with c families each of size c/2 + 1. Then, there is at least one family, w.l.o.g. F1, to which M assigns admittance probability at most 1/c. Now consider what happens if F1 enlarges itself to size c, by adding external people. Then, it must be that M still gives this new F1 probability at most 1/c. But then the utilization, of this new instance, is bounded by:

c + c/2 + 1

while this instance has a solution with utilization 1. So, M does not approximate the optimal utilization to 1/2 + ϵ.

Proposition 7. Any mechanism that is any one of the following: (i) egalitarian welfare optimal, (ii) leximin optimal, (iii) envyfree, cannot guarantee to approximate the optimal utilization to within any constant greater than 1/2.

Proof. Consider ϵ > 0, and pick c > 2/ϵ, even. Consider the setting with c 1 families of size c/2 + 1 and one family of size c. Then, any solution that is egalitarian welfare optimal, leximin optimal, or envyfree must give all families identical probability 1/c. As in the proof above, the utilization of this solution is less than 1/2 + ϵ. So, the utilization is less than 1/2 + ϵ of the optimal (which is 1 in this case).

4 A Polynomial Mechanism We now provide a polynomial mechanism to Ga L that guarantees most of the desired properties that can be simultaneously obtained.

4.1 A Linear Programming Formulation We start with a linear programming formulation of the problem. Maximizing the eg(D), can formulated as follows:

max ˆp s.t. X

S:Fj S p(S) ˆp j = 1, . . . , n

ˆp, p(S) 0, S A

Here, ˆp is the egalitarian welfare, which we wish to maximize. The first constraint (together with non-negativity) states that the p(S) s constitute a distribution. The second set of constraints states that the admittance probability of each family Fj is at least ˆp. This enables us to maximize eg(D), but does not necessarily produce a leximin optimal or even a Pareto-optimal solution. To obtain such a solution, we will need to iterate through a slightly more complex program. Suppose that for some subset of families we have already found their optimal/maximal probability, and we only seek to maximize the probability of the remaining families. That is, there is a collection of families H F, and a sequence of probabilities ˆpˆpˆp H = (ˆp(Fj))Fj H, such that for each Fj H, we only require its total probability is ˆp(Fj), and do not seek to further maximize it. Then, the LP formalization of the problem is:

max ˆp s.t. X

S:Fj S p(S) = ˆp(Fj), for Fj H

S:Fj S p(S) ˆp, for Fj H

ˆp, p(S) 0, S A Denote the above linear program by LP(H, ˆpˆpˆp H). This program has an exponential number of variables. Nonetheless, we now show that it can be solved in time that is polynomial in n and c, using a separation oracle for the dual.

4.2 Solving the Linear Program Using the Dual The dual of LP(H, ˆpˆpˆp H) is

j:Fj H ˆp(Fj)yj)

j:Fj H yj 1 (1)

j:Fj S yj, S A (2)

yj 0, j : Fj H This programs has a polynomial number of variables, but an exponential number of constraints. We will now construct a separation oracle for the problem, which operates in time that is polynomial in n and c. So, the program can be solved in poly(c,n) time (Gr otschel, Lov asz, and Schrijver 1981).

A Separation Oracle. Given an assignment T, y1, . . . , yn, constraint (1) is easy to check. Consider the set of constraints of type (2). These, collectively, can be represented as a knapsack problem with n items, wherein item j has weight |Fj| and value yj, and the knapsack has capacity c. Then, a packing of the knapsack with value > T corresponds to an admissible set for which the constraint is violated. Conversely, if the maximum value of the knapsack problem is T, then no constraint is violated. Using dynamic programming Knapsack can be solved in time poly(c,n). This construction is similar to that of (Karmarkar and Karp 1982).

Algorithm 1: Iterative Probability Maximization (IPMAX) Input: families F1, . . . , Fn, ordered in decreasing size; c Output: Distribution D 1: H ; ˆpˆpˆp H () (the empty list) 2: for i = 1 to n do 3: Solve LP(H, ˆp H). Let D be the optimal assignment and ˆp the optimal value 4: H H {i}; ˆp(Fi) ˆp 5: end for 6: return D

Solving the Primal. Given a solution to the dual, it is now possible to obtain a solution to the primal. For completeness, we outline the process. Let H be the set of constraints actually used in the process of solving the primal. Then |H| is polynomial. Let x H be the set of primal variables associates with the dual constraints of H. By complementary slackness, only the variables of x H need to get positive values. So, one can solve the primal with these variables alone, which is a polynomial size program.

4.3 IPMAX - The Iterative Algorithm

We now describe an iterative algorithm that produces the desired solution. Order the families in decreasing order of size; that is, |F1| |F2| |Fn|. The algorithm, fully described in Algorithm 1, iteratively optimizes and fixes the probabilities of the families, one by one, by order of size. In each iteration, having fixed the probabilities of the bigger families, it maximizes the egalitarian welfare of the remaining families. This is similar in spirit to mechanisms for maxmin fairness in routing and load-balancing (Nace, Pioro, and Doan 2006), but here families are considered in order of size - which is key to proving strategy proofness.

Theorem 1. Algorithm IPMAX is hybrid adjunctive group strategyproof (and in particular group strategy proof), produces a solution that is leximin optimal, and approximates the utilization to at least a 1/2 factor.

By Propositions 3 and 2, IPMAX is also anonymous, envy-free, and Pareto optimal (ex-ante and ex-post). By Propositions 4 and 5, hybrid adjunctive group strategyproof is the strongest possible stretegy proofness if leximin optimality is desired, and by Propositions 7 and 6, a 1/2 utilization is the best possible for either leximin optimality or hybrid adjunctive group strategyproofness. So, in this sense, the properties of IPMAX are the best possible. The remainder of this section is devoted to proving Theorem 1.

4.4 Leximin Optimality

Lemma 1. ˆp(Fi) ˆp(Fi+1) for all i.

Proof. ˆp(Fi) is fixed to the optimum of the LP of the i-th iteration, which admits all families indexed i and up, with probability ˆp(Fi). So, this optimal assignment is also a feasible assignment for the LP of the next iteration, in which ˆp(Fi+1) is fixed.

Lemma 2. There always exists a leximin optimal distribution D wherein D(Fi) D(Fj) whenever |Fi| |Fj|.

Proof. Let D be leximin optimal distribution. If the claim does not already holds for D, then let i, j be such that |Fi| > |Fj| and D(Fi) > D(Fj). We construct another distribution D, wherein the probabilities of Fi and Fj are switched, while all other probabilities remain the same. Iterating this process, the result follows. Set = D(Fi) D(Fj). By assumption is > 0. Let Ai, j be the admissible sets that contain Fi but not Fj. Set q = P S Ai, j p D(S). Then, q . For S Ai, j, let Si j = S \ Fi Fj. Since |Fi| |Fj|, Si j is also admissible. Let D be the distribution wherein for each S Ai, j, instead of admitting S with probability p D(S), we admit S with probability p D(S) (1

q ), and Si j with probability p D(S)

q (this probability is added to the original probability of this set). Then, the total amount of probability added to Fj is P S Ai, j p D(S)

q = , and the same amount is subtracted from the admittance probability of Fi.

Claim 1. The output of IPMAX is leximin optimal.

Proof. Let D be the output of IPMAX, and, contrariwise, suppose it is not leximin optimal. Let D be a leximin optimal distribution. By Lemma 2, we may assume that D(Fi) D(Fi+1), for all i. Let i be the minimum integer such that D(Fi) < D(Fi). So, D(Fi) D(Fj) for j > i. So, the distribution D is a feasible solution for the LP solved in the i-th iteration of IPMAX. So, the optimum of this LP must be at least D(Fi), which we assumed is not the case.

4.5 Strategy Proofness We now prove that IPMAX is hybrid adjunctive group strategyproof, and, in particular, group strategyproof. Let D = IPMAX(F, c). We call the families of F the original families. Consider C F, which we call the cheating families. Let S be such that S is disjoint from Fi FFi (S are the additional, uninterested registrants). Let G = {G1, . . . , Gk} be a partition of Fj CFj S, such that for all j, Gj S (this is the hybrid requirement). We call the families of G contrived families, and those of F \C - authentic.4 Set F = F \C G. Let D = IPMAX(F , c). We need to show that it cannot be that D (Fj) > D(Fj) for all cheating families. Suppose that this is the case. The following Lemmas 4-7 are under this counter-factual assumption. Order the families of F in decreasing size order, F = {B1, B2, . . . , Bn }. Some of the Bi s are authentic families and some contrived. Note that the distribution D induces admittance probabilities on the original families. First note that it cannot be that D (Fj) D(Fj) for all authentic families, as this would mean that D is a Pareto improvement over D. Accordingly, let d be the least index such that Bd is an authentic family and D (Bd) < D(Bd). Families of size at least |Bd| we call big, and the others

4Note that a contrived family may also be original.

small. The following technical lemma will be useful in the future. Lemma 3. Let X = {x1, . . . , xk}, Y = {y1, . . . , yk} sets (of numbers), ordered in decreasing size, such that there exist indexes i1 i2 such that: (a) for i < i1, yi xj for some j i, (b) for i1 i < i2, yi xj, for some j > i, (c) yi2 > xi1. Then, X leximin Y .

Proof. From (a) we have that yi xi for i < i1, and from (b) that yi xi+1, for i1 i < i2. So for i < i2, yi xi, and for i = i2, yi yi 1 xji 1 xi. So, yi xi for i i2. Suppose that they are all equal. Then, xi1 = yi1 xi1+1 = yi1+1 xi2 = yi2, in contradiction to (c).

Lemma 4. All contrived families are small.

Proof. Contrariwise, suppose that Bℓis a big contrived family. First, suppose that Bℓintersects with a small cheating family Fj. Then D (Fj) D (Bℓ) since Fj intersects Bℓ D (Bd) since |Bℓ| |Bd| < D(Bd) by definition of Bd D(Fj) since |Bd| |Fj| But this means that D reduces the probability of the cheating family Fj, which cannot be. Hence, Bℓintersects only with big cheating families. Let Fb be the cheating family with the least probability according to D . Then, D (Fb) D (Bℓ) D (Bd). Consider the sets P(D) = {D(Fj)}n j=1 and P(D ) = {D (Fj)}n j=1. Let k be the number entries of P(D ) smaller than D (Fb). These k elements are all of authentic families, D (Fj1), . . . , D (Fjk). Clearly, jt j, for all t = 1, . . . , k. Now, consider the k + 1 smallest elements of P(D). These are D(F1), . . . , D(Fk+1). Consider two case.

1. F1, . . . , Fk+1 are all non-cheating. Then, b > k + 1, and D (Fb) > D(Fb) D(Fk+1), and the conditions of Lemma 3 hold with i1 = i2 = k + 1. 2. There exists ˆi k + 1 such Fˆi is a cheating family, and ˆi is the smallest such index. So, D (Fb) > D(Fb) D(Fˆi). So, the conditions of Lemma 3 hold with i1 = ˆi and i2 = k + 1.

In both cases, D leximin dominates D on F, in contradiction to the leximin optimality of D.

Lemma 5. For all i < d, D (Bi) = D(Bi).

Proof. By Lemma 4, for i < d, all families Bi are authentic. So, D (Bi) D(Bi), by the definition of d. Suppose that D (Bˆi) > D(Bˆi), for some ˆi < d. Let P(D) = {D(Fj)}n j=1 and P(D ) = {D (Fj)}n j=1. Then, for i < ˆi, D (Bi) D(Bi) D(Fi), and D (Bˆi) > D(Bˆi) D(Fˆi). So, D leximin dominates D (on the original families), which cannot be.

Lemma 6. For every contrived family Bℓ, D (Bℓ) > D (Bd).

Proof. First, suppose that Bℓintersects with a small cheating family Fj. Then,

D (Bℓ) > D(Fj) D(Bd) > D (Bd) (1)

Hence, suppose that Bℓintersects with a big cheating family. By Lemma 4 Bℓis small. So, D (Bℓ) D (Bd). Suppose that D (Bℓ) = D (Bd). Then, we show that D leximin dominates D on F. Consider P(D) = {D(Fj)}n j=1 and P(D ) = {D (Fi)}n j=1. We show that the conditions of Lemma 3 hold.The smallest d elements of P(D ) are D (B1), . . . , D (Bd), which are all of probabilities of authentic families. So, they are the d smallest authentic families, which we denote Fj1, Fj2, Fjd. Clearly, jt t for all t. The d smallest elements of P(D) are D(F1), . . . , D(Fd). Let Fb be a big cheating family intersecting Bℓ. Consider two cases. If b > d, Then,

D (Bd) = D (Bℓ) D (Fb) > D(Fb) D(Fd).

So, the conditions of Lemma 3 hold with i1 = i2 = d. If b d, then

D (Bd) = D (Bℓ) D (Fb) > D(Fb).

So, the conditions of Lemma 3 hold with i1 = b, i2 = d.

Let t be the smallest index for which D (Bt) > D (Bd). We will now construct a distribution D that leximin dominates D on the instance (F , c). Choose a q with 1 > q > D (Bd) D (Bt) . Let D be the mixture probability D = q D + (1 q)D.5 Then, Lemma 7. D leximin dominates D on F .

Proof. Set P(D ) = {D (Bi)}n i=1 and P(D ) = {D (Bi)}n i=1. Consider the different possible values of i. i t:

D (Bi) q D (Bi) q D (Bt)

D (Bt) D (Bt) = D (Bd).

d i < t: By Lemma 6 all these Bi s are authentic. So,

D (Bi) = q D (Bi) + (1 q)D(Bi) q D (Bd) + (1 q)D(Bd) > D (Bd).

i < d: by Lemma 4 Bi is authentic. So, by Lemma 5,

D (Bi) = q D (Bi) + (1 q)D(Bi) = D (Bi) D (Bd),

where the last inequality is since i < d. So, D (B1), . . . , D (Bd 1), are the d 1 smallest elements of P(D ), and are identical to the d 1 smallest elements of P(D ), which are D (B1), . . . , D (Bd 1). The d-th smallest element of P(D ) is D (Bd), while all other elements of P(D ) are greater than this value, as we have seen. So, P(D ) leximin dominates P(D ).

5Note that while D was computed based on the original families, it induces an admittance probability for any set, including contrived ones. For any set F, D(F) = P

F S p D(S).

Lemma 7, which ultimately results from the contrariwise assumption, is in contradiction to Claim 1. We thus obtain: Claim 2. IPMAX is hybrid adjunctive group strategyproof.

4.6 Utilization Claim 3. The utilization the output of IPMAX is at least 1/2 of the optimal (for the instance). Proof. If all families can be admitted together, than this will be the solution, and the utility is 1. Otherwise, let AM be the set of maximal admissible sets; i.e. those not strictly contained in another admissible set. Since D is ex-post Pareto optimal it gives a positive probability only to sets of AM. Note that for any S, S AM, S = S , it must be that |S| + |S | > c (or else they are not maximally admissible). In particular, there is at most one set ˆS AM with ˆS c/2. If there is no such set ˆS, then the utilization is clearly > 1/2. Otherwise, consider two cases. p = p D( ˆS) 1/2: Set ˆs = | ˆS|/c. The utilization in this case is X

S AM,S = ˆS p D(S)|S|

c + pˆs (1 p)(1 ˆs) + pˆs

2(1 ˆs) + 1

where the second line follows since the last term in the first is non-increasing in p.

p = p D( ˆS) > 1/2: Then, for any Fi ˆS, D(Fi) < 1/2. Now consider D which shifts some probability from ˆS to the other sets: p D ( ˆS) = 1/2, and for all other sets S AM, p D (S) = p D(S) 1/2

1 p. Then, D increases the

probability of families not in ˆS, while keeping those of ˆS at least 1/2. So, it leximin dominates D, which cannot be.

5 Future Work There are many ways in which this work can and should be extended. We mention a few. This work considered a single incarnation of the resource. In practice, there may be several incarnation, e.g. several days in which the event takes place. In such a case, agent groups may indicate days in which they can and cannot attend, or even preferences over the days. This is actually the setting in many of the park entrance lotteries. Additionally, there may be several different resources, e.g. several different parks, and the goal is to achieve fairness in the overall allocation. Another interesting extension is where individuals may belong to several groups, e.g. family and friends, and they are satisfied if they are admitted in any one of them. In this work we focused on fair solutions. An interesting question is what can be achieved when the fairness requirement is dropped, and only utilization is of interest? In particular, it is easy to see that group strategy proofness rules out (guaranteeing) a utilization better than 5/6, but can 5/6 be achieved? what is the true bound?

References Abdulkadiroglu, A.; Pathak, P.; Roth, A. E.; and Sonmez, T. 2006. Changing the Boston school choice mechanism. NBER Working Papers 11965, National Bureau of Economic Research. Abizada, A. 2016. Stability and incentives for college admissions with budget constraints. Theoretical Economics, 11(2): 735 756. Arnosti, N.; and Bonet, C. 2021. Lotteries for Shared Experiences. http://nickarnosti.com/Research Papers/Arnosti Bonet Shared Experiences.pdf. Accessed: 2022-03-14. Ashlagi, I.; Braverman, M.; and Hassidim, A. 2011. Matching with Couples Revisited. In Proceedings of the 12th ACM Conference on Electronic Commerce, EC 11, 335 336. New York, NY, USA: Association for Computing Machinery. ISBN 9781450302616. Aziz, H.; Bogomolnaia, A.; and Moulin, H. 2019. Fair Mixing: The Case of Dichotomous Preferences. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 19, 753 781. New York, NY, USA: Association for Computing Machinery. ISBN 9781450367929. Bogomolnaia, A.; and Moulin, H. 2001. A new solution to the random assignment problem. Journal of Economic theory, 100(2): 295 328. Brams, S. J.; and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Bronfman, S.; Alon, N.; Hassidim, A.; and Romm, A. 2018. Redesigning the Israeli Medical Internship Match. ACM Trans. Econ. Comput., 6(3 4). Budish, E.; Che, Y.-K.; Kojima, F.; and Milgrom, P. 2013. Designing Random Allocation Mechanisms: Theory and Applications. American Economic Review, 103(2): 585 623. Chen, Y.; Lai, J. K.; Parkes, D. C.; and Procaccia, A. D. 2013. Truth, justice, and cake cutting. Games and Economic Behavior, 77(1): 284 297. Dall Aglio, M.; Branzei, R.; and Tijs, S. 2009. Cooperation in dividing the cake. Top, 17(2): 417. Gr otschel, M.; Lov asz, L.; and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2): 169 197. Gutman, A.; and Nisan, N. 2012. Fair Allocation without Trade. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS 12, 719 728. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems. ISBN 0981738125. Hylland, A.; and Zeckhauser, R. 1979. The Efficient Allocation of Individuals to Positions. Journal of Political Economy, 87(2): 293 314. Karmarkar, N.; and Karp, R. M. 1982. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), 312 320. IEEE.

Kawase, Y.; and Iwasaki, A. 2017. Near-Feasible Stable Matchings with Budget Constraints. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, 242 248. Kojima, F.; Pathak, P. A.; and Roth, A. E. 2013. Matching with couples: Stability and incentives in large markets. The Quarterly Journal of Economics, 128(4): 1585 1632. Maya, A.; and Nisan, N. 2012. Incentive compatible two player cake cutting. In International Workshop on Internet and Network Economics, 170 183. Springer. Mossel, E.; and Tamuz, O. 2010. Truthful fair division. In International Symposium on Algorithmic Game Theory, 288 299. Springer. Moulin, H. 2004. Fair Division and Collective Welfare. Number 0262633116 in MIT Press Books. The MIT Press. ISBN ARRAY(0x484429d0). Nace, D.; Pioro, M.; and Doan, L. 2006. A tutorial on maxmin fairness and its applications to routing, load-balancing and network design. In 4th IEEE International Conference on Computer Sciences Research, Innovation and Vision for the Future (RIVF 2006). Nguyen, T.; Peivandi, A.; and Vohra, R. 2014. One-Sided Matching with Limited Complementarities. PIER Working Paper Archive 14-030, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania. P apai, S. 2000. Strategyproof Assignment by Hierarchical Exchange. Econometrica, 68(6): 1403 1433. Pycia, M.; and Unver, M. U. 2017. Incentive compatible allocation and exchange of discrete resources. Theoretical Economics, 12(1): 287 329. Roth, A. E. 1985. The college admissions problem is not equivalent to the marriage problem. Journal of Economic Theory, 36(2): 277 288. Svensson, L.-G. 1999. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4): 557 567.