Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
37,749 characters · 15 sections · 38 citation commands
Scalable Fair Division for `At Most One' Preferences
Many important practical problems involve distributing a finite set of items across a set of individuals in a `good' way. While the exact definition of `good' is hotly debated, typically there are several desiderata: the allocation should be efficient in some way, should be fair in some way, and should have good incentive properties for the individuals brams1996fair,roth2015gets,brandt2016handbook,milgrom2004putting. In this paper we study allocation in an environment where preferences are additive, individuals want at most one of any given item, monetary transfers are not possible, and lotteries are allowed. Examples of such assignment problems in practice are course assignment at universities budish2012multi, pilot-to-plane assignment for airlines, dividing up estates goldman2014spliddit, and recommender systems for scarce goods. We show that when instances are large and `low rank' we can construct a strategy-proof mechanism that generates Pareto Optimal and envy-free allocations. This mechanism requires only solving a convex program (potentially via gradient methods) so it is scalable to extremely large assignment problems.
All item assignment mechanisms must trade off between total utility attained and various measures of fairness of the division. One distributionally fair allocation is the one which maximizes the product of the utilities (or the sum of the log utilities). This is called max Nash welfare (MNW nash1953two,binmore1986nash). MNW has many other nice properties leading researchers to refer to MNW as an `unreasonably fair' allocation method caragiannis2016unreasonable. MNW is employed at spliddit.org which allows individuals to fairly split items such as estates goldman2014spliddit.
Another popular assignment method is competitive equilibrium from equal incomes (CEEI varian1974efficiency,budish2011combinatorial). In CEEI individuals are given a budget of faux currency and prices for items are computed such that the total demand for each item (given the budgets) equals the supply. Because CEEI is based on a market equilibrium, we know that CEEI allocations will be Pareto efficient (nobody can be made better off without making someone worse off), envy-free (nobody prefers anyone else's allocation), and strategy-proof in the large (when individuals report their preferences to the CEEI mechanism, they have no incentive to lie). Due to these attractive properties CEEI is employed in the CourseMatch system which is used to assign course slots to individuals at universities budish2016course. A downside of the CEEI mechanism is that solving for market equilibrium with general preferences is extremely difficult and even in relatively small instances the CourseMatch system needs to “use heuristic search that solves billions of Mixed-Integer Programs to output an approximate competitive equilibrium.” budish2016course. Indeed, computation of approximate CEEI in general is known to be PPAD hard othman2016complexity.
A surprising coincidence occurs when items are divisible and preferences are additive. Here the MNW solution can be found by solving a convex optimization problem and the MNW allocations happens to coincide with a CEEI allocation eisenberg1959consensus. This program is often called the Eisenberg-Gale (EG) convex program. This means that MNW solutions inherit the desirable properties above, and also that a CEEI can be computed extremely efficiently.
However, even if there is no complementarity between items the linear allocation rule is restrictive. For example, in the case of course allocation we do not want to assign an individual $5.6$ seats in a course. Thus, in this paper we consider the problem of at most one (AMO) preferences. We assume that preferences for items are additive but that individuals do not desire more than one of an item.\footnote{For ease of notation we consider individuals only wanting at most one of each item, but most of our results carry over to the case where `buyer capacity constraints' hold across items - for example there may be $10$ different brands of vacuum cleaners which individuals may value differently, however still want at most $K$ vacuum cleaners total. In the Appendix we describe this in more detail but keep the AMO constraint in the main text for ease of exposition.} We also assume that lotteries are allowed and so item allocations are now real numbers between $0$ and $1.$
Our main theoretical contribution is to show that when the underlying valuations have a low-rank structure and the instance is large the convex program corresponding to AMO-MNW maximization also yields an allocation which is an approximate CEEI. This can be interpreted either as saying that large scale AMO-MNW has the good properties of CEEI or that approximate large scale linear-AMO-CEEI can be computed in polynomial time.
We then investigate whether good properties of large scale, low-rank AMO-MNW hold in real datasets. We consider two markets, one for course allocation at Harvard Business School budish2012multi and one using a recommender system harper2016movielens. We show that in these markets AMO-MNW produces good solutions at a great speedup over standard CEEI implementations. Finally, we investigate incentive properties of AMO-MNW by using Bayesian Optimization to search for profitable deviations from truthful revelation. We find that in AMO-MNW deviations are fairly difficult to find and even when found produce only marginal improvements over truthful revelations.
There is a large literature on computing market equilibria in Fisher markets using convex programming eisenberg1959consensus,shmyrev2009algorithm,cole2017convex or gradient-based methods birnbaum2011distributed,nesterov2018computation. There is also work extending the EG program to new settings such as quasi-linear utilities and indivisible items cole2017convex,cole2018approximating,caragiannis2016unreasonable. Our paper complements this existing work as we extend the EG program to the case of AMO preferences and show that when markets are large and low rank this again continues to construct a market equilibrium allocation.
An important real world usage of multi-item allocation is online advertising where ad slots are assigned to individuals via an auction mechanism. This problem is known to be hard in large multi-unit, multi-bidder cases especially with budgets borgs2005multi. It is also known that there is an equivalence between paced dynamic auctions and the equilibria resulting from solving the EG problem conitzer2019pacing. Our paper shows that EG equilibrium can be used as a flexible tool for such allocation problems with AMO preferences. Note that our results here are for the `fake money' setting but they can be extended to the case where money is real (aka. quasi-linear settings) easily cole2017convex.
We consider the setting of $N$ individuals with generic element $i$ and $M$ items with generic element $j$. Each item has a finite supply $s_j$ with $s_{max}$ being the maximum supply of an item. Individual $i$ has utility $v_{ij}$ for item $j$. We let $x$ denote an $N \times M$ matrix which we call the allocation of items to individuals with $x_i$ denoting a vector of how much of each item individual $i$ receives.
The main question is what is a good $x$ to use. One answer given by the literature is to maximize the product of utilities - equivalently, the sum of the log utilities. This is known as the max Nash welfare (MNW) solution. It is the solution to the following constrained optimization problem:
\[ \max_{x\geq 0} \sum_{i} \text{log} (u_i(x_i)) \text{ s.t. } \forall j \sum_{i} x_{ij} \leq s_j \]
When items are divisible and utilities are linear (i.e. when $u_i(x_i) = x_i v_{i} = \sum_{j} x_{ij} v_{ij}$) the problem above is a convex program known as the Eisenberg-Gale (EG) convex program and can be solved efficiently eisenberg1959consensus.
Surprisingly, the EG program has an economic interpretation. Starting with the setup above we can consider the case where each individual is given a budget of $1$ unit of faux-currency. Each item is assigned a price $p_j$ and given these prices we define:
A deep connection between the convex program above and the concept of market equilibrium comes from the following equivalence. Solve the convex program and let $x^{EG}$ be the solution. Let $\lambda^{EG}$ be the $M$ Lagrange multipliers at the optimum (one per item). It can be shown that $(x^{EG}, \lambda^{EG})$ form a market equilibrium.
This connection tells us a lot about properties of the EG solution. We know that any CEEI is envy-free (no individual prefers another's bundle to their own), is Pareto Optimal (nobody can be made better without someone else being made worse off). In addition, market equilibrium can be used as an allocative mechanism - individuals are asked to report their valuations, an equilibrium is computed, and the resulting allocation is enacted. This mechanism is incentive compatible in the large - i.e. when markets get large, no individual has an incentive to lie about their true preferences.
The simple EG solution above is not applicable to many real world problems. This is for two reasons, first, many real world goods are indivisible. However, a fractional allocation can always be thought of as a lottery and resolved at the end of the mechanism. A bigger issue is that in many real world applications such as course allocation, recommender systems, or advertising slots the individuals do not want more than $1$ of any single item. We refer to this as the at most one (AMO) setting.
We can rewrite our slate constrained problem (which we refer to as the AMO Eisenberg-Gale or AMO-EG) as:
\[ \max_{x \geq 0} \sum_{i} \text{log} (x_i v_i) \text{ s.t. } \forall j \sum_{i} x_{ij} \leq s_j \text{ and } x_{ij} \leq 1 \]
Unfortunately, the solution to the AMO-EG program no longer has the nice properties of the original EG (although given that it is a maximization problem the resulting allocation remains Pareto optimal).
To see this, consider the example of $2$ individuals and $2$ items. There is supply $2$ of item $1$ and supply $1$ of item $2$. Both value item $1$ at $1$, individual $1$ values item $2$ at $1$ and individual $2$ values it at $100.$ In the AMO-EG solution here both individuals get $1$ of item $1$ due to the constraint and split item $2$. However, individual $2$ receives more of item $2$ than individual $1$, thus individual $1$ must envy individual $2$. Since the solution exhibits envy, it cannot be a CEEI solution.\footnote{Thanks to Nisarg Shah for providing this example.}
To see where the original EG and CEEI equivalence breaks down, notice that unlike the standard EG problem, the AMO-EG problem now has constraints both at the item level ($M$ supply constraints which we refer to as $\lambda^{AMO}$) and the buyer-item level ($N \times M$ AMO constraints). Due to the presence of buyer-item specific multipliers the $M$ supply-Lagrange multipliers at the optimum may no longer be thought of as prices supporting the solution $x^{AMO}$.
However, we now give a condition for when they approximately support $x^{AMO}$ as an equilibrium allocation.
We show that when every buyer has a sufficiently-large set of “twins” then they receive approximate demands in AMO-EG. Note that in the AMO setting buyers must take into account the AMO constraint when computing demands.
The Theorem here is written that for any $\delta$ there exists an $\epsilon.$ In fact, we can derive a much stronger result: given an instantiation of individuals, items, valuations, supplies, and budgets, we can explicitly bound how $\delta$-approximate of a CEEI the AMO-EG solution is by considering the largest $\epsilon$ such that each individual has an $\epsilon$ twin. This bound is quite complex and requires the introduction of a lot of notation, thus we relegate it to the Appendix. In addition, this bound lets us derive a weaker, but harder to interpret condition for $\delta$-approximate CEEI which implies the one in Theorem (ref) above. We provide a more general theorem which implies Theorem (ref) in the Appendix.
Here we give a sketch of the intuition for Theorem (ref). First, recall that the Lagrange multipliers of a convex program measure the shadow value of locally relaxing a constraint. Consider a group of $s_{max} + 1$ exact twins with identical valuation functions. In any allocation the AMO constraints for some item $j$ bind for at most $s_{max}$ of them. However, the last twin, by assumption, is unconstrained. This means that for that item $j$ the AMO Lagrange multipliers are $0$ at $x^{AMO}$ since the last twin is unconstrained and all twins contribute equally to the convex program's objective. It can then be shown, just as in the standard EG program, that the remaining non-zero Lagrange multipliers (the $M$ supply constraints) can again be thought of as prices. Looking at approximate instead of exact twins is slightly more complex but follows a related logic.
Approximate CEEI is attractive because it approximately retains the nice properties of CEEI. When receiving an item in their demand, a given individual $i$ has no envy (since they can afford any bundle received by some other individual) and receives their proportional share (since prices sum to less than $N$). It follows that in $\delta$-approximate CEEI every individual has at most $\delta$ envy, and receives all but $\delta$ of their proportional share.
We now ask: under what generating process for a large market is the approximate twin condition satisfied?
We propose a simple market generating process that is a model of many real world markets. We look at low rank markets where every individual $i$ has a latent vector $\theta_i$ drawn from some set $\Theta$ which is a compact subset of $\mathbb{R}^d_+$. Every item has a vector $\psi$ from some set $\Psi$ which is also some compact subset of $\mathbb{R}^d_+$ with $d$ fixed. The supply of each item is some constant $s>1$. The valuation of an individual is $v_{ij} = \theta_i \cdot \psi_j$. This states that item valuations are not independent and valuation of one item can be at least partially predicted from valuations of other items. This is true in most real world recommendation settings and is exploited in most recommender systems.
Consider growing a low rank market by drawing $N$ individuals from some continuous distribution on $\Theta$ and drawing $kN$ items from $\Psi.$
Thus, in large, low-rank markets AMO-EG is a convex program that finds an approximate CEEI.
Low rank markets are a natural model under which our approximate-twin conditions are satisfies. However, there are also many other market models one could construct where these same conditions hold. A commonly used example is replicator markets, where we start with some finite base economy, and the market grows by replicating the set of individuals and items. Here every individual gets $k$ exact twins, where $k$ is the number of market replicates. Assuming that the AMO constraint is local to each market replicate this immediately implies the condition of Theorem (ref).
An important part of any mechanism is individuals reporting their valuations. If reporting truthfully yields a higher utility than lying a mechanism is known as strategy proof. While CEEI is not strategy proof in general, it is known that it becomes strategy proof in the large (SP-L).
We now extend some known results azevedo2018strategy,peysakhovich2019fair to our setting to show that AMO-EG is SP-L in low rank markets. Note that the low rank model differs from the results in azevedo2018strategy as it assumes an infinite number of outcomes (since allocations are continuous). It also differs from the related SP-L results in peysakhovich2019fair as it assumes a growing number of items.
We consider the definition of SP-L introduced by azevedo2018strategy and used in peysakhovich2019fair. Let $\sigma$ be a mapping (not necessarily truthful) from valuations to reports. Suppose that $\sigma$ has full range (i.e. for any report, there is a type that gives that report with some probability). Consider an individual $i$ who can either report their true valuations $v_i$ or some other valuation $v'_i$ with everyone else reporting according to $\sigma$. Consider $i$'s expected utility with the expectation taken relative to the $n-1$ other individuals behaving according to $\sigma$ with their true types drawn from $\mathcal{F}$.
In the prior section we have shown results for AMO-EG. We have done this for ease of exposition and because the at-most-one constraint seems reasonable for many practical applications. Importantly, however, our result generalize to a more general market model. In the Appendix we prove the EG, market equilibrium equivalence for a more general model where items are partitioned into item-sets and individuals want at most one item from each item set (for example, in the case of household items there may be multiple vacuum cleaner brands but individuals may still only want one vacuum cleaner). The more general model also allows arbitrary budgets. AMO is a special case where each item set includes just a single item, and CEEI is a special case where all budgets are $1$. For the paper, we stick to the simpler AMO model as it is easier to discuss and gain intuition about.
We consider two datasets of allocation preferences. First, we use a synthetic market from a recommender system as used in kroer2019computing,peysakhovich2019fair. To construct this market we take the MovieLens1M dataset in which 6000 users rate subsets of 4000 movies. We use the same procedure/hyperparamters from kroer2019computing to construct estimates for unobserved user/movie pairs. We then take the top 200 users with the most ratings and the top 1000 movies with the most ratings and construct markets from this subset. We consider a growing set of markets by taking $\lbrace 50, 100, 200, 500, 1000 \rbrace$ items and holding the number of buyers fixed. We set the sum of supplies to be in $\lbrace 500, 1000, 2000 \rbrace.$ This procedure gives us 15 nested markets that grow as the conditions of Theorem (ref) suggest.
We also consider an allocation dataset from course allocation at Harvard Business school budish2012multi. In this dataset there are $936$ students and $93$ courses with fixed supplies. Students rank their top $30$ courses. To transform these ranks into utilities we assume that a rank $r$ course gives utility $\frac{31-r}{30}$ and courses that receive no ranking have utility $0$ (recall that MNW is invariant to the scale of individual utilities so normalizing the top ranked course to have utility $1$ has no effect on our computation). Note that this dataset is not like the limit markets considered in Theorem (ref) as it has many buyers and relatively few items.
We now turn to evaluating AMO-EG in our data. We solve for the equilibrium using a commercial convex programming solver that supports maximizing logarithmic utilities (MOSEK 9 dahl2019primal), though at larger scales (e.g. millions) we would need to use a first-order method. We refer the reader to kroer2019computing for specialized techniques for solving extremely large scale EG problems which are directly generalizable to our AMO-EG setting.
As a first cut, we will compare the EG solution to the AMO-EG solution. In particular, we will see how often the standard EG violates the AMO constraint. If EG solutions do not violate the AMO constraint then AMO-EG is trivially a market equilibrium and indeed can be used out of the box without our modifications. However, figure (ref) shows us this is not the case in any of our datasets. We count both the number of individuals that receive more than one of an item (number of violators) and the amount of items they receive conditional on receiving more than one (violation size).
The naive EG solution allocates almost every buyer in the MovieLens markets more than one of an item and often large multiples. In the course data (right panel) we see that EG allocates some individuals as many as 19 seats in a course. Thus, naive EG ignoring the AMO constraints yields poor solutions for AMO preferences and thus the AMO-EG program is needed.
One advantage of the AMO-EG procedure is that it is a result of a convex optimization problem. An approximate version of CEEI (aCEEI) is used in practice to match individuals to courses at leading business schools - the algorithm used for this task is known as CourseMatch (see \url{https://mba-inside.wharton.upenn.edu/course-match/} for a student-facing tutorial of the mechanism).
The algorithm underlying it is described in budish2016course. budish2011combinatorial uses the same course data we do and describes the performance of the aCEEI algorithm as: “the othman2010finding computational procedure can solve problems ... 50 courses and schedules...in around 20 minutes in Matlab on a standard workstation. It can solve problems the size of a full year at HBS, in which there are roughly 100 courses and schedules....in around 11 hours in a more sophisticated computing environment.” By contrast the AMO-EG solution on a full year of HBS data can be computed using an industrial grade solver (MOSEK) on a commodity laptop in approximately 15 seconds.\footnote{Of course, aCEEI allows for more general preferences over bundles than our simple additive ones. However existing benchmarks for aCEEI such as budish2011combinatorial already make the assumption that “(A1) preferences are additively-separable; and (A2) students care about the average rank of the courses they receive”, moreover the same author reports that “preliminary exploration of preferences more complex than average-rank suggest that all of the reported results are robust” so actually the linearity assumption is both commonly used and not as serious as it may seem.}
In order to make the allocation space well behaved, AMO-EG uses continuous allocations. Since we use AMO preferences, these can be thought of as lotteries over pure allocations. An important question is whether this convexification leads to very random allocations (many $x_{ij} \in (0,1)$) or whether the resulting allocations are mostly pure. We plot these for all of our markets in Figure (ref) and see that AMO-EG allocations are mostly pure in practice.
We now ask whether the AMO-EG has good properties. We start by considering envy and regret.
First, we define envy for the AMO-EG solution. Let $x^{AMO}$ be the AMO-EG allocation. We compute the envy of individual $i$ as $$\max_{i' \in N} v_i (x^{AMO}_{i'} - x^{AMO}_i).$$ Our measure of envy will be this averaged across all individuals. Equilibria are envy-free (and indeed envy-freeness is an important reason why CEEI is a compelling mechanism) so this is one measure of finite sample performance.
Recall that the EG convex program yielded an equilibrium by using the Lagrange multipliers for the supply constraints at the optimum as the prices that supported its allocation. AMO-EG also has Lagrange multipliers for these constraints (in addition to extra multipliers for each of the AMO constraints). We now ask whether the supply-constraint Lagrange multipliers can be interpreted as equilibrium prices. We refer to these at the optimum as $p^{AMO}.$ We will take $p^{AMO}$ and for each individual compute their demand $D_i (p^{AMO})$. Recall that the demand may be a set but that all possible allocations in the demand must yield the same utility level. We refer to this as $\bar{u}_i (p^{AMO})$. We will compute the normalized regret of an individual $i$ facing these prices:
\[ \text{PriceRegret}_i (x^{AMO}, p^{AMO}) = \dfrac{\bar{u} (p^{AMO} - v_i x^{AMO}_i)}{\bar{u}(p^{AMO})}. \]
If an individual $i$'s regret is $0$, it means that $x^{AMO}_i \in D_i (p^{AMO}).$ Note that this is an upper bound on regret, there may exist prices which have lower expected regret for the AMO allocation.
We find that AMO-EG has basically no envy in any of the markets we study (Figure (ref)). By contrast we see that the Price Regret of AMO-EG goes away as markets grow in the fashion required by our theory. How important price regret is from a practical point of view is an open question since even in the CEEI mechanism the currency and prices are `fake'. Nevertheless, it is one possible measure of how close AMO-EG is to a market equilibrium and perhaps useful in a hybrid mechanism where the mechanism only sets prices and individuals are allowed to buy items as they wish.
Finally, an important practical reason for the use of CEEI is that it is incentive compatible. However, this property is only guaranteed as the market becomes large. We ask how incentive compatible AMO-EG is in our datasets. In particular, we will ask how much individuals can gain by misreporting their preferences given the fixed valuations of all other individuals. We will compare this to the ability of individuals to deviate in the EG using the same valuation matrix without the AMO constraints.
Ideally, we would like to solve the following problem for each individual. Let $(v'_{i}, v_{-i})$ denote a vector of reports for individual $i$ $(v'_i)$ and for everyone else $(v_{-i})$. Let $x^{AMO} (v'_{i}, v_{-i})$ denote the AMO-EG allocation from these reports. Suppose each individual $i$ has true valuation $v_i$. We would like to measure how much they can gain from reporting non-truthfully. However, computing this quantity is difficult in practice since it requires computing the optimal deviation.
Since we are not guaranteed convexity of the deviation function, we need to perform a global search. The simplest solution is to discretize the type space and construct a grid-search. However, in high dimensions this quickly becomes intractable. An alternative is to use Bayesian Optimization (BO) techniques which allow for sample efficient exploration of a parameter space shahriari2015taking.
Standard BO works as follows: given a space $\Theta$ of possible parameters, we want to maximize a function $f(\theta)$. We sample $K$ points $\theta$ from $\Theta$ and fit a Gaussian Process (GP) model to the observed values $f(\theta).$ GPs give a posterior mean and uncertainty associated with any point $\theta$ in parameter space, so we can use the model uncertainty to search for an optimal next point to sample. We sample this next point, update the model and repeat. A full description of the details involved in each of the steps above is beyond this paper and a large literature addresses many common usecases. For the purposes of this paper we use an open source BO optimization platform deployed at industrial scale (e.g. at facebook) called Adaptive Experiment (Ax, bakshyae). Ax is a high level abstraction for BoTorch (\url{https://github.com/pytorch/botorch}) which is itself an extension of the deep learning framework PyTorch paszke2017automatic. We use the standard Ax's service API to construct the optimization procedure as detailed in the Ax tutorial here: \url{https://ax.dev/}. We use 50 trials per run with 3 random restarts per person.
Unfortunately, even with the sample efficient exploration strategy given by BO, our parameter space is intractably large (a valuation for each item). We reduce the parameter space by exploiting the fact that in our data valuations for items are correlated and thus the full valuation matrix can be approximated by a lower rank matrix quite well. The valuation matrix $V$ can be well approximated by the matrix product $V \sim B K^t$ where $B$ is an $N \times d$ matrix of vectors for individuals and $K$ is an $M \times d$ matrix of vectors for items so $v_{ij}$ can be well approximated by $b_i k_j.$ We consider deviations by individuals only across these principal directions of variation that are fixed by the matrix $K.$
We allow deviations where individuals choose $b_i$ from a compact subset of $\mathbb{R}^d$ which then gives us a full deviation vector of the form $v'_{ij} = v_{ij} + b_i \cdot k_j.$ Here choosing $0^d$ corresponds to truth telling. We refer to these as low-rank deviations.
If $d < M$ then we have reduced the size of the parameter space that we need to search. In practice we will use $d=10.$ We justify the focus on low rank deviations by the fact that in many large scale systems (e.g. recommender systems, online advertising) it is infeasible to report a full vector of valuations. In practice such systems have missing valuations which are filled in by assuming a low rank structure and using matrix completion. Since an individual $i$ is small relative to the market changing their report won't change the found latent space so indeed they can only deviate in the low rank space.
Even with these heavy restrictions, the optimization process is quite computationally expensive as it requires solving for the AMO-EG/EG equilibrium at each time step. We consider three instances: the `worst case' MovieLens marker (200 buyers, 50 items, total supply 2000), the `best case' MovieLens market (200 buyers, 1000 items, total supply 2000) and the HBS course market.
In each replicate we sample an individual from the market, hold the others fixed, and use BO as described above to try to find a low rank deviation which increases that individual's utility. We repeat this for $49$ individuals from each market. We see that finding low rank deviations (LRDs) is quite difficult (Table (ref)) - only about $5$ to $20 \%$ of the time does BO find any deviation from truthtelling and even when it does the gains are no more than $5$ percent of the baseline utility.
This analysis provides no guarantee that bigger deviations do not exist. Indeed, perhaps profitable deviations exist in the cut off parts of the spectrum or perhaps BO is not a good optimizing technique to find them. We also tried using standard zeroth order methods provided with SciPy jones2001scipy. We found these to perform even worse both with initialization at truthtelling and with random restarts. In addition, we tried looking for low rank deviations in a different mechanism: one which inputs valuations and outputs the social efficiency (sum of utilities) maximizing allocation. Here there is an obvious profitable deviation - report high values for all items and receive all of them. We found that in this setting BO easily found optimal low rank deviations. Developing better methods for computing the incentive compatibility of a particular instance is an important topic for future work.
The multi-unit assignment problem is heavily studied both in theory and in practice. We have shown that a convex program can be used to efficiently apply the CEEI mechanism in the case of linear, at-most-one preferences with divisible goods (or lotteries). This is a natural preference class for many real world allocation problems and our results allow CEEI to scale to very large assignment tasks.
Many open questions remain: can we incorporate substitutes and complements into the CEEI mechanism in a tractable way? What other preference classes allow for simple scalable solutions to the CEEI problem? How can we take advantage of the special structure of the EG convex program to solve it more efficiently for large low-rank markets?