# fair_division_with_a_secretive_agent__fdb7bd77.pdf

The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)

Fair Division with a Secretive Agent

Eshwar Ram Arunachaleswaran,1 Siddharth Barman,1 Nidhi Rathi1

1Indian Institute of Science eshwarram.arunachaleswaran@gmail.com, barman@iisc.ac.in, nidhirathi@iisc.ac.in

We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with cardinal preferences. We will show that, for all of these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation. For the rent-division setting we prove that well-behaved utilities of n 1 agents suffice to find a rent division among n rooms such that, for every possible room selection of the secretive agent, there exists an allocation (of the remaining n 1 rooms among the n 1 agents) which ensures overall envy freeness (fairness). We complement this existential result by developing a polynomial-time algorithm for the case of quasilinear utilities. In this partial information setting, we also develop efficient algorithms to compute allocations that are envy-free up to one good (EF1) and ε-approximate envy free. These two notions of fairness are applicable in the context of indivisible goods and divisible goods (cake cutting), respectively. One of the main technical contributions of this paper is the development of novel connections between different fairdivision paradigms, e.g., we use our existential results for envy-free rent-division to develop an efficient EF1 algorithm.

1 Introduction

The theory of fair division addresses the fundamental problem of dividing resources/goods in a fair manner among agents with heterogeneous valuations, but equal entitlements (Moulin 1986). Many recent results in artificial intelligence and algorithmic game theory address computational aspects of fair division, see, e.g., (Brandt et al. 2016) and (Rothe and others 2015) for excellent expositions. A central thread of research here is to design algorithms that complement nonconstructive existential results. This computational perspective has lead to notable algorithms, hardness results, and the development of novel solution concepts; in fact, a number of such notions and algorithms have been integrated into

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

widely-used websites (e.g., Spliddit and Adjusted Winner 1), which provide methods for fair division of resources, rent, and tasks. This works contributes to computational thinking in fair division and, in particular, studies algorithmic aspects of existential results which show that the preferences of only n 1 agents suffice to find a fair division among n agents. Such an existential result for the case of two agents and a divisible good (which is metaphorically represented as a cake) follows directly from the standard divide-and-choose protocol: considering the valuation of just the first agent we can partition the cake into two parts of equal value (for the first agent) and, then, the second agent can select her most preferred piece. This protocol leads to an envy-free cake division, i.e., in the resulting allocation no agent has a strictly stronger preference for the other agent s piece. Envy freeness is a standard notion of fairness ((Foley 1967), (Varian 1974), (Stromquist 1980)) and the divide-and-choose method shows that a fair division with respect to this notion can be found even if the second agent is secretive and just selects a piece after we partition the cake. Asada et al. (2018) showed that this result extends to higher number of agents who are endowed with ordinal preferences: there exists a division of the cake into n parts, which depends on the (subjective) preferences of only n 1 agents, such that the nth (secretive) agent can select an arbitrary piece and still we would be able to allocate the remaining n 1 pieces in an envy free manner. In other words, independent of the choice of the secretive agent, there exists an allocation in which no agent has a strictly stronger preference for the piece of any other agent (including the secretive one). This result of Asada et al. relies on a fixedpoint argument specifically, it uses a version of the Knaster Kuratowski-Mazurkiewicz (KKM) Lemma (1929). Frick et al. (2017) show that an analogous result holds in the context of fair rent division. Rent division is another well-studied problem in the fair-division literature, and it entails allocating n rooms among n agents and splitting the rent such that envy freeness is achieved; see, e.g., Su (1999), Alkan et al. (1991), Aragones (1995), Klijn (2000) and Gal et al. (2017). Considering agents who have ordinal preferences over the rooms (for every possible division of the

1http://www.spliddit.org/, http://www.nyu.edu/projects/ adjustedwinner/

rent), Frick et al. (2017) proved that the preferences of n 1 agents suffice to find a rent division such that secretive agent can select an arbitrary room (at its price) and still an overall envy-free allocation of the remaining n 1 rooms (at their respective prices and among the n 1 agents) would exist. In this paper we will consider agents who have cardinal valuations over the good(s) and develop efficient algorithms for secretive fair division in multiple settings. Specifically, we will study fair division of rent, cake, and indivisible goods. We will show that, under appropriate valuations, for all of these settings a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will continue to admit a fair allocation. Overall, this work establishes existential and algorithmic results for secretive analogues of standard fair-division problems.

Fair rent division: This problem entails splitting the rent and allocating n rooms among n agents such that, under the imposed rents, each agent prefers the room allocated to it over that of any other agent. In the cardinal version of this problem the preferences of the agents for the rooms are expressed via functions (one for each agent-room pair) which specify agents utility for the rooms at every possible room rent. The works of Svensson (1983) and Alkan et al. (1991) shows that if the utility functions of all the n agents for each of the n rooms are continuous, strictly decreasing, and bounded, then an envy-free rent division is guaranteed to exist. We extend these results and prove that, considering the utility functions of n 1 agents,2 we can propose a rent division among the n rooms such that for every possible room selection of the secretive agent there exists an allocation (of the remaining n 1 rooms among the n 1 agents) which ensures overall envy freeness (Theorem 4). Hence, analogous to the result of Asada et al. (which considered ordinal preferences), we show that fair rent division with a secretive agent can be achieved in the cardinal setting as well.3

