Efficient Resource Allocation with Secretive Agents

1 Introduction

We study a resource allocation problem in which divisible goods must be allocated to agents with linear additive valuations. 1 Treating goods as divisible captures cases where they are inherently divisible (such as land or food), and where they are indivisible (such as jewelry or artwork) but can be allocated randomly or timeshared. Formally, an allocation is a matrix x, where xi,j ∈ [0, 1] is the fraction of resource j given to agent i and ∑i xi,j = 1 for all j. The preferences of agent i are given by a valuation function vi such that her utility from allocation x is vi(xi) = ∑j vi(j) · xi,j .

A classic solution is to allocate the resources in a way that maximizes some social welfare function, which maps the utilities of the agents to a single aggregate measure of allocation quality. Common examples include the utilitarian welfare ( 1n ∑i vi(xi)), the Nash welfare ((∏i vi(xi))1/n ), and the egalitarian welfare (mini vi(xi)), where n is the number of agents. In fact, these are members of the broader class of p-mean welfare functions, given by ( 1n ∑i vi(xi)p )1/p , with p = 1, p → 0, and p → -∞ respectively.

When we have complete information about the valuation function of each agent, finding an allocation that maximizes social welfare is conceptually trivial (algorithmically, however, some welfare functions may be challenging to maximize [Lee, 2017; Garg et al., 2021; Bez´akov´a and Dani, 2005; Asadpour and Saberi, 2010]). But when we have only partial information, it is less clear what outcomes are prescribed by the social welfare maximization paradigm. One approach in the literature is to consider the distortion, which is the worst-case approximation ratio of the maximum social welfare that could be achieved with full information to the social welfare achieved by the allocation rule given partial information. Distortion can be viewed as the "price" of missing information, and minimizing distortion provably reduces the (worst-case) impact that the missing information has on the solution quality. Distortion was originally defined by Procaccia and Rosenschein [2006] in the context of voting, where it has led to an extensive literature of follow-up work; we point the reader to the recent survey by Anshelevich et al. [2021] for a summary. The approach has since been applied to other settings including matching [Amanatidis et al., 2021; Ma et al., 2021; Anshelevich and Zhu, 2021] and resource allocation [Halpern and Shah, 2021].

1 We discuss allocation of indivisible goods in the full version: https://www.cs.toronto.edu/∼nisarg/papers/secretive.pdf