Efficient algorithms for fair rent division are known for the quasilinear utility model (Aragones 1995), (Gal et al. 2017) and (Klijn 2000). In this setup every agent a has a base value for each room r, and a s utility for room r when its rent is pr is equal to the base value minus pr. We show that, under quasilinear utilities, an efficient, fair-division algorithm exists even in the secretive case (Theorem 6). EF1 Allocations of indivisible goods: As mentioned previously, envy-free divisions always exist for divisible goods. By contrast, such a universal existential guarantee does not hold in the context of indivisible goods.4 To address this is-

2As in the standard rent-division case, these utilities are assumed to be continuous, strictly decreasing, and bounded. 3The assumptions considered in (Asada et al. 2018) render that result incomparable with the cardinal setting of the present paper. 4For a single indivisible good and two agents (with nonzero valuation for the good), the losing agent will be envious in any allocation

sue and motivated by allocation problems that involve discrete resources (such as courses at universities (Budish et al. 2016)), a number of recent results have formulated and studied fairness notions that specifically address discrete goods (Budish 2011), (Procaccia and Wang 2014), (Bouveret and Lemaˆıtre 2016). A prominent notion in this line of work is that of envy freeness up to one good (EF1), which is a compelling analogue of envy freeness in this setting (2011). Specifically, an allocation is said to be EF1 if every agent prefers her own bundle over any other agent s bundle, up to the removal of one good from the other agent s bundle. Lipton et al. (2004) proved that if the valuations of the agents (over subsets of goods) are monotone, then an EF1 allocation always exists and can be computed in polynomial time. The result is notably general, since it encompasses all monotone (combinatorial) valuations. We prove that, even with a secretive agent, fairness in terms of EF1 can be guaranteed. In particular, we show that, given n 1 agents with monotone valuations, we can efficiently partition the set of indivisible goods into n disjoint subsets, S = {S1, S2, . . . , Sn}, such that every collection of n 1 subsets from S can be assigned (among the n 1 agents) to obtain an EF1 allocation overall (Section 4). Note that our result shows that an EF1 allocation exists if n 1 agents have monotone valuations; the valuation of the nth agent can be completely arbitrary. Hence, as a corollary, we get a strengthening of the existence guarantee of Lipton et al. (2004). Proportionality: Proportionality is another fundamental fairness criterion and, in the context of cake cutting, it deems a partition among n agents to be fair if each agent receives a piece of value at least 1/n times her value for the entire cake (Steinhaus 1948). Note that additivity of the valuations ensure that an envy free allocation satisfies proportionality. However, in contrast to envy freeness, a proportional division of the cake can be efficiently achieved by following the moving-knife procedure of Dubins and Spanier (1961). We show that, interestingly, this moving-knife procedure can be executed with n 1 agents to obtain an n-partition which is proportionally fair even with a secretive agent. In the context of indivisible goods, maximin fairness provides a natural relaxation of proportionality and this notion has been extensively studied in recent years.5 Our work develops an efficient algorithm that, even with a secretive agent, finds a 1/19-approximate maximin fair allocation (of indivisible goods) under submodular valuations of the nonsecretive agents. An improved approximation guarantee of 1/2 is obtained for additive valuations. In the interest of space, results on proportional and maximin fairness have been deferred to the full version of the paper. Overall, the paper shows that a broad spectrum of fair division problems can be addressed in a partial information setting. Indeed, with respect to a specific agent, these results prove that a limited number of valuation queries suffice to find a fair division. Furthermore, our work implies stronger versions of standard existential and algorithmic results, e.g., the rent-division result developed in the paper shows that as

5In the case of indivisible goods, proportional fair divisions are not guaranteed to exist.

long as n 1 agents have quasilinear utilities, an envy-free rent division can be computed efficiently. Here, the utility function of the nth agent can be arbitrary; this is in contrast to prior works, which require all the agents to have quasilinear utilities. We obtain these results by developing connections between different fair division paradigms; in particular, we establish the result for EF1 by using the rentdivision guarantees. These connections are mentioned below, and they might be of independent interest. Our Techniques: We use the generalization of the KKM lemma developed in Asada et al. (2018) to establish the existence of fair rent division with a secretive agent. It is relevant to note that the work of Frick et al. (2017) (which addresses ordinal preferences) does not encompass the cardinal setting considered in this paper. In particular, the existence guarantee in Frick et al. (2017) requires that each agent prefers a room with zero rent over any room with nonzero rent. Since, in general, this assumption is not satisfied even for quasilinear utilities, the result of Frick et al. (2017) does not directly hold for cardinal preferences. Our efficient algorithm for quasilinear utilities draws upon the equivalence between envy-free rents and Walrasian equilibria. Specifically, the Second Welfare Theorem for Walrasian equilibrium ensures that if the n 1 agents have quasilinear utilities, then every maximum weight matching between the agents and the rooms induces an envy-free solution; here the weights between agents and rooms are set to be the corresponding base values. We use this property to formulate a linear program whose solution is a fair rent division which is robust to the choice of the secretive agent. Instantiating the result for quasilinear utilities, we show that if n 1 agents have monotone valuations, then an EF1 allocation (with a secretive agent) always exists and can be computed efficiently. Specifically, we develop an algorithm that iteratively allocates goods to bundles and maintains the EF1 property as an invariant. We use the rent-division result to show that in each iteration the algorithm can efficiently find a bundle and allocate the next good to it such that the invariant continues to hold. Note that, in contrast to the existential result of Lipton et al. which relies on a direct parity argument our work uses a novel connection between rent division and discrete fair division. The developed EF1 algorithm in turn provides an efficient method to find an approximate envy-free cake division through the reduction employed by Lipton et al (2004) : we partition the cake into pieces such that, for each of the n 1 agents, the value of any piece is at most ε. Then, considering these low-valued pieces as indivisible goods, we execute the EF1 algorithm to obtain an approximately envy-free division which can accommodate an arbitrary selection by the secretive agent. The formal description of the problem and the reduction can be found in the full version of the paper.

2 Notation and Preliminaries Envy Free Rent Division: An instance of the (standard) envy-free rent division problem is represented by the following tuple A, R, {va(r, )}a A,r R wherein A := [n] denotes the set of n agents and R := [n] denotes the set of n rooms. The cardinal preference of each agent a A for

every room r R is specified via a utility function va(r, ), i.e., a s utility for r at price (rent) pr R is va(r, pr) R. A solution to the rent division problem comprises of the tuple (π, p), where π : A 7 R is a bijection from the set of agents to the set of rooms and p Rn is a price vector for the set of rooms. The tuple (π, p) is said to be an envy-free solution of the given instance if for all a A and r R we have va(π(a), pπ(a)) va(r, pr), i.e., under the given price vector, no agent strongly prefers (envies) any other room to the one allocated to her. Envy-Free Rent Division with a Secretive Agent: A rent-division instance with a secretive agent is a tuple A, R, {va(r, )}a A\{n},r R , wherein A = [n] and R = [n] denote the set of n agents and n rooms, respectively. We will use va(r, ) to denote the utility function of agent a A \ {n} for room r R. Here, in contrast to the standard rent division setting, the problem instances have a distinguished, secretive agent, n, who gets to pick any room of her choice after the prices for the rooms have been proposed.6 A secretive envy-free solution is a price vector p Rn that satisfies the following property: for every room k R, there exists a bijection πk : A\{n} 7 R\{k} such that (πk, p) is envy-free, i.e., for all a A \ {n} and r R we have va(πk(a), pπk(a)) va(r, pr). Intuitively, a price vector p Rn constitutes a solution in the secretive setting if for any arbitrary room choice, k R, of the secretive agent, the properties of p allow us to allocate the remaining rooms (using πk) among the agents such that no agent strictly prefers any other agent s room. Note that such a price vector p is computed before the choice k is made by the secretive agent and without taking into account any information about her utilities. We will focus on two classes of utility functions. First, we will establish existential results for bounded, continuous and monotone (strictly) decreasing utilities. The utility functions {va(r, )}a A\{n},r R are bounded in the sense that there exists M R+ such that for all agents a A \ {n} and all pairs of rooms r, r R the following inequality holds va(r, M) < va(r , 0). A special, well-studied subclass of bounded, continuous and monotone decreasing utility functions is that of quasilinear utilities in which each utility function va(r, x) is of the form Ba r x; here Ba r R+ is the base value of room r for agent a. In other words, in the quasilinear setup the utility of agent a for room r is equal to her base value for the room minus the rent of r. Secretive EF1 Allocations of Indivisible Goods: An instance of the fair division problem with indivisible goods and a secretive agent is a tuple A, G, {va}a A\{n} in which A := [n] stands for the set of n agents, G := [m] denotes the set of m indivisible goods, and vas specify the valuation of each agent a A \ {n} over the set of goods. The valuation functions va : 2G 7 R+ are assumed to be nonnegative and monotone for all agents a A\{n}.7 Write

6Note that the instances do not contain any information about the utilities of the (nth) secretive agent. 7Note that, analogous to the rent-division case, the instance tuple contains no information about the valuation function of agent

Πn(G) to denote the set of all n-partitions of G. In the standard (non-secretive) context with n agents and set of indivisible goods G, an n-partition A = (A1, . . . , An) Πn(G) is said to be envy-free up to one good (EF1) iff for all agents a, b there exists a good g Ab such that va(Aa) va(Ab \ {g}); here, each agent a is assigned the subset of goods (bundle) Aa. Note that the definition ensures that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. This definition extends to address fair division of indivisible goods with a secretive agent. Formally, an n-partition P = (P1, ..., Pn) Πn(G) of the set of goods G is said to be a secretive EF1 allocation iff it satisfies the following property: for each choice of bundle Pk from partition P, there exists a bijection πk : A\{n} 7 [n]\{k} such that the allocation defined by πk on (P1, . . . , Pk 1, Pk+1, . . . , Pn) is EF1, i.e., for all a A\{n} and all bundles Pb, with b [n], there exists a good g Pb such that va(Pπk(a)) va(Pb \ {g}). In other words, for every choice of bundle Pk made by the secretive agent, the secretive EF1 solution P = (P1, P2, ..., Pn) allows for an EF1 allocation of the remaining bundles among the first n 1 agents.

Remark. Note that the secretive agent gets to pick her first choice. Therefore, in all the settings mentioned above (cake cutting, division of indivisible goods, and rent division), the secretive agent can achieve envy freeness.

Framework for Secretive Solutions Concepts

Note that in all the solution concepts defined above, the bijections/permutations {π1, . . . , πn} (that enable a fair division after the secretive agent makes a choice) are not an explicit part of the solution. However, for all settings considered in this work, these permutations can be computed in polynomial time. We now provide a formalism for secretive solutions which, in particular, will be used for finding secretive EF1 allocations. Let P = (P1, . . . , Pn) represent a collection of n bundles that constitute a candidate solution to a fair division problem with agents A and known valuations {va}a A\{n}. In this abstract setting, the bundles can be divisible goods, or indivisible goods, or even a combination of both (e.g., a bundle can comprise of a room and its rent). Write H to denote the bipartite graph with the two vertex parts being A\{n} and {P1, P2, . . . , Pn}, respectively.8 The edge set of H is constructed to account for the underlying fairness property: edge (a, Pi) is included in H iff bundle Pi satisfies the fairness criterion for agent a. For example, in the context of rent division wherein each bundle Pi is a tuple of a room i and its rent pi edge (a, Pi) is included iff assigning room i to agent a ensures envy freeness for a, i.e., iff va(i, pi) va(r, pr) for r R. Note that the collection of bundles P is a secretive solution (satisfying the required fairness criterion) iff for every k [n] (i.e., each choice Pk of the secretive agent),

n, who is designated to be the secretive agent. 8Note that the two bipartite vertex sets of H are of size n 1 and n, respectively.

there exists a perfect matching πk in the bipartite graph obtained by removing (vertex) Pk from H. This property leads to the following characterization: a collection of bundles P is a secretive solution, with respect to the underlying fairness property, iff for every subset S A \ {n} we have |ΓH(S)| |S|+1; here ΓH(S) denotes the set of neighbors of S in the graph H.

3 Envy-Free Rent Division This section presents our results for fair rent division. We show that, for any rent-division instance with reasonably general utility functions, a secretive envy-free solution is guaranteed to exist. We complement this existential result by developing an efficient algorithm for computing such solutions for when the known utilities are quasilinear.

Existential Result This subsection considers rent-division instances I = A = [n], R = [n], {va(r, )}a A\{n},r R with a secretive agent and utilities, {va(r, )}a A\{n},r R, that are bounded, continuous, and monotone decreasing. Recall that for bounded utility functions {va(r, )}a A\{n},r R there exist parameter M R+ such that for all agents a A \ {n} and all pairs of rooms r, r R:

va(r, M) < va(r , 0) (1)

Write {ei}i [n] to denote the standard basis vectors of Rn and let n be the standard simplex in Rn, i.e., n := conv({ei}i [n]). First we define KKM covers of the simplex and then state the KKM generalization of Asada et al. (2018).

Definition 1 (KKM Cover). A collection of n closed sets C1, C2, ..., Cn Rn is said to form a KKM cover of the simplex n, if and only if for all I [n], the convex hull of the basis vectors corresponding to I is covered by S

i I Ci, i.e., iff for all I [n], we have conv ({ei}i I) S

The following lemma, proved by Asada et. al (2018), establishes a useful property of any n 1 KKM covers of n. The lemma states that for every index k [n], it is possible to pick one set from each KKM Cover such that no two sets have the same index and the index k is not used, with the property that the intersection of these selected sets is non empty.

Lemma 2 ((Asada et al. 2018)). Given (n 1) KKM Covers C1, C2, . . . , Cn 1 (here each Ci = {Ci 1, Ci 2, . . . , Ci n} is a collection of n sets) of the standard simplex n, there exists a point x n and n bijections πk : [n 1] 7 [n] \ {k} with 1 k [n] such that, x T