Traditionally, the distortion framework has been applied when every agent reports ordinal preferences [Boutilier et al., 2015; Anshelevich et al., 2018; Halpern and Shah, 2021]. In this paper, we introduce and study a different model, in which some agents provide complete cardinal valuation functions while others provide no information. We term the latter agents secretive agents. In practice, agents may be secretive because they do not want to disclose their valuations for privacy reasons, or because they are simply unresponsive to requests for information. For example, on a popular resource allocation website Spliddit.org, more than 10% of the goods division instances did not succeed because at least one user did not submit their valuation function. 2 Prior work in resource allocation has considered secretive agents [Asada et al., 2018; Frick et al., 2019; Ch`eze, 2019; Arunachaleswaran et al., 2019], but these focus on guaranteeing certain fairness properties in the presence of secretive agents, not on welfare maximization or distortion. Further, unlike in our work, none of them allow more than a single agent to be secretive because guaranteeing the fairness properties they seek becomes trivially impossible in this case.

In the presence of one or more secretive agents, it is not a priori clear what a "good" allocation looks like. On the one hand, if we assign any good to a secretive agent, she might turn out to have very low value for that good, resulting in the good effectively being wasted. On the other hand, if we allocate nothing to the secretive agents, we run the risk of facing high distortion due to instances where the secretive agents are the key to achieving high welfare. How do we balance these considerations? Should we allocate any resources to the secretive agents? If so, how do we determine how much of a resource should be allocated to the secretive agents? We answer these questions by identifying worst-case optimal allocation rules, which turn out to be surprisingly simple.

2 For chore division instances, it was even higher at over 32%.

1.1 Our Results

Let n be the number of agents, k of whom are secretive. We present our results for divisible goods in the main body and defer the treatment of indivisible goods to the full version. For divisible goods, we provide a complete picture of the exact distortion for all p-mean social welfare functions. We introduce a family of allocation rules parameterized by α ∈ [0, 1] and show that all our upper bounds can be achieved by setting the right value of α as a function of p, n, and k. Given α, the corresponding rule allocates α fractions of all the goods to the non-secretive agents in such a way to maximize their social welfare and splits the remaining 1 - α fraction of each good equally among the secretive agents. In each case, we can obtain an exactly matching lower bound. A summary of our results is presented in Table 1 and Figure 1 shows how the distortion varies with p, n, and k.

The distortion naturally increases as the number of secretive agents k increases; for every p, the distortion starts at 1 when k = 0 (full information) and increases to n at k = n (no information). Interestingly, for p = 1 (the utilitarian welfare), p → 0 (the Nash welfare), and p → -∞ (the egalitarian welfare), the distortion already becomes n at k = n - 1, meaning that knowing the valuation function of a single agent is not helpful for these welfare functions, but this is not the case for intermediate values of p. When k = Θ(n), the distortion is Θ(n) for p ⩽ 1 and Θ(n)1/p for p > 1. When k ≪ n, it is worth noting that the distortion for the Nash welfare is ≈ 1 + k lnn/n, which grows linearly in k like for the utilitarian and egalitarian welfare, but at a lower rate. More generally, the Nash welfare leads to a surprisingly low distortion; see Figure 1.

Finally, we conduct simulations on synthetic data and real data from Spliddit.org to evaluate the empirical performance of our algorithms with respect to the utilitarian social welfare. While every α ∈ [1/(k+1), 1] is optimal in the worst case, we find that higher values of α perform better empirically.

1.2 RelatedWork

In the voting literature, the idea of distortion has been analyzed under two primary frameworks, distinguished by what they assume the underlying expressive preference format to be: the utilitarian framework assumes that voters have utilities for candidates [Boutilier et al., 2015; Caragiannis et al., 2017; Benad`e et al., 2017], while the metric framework assumes that voters have costs for candidates satisfying the triangle inequality [Anshelevich et al., 2018; Gkatzelis et al., 2020]. Following Halpern and Shah [2021], our work follows the utilitarian framework as it is more applicable to allocating goods.

Halpern and Shah [2021], like us, assume that agents have additive cardinal valuations, but they study the case where every agent reports a ranking of her t most favorite goods. They analyze the best possible distortion with respect to the utilitarian social welfare as a function of t in relation to the number of goods m. In particular, when every agent ranks all the goods (i.e., t = m), they show that the best possible distortion (with a randomized rule) is n, which is what one can achieve with no preference information whatsoever. That is, they argue that having access to ordinal preference information is not helpful for welfare maximization. In contrast, our distortion bound is better when k ⩽ n-2, i.e., even when we have access to the valuation functions of just two agents. In a sense, this shows the usefulness of eliciting cardinal preferences as opposed to ordinal preferences in resource allocation settings.

Finally, we note that the idea of secretive agents is also explored in the voting literature, albeit with very different motivations. Borodin et al. [2019, Lemma 4] show that constant metric distortion can be achieved in elections where any subset of voters that is at least a constant fraction of the electorate participate and submit ordinal preferences; such a strong guarantee is known to be impossible to achieve in the utilitarian framework, but may be possible if the participating subset of voters is assumed to be drawn at random. Micha and Shah [2020] study voting rules which have access to the votes of only a subset of voters, but instead of analyzing the distortion, their aim is to predict what popular voting rules would have returned given all the votes. One of their primary motivations is to design voting rules to apply to polls in order to predict the outcome of an upcoming election.

2 Preliminaries

A resource allocation instance (N,M, v) consists of a set of n agents N, a set of m goods M, and a utility profile v = (v1, . . . , vn), where vi : M → R⩾0 is the valuation function of agent i. We normalize the valuations of each agent i to sum up to one, i.e., ∑j∈M vi(j) = 1. This unit-sum normalization is widely used in welfare maximization [Aziz, 2020]. 3

Allocations. An allocation is a division of the goods among the agents, denoted by x = (x1, . . . , xn), where xi,j is the fraction of good j allocated to agent i and each good j is fully allocated (i.e., ∑i∈N xi,j = 1 for each j). We consider the class of linear additive utilities, where the utility of agent i for her share xi is, with slight abuse of notation, defined as vi(xi) = ∑j∈M vi(j) · xi,j.

Welfare functions. A welfare function W aggregates the utilities to the agents under an allocation x into a single nonnegative real number measuring the efficiency of the allocation. Following Barman et al. [2020a], we consider the following class of welfare functions.

Definition 1 (p-Mean Welfare). For p ∈ R, the p-mean welfare of allocation x is defined as

This class contains three popular welfare functions:

• Choosing p = 1 induces the utilitarian welfare, given by UW(x) = (1/n) · ∑i∈N vi(xi),
• The limit p → 0 induces the Nash welfare, given by NW(x) = (∏i∈N vi(xi))1/n ,
• The limit p → -∞ induces the egalitarian welfare, given by EW(x) = mini∈N vi(xi).

It is known that p-mean welfare functions are characterized by five natural axioms [Moulin, 2003, pp. 66-69], and further imposing the Pigou-Dalton principle induces p ⩽ 1. It is interesting that our result for the warm-up case of k = n also differs depending on whether p ⩽ 1 or p > 1 (see Section 3.1).

2.1 Secretive Agents &Distortion

In our setting, we assume that we have no information about the valuation functions of k agents, whom we term secretive agents, while we have complete information on the valuation functions of the remaining agents, whom we term nonsecretive agents. Our goal is to find an allocation that minimizes the worst-case multiplicative loss of efficiency measured by a p-mean welfare function.

More formally, let Nsec and Nnonsec denote the sets of secretive and non-secretive agents, respectively. An instance of resource allocation with secretive agents (N,M, vnonsec) consists of a set N of agent, a set Mof items, and a valuation function vi for each non-secretive agent (the valuation functions implicitly define the sets Nsec and Nnonsec). We aim to find an optimal strategy for the following game:

3 Our results for the Nash welfare hold independently of any normalization. However, for every other p-mean welfare function, the optimal distortion is k + 1 in the absence of any normalization.

1. The adversary chooses the valuation functions of the non-secretive agents, denoted by vnonsec = (vi)i∈Nnonsec .
2. The player chooses an allocation x of the goods to all agents (secretive and non-secretive).
3. The adversary chooses the valuation functions of the secretive agents, denoted by vsec = (vi)i∈Nsec , as well as an allocation x∗ .
4. The player incurs the (multiplicative) loss W(x∗ )/W(x).

This game is formalized via the notion of distortion.

Definition 2 (Distortion with Secretive Agents). Given the number of agents n, the number of secretive agents k, and a welfare function W, the distortion is defined as

Note that the distortion is always at least 1 as the adversary can always return the same allocation as the player returns, i.e., x∗ = x.

A strategy for the player corresponds to an allocation rule that maps instances to allocations. Because we express distortion values that depend on n and m (that is, we are typically interested in varying vnonsec), we suppress the dependence on N and M and simply write A(vnonsec) to denote the output of allocation rule A on instance (N,M, vnonsec).

Definition 3 (Distortion of an Allocation Rule). Given n agents, k secretive agents, and a welfare function W, the distortion of an allocation rule A is defined as

If DWn,k (A) = DWn,k then we refer to A as an optimal strategy for the player.

3 Distortion Values

In this section, we present allocation rules that provide provable guarantees on the distortion with respect to p-mean welfare functions.

3.1 Warm-up: k = 0 and k = n

First, let us consider two extreme cases where k = 0 and k = n which provide us some intuition for the general case.

Case k = 0. If there are no secretive agents, then we have full information of the utilities and we can return the allocation that maximizes the welfare for all agents. The adversary cannot obtain a welfare higher than us, therefore, the distortion value is 1. As N = Nnonsec in this case, we may say our strategy was maximizing the welfare for the non-secretive agents. Denote this strategy by

.

Case k = n. Suppose all agents are secretive and we do not have any information from their utilities. To assist with intuition, assume p ⩽ 1. Our best response would be to return a uniform allocation, i.e. allocate 1/n of each item to each (secretive) agent. Intuitively speaking, this follows from the concavity of Mp for p ⩽ 1. If we act differently, the adversary can use the asymmetry in our allocation to incur a higher distortion (details provided in the full version). Denote this strategy by

Regardless of the utilities, for all agents we have vi(x) = 1/n. Hence, the welfare obtained is 1/n. The adversary cannot achieve mean welfare of more than 1. Thus, we get an upper bound of DWn,k=n ⩽ n. In the full version, we also show a matching lower bound.

Lemma 1. For all p-mean welfare functions with p ∈ (-∞, 1] (including NW and UW) and EW, the distortion with n secretive agents is DWn,n = n.

The analysis presented does not hold for p > 1. By the convexity of Mp when p > 1, our best response is to allocate all items to one agent. Then, only one agent will have a utility of 1 while others get 0 utility. Therefore, ( 1n ∑i∈N vi(x)p )1/p = (1/n)1/p leading to an upper bound of DMp n,n ⩽ 1 n-1/p = n1/p .

Lemma 2. For all p-mean welfare functions with p ∈ (1, ∞), the distortion is DWn,n = n1/p .

3.2 Results for 1 ⩽ k ⩽ n-1

In general, our strategy for the general case is to mix the two strategies described for the extreme cases of k ∈ {0, n}. That is, our allocation rule is one from the following class of allocation rules,

where we allocate α ∈ [0, 1] portion of each item according to the OPTnonsec rule, and the rest uniformly among the secretive agents. The proper choice of α however, depends on the chosen welfare function.

We begin with a lemma that provides an upper bound on the adversary's welfare. Throughout this paper, we often use β = ∑i∈Nnonsec vi(OPTnonsec(vnonsec))p to refer to the unnormalized welfare (i.e., the p-th power of the p-mean welfare) that the non-secretive agents receive under OPTnonsec.

Lemma 3. For any valuations of the non-secretive agents vnonsec and p ∈ R, it holds that

where β = ∑i∈Nnonsec vi(OPTnonsec(vnonsec))p . That is, the welfare achieved by the adversary is at most k + 1 times higher than the welfare achieved by the allocation rule A1/(k+1) .

Proof. Let ui denote the utility achieved by non-secretive agent i under OPTnonsec. Note that each secretive agent receives utility at most 1 due to the unit-sum normalization. Hence,

.

On the other hand, note that the utility vector under A1/(k+1) (vnonsec) is ( u1 k+1 , . . . , un-k k+1 , 1 k+1 , . . . , 1 k+1 ) because 1 k+1 fraction of each item is allocated according to OPTnonsec and 1 k+1 fraction of each item is allocated to each of k secre-

Lemma 3 immediately implies the following Corollary. Corollary 1. For all p-mean welfare functions W, the allocation rule A1/(k+1) has distortion DWn,k (A1/(k+1) ) ⩽ k + 1 for all n ⩾ k ⩾ 0.

It turns out that the upper bound of k+1 is only tight for the egalitarian and utilitarian welfare functions. For other values of p, we can achieve lower distortion by tailoring our strategy to the particular welfare function. The next two lemmas contain common parts to the analysis that we will use to prove our guarantees.

Lemma 4. Consider a resource allocation instance with secretive agents. For all α ∈ [0, 1] and any p-mean welfare Mp we have

Proof. By Lemma 3, the welfare achieved by the adversary is upper bounded by Mp(x∗ ) ⩽ ( 1n (β + k))1/p . Next, using the allocation rule Aα, the player achieves a welfare of

Lemma 4 immediately implies that

Lemma 5. Let fp(β, α) be as defined in (3). Then, for a fixed α ⩾ 1 k+1 , fp is non-increasing over β ⩾ 1.

Proof. As fp(β, α) ⩾ 1 and since log preserves monotonicity, it is sufficient to show d dβ log fp(β, α) ⩽ 0 for all β ⩾ 1.

By α ⩾ 1 k+1 , we have 1-α αk ⩽ 1. Then, we can check this expression is non-positive both for p > 0 and p < 0.

As fp is non-increasing, to obtain an upper bound on the distortion, we need a lower bound on β. This value, as well as the proper choice of α, depends on p. In the rest of this section, we will find the proper choices for α and β based on the welfare function. We begin with p ∈ (-∞, 0).

Taking the limit as p → 0 and p → -∞ in Theorem 1 suggests upper bounds of n( 1 n-k ) n-k n and k+1 for the Nash and egalitarian welfare respectively. For the egalitarian welfare, we have already shown an upper bound of k + 1 in Corollary 1, and the following lemma proves that this upper bound is achievable for the Nash welfare.

Theorem 2. For the Nash welfare, the allocation rule A(n-k)/n achieves DNW n,k (Aα) ⩽ n ( 1 n-k ) n-k n .

Now, we will focus on the range p ∈ (0, 1].

Proof. The requirement of Lemma 5 is met, as for k < n, (n - k)(k + 1) ⩾ n ⇒ n-k n ⩾ 1 k+1 .

By Lemma 4, distortion is bounded by (3), and by Lemma 5, this bound is maximized when β is minimized. For any given vnonsec, one suboptimal allocation is Uniformnonsec. Each agent gets vi = 1 n-k utility from this rule. Hence, β ⩾ (n-k)( 1 n-k )p = (n - k)1-p .

By substituting β and α in (3), we have

Note that for p = 1, Theorem 3 implies an upper bound of k + 1 for the utilitarian welfare, matching the upper bound from Corollary 1. Moreover, by taking the limit p → 0 in Theorem 3, we get the same upper bound proven in Theorem 2.

In fact, for the case of utilitarian welfare, a range of strategies all yield a distortion of k + 1.

Proposition 1. For the utilitarian welfare and for all α ∈ [ 1 k+1 , 1], the allocation rule Aα achieves DUW n,k (Aα) ⩽ k + 1.

Proof. By Lemma 4 we have DUW n,k ⩽ maxβ β+k αβ+(1-α) . As the utilitarian welfare in any instance is at least 1, e.g. by giving all items to one agent, by Lemma 5 and setting β = 1 we have DUW n,k ⩽ 1+k α+(1-α) = k + 1.

Lastly, the following theorem treats the case of p > 1.

Theorem 4. For p ∈ (1,∞), the allocation rule A1 achieves DMp n,k (A1) ⩽ (k + 1) 1p .

In the full version, we present matching lower bounds for all of the upper bounds proven in this section.

4 Experiments

In this section, we measure the average-case approximation ratio of utilitarian welfare achieved by different rules based on synthetic and real-world data. In principle, one could conduct a similar analysis with other welfare measures, but we focus on utilitarianism for simplicity and conciseness.

Rules. We compare the following allocation rules motivated by Section 1.1: Uniform (allocate items uniformly to all agents), Aα with α = 1 k+1 , α = n-k n , and α = 1. Recall that A1 returns a utilitarian welfare maximizing allocation for the nonsecretive agents, and all three of the Aα rules tested achieve the optimal distortion for utilitarian welfare.

Measurement. For a resource allocation instance with secretive agents, we measure the ratio between the maximum feasible welfare by full information and the welfare obtained by the rule, averaged over many instances. This provides us with an average-case analogue of the (worst-case) distortion.

4.1 Synthetic Data

Data Generation. We generate utilities for each agent, either secretive or nonsecretive, sampled i.i.d. from a Dirichlet distribution with m concentration parameters all set at 1, i.e. Dir(1, . . . , 1). Each reported datum is the average of welfare ratios over 1000 randomly generated instances.

Experiments. We conduct three experiments each varying a parameter while fixing the others: vary k (Figure 2a), vary n with a fixed k (Figure 2b), vary n with a fixed ratio of k/n (Figure 2c), and vary m (in the full version).

Results. In all four figures we see a consistent relationship between the rules: rules with higher α outperform rules with lower α and all three of the Aα rules outperform Uniform. This is perhaps not surprising, since higher values of α more heavily exploit the information available to the rule from the non-secretive agents, with the Uniform rule being one example of an extreme case that ignores all available information about the utility functions.

In Figure 2a we see all three Aα rules achieve average welfare ratio 1 when k = 0, with the welfare ratio converging to that of Uniform when k = n, as expected. Of particular note is A1, which achieves an average welfare ratio close to 1 even for relatively large values of k (for example, the average welfare ratio is ∼ 1.23 when k = 10) before rapidly increasing for large k. Of note is that all algorithms significantly outperform the worst-case bound of k + 1 displayed with a dotted line in the figure.

Figure 2b reveals an interesting separation when A1 and A(n-k)/n are compared to A1/(k+1) and Uniform. The average welfare ratio of the former rules decreases to 1 as n increases (with k = 5) while the average welfare ratio of the other rules actually increases with n. Figure 2c suggests that this increase persists even when the ratio k/n is held (approximately) constant.

line y = k + 1, i.e. the distortion value.

Figure 3: Average welfare ratio by different strategies on the Spliddit data. The x-axis is sorted by n and then k.

4.2 Spliddit Data

Data Generation. We also used the real-world goods division instances from Spliddit.org. For each instance with n agents and a fixed k, we randomly sampled k (secretive) agents, hid their utilities from the allocation rules and measured the welfare ratio based on the actual utilities. Similar to the simulated experiments, we report the average of 1000 such simulations.

Data Statistics. The report is based on 4679 Spliddit instances. The distribution of the number of agents n is {2 : 27.5%, 3 : 67.3%, 4 : 2.4%, 5 : 1.7%, 6 : 0.4%, and n ⩾ 7 : 0.7%}. The number of goods m was in the range [2, 96] with the mean and std. dev. of 31.1 ± 26.3.

Experiments. We divided instances based on n and varied k from 1 to min(5, n - 1). The average welfare ratio is presented in Figure 3.

Results. In line with the results on synthetic data, we see higher α outperform lower α (and all outperform Uniform). The dependence on n and k also follows similar patterns as the synthetic case. Additionally, it is interesting to note the magnitude of the welfare ratio achieved by our rules. For Spliddit instances with 5 or fewer agents and at least 2 nonsecretive agents (k ⩽ n - 2), the average welfare ratio is never higher than 1.5 for the rule A1. That is, on average, we could achieve two-thirds of the maximum possible utilitarian welfare even if one or two agents do not respond to requests for their utility information.

5 Discussion

We studied distortion in resource allocation when k of the agents are secretive. For the utilitarian welfare, we identified a family of rules parametrized by α ∈ [1/k+1, 1] as worst-case optimal. Among this family, we find the rule with α = 1 to be particularly interesting because it allocates no resources to the secretive agents and thus, unlike α < 1, provides no incentive to an agent to be secretive. This can lead to fewer agents being secretive, which can further reduce distortion.

It is known that maximizing the Nash welfare yields desirable fairness guarantees [Caragiannis et al., 2019; Conitzer et al., 2019]. Fortunately, we find that the Nash welfare is the most approximable among all p-mean welfare functions.

Our work opens the door for interesting directions for future work. It would be interesting to study instance-wise optimal allocations, that is, allocations that minimize the worstcase approximation ratio on a given instance. It is likely that such allocations would more carefully decide which (and how much of) resources to allocate to the secretive agents depending on how highly they are valued by the non-secretive agents.

One may wish to reconcile distortion (welfare maximization) with fairness in the presence of secretive agents. If the goal is to only ensure fairness among the non-secretive agents, one can easily modify the rules proposed in this work by replacing OPTnonsec (the welfare-optimal allocation to the non-secretive agents) by an allocation to the non-secretive agents that maximizes welfare subject to the fairness guarantee. The additional loss in welfare incurred is precisely the price of fairness, which is well understood [Caragiannis et al., 2012; Bertsimas et al., 2011; Bei et al., 2019; Barman et al., 2020b]. 4 However, if the goal is to ensure fairness to all agents, it may be necessary that no more than a single agent is secretive, and even then, achieving fairness alone is already challenging [Arunachaleswaran et al., 2019].

4 For ensuring proportionality to the non-secretive agents, we would need α ⩾ (n - k)/n, which can be set for p ∈ [0, 1] while still using our analysis.

Acknowledgements

Shah was partially supported by an NSERC Discovery Grant.