i [n 1] Ci πk(i).

To apply this lemma we will map points in the simplex to room rents (price vectors). Such a mapping enables us to construct KKM covers from the utilities of the first n 1 agents. Specifically, we define a function h(z) := M(1 nz), where M R+ is a large enough real number satisfying the boundedness condition (1) for the given rent-division instance. Given a simplex point x n, we

apply h component-wise to generate the price (rent) of each room, i.e., price vector p is generated from x by setting pr := h(xr) for all r [n]. Note that h(0) = M and h(M) = 0. For each agent a [n 1], we define a collection of sets Ca = {Ca 1 , Ca 2 , ..., Ca n} such that the set Ca r consists of all the simplex points whose corresponding prices render room r as a first choice of agent a. Formally,

Ca r := {x n | va(r, h(xr)) va(r , h(xr )) r [n]} (2)

The following claim establishes that each agent s collection of sets forms a KKM cover. The proof can be found in the full version.

Claim 3. For each agent a [n 1], the set Ca = {Ca 1 , Ca 2 , ..., Ca n} (as defined above) is a KKM cover of the simplex n.

With the n 1 KKM covers (one for each agent a A \ {n}) at our disposal, we apply Lemma 2 to find a secretive envy-free solution.

Theorem 4. Let I = A, R, {va(r, )}a A\{n},r R be a rent-division instance with a secretive agent. If the utilities, {va(r, )}a A\{n},r R}, of the instance are bounded, continuous, and monotone decreasing, then I admits a secretive envy-free solution p Rn.

Proof. Consider the n 1 KKM covers, C1, . . . , Cn 1, obtained by Definition 1 with valuation functions {va(r, )}a A\{n},r R. Lemma 2 ensures that there exists a point x n and n bijections πk : [n 1] 7 [n] \ {k}, with 1 k n, such that x T

i [n 1] Ci πk(i). We will show that the price vector, p , obtained by componentwise applying function h on x is a secretive envy-free solution. Say, under price vector p , the secretive agent selects room k [n]. Then, the property of the bijection πk : [n 1] 7 [n] \ {k} gives us x T

i [n 1] Ci πk(i), i.e., for all agents a [n 1], the point x is contained in the set Ca πk(a). The definition of KKM covers (see definition in Equation 2) implies that the room πk(a) is a first choice of each agent a A \ {n}. Therefore, for any k R = [n], the allocation (πk, p ) provides an envy-free solution. Overall, we get that p is a secretive envy-free solution of the rent-division instance.

Algorithmic Result for Quasilinear Utilities Efficient algorithms for finding envy-free rent divisions (in the non-secretive setting) have been developed in prior work under quasilinear utilities, see, e.g., (Aragones 1995). In this utility model each function va(r, pr) is of the form Ba r pr, i.e., agent a s utility for room r when its rent is pr is equal to the base value, Ba r , minus pr. Note that Theorem 4 applies to quasilinear utilities, since they are a subclass of bounded, continuous, and monotone decreasing utilities. For a given rent-division instance I = A, R, {va(r, )}a A\{n},r with a secretive agent and quasilinear utilities, throughout this subsection we will use

write H = (A \ {n} R, A R) to denote the complete, weighted bipartite graph (between agents and rooms) in which weight of each edge (a, r) is equal to the base value Ba r . Also, write Hk to denote the weighted, bipartite graph obtained by removing the kth vertex from the rooms side in H. The subsequent lemma provides an analogue of the second welfare theorem for the secretive context. The lemma shows that if πk is a maximum weight matching in bipartite graph Hk, for all k [n], then for any secretive envy-free solution p and any (room) choice k of the secretive agent, one can use πk to find an allocation that achieves envy freeness overall. We use this result to establish the correctness of Algorithm 1 and its proof appears in full version.

Lemma 5. Let I = A, R, {va(r, )}a A\{n},r be a rentdivision instance with a secretive agent and quasilinear utilities (i.e., va(r, x) = Ba r x for all a A\{n} and r R). In addition, for all k [n], let πk be a maximum weight perfect matching in the bipartite graph Hk and p Rn + be any secretive envy-free solution (price vector) of I. Then, (πk, p ) for all k [n] is an envy-free solution of I, i.e., va(πk(a), pπk(a)) va(r, pr) for all k [n], a A \ {n} and r R.

Algorithm 1 Secretive Envy-Free Rent Division under Quasilinear Utilities Input: A rent-division instance with a secretive agent and quasilinear utilities A, R, {va(r, )}a A\{n},r R (here, va(r, x) = Ba r x for all a A \ {n} and all r). Output: A secretive envy-free solution p R+ n and n bijections {πk}k R 1: For all k R, set πk to be a maximum weight perfect matching in graph Hk. 2: Set p Rn + to be the solution of the following linear program {Here we find a single price vector under which each πk is an envy-free allocation}

subject to xr 0 for all r [n] Ba πk(a) xπk(a) Ba r xr for all a A \ {n} and k, r [n]

3: return price vector p and the n bijections {πk}k R.

Theorem 6 establishes the correctness of Algorithm 1.

Theorem 6. Given any rent-division instance I = A, R, {va(r, )}a A\{n},r R with a secretive agent and quasilinear utilities, a secretive envy-free solution p Rn + of I can be computed in polynomial time.

Proof. Theorem 4 ensures that the given instance I admits a secretive envy-free solution p Rn. We can assume that p is componentwise nonnegative uniform, additive shifts on a

price vector maintain envy freeness under quasilinear utilities. In addition, using Lemma 5, for each πk (a maximum weight matching in Hk) we have va(πk(a), pσk(a)) va(r, pr), i.e., πks provide envy-free allocations for every choice k of the secretive agent. Therefore, p certifies the feasibility of the linear program (LP) formulated in Algorithm 1. Since this LP is also bounded, the algorithm will necessarily find a price vector p which (paired with the bijections {πk}k R) explicitly satisfies the definition of a secretive envy-free solution. Given that the number of variables and constraints in the LP are polynomial, it can solved efficiently. Therefore, Algorithm 1 runs in polynomial time.

We conclude this section by stating and proving a combinatorial lemma, which will be essential while establishing the EF1 results. The lemma asserts that for with respect to maximum weight matchings πks (in graphs Hks) there will always be a room that is universally despised by all agents and across all the n bijections πks.

Lemma 7. Let I = A, R, {va(r, )}a A\{n},r be a rentdivision instance with a secretive agent and quasilinear utilities (i.e., va(r, x) = Ba r x for all a A\{n} and r R). In addition, for all k [n], let πk be a maximum weight perfect matching in the bipartite graph Hk. Then, there always exists a room ρ [n] such that Ba πk(a) Ba ρ, for all agents a A \ {n} and all bijections πk, with k [n].

Proof. Write p to denote a secretive envy-free solution of the quasilinear instance I; such a price vector always exists (Theorem 4). Consider a room ρ R with the smallest rent under p: ρ arg minr R pr. Since p is a secretive envy-free solution, for any choice k R of the secretive agent, πk provides an envy-free allocation (Lemma 5). In particular, at the imposed prices, no agent a strongly prefers room ρ to the room allocated to her, i.e., to πk(a). Therefore, va(πk(a), pπk(a)) va(ρ, pρ). Since the utilities are quasilinear we have Ba πk(a) pπk(a) Ba ρ pρ. Finally, the definition of ρ (i.e., pρ pπk(a)) gives us the desired inequality Ba πk(a) Ba ρ.

4 EF1 Division of Indivisible Goods In this section, we address indivisible goods and show that a secretive EF1 allocation always exists and can be computed efficiently, as long as the valuations of the non-secretive agents are monotone increasing. The full version also provides results for divisible goods (i.e., cake cutting). In particular, we reduce the problem of finding a secretive ε-EF solution (in the cake-cutting setup) to that of computing a secretive EF1 allocation (over indivisible goods), by employing the reduction of Lipton et al. (2004) for the same two problems in standard settings. Therefore, using the results developed here, we can obtain existential and algorithmic results for secretive ε-EF cake division. We begin by stating notation which will be required for detailing the algorithm that efficiently finds a secretive EF1 allocation (Algorithm 2). Consider a fair division instance I = A = [n], G = [m], {va}a A\{n} with a secretive

agent and indivisible goods G. Let P = (P1, P2, ...Pn) be an n-partition of of a subset of goods i Pi G; we will refer to such an n-partition P as a partial allocation. Given any partial allocation P, write HP := ((A \ {n}) {Pi}i, (A \ {n}) {Pi}i) to denote the weighted bipartite graph with the two vertex parts being the set of agents A \ {n} and the bundles {P1, . . . Pn}, respectively. Here, an edge (a, Pi) (A \ {n}) {P1, . . . , Pn} is said to be satisfy the EF1 property iff for all bundles Pj in P there exists a good g Pj such that va(Pi) va(Pj \ {g}). Write EP to denote the set of edges that satisfy the EF1 property and Ec P to denote the set of edges that do not, Ec P = ((A \ {n}) {Pi}i) \ EP. In HP, the weight of each edge (a, Pi) that satisfies the EF1 property is set to be va(Pi) and all edges (b, Pj) Ec P are assigned a weight equal to m maxa A\{n} va(G) , where m is the total number of goods. Finally, we will use Hk P to denote the bipartite graph obtained by removing vertex Pk from the graph HP. Note that the partition P is a secretive EF1 allocation (of the subset of goods i Pi G) if and only if, for every possible (choice of the secretive agent) k [n], there exists a perfect matching πk in Hk P that contains only EF1 edges, i.e., satisfies πk EP.9 Here, the choice of edge weights ensures that if there is a perfect matching in Hk P consisting solely of EF1 edges, then any maximum weight matching will also be composed entirely of EF1 edges. Next, we will use these constructs to describe Algorithm 2 and prove its correctness in Theorem 9. A key argument in the proof is an application of Lemma 8 to show that Step 5 of Algorithm 2 always succeeds. In particular, Lemma 8 guarantees the existence of a universally-despised bundle. Lemma 8. Let P = (P1, . . . , Pn) be a partial allocation of the indivisible goods in an instance I = A, G, {va}a A\{n} and let πk be a maximin weight perfect matching in the bipartite graph Hk P, for each k [n]. If the matching πks are composed entirely of EF1 edges (πk EP), then there exists an index (bundle) ρ [n] such that va(Pπk(a)) va(Pρ) for all a A \ {n} and all k [n].

Proof. From the given instance I and partial allocation P = (P1, . . . , Pn), we construct a rent-division instance b I = A, R = [n], {va(r, )}a A\{n},r R in which the ith room corresponds to the ith bundle Pi. The utilities in b I are set to be quasilinear, va(i, z) := Ba i z. Here, Ba i (the base value of room i for agent a) is assigned to the weight of the edge (a, Pi) in the bipartite graph HP. That is, if edge (a, Pi) satisfies the EF1 property then Ba i = va(Pi). Otherwise, if (b, Pj) is not an EF1 edge, then Bb j = m T. An application of Lemma 7 over rent-division instance b I shows that there exists a room ρ [n] such that for all agents a A \ {n} and maximum weight matchings πk we have Ba πk(a) Ba ρ.10

9Here, for ease of presentation, we overload notation and use πk to represent both a bijection and a matching (subset of edges). 10By construction of b I, the bipartite graph Hk considered in

Using the fact that every edge in the matching πk is an EF1 edge, we get Ba πk(a) = va(Pπk(a)) for all agents a A \ {n}. Now, if for an agent a edge (a, Pρ) satisfies the EF1 property then Ba ρ = va(Pρ) and we get the desired inequality va(Pπk(a)) va(Pρ). Otherwise, if edge (a, Pρ) is not an EF1 edge, then there must exist a bundle Pj such that for all g Pj the inequality va(Pρ) < va(Pj \{g }) holds. Again, using the fact that (a, Pπk(a)) is an EF1 edge, we get that there exists g Pj for which va(Pπk(a)) va(Pj \ { g}). Hence, the desired inequality va(Pπk(a)) va(Pρ) holds in all cases.

Algorithm 2 Computation of Secretive EF1 Allocations Input: Instance I = A, G, {va}a A\{n} with a secretive agent, m indivisible goods along with nonnegative and monotone valuations va : 2[m] R+ for a A \ {n} Output: An allocation (P1, . . . , Pn) and n bijections {πk}k [n] that provide a secretive EF1 solution

1: Initialize t 0 and set P t a = for 1 a n, i.e., partial allocation P0 = ( , . . . , ). 2: while G = do 3: For partial allocation Pt = (P t 1, . . . , P t n), construct the bipartite graph HPt 4: For each k [n], set πk to be a maximum weight perfect matching in the graph Hk Pt 5: Find a bundle P t ρ such that for all k [n] and all a A \ {n} we have va(P t πk(a)) va(P t ρ) {We will prove that such a universally-despised bundle always exists and can be found efficiently} 6: Select an arbitrary good g G and set P t+1 ρ = P t ρ {g}. For all i [n] \ {ρ} set P t+1 i = P t i . Update t t + 1 and G G \ {g}. 7: end while 8: return Partition P t = (P t 1, P t 2, ..., P t n) and the n bijections {πk}k [n]

Theorem 9. Let I = A, G, {va}a A\{n} be a fair division instance with indivisible goods, G, and a secretive agent. If the valuations {va}a A\{n} are nonnegative and monotone (increasing), then a secretive EF1 allocation P = (P1, P2, . . . , Pn) for I is guaranteed to exist and can be computed in polynomial time.

Proof. We will use an inductive argument to establish the correctness of Algorithm 2. Write Pt to denote the partial allocation considered by Algorithm 2 in the tth iteration of the while-loop. We will show that the maximum weight matching matchings computed by algorithm during any iteration t, say πks, satisfy πk EPt, i.e., in all iterations, the computed matchings are composed entirely of EF1 edges. In conjunction, we will prove that there exits a bundle P t ρ such

Lemma 7 is identical to Hk P. Hence, we can apply the lemma to πks, the maximum wight perfect matchings of Hk Ps.

that the inequality va(P t πk(a)) va(P t ρ) holds for all agents a A \ {n} and all matchings πk. Both of these conditions hold when t = 0, since P 0 i = for all i [n]. This gives us the base case for induction. Now, say via the induction hypothesis that the conditions hold for the (t 1)th iteration. In particular, if bπks are the maximum weight matchings considered in the (t 1)th iteration, then we have bπk EPt 1 and va(P t 1 bπk(a)) va(P t 1 bρ ) for some room bρ.

By construction, P t bρ = P t 1 bρ {g} and P t i = P t 1 i for all i = bρ. Note that, even after this update, the edges in matchings bπks continue to satisfy the EF1 property: if (a, P t 1 i ) is an edge in bπk (i.e., i = bπk(a)), then va(P t 1 i ) va(P t 1 bρ ). Therefore, va(P t i ) va(P t bρ \ {g}). Since no other bundle receives a good, the ith bundle satisfies the EF1 property for a in the new partial allocation Pt = (P t 1, . . . , P t n) as well. This implies that there exists a perfect matching in the bipartite graph Hk Pt (specifically, bπk) which is entirely composed on EF1 edges. The weight of all the edges in Ec Pt is low (negative) enough to ensure that if Hk Pt admits a perfect matching composed entirely of EF1 edges, then a maximum weight matching, πk, in Hk Pt will satisfy πk EPt. Furthermore, Lemma 8 (applied to Pt) implies that there exists a bundle P t ρ which satisfies the desired inequalities va(P t πk(a)) va(P t ρ). This concludes the inductive argument and shows that Step 5 will necessarily succeed in finding bundle P t ρ. Also, note that with matchings πks in hand, an exhaustive search can be performed to efficiently find P t ρ. Hence, the algorithm runs in polynomial time. Finally, note that if P is the final partition and πks are the corresponding (returned) matchings, then we know that πks are composed entirely of EF1 (with respect to bundles in P) edges. Therefore, P is a secretive EF1 allocation and the claim follows.

5 Conclusion

This paper addresses a setup wherein soliciting valuations from a specific (secretive) agent is prohibited and shows that, even with such a constraint, fairness can be achieved in terms of various solution concepts. Extending this work to encompass multiple secretive agents and, in general, addressing other partial-information settings remains an interesting direction of future work.11 In the context of maximin fairness, it would be relevant to improve the approximation guarantees or establish a separation with respect to achievable approximation bounds between the secretive and the standard setting. Acknowledgment. Siddharth Barman was supported by a Ramanujan Fellowship (SERB - SB/S2/RJN-128/2015).

11Note that, in the presence of multiple secretive agents, to obtain meaningful results one must assume that the secretive agents do not compete for the same good after a division is proposed.

Alkan, A.; Demange, G.; and Gale, D. 1991. Fair allocation of indivisible goods and criteria of justice. Econometrica: Journal of the Econometric Society 1023 1039. Aragones, E. 1995. A derivation of the money rawlsian solution. Social Choice and Welfare 12(3):267 276. Asada, M.; Frick, F.; Pisharody, V.; Polevy, M.; Stoner, D.; Tsang, L. H.; and Wellner, Z. 2018. Fair division and generalizations of sperner-and kkm-type results. SIAM Journal on Discrete Mathematics 32(1):591 610. Bouveret, S., and Lemaˆıtre, M. 2016. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems 30(2):259 290. Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D. 2016. Handbook of computational social choice. Cambridge University Press. Budish, E.; Cachon, G. P.; Kessler, J. B.; and Othman, A. 2016. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research 65(2):314 336. Budish, E. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119(6):1061 1103. Foley, D. K. 1967. Resource allocation and the public sector. Yale Economic Essays. Frick, F.; Houston-Edwards, K.; and Meunier, F. 2017. Achieving rental harmony with a secretive roommate. ar Xiv preprint ar Xiv:1702.07325. Gal, Y. K.; Mash, M.; Procaccia, A. D.; and Zick, Y. 2017. Which is the fairest (rent division) of them all? J. ACM 64(6). Klijn, F. 2000. An algorithm for envy-free allocations in an economy with indivisible objects and money. Social Choice and Welfare 17(2):201 215. Knaster, B.; Kuratowski, C.; and Mazurkiewicz, S. 1929. Ein beweis des fixpunktsatzes f ur n-dimensionale simplexe. Fundamenta Mathematicae 14(1):132 137. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on Electronic commerce, 125 131. ACM. Moulin, H. 1986. Game theory for the social sciences. NYU press. Procaccia, A. D., and Wang, J. 2014. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of the fifteenth ACM conference on Economics and computation, 675 692. ACM. Rothe, J., et al. 2015. Economics and computation. An Introduction to Algorithmic Game. Stromquist, W. 1980. How to cut a cake fairly. The American Mathematical Monthly 87(8):640 644.

Su, F. E. 1999. Rental harmony: Sperner s lemma in fair division. The American mathematical monthly 106(10):930 942. Svensson, L.-G. 1983. Large indivisibles: an analysis with respect to price equilibrium and fairness. Econometrica: Journal of the Econometric Society 939 954. Varian, H. R. 1974. Equity, envy, and efficiency. Journal of economic theory 9(1):63 91.