1 Introduction↩︎

Fair division of indivisible goods has numerous applications, ranging from allocating first-aid supplies during a crisis or donated food to people in need to distributing compute resources or scheduling access to shared laboratory equipment. Over the past two decades, the research community has made significant progress in articulating and formalizing what fairness means in the presence of indivisibilities, as well as how to algorithmically find solutions satisfying these desiderata; see the survey of [1]. The most classic notion of fairness — originating in the literature on fair division of divisible goods — is envy-freeness (EF), which requires that no agent prefer another agent’s bundle to their own.

Exact envy-freeness is often impossible to achieve when items cannot be split¹, and hence, weaker notions or relaxations of EF have been proposed. Among these relaxations, perhaps the most frequently studied one is envy-freeness up to one item (EF1), which requires that any envy an agent may have towards another agent can be eliminated by removing a single item from the other agent’s bundle. It is known that allocations satisfying EF1 can be computed for broad classes of valuations (e.g., general monotone non-negative valuations) by simple and efficient algorithms such as Envy-Cycle Elimination, and by the even simpler Round Robin algorithm (in which agents take turns selecting their most preferred remaining item) when the valuations are additive [2], [3].

These algorithms are expressed in the “standard” algorithmic framework in which the algorithm has full access to the input; here, the input would be numerical utilities or a ranking over all bundles for all players (in the case of general valuations), or the utilities/rankings for individual items (for additive valuations). Some work has also considered models in which the algorithm gets to elicit information from players actively, e.g., by eliciting their valuations over an item or a bundle of items [4]–[6] or by asking them to compare pairs of bundles [7]. Doing so may help decrease the amount of information which agents must communicate about their valuations.

However, in many cases, algorithms must be deployed, and make decisions, without having access to all relevant . In such cases, the algorithm must “learn from its mistakes”, in the sense of treating the allocation task as an online learning problem. As a concrete motivating example, consider the allocation of a resource (such as a lab, robots, or similar equipment) among multiple research groups over the course of a week. Groups may have very idiosyncratic preferences over subsets of allocated time slots, based on contiguity, schedules of specific team members etc. Specifying all of the preferences or utilities ahead of time may be challenging and lead to a combinatorial explosion.

An alternative is for an algorithm to propose an allocation to be used for the following week. At the end of the week, groups may provide feedback if they believe that the allocation was not fair — for instance, if one group received a disproportionate number of desirable slots or if another group was assigned predominantly late-night slots that might be considered less desirable. These reports could then be taken into account in deciding on the next week’s allocation. The goal for such an algorithm would be to converge quickly to an allocation that satisfies desirable fairness properties.

This approach recasts the fair allocation problem in the general framework of online interactive learning, and more specifically into a model akin to the Equivalence Query Model of angluin:queries-concept?. Under the Equivalence Query Model, defined by angluin:queries-concept? for the goal of learning a binary classifer, an online learner repeatedly proposes a candidate binary classifier; unless the classifier happens to be correct, the learner is given a (adversarially chosen) misclassified point. This model was phrased more abstractly and generalized by OnlineLearning?. The abstract form again has the learner proposing a solution, which is either accepted, or results in learning a violated constraint/feature. As such, the framework captures the challenges of “learning on the job”, where information can only be obtained in response to an attempted solution, rather than via targeted queries.

In our Interactive Learning for Fair Division model, in each round, the learning algorithm proposes a (complete) allocation to the agents, i.e., all items must be allocated. Unless the allocation satisfies the fairness criterion, the algorithm receives feedback which it can use to propose different allocations in the future. In keeping with the equivalence query and interactive learning models of angluin:queries-concept?, OnlineLearning?, we assume that the feedback takes the form of one violation of a desirable fairness property. In the prototypical case of EF1 fairness, the violation would be one pair \((i,j)\) of agents such that \(i\) envies \(j\)’s bundle even when any one item is removed. If there are multiple such pairs, the pair that is revealed comes with no guarantees; in order to perform a worst-case analysis, we will therefore treat it as adversarial.

Our primary goal is to understand the information-theoretic and computational complexity of finding a fair allocation under the (adversarial) interactive learning model for fair allocations. That is, how many iterations does an interactive algorithm need until it is guaranteed to find a fair allocation, and what is the time required for the internal computations?

A first natural approach might be to simply give \(i\) an item previously allocated to \(j\) whenever \(i\) envies \(j\) even with any one item removed. In Appendix [sec:local95adjustment], we give a simple example showing that even for additive valuations, such an approach may cycle. Hence, a more sophisticated algorithm is needed.

1.1 Our contributions↩︎

Our first main result addresses the problem whenever the valuations are additive. In this case, we show that even for mixed goods and chores, an EF1 allocation can be found in polynomially many rounds, with polynomial computation. The main idea is the following: the algorithm maintains a polytope of feasible item valuations for all agents, which are valuations \(\mathbf{v}\) consistent with all feedback the algorithm has received in the past. The algorithm then chooses a feasible valuation \(\mathbf{v}\) as a putative valuation and computes an allocation that would be EF1 under \(\mathbf{v}\). If the allocation violated EF1, the EF1 violation feedback gives rise to (at least) one hyperplane separating \(\mathbf{v}\) from the (now updated) polytope of feasible valuations. Thus, the feedback on violated EF1 conditions serves as a separation oracle, and choosing the putative valuation according to the ellipsoid algorithm’s choice means that the guarantees on the ellipsoid algorithm’s convergence transfer to our setting.

This framework can be applied whenever the valuations are captured by polynomially many variables, fairness violations give rise to a separating hyperplane, and there is a polynomial-time algorithm for finding a fair allocation given access to the agents’ valuations. Under these conditions, which include other fairness notions as well as some other settings, our framework yields an interactive learning algorithm for fair allocations in a polynomial number of rounds and using polynomial computation.

In principle, the framework could be applied for general (monotone) valuations; however, the number of variables required to fully encode an agent’s valuation function is \(2^m\) (where \(m\) is the number of items), resulting only in a trivial guarantee on the number of iterations. Instead, we consider a different approach, restricting the class of allocations which the algorithm ever proposes. Specifically, the algorithm fixes an arbitrary ordering over the items, and will only consider allocations in which each agent receives an interval plus at most one additional item; we call such allocations almost-contiguous allocations. As in the work of [5], this restriction only serves to reduce the size of the search space, not because intervals are of intrinsic interest. Our main technical contribution here is to modify the proof of [8] (which showed non-constructively that there always exists an EF2 allocation all of whose bundles are intervals) to show that there is always an almost-contiguous allocation which is EF1.

The algorithm still follows the approach of using the ellipsoid algorithm to obtain putative agent valuations. The fact that the algorithm only uses bundles which are the union of an interval plus at most one more item implies that it suffices to encode each agent’s valuation using polynomially many variables, which in turn yields a polynomial bound on the number of iterations until an EF1 allocation is found. However, in each iteration, the algorithm must find an EF1 almost-contiguous allocation with respect to the putative valuations, and the existence of such an allocation was only established non-constructively. Indeed, we are not aware of a polynomial-time algorithm for finding such an allocation, implying that we cannot bound the computation time by a polynomial. We also consider a modification of the algorithm, which does not use the Ellipsoid algorithm and feasible/putative valuations at all, but simply avoids allocations containing bundle combinations previously exhibited as EF1 violations. We show that while this variant also only requires polynomially many iterations, the computational problem required in the iterations of this modified algorithm is in fact NP-hard.

While our focus is on the interactive learning model, one may naturally wonder how well an algorithm can perform if it receives more or less feedback.

A natural weaker model would be one in which the algorithm only learns that there exists some EF1 violation, but no further information; that is, the algorithm obtains only one bit of information about the proposed allocation. For this model, as we show in Section 6, a number of proposed allocations exponential in the number \(n\) of agents is information-theoretically unavoidable, even for the very restrictive special case of identical binary valuations. Conversely, by considering a carefully parameterized space of allocations, one can exhaustively search over \(m^{O(n)}\) possible allocations, one of which is guaranteed to satisfy EF1; this implies that for a constant number of agents, an EF1 allocation can be found in polynomial time.

At the other extreme is a model in which the algorithm learns all pairs \((i,j)\) such that \(i\) envies \(j\)’s bundle even when any one item is removed.² Note that in the equivalence query model of angluin:queries-concept?, this feedback would correspond to revealing all misclassified items, trivially allowing the learner to infer the correct classifier after one round. While the situation is not quite as trivial for the goal of finding fair allocations, we show in Section 7 that it is fairly easy to simulate the Envy-Cycle Elimination Algorithm with only polynomial blowup in the number of rounds. Thus, one can, in a polynomial number of rounds and with polynomial computation, find an EF1 allocation even when the agents’ valuations are arbitrary monotone functions. This is further evidence that this model gives the algorithm too much information; from a practical perspective, relying on the fact that all agents reveal all of their envy is clearly also risky. We briefly remark that if the algorithm instead of all EF1 violation leans only a single i.i.d. uniformly random EF1 violation, then by proposing the same allocation multiple times, in a number of rounds polynomial in \(n\), the algorithm can with high probability obtain all EF1 violations after all, so this model only results in polynomial blowup compared to the preceding one.

1.2 Related Work↩︎

Our work contributes to the growing literature on fair division of indivisible goods when the preferences of the agents are not known. Multiple works have focused on value queries, in which the algorithm may ask an agent for the value of a specific bundle [4], [5], or partial-ranking feedback, where agents provide coarse ordinal information over items or bundles [9], [10]. [11] recently studied the communication complexity of fair division and quantified how many bits an agent must report in order for a fair allocation to be computed. Other recent works have also considered models based on comparison queries, in which agents compare different items or bundles without revealing exact numerical values [6], [7]. In contrast, our model does not allow targeted queries of any kind. Each interaction consists of proposing a complete allocation, and the only feedback the algorithm receives — when the allocation is not fair — is a witness of violation, such as an EF1 envy pair. Thus, the feedback is substantially more limited than in standard preference-query models: the algorithm cannot isolate a single pair of bundles to compare, cannot request information about a specific agent, and cannot probe the valuation of any sub-bundle. All information must be inferred from counterexamples produced in response to full allocations, placing our framework much closer to mistake-driven and interactive online learning models than to traditional elicitation.

Interactive learning has been studied in multiple settings. To the best of our knowledge, the earliest work formalizing the idea of trial-and-error learning through local mistakes is the seminal work of angluin:queries-concept?, which introduced the Equivalence Query Model. In this model, a learner proposes a binary classifier, and if the classifier is incorrect, the learner is given an adversarially chosen misclassified point. As explained by angluin:colt-survey?, this model is equivalent to the simultaneously proposed and more widely known standard Online Learning model of littlestone:learning?, in which the learner is given one example to classify in each round, and learns whether this example was classified correctly, using the feedback to update its (internal) classifier.

The equivalence query framework was generalized by OnlineLearning?, who studied interactive problems represented as weighted undirected graphs \((V,E)\): the target solution is a node \(s^*\), and whenever the learner proposes a node \(s\), the feedback consists of a neighboring node \(s'\) that is strictly closer to \(s^*\). Prior work by BinarySearch? had shown that a learner can identify \(s^*\) within \(O(\log |V|)\) interactions, directly implying efficient interactive learning algorithms for classification, ranking, and clustering. While the graph-based framework is a powerful abstraction, our interactive fair-division model does not fall into this framework. When an allocation violates EF1, the learner receives only a witness of violation — for example, a pair \((i,j)\) such that agent \(i\) envies agent \(j\). This feedback does not necessarily guide the learner to an allocation that is “closer” to a valid EF1 solution in any graph-theoretic or metric sense.

The interactive learning model has been studied across multiple settings. In clustering, a learner proposes candidate clusterings and receives limited feedback, often in the form of requests to merge or split clusters AdaptiveHierarchical?, balcan:blum:split-merge?, awasthi:zadeh:supervised-clustering?, awasthi:balcan:voevodski:local-algorithm-journal?. In stable matching, interactive feedback identifies blocking pairs; information on these blocking pairs guides the learner toward a stable matching [12], LearningStableMatching?. In ranking, coactive and interactive query models learn a target ranking by allowing the learner to propose an option and having the user return a preferred alternative higher in their ranking [13]. Recent work has also explored interactive learning for computing voting rules, where the learner iteratively proposes outcomes, and agents respond with improvements according to their rankings [14]. Finally, in training large language models, interactive and coactive learning frameworks enable models to refine their outputs through localized human-feedback improvements [15]. To the best of our knowledge, we are the first to introduce an interactive learning framework for fair division.

Somewhat similar ideas to the ones we use are used in the context of multidimensional binary search and its generalizations [16]–[19]. This model is motivated by online problems such as contextual pricing. In the most basic model, there is a product with \(d\) relevant features, and each user’s utility (or willingness to pay) is obtained as a linear combination of these features. The feature vector \(\mathbf{\theta}\) is unknown, and can/must be inferred by interacting with a sequence of agents. Each agent/context \(k\) is characterized by a vector \(\mathbf{x}_k\), and the algorithm can ask a simple query about the inner product \(\mathbf{\theta} \cdot \mathbf{x}_k\), such as asking to compare it to a proposed threshold (which would correspond to observing whether the agent bought the product at the proposed price). Such queries can be construed as revealing separating hyperplanes for the vector \(\mathbf{\theta}\), as in our algorithms. As in our case, the core of the analysis is to show that the remaining feasible region for \(\mathbf{\theta}\) shrinks sufficiently fast in a meaningful way. A key difference is in the level of control. In the work mentioned above, the algorithm can choose the threshold given the context, whereas in our work, the algorithm proposes an allocation, but does not know about the normal of the hyperplane it will observe.

2 Preliminaries and Model Setup↩︎

Let \(N = [n]\) be the set of agents and \(M\) the set of \(m\) indivisible items. Each agent \(i \in N\) has a valuation function \(v_i : 2^{M} \to \mathbb{R}\) assigning a real value to every bundle of items. Without loss of generality, we assume that the valuations satisfy \(v_i(\emptyset) = 0\).

We consider three standard settings:

• Goods setting: \(v_i(S) \ge 0\) for all \(S \subseteq M\), capturing allocations of desirable items such as resources or prizes.

• Chores setting: \(v_i(S) \le 0\) for all \(S \subseteq M\), corresponding to allocations of undesirable tasks or chores.

• Mixed setting: valuations may take both positive and negative values, capturing combinations of goods and chores.

A valuation function is additive if for every bundle \(S \subseteq M\), \(v_i(S) = \sum_{x \in S} v_i(x)\), where \(v_i(x) = v_i(\left\{ x \right\})\) denotes the value of item \(x\) to agent \(i\). A more general class is the class of all monotone valuations. A valuation \(v_i\) (for goods) is monotone if for all \(S,T \subseteq M\) with \(S \subseteq T\), we have \(v_i(S) \le v_i(T)\). An allocation \(A = (A_1,\ldots, A_n)\) assigns each agent \(i \in N\) a bundle \(A_i \subseteq M\) of items such that the bundles form a partition of \(M\), i.e., \(A_i \cap A_j = \emptyset\) for \(i \ne j\), and \(\bigcup_{i=1}^n A_i = M\).

2.1 Fairness Notions↩︎

We are specifically interested in finding fair allocations, and we now define suitable notions of fairness. Classical notions of fairness are defined in terms of agents’ valuations over their assigned bundles. An allocation is envy-free (EF) if no agent prefers another’s bundle to their own, i.e., \(v_i(A_i) \ge v_i(A_j)\) for all \(i,j \in N\). Another standard notion is proportionality (PROP), which requires each agent to receive at least a \(1/n\) fraction of their total value for all items, i.e., \(v_i(A_i) \ge v_i(M)/n\). However, allocations satisfying EF or PROP do not always exist for indivisible items, as can be seen from the simple case of two agents and one item.

To address this issue, [20] introduced envy-freeness up to one good (EF1) as a relaxation of EF, and [21] proposed the analogous notion of proportionality up to one good (PROP1).

More recently, [22] extended both notions to settings involving mixtures of goods and chores, showing that EF1 and PROP1 allocations always exist for additive valuations.

The first condition captures that \(i\) envies \(j\)’s bundle. The second condition states that there is no item \(x\) to remove from \(A_j\) (in the case of goods) that would make \(i\) not envy \(j\) any more, and there is no item \(x\) to remove from \(A_i\) (in the case of chores) that would make \(i\) not envy \(j\) any more. Together, the conditions capture that no single item can be removed from either bundle to make \(i\) not envy \(j\) any more.

This definition mirrors the EF1 definition for the mixed setting. The second and third conditions capture that proportionality cannot be achieved by adding at most one good to agent \(i\)’s bundle or removing at most one chore from it, respectively.

[21] showed that, under additive valuations in the goods setting, every EF1 allocation is also PROP1. For general monotone valuations over goods, however, this implication does not hold. The well-known Envy-Cycle Elimination algorithm of [2] guarantees the existence of EF1 allocations for monotone goods, but allocations satisfying PROP1 may not exist even in very simple instances. Consider two agents and three items, with both agents valuing the entire set at 1 and every strict subset at 0; any allocation violates PROP1. Consequently, most studies of PROP1 focus on additive valuations, while EF1 has been explored more broadly.

[22] further generalized the implication of [21] from goods to mixed settings, proving that every EF1 allocation is also PROP1 under additive valuations.

2.2 Interactive Feedback Models↩︎

We study the problem of finding fair allocations via interactive algorithms that “learn on the job”. Instead of having access to agents’ valuation functions or direct queries, the algorithm can only interact with the environment by proposing an allocation and observing the resulting feedback. Our main focus is on the fairness notions EF1 and PROP1. In each round \(t = 1,2,\ldots\), the algorithm proposes an allocation \(A^{(t)} = (A^{(t)}_1,\ldots,A^{(t)}_n)\). If the proposed allocation satisfies the target fairness notion, the interaction terminates successfully. Otherwise, the algorithm receives feedback indicating that the allocation violates the fairness requirement.

Different feedback models correspond to different levels of information about fairness violations. In particular, when a proposed allocation is not fair, the feedback may reveal information about the specific way in which fairness was violated. At one extreme, the feedback may only indicate whether the allocation satisfies the target fairness notion, without revealing any additional information. At the other extreme, the feedback may reveal all individual violations, e.g., all pairs of agents \(i, j\) such that \(i\) envies \(j\) even after the removal of any one item from \(j\)’s bundle (EF1) or all agents \(i\) such that \(i\) does not receive a proportional share (PROP1). Our focus lies on intermediate models in which the feedback reveals a single violation. To ensure robustness of our algorithms, we assume that whenever such a witness is revealed, it is chosen adversarially. We now formalize such intermediate feedback models for EF1 and PROP1.

For completeness, we also consider the two extreme feedback models for EF1, corresponding to revealing no witness or revealing all violating witnesses.

It is worth noting that a model in which a single violating witness is chosen uniformly at random in each round is comparable to the All-Witness Model. Since there are only polynomially many potential violating pairs for EF1, standard coupon collector arguments imply that repeating the interaction sufficiently many times will reveal all violations with high probability. For this reason, and to ensure robustness to worst-case interaction, we model the single-witness feedback as being chosen adversarially.

Having defined these feedback models, we now turn to the algorithmic questions they give rise to. We study the interaction and computational complexity of finding fair allocations under the above interactive feedback models.

Throughout the paper, each interaction consists of the algorithm proposing an allocation and receiving the corresponding feedback. We measure the algorithm’s interaction complexity by the total number of interactions, equivalently, the total number of allocation proposals it makes. An algorithm is said to use a polynomial number of interactions if this number is bounded by \(\mathrm{poly}(n,m)\). Separately, we measure the algorithm’s computational complexity in the standard sense, counting the total running time required by the algorithm.

For convenience, we refer to interactions under the Single-Witness EF1, Single-Witness PROP1, Membership EF1, and All-Witness EF1 Models as single-witness EF1, single-witness PROP1, membership EF1, and all-witness EF1 interactions, respectively. We will occasionally use the terms “interaction” and “allocation proposal” interchangeably to denote a single interaction between the algorithm and the feedback model. An allocation that is certified by the feedback as satisfying EF1 or PROP1 will be called a certified EF1 or certified PROP1 allocation.

3 Polynomial-Time EF1 in the Single-Witness Model under Additive Valuations↩︎

We start by presenting a polynomial-time algorithm that finds an EF1 allocation under additive valuations in the mixed-items setting with polynomially many single-witness EF1 interactions. The key idea is to have the algorithm guess a putative valuation for each agent that is not in conflict with any feedback received so far. Each witness EF1 feedback can then be interpreted as imposing hyperplane constraints on the corresponding agent’s valuation. These constraints are used to iteratively refine the set of feasible putative valuations through an ellipsoid-based update process until an EF1 allocation is certified.

In Section 4, we will show how this framework extends to other fairness notions, such as proportionality up to one item (PROP1).

3.1 Overview of the Algorithm↩︎

Our algorithm alternates between computing candidate allocations under the current guess of the agents’ valuations and refining these guesses using feedback received. At a high level, the algorithm maintains for each agent \(i\) a putative valuation vector \(\vval[i]\), representing the algorithm’s current estimate of \(i\)’s (unknown) valuation.

In each iteration, the algorithm calls a full-information EF1 subroutine as a black box, which returns an EF1 allocation under the current \(\vval\). In our implementation (Algorithm 1), we instantiate the subroutine with the DoubleRoundRobin algorithm of [22], which runs in polynomial time and guarantees EF1 under additive valuations even for mixed valuations. However, in principle, any full-information EF1 algorithm suitable for the class of valuation functions under consideration can be used.

The allocation computed by the EF1 subroutine is then proposed, and feedback is received in response. If the feedback certifies that the allocation is EF1 under the agents’ valuations, the algorithm terminates. Otherwise, the feedback identifies a violating pair \((i,j)\), and we will show that such a pair always yields a linear constraint separating \(i\)’s true valuation from \(i\)’s current putative valuation. This constraint is then incorporated into the feasible valuation region, and the algorithm uses an ellipsoid-based update to refine its putative valuations, excluding the current (incorrect) estimate and moving closer to the true valuation profile.

This iterative process repeats until an allocation is certified EF1. The key structural insight is that each round either identifies an EF1 allocation or rules out a portion of the valuation space via a valid separating constraint. As a result, the algorithm can exactly be viewed as an execution of the ellipsoid algorithm for Linear Programming with a separation oracle, which is known to terminate in a number of iterations polynomial in the number of variables; the number of variables here equals the number of valuations \(\widehat{v}_i(x)\), i.e., it is \(nm\).

Before proving Theorem 1, we recall the ellipsoid method [23], [24] and explain how the separating constraints derived from the single-witness feedback are used to refine the feasible valuation region and update the putative valuations in Algorithm 1.

3.2 Ellipsoid-Based Valuation Refinement↩︎

The ellipsoid method [23], [24] provides a general polynomial-time procedure for solving linear feasibility problems of the form \[\text{find } \mathbf{x} \in \mathbb{R}^d \text{ such that } A \mathbf{x} \le \mathbf{b},\] given access to a separation oracle. For any candidate point \(\mathbf{\widehat{x}}\), the oracle either confirms that \(\mathbf{\widehat{x}}\) is feasible, or returns a violated inequality \({\mathbf{a}^{\top}_i} \mathbf{\widehat{x}} > {b_i}\), where \(\mathbf{a}_i^\top\) is the \({i}^{\rm th}\) row of the matrix \(A\) and \(b_i\) the corresponding entry of the vector \(\mathbf{b}\), thereby separating \(\mathbf{\widehat{x}}\) from the feasible region.

The ellipsoid algorithm maintains an ellipsoid \(E_t\) that always contains the current feasible region. In each iteration, it queries the oracle at the center of \(E_t\): if the oracle certifies feasibility, the algorithm terminates; otherwise, the returned separating hyperplane cuts off the current center while preserving all feasible points. The next ellipsoid \(E_{t+1}\) is chosen to contain the intersection of \(E_t\) with the feasible halfspace identified by the oracle. Each iteration shrinks the ellipsoid’s volume by a fixed multiplicative factor (depending only on the dimension \(d\)), while ensuring that all feasible points remain inside. After a number of oracle calls polynomial in the dimension \(d\), the method either finds a feasible point (if one exists) or correctly certifies that no feasible solution exists.

3.2.0.1 Ellipsoid updates in our algorithm.

In Algorithm 1, the ellipsoid method is applied separately to the valuation space of each agent. For a fixed agent \(i\), the algorithm maintains a convex feasible region \(\mathcal{R}_i^{(t)} \subseteq \mathbb{R}^m\) consisting of all additive valuations not yet ruled out by previously derived EF1-based constraints. The putative valuation\(\vval[i][(t+1)]\) used by the algorithm is the center of the ellipsoid enclosing \(\mathcal{R}_i^{(t)}\).

When an allocation constructed from all of the \(\vval[i][t]\) is proposed, it is either certified as EF1, or a violating pair \((i,j)\) is returned. Certification corresponds to the separation oracle declaring the current ellipsoid center feasible. A violating pair corresponds to the infeasible case in the ellipsoid framework. In this case, each EF violation implied by the EF1 violation gives rise to a linear constraint. We will show in Section 3.3 that among these constraints, at least one must be new and provides the separating hyperplane required by the ellipsoid method.

After the constraint is obtained, the feasible region is refined according to \[\mathcal{R}_i^{(t)} = \mathcal{R}_i^{(t-1)} \cap \mathcal{C}_i^{(t)},\] where \(\mathcal{C}_i^{(t)}\) denotes the polyhedral region defined by the intersection of the halfspaces corresponding to all linear constraints implied by the feedback received at iteration \(t\). Since the algorithm incorporates all such constraints, including additional (possibly redundant) ones that do not affect correctness, the feasible region can only shrink further. The ellipsoid method then computes a new ellipsoid enclosing \(\mathcal{R}_i^{(t)}\), and its center becomes the next putative valuation\(\vval[i][(t)]\). Consequently, each iteration further refines the valuation estimates.

3.3 Correctness and Complexity↩︎

4 Generalizing the Ellipsoid Framework↩︎

We now show that the ellipsoid-based approach introduced in Section 3 extends beyond envy-freeness and yields a general framework for computing fair allocations from limited interactive feedback. The framework applies whenever a fairness violation, together with the available feedback, can be translated into a separating constraint on the agents’ valuations.

We first illustrate the framework by instantiating it for proportionality up to one item (PROP1) under additive valuations. This example shows that the same algorithmic structure and correctness argument extend beyond EF1. We then abstract the common structure underlying the EF1 and PROP1 instantiations to formulate a general ellipsoid-based fairness framework.

4.1 An Instantiation: PROP1 under Additive Valuations↩︎

To adapt the framework to PROP1, three components may in principle require modification: the allocation subroutine, the form of witness-based feedback, and the rule for identifying new separating constraints in step (b).

However, under additive valuations, EF1 implies PROP1, and hence any subroutine that finds an EF1 allocation under the true valuations also guarantees PROP1. We therefore retain the same DoubleRoundRobin algorithm as the allocation module, and only replace the EF1 witness with its PROP1 counterpart, while updating the constraint construction rule accordingly. The resulting procedure, given as Algorithm 2, differs from Algorithm 1 only in the type of witness feedback and corresponding constraints. Its correctness and polynomial complexity follow by arguments analogous to the EF1 case.

4.2 General Ellipsoid-Based Fairness Framework↩︎

We now abstract the common structure underlying the EF1 and PROP1 instantiations to obtain a general ellipsoid-based framework for interaction-efficient fair allocation under limited feedback. The framework consists of four modular components, each of which can be replaced or adapted to target different fairness notions and valuation classes.

(1) Allocation Subroutine.

Given access to the true valuations from a specified valuation class, this subroutine must output an allocation satisfying the target fairness notion in polynomial time. For EF1 and PROP1 under additive valuations, we instantiate this module with the DoubleRoundRobin algorithm of [22]; the Generalized Envy Graph algorithm proposed in [22] can also serve as an alternative. For PROP1, one may further use the polynomial-time procedure established by [22], which computes a contiguous PROP1 allocation. Here, “contiguous” means that the items are arranged in some arbitrary order, and each agent receives a block of consecutive items in that order. In the setting of identical monotone valuations with goods, an EF1 connected allocation can also be computed via Algorithm 1 of [8], and may be used as an allocation subroutine when contiguity is required.

(2) Feedback Model.

The feedback model specifies the form of feedback received in response to a fairness violation, and thereby determines the information structure available to the algorithm. Our framework applies whenever the feedback provides a witness that enables the algorithm to construct a valid separating constraint. The single-witness EF1 and PROP1 models are examples of such feedback models. More informative models, for instance those that allow direct EF1 interactions between specific agents, also fit naturally into the framework. In contrast, weaker models that merely report that some agent \(i\) violates EF1 without identifying a concrete witness are insufficient, since they do not provide enough information to construct a separating hyperplane between the current and true valuations.

(3) Separation construction rule.

Given the feedback, the algorithm must specify how to translate the witness into one or more linear constraints that separate the current putative valuation from the true valuation. The precise rule depends on the fairness notion and adversary type. In our EF1 and PROP1 instantiations, each fairness violation witness naturally induces a collection of linear inequalities, corresponding to the relevant violated EF1 or PROP1 conditions. These inequalities define a set of halfspace constraints that is consistent with the true valuations. As shown in the correctness analysis, at least one constraint separates the current putative valuation from the true one, thus providing the separating hyperplane required by the ellipsoid method.

(4) Valuation Encoding.

The valuation space must first admit a convex representation so that the ellipsoid update applies. The dimensionality of the ellipsoid then depends on how valuations are encoded. For additive valuations, the representation for each agent’s valuations is \(m\)-dimensional, with one coordinate per item, which leads to a polynomial-time implementation. For richer valuation classes such as monotone valuations, the dimensionality typically increases substantially (for example, to \(2^m\) if each subset is assigned an independent value). In these cases, the ellipsoid method remains conceptually applicable, but the number of iterations is no longer polynomial in the natural parameters \(n\) and \(m\). A somewhat natural restriction of this general model (here considered for goods) would be one in which agents are interested in bundles of at most \(s\) items, for some constant \(s\). Then, \(v_i(A) = \max_{A' \subseteq A: |A'| \leq s} v_i(A')\) for all \(A\) with \(| A | > s\). In this setting, the number of variables is \(O(n m^s)\), and the algorithm can compute the valuation of \(i\) for a bundle \(A\) from the LP variables \(v_i(A')\) (for \(| A' | \leq s\)) in time \(O(m^s)\). Another natural class of models can be obtained when the algorithm only considers a polynomial-sized subset of possible bundles; we will see this in Section 5, where the algorithm chooses an (arbitrary, but fixed) ordering of items, and only allocates agents bundles which are the union of an interval plus at most one additional item; note that there are at most polynomially many such bundles whose valuations must be learned.

Together, these components form a unified ellipsoid-based framework that captures a wide spectrum of fairness notions and feedback structures. Whenever the allocation subroutine and adversary together admit a valid separating rule, the framework achieves convergence in a number of interactions polynomial in the valuation dimension. We further demonstrate in Appendix [sec:efx-charity] that this framework extends naturally to another relaxation of envy-freeness, namely EFX-with-charity.

In the remainder of the paper, we return to EF1 as our primary fairness notion, and focus on refined algorithmic guarantees and structural insights specific to EF1.

5 Polynomial-Interaction EF1 in the Single-Witness Model under Monotone Valuations↩︎

As discussed in the context of valuation encoding in the general framework, the ellipsoid-based approach remains conceptually applicable to monotone valuations. However, when valuations are represented by vectors, a monotone valuation requires an encoding with exponentially many dimensions — one for each subset of the items — which in turn leads to exponentially many ellipsoid iterations and hence exponential interaction complexity. This motivates a fundamentally different approach that avoids reasoning over such high-dimensional valuation representations.

Throughout this section, we restrict attention to the goods setting with monotone valuations. As noted in Section 2, monotonicity is defined in the opposite direction for chores, and the mixed setting does not admit a well-defined notion of monotonicity.

Our strategy is to impose additional structure on the allocations rather than on the valuations. By restricting attention to allocations with simple geometric form, we ensure that EF1 violations can arise only in a controlled number of ways, which in turn allows the algorithm to make progress using only polynomially many single-witness EF1 interactions.

To this end, the algorithm puts the items in an arbitrary but fixed order, and considers only bundles that are “simple” with respect to this ordering. The simplest such bundles are contiguous intervals, i.e., bundles consisting of items that occupy consecutive positions in the chosen ordering. However, while interval EF1 allocations are known to exist in the special case of identical valuations [5], their existence for heterogeneous monotone valuations remains open [8]. To overcome this obstacle, we relax the contiguity requirement. Building on [8], which establishes the existence of interval EF2 allocations under monotone valuations, we show that EF1 can be achieved with a slight relaxation of the interval structure.

Specifically, our first main result establishes that every fair division instance with monotone valuations admits an EF1 allocation in which each agent receives a bundle obtained from an interval plus at most one additional item. We then exploit this structural characterization to design an EF1 algorithm with polynomial interaction complexity under the Single-Witness EF1 Model.

5.1 Existence of Almost-Contiguous EF1 Allocations↩︎

We begin by formalizing the notion of an almost-contiguous allocation. We will frequently reason about intervals of discrete numbers, and use the notation \(\left[L,R\right] = \left\{ j \in \mathbb{Z} \mid L \leq j \leq R \right\}\), with the understanding that \(\left[L,R\right] = \emptyset\) when \(R < L\).

Proof overview. The proof builds on the existential argument of [8], which uses a carefully constructed representation of partial interval allocations together with Sperner’s Lemma to establish the existence of a contiguous EF2 allocation under monotone valuations. We modify their construction to obtain an almost-contiguous EF1 allocation.

5.1.1 Background and proof intuition.↩︎

The idea of allocating contiguous bundles is closely related to the classical problem of cake cutting, which studies fair division of a divisible heterogeneous resource. In this literature, the resource is typically modeled as the interval \([0,1]\), and each agent has their own valuation over measurable subsets. A central goal is to partition the cake into pieces and allocate one piece to each agent such that the resulting allocation is envy-free.

A fundamental result in this area shows that envy-free cake divisions always exist. Specifically, it is known that there always exists an envy-free allocation in which each agent receives a single interval of the cake [25]. A classical approach to proving this result uses Sperner’s Lemma [26]: one considers the space of all interval partitions of the cake, labels them according to agents’ preferences, and applies a Sperner’s Lemma argument to establish the existence of an envy-free division. Within this framework, the positions of the cuts between intervals play a central role. These positions, often referred to as knife positions, parameterize the space of possible allocations.

The indivisible-goods setting introduces additional challenges, as items cannot be split. Building on the ideas underlying the cake-cutting proofs, [8] establish an existence result for indivisible goods with monotone valuations. At a high level, their argument considers a discrete analogue of interval partitions along a fixed ordering of the items. The knife positions are allowed to be either between two items or on an item (covering the item), and the construction allows the boundary items, namely items covered by the knife positions, to remain temporarily unassigned.

By organizing these partial allocations into a lattice and applying Sperner’s lemma, [8] show the existence of a collection of \(n\) “partial allocations” that differ only in the assignment of the boundary items and agree on the assignment of the remaining interval bundles to agents. These partial allocations have the property that there exists a one-to-one matching between agents and these partial allocations (i.e., the entire allocation of bundles to all agents) such that, in the partial allocation assigned to agent \(i\), agent \(i\) is envy-free with respect to their own bundle. A careful assignment of the remaining boundary items then yields a fully contiguous allocation that is EF2.

We build on this framework and modify the argument to obtain EF1, while slightly relaxing the requirement of contiguity.

5.1.2 Knife positions and interval partitions.↩︎

We omit the technical details of the application of Sperner’s lemma in the proof of [8], and instead work directly with the discrete structure that arises from their existence argument.

Fix an arbitrary ordering of the items, which we identify without loss of generality with positions \(1,2,\ldots,m\) along a line. A knife position is a vector \(\boldsymbol{k}=(k^1,\ldots,k^{n-1})\) specifying the locations of \(n{-}1\) cuts between consecutive agents’ bundles. Each coordinate \(k^j\) is chosen from the discrete grid \[\left\{\tfrac12, 1, \tfrac32, \ldots, m, m+\tfrac12\right\}.\] A half-integer value indicates a cut between two consecutive items, whereas an integer value indicates that the cut covers the item at that position.

Given a knife position \(\boldsymbol{k}\), it induces a partial interval partition \(P(\boldsymbol{k})=\left(P(\boldsymbol{k})_1,\ldots,P(\boldsymbol{k})_n\right)\) of the items as follows: \[\begin{align} P(\boldsymbol{k})_1 &= \left[1,\left\lfloor k^1-\tfrac 12 \right \rfloor\right],\\ P(\boldsymbol{k})_j &= \left[\left\lceil k^{j-1}+\tfrac 12 \right\rceil,\left\lfloor k^j-\tfrac 12 \right\rfloor\right] && (2 \le j \le n{-}1),\\ P(\boldsymbol{k})_n &= \left[\left\lceil k^{n-1}+\tfrac 12 \right\rceil,m\right]. \end{align}\] If a coordinate \(k^j\) is integral, the corresponding item is covered by the knife and does not belong to either adjacent bundle. Such items are referred to as boundary items and are treated as temporarily unassigned, as discussed above.

To illustrate the knife construction, consider \(n=4\) agents and \(m=5\) items labeled \(1\)–\(5\) in order, and the knife position \(\boldsymbol{k}=(1,\,2.5,\,4)\). The resulting partial interval partition is summarized in Table 1.

5.1.3 Families of knife positions.↩︎

We now describe the specific family of knife positions that arises in the existence proof of [8].

Fix any valid knife position (i.e., vector) \(\boldsymbol{k}_1\). From this initial position, we define a family \(\boldsymbol{k}_1,\boldsymbol{k}_2,\ldots,\boldsymbol{k}_n\) of knife positions as follows. For each \(i \in \left\{ 1,\ldots,n-1 \right\}\), the position \(\boldsymbol{k}_{i+1}\) is obtained from \(\boldsymbol{k}_i\) by shifting the \({i}^{\rm th}\) knife by a half unit to the right, while leaving all other knives unchanged: \[k_{i+1}^j = \begin{cases} k_i^j + \tfrac12, & \text{if } j=i,\\[2pt] k_i^j, & \text{otherwise.} \end{cases}\]

We illustrate this construction by returning to the example introduced above with \(n=4\) agents and \(m=5\) items, and taking \(\boldsymbol{k}_1=(1,\,2.5,\,4)\). The resulting family of knife positions and the induced partial partitions are shown in Table 2.

We now state the key guarantee for the family of knife positions that is implicit in the existence proof of [8] and will be crucial for our construction.

We refer to \(P\!\left(\mathbf{k}_{\varphi(i)}\right)_{\sigma(i)}\) as agent \(i\)’ s designated bundle. The family of designated bundles \[\left\{ P\!\left(\boldsymbol{k}_{\varphi(i)}\right)_{\sigma(i)} \mid i \in [n] \right\}\] forms a (partial) partition of \(M\); that is, the bundles are pairwise disjoint, but do not necessarily cover all of \(M\).

5.1.4 Basic partition and boundary items.↩︎

Based on these \(n\) knife positions, [8] define the basic bundle of agent \(i\) as the set of items which \(i\) receives under all of the partial allocations, i.e., \[\bp[\sigma(i)] \;= \; \bigcap_{j=1}^n P(\mathbf{k}_j)_{\sigma(i)}.\] The resulting partial partition \(\bp = (\bp[\sigma(1)], \ldots, \bp[\sigma(n)])\) is then referred to as the basic partition. The remaining items are referred to as boundary items because they must lie on the boundary between bundles: \[R \;:=\; M \setminus \bigcup_{i=1}^n \bp[\sigma(i)].\] Equivalently, \(R\) can be characterized directly in terms of the initial knife position \(\boldsymbol{k}_1\) as \[R \;=\; \left\{ k_1^j \mid k_1^j \in \mathbb{Z},\; k_1^j \le m \right\} \;\cup\; \left\{ k_1^j+\tfrac{1}{2} \mid k_1^j \in \tfrac{1}{2}+\mathbb{Z},\; k_1^j+\tfrac{1}{2} \le m \right\}.\]

As an immediate consequence of this alternate characterization, each knife contributes at most one boundary item: it contributes the item it covers if its coordinate is integral, and the item immediately to its right if its coordinate is a half-integer, since this item will eventually be covered in \(\mathbf{k}_n\) by the movement rule of the knives. Hence, \[|R| \;\le\; n-1.\] Moreover, as observed by [8], each boundary item can appear in the bundles of at most one side (either in the bundle immediately to its left or in the bundle immediately to its right) throughout all knife positions \(\mathbf{k}_1,\dots,\mathbf{k}_n\). In particular, no boundary item ever switches sides across different knife configurations.

Example (continued). Continuing the example with \(n=4\) agents, \(m=5\) items, and the knife-position family generated from \(\boldsymbol{k}_1 = (1,\,2.5,\,4)\) as shown above, the resulting basic partition and boundary items are summarized in Table 3.

We now relate the designated bundles identified in Lemma 1 to the basic partition and the boundary items defined above.

5.1.5 Proof of Theorem 3↩︎

We are now ready to prove Theorem 3.

5.2 A Polynomial-Interaction Algorithm via Almost-Contiguous Allocations↩︎

We now return to the ellipsoid-based elimination framework developed in Section 4.2, and show how it can be instantiated to obtain a polynomial-interaction algorithm for EF1 under general monotone valuations. The key new ingredient is to restrict the allocation subroutine to the class of almost-contiguous EF1 allocations introduced in Section 5.1, whose existence is guaranteed by Theorem 3. At a high level, the algorithm proceeds exactly as Algorithm 1. The only differences are the following:

• In step (a), the ellipsoid method maintains a putative valuation profile \(\vval\), as before. Given \(\vval\), the allocation subroutine of DoubleRoundRobin is replaced with the allocation routine described in  5.1, which returns an EF1 allocation that is almost-contiguous.

• Since we now focus on the pure goods setting with monotone valuations, the initialization of the ellipsoid is modified accordingly: the domain of all valuations is now \([0,1]\).

  Moreover, while monotone valuations are fully characterized only by the agents’ valuations for every subset of items, we exploit the fact that the allocation subroutine only ever produces almost-contiguous allocations. Consequently, it suffices to maintain value variables only foralmost-contiguous bundles. Since there are (at most) \(m \cdot (m+1)m/2\) such almost-contiguous bundles (i.e., \(m\) choices for the extra item and \((m+1)m/2\) contiguous intervals defined by their two endpoints), the initial ellipsoid is taken to be the hypercube \([0,1]^{m \cdot (m+1)m/2}\).

Note that Theorem 4 only bounds the number of proposed allocations which the algorithm makes before it finds an EF1 allocation with respect to the true valuations. It does not bound the running time of the algorithm’s internal computation.

From a computational perspective, restricting attention to almost-contiguous allocations circumvents the primary obstacle in the monotone setting, namely the exponential-size valuation encoding. In particular, when attention is restricted to almost-contiguous bundles, the dimension of the valuation representation becomes polynomial in \(m\). Nevertheless, this restriction introduces a different computational challenge. When we additionally require the allocation to be almost-contiguous, computing an EF1 allocation becomes a nontrivial task. Recall that the existence proof for Theorem 3 was non-constructive, and relied on Sperner’s Lemma. The proof gives rise to a search procedure, by considering all starting knife positions \(\mathbf{k}_1\) and their corresponding sequences of knife positions and allocations. However, this search would take exponential time. Whether almost-contiguous EF1 allocations can be found in polynomial time remains open, paralleling an open question of [8]: whether interval EF2 allocations can be found in polynomial time. Indeed, given the nature of the existence proof, it is quite conceivable that the search problem could be PPAD-complete.

Motivated by this observation, one could try to eliminate the ellipsoid method altogether and instead directly keep track of “blacklisted” almost-contiguous EF1 allocations, only proposing allocations which have not been blacklisted. However, this shift comes at a different cost. As we show in Appendix [sec:direct-almost-contiguous] using a reduction from Independent Set, by directly focusing on interval-based allocations, we replace a computational subproblem whose complexity is open with a problem that is NP-complete in general.

6 The Membership EF1 Model↩︎

In contrast to the Single-Witness Model, where the adversary provides witnesses of fairness violations, the Membership Model reveals only a single bit of feedback indicating whether the proposed allocation satisfies the target fairness notion. This minimal feedback severely limits the learner’s information gain per proposed allocation.

In this section, we establish that for EF1 even under the extremely restricted class of identical additive binary valuations, any algorithm operating in the Membership Model must make exponentially many allocation proposals in the number of agents \(n\). We also present positive results demonstrating that when the number of agents \(n\) is fixed, EF1 can still be achieved with a polynomial number of membership interactions.

6.1 Exponential Interaction Lower Bound↩︎

Recall that in the additive setting, each valuation satisfies \(v_i(S) = \sum_{x \in S} v_i(x)\) for all \(S \subseteq M\). In this subsection, we focus on the highly restricted class of identical binary additive valuations, where \(v_i(x) = v(x) \in \left\{ 0,1 \right\}\) for every agent \(i\) and item \(x\).

We show that the Membership Model still requires exponentially many allocation proposals in \(\min(m-n,n)\) in order to find an EF1 allocation. In particular, when \(m \ge 2n\), the required number of allocation proposals is exponential in \(n\). Our lower bound holds for any \(m>n\). (The case \(m\le n\) is trivial, as assigning each agent (at most) one distinct good yields an EF1 allocation.)

Our proof uses the probabilistic method. In the Membership Model, every proposed allocation receives the same yes-or-no type of response, so a deterministic algorithm inevitably commits to a fixed sequence of proposed allocations until an EF1 allocation is found. If the algorithm tries fewer than exponentially many allocation proposals, we show that there exists a binary additive valuation for which none of these proposed allocations is EF1. Hence, no deterministic procedure can succeed with fewer proposed allocations. By standard arguments, the same conclusion extends to randomized algorithms as well, implying that exponential interaction complexity is unavoidable in the Membership Model.

Much of the tedious technical work is encapsulated by the following lemma, which captures that without loss of generality, an allocation maximizing the probability of being EF1 contains no empty bundles, and as few singleton bundles as possible. The proof of this lemma is given in Section 6.1.1.

The following technical lemma will be used to upper-bound the probability that a single allocation is EF1 under identical binary valuations. The proof of this lemma is given in Appendix [sec:binom-two-point].

6.1.1 Proof of Lemma 3↩︎

6.2 Algorithms for a Constant Number of Agents↩︎

Theorem 5 shows that under the Membership Model — unless the number of items is very small — the number of iterations required to guarantee an EF1 allocation is exponential in the number of agents \(n\). Here, we show that an exponential dependence is indeed required only for \(n\); when \(n\) is treated as a constant, then even under the Membership Model, an EF1 allocation can be found in time polynomial in the number of items \(m\). This holds very generally, namely, under general monotone valuation functions.

The bound given in Theorem 6 was optimized for simplicity instead of tightness. For example, from the proof of Theorem 3, we know that the added items must be at interval boundaries, reducing the search space. Furthermore, the search space can be reduced if additional assumptions are made on the agents’ valuation functions. In particular, when the agents have identical monotone valuations, instead of using Theorem 3, we can use Lemma 5.3 of [5], which guarantees the existence of an EF1 allocation all of whose bundles are intervals. Enumerating all cut positions induces all contiguous allocations, and since the valuations are identical, the bundle-agent assignments are immaterial. Thus, proposing one allocation per cut position suffices, yielding an \(O(m^n)\) interaction and time bound.

7 The All-Witness EF1 Model: Algorithms via Envy-Cycle Elimination↩︎

We now turn to the most informative feedback model for EF1, which we call the All-Witness EF1 Model. In this model, upon proposing an allocation \(A\), the algorithm learns the complete set of agent pairs \((i,j)\) for which agent \(i\) envies agent \(j\)’s bundle even after the removal of any single item, i.e., all pairs \(i,j\) with \(A_i \prec_i^{\mathrm{EF1}} A_j\).

Such rich feedback substantially simplifies the problem. While the classical Envy-Cycle Elimination Algorithm cannot be applied directly, we show that it can be simulated with only minor modifications in the All-Witness Model. This yields a polynomial-interaction and polynomial-time procedure for finding an EF1 allocation under arbitrary monotone valuations.

7.1 Algorithmic Overview↩︎

We begin by briefly recalling the classical Envy-Cycle Elimination Algorithm [2], which incrementally constructs an EF1 allocation by maintaining a partial allocation and repeatedly eliminating cycles in the induced envy graph. While this approach is well-suited to the full-information setting, it does not immediately apply to our interactive model with all-witness EF1 feedback.

There are two main obstacles. First, envy-cycle elimination operates on partial allocations, whereas in our model, the algorithm must propose a complete allocation in every round. Second, the algorithm relies on access to the full envy graph, i.e., access to every envy-free violation, while the feedback we obtain consists only of EF1 violations, which is strictly weaker information.

We address these two issues separately. To overcome the first obstacle, our algorithm designates the three agents \(1,2,3\) to serve as buffers which temporarily hold items outside the target partial allocation. For each partial allocation proposed by the Envy-Cycle Elimination Algorithm, our algorithm proposes three allocations. In the first proposal, all such remaining items are assigned to agent \(1\) (in addition to items which agent 1 might be allocated in the partial allocation); this reveals all EF1 violations between pairs \((i,j)\) with \(i,j \neq 1\). In the second proposal, the remaining items are instead assigned to agent \(2\), which reveals all violations between pairs of agents \(i,j \neq 2\). Finally, assigning the remaining items to agent \(3\) reveals all EF1 violations between agents \(i,j \neq 3\). Together, these three proposals allow the algorithm to recover all EF1 violations among the agents under the target partial allocation. This construction requires the presence of at least three agents. When there are only \(n=2\) agents, we have shown in Section 6.2 how to obtain an algorithm with polynomial complexity even in the Membership Model. In Appendix [sec:two-agent-case], we show how to straightforwardly adapt ideas of [5] to improve the number of iterations, and find an EF1 allocation in \(O(\log m)\) iterations.

To overcome the second obstacle, we show that EF1 feedback suffices to infer a (possibly incomplete) directed envy graph over the agents in the partial allocation. We then prove that applying envy-cycle elimination to this partial graph and assigning the next item to an agent with in-degree zero in the resulting graph preserves the EF1 property of the partial allocation. Repeating this process allows the algorithm to simulate envy-cycle elimination until a complete EF1 allocation is obtained.

7.2 The Algorithm for Three or More Agents↩︎

We now present the details of the algorithm for the All-Witness EF1 Model in instances with \(n \ge 3\) agents and monotone valuation functions.

The algorithm proceeds in rounds, allocating one item per round, in the spirit of the classical envy-cycle elimination procedure. Throughout the process, it maintains the invariant that the current partial allocation is EF1.

We fix an arbitrary ordering of the items. Let \(\tilde{A}^{(t)} = (\tilde{A}^{(t)}_1,\ldots,\tilde{A}^{(t)}_n)\) denote the partial allocation maintained by the algorithm after round \(t\), where \(\tilde{A}^{(t)}_i \subseteq [m]\) is the bundle currently assigned to agent \(i\). Initially, no items are allocated, and the empty allocation \(\tilde{A}^{(0)}\) trivially satisfies EF1. Suppose that after some round the algorithm has constructed an EF1 partial allocation \(\tilde{A}^{(t-1)}\), and consider the next item \(t\) to be allocated.

The algorithm tentatively assigns this item to agents one by one. For each tentative assignment, it uses all-witness EF1 feedback together with the buffer-agent construction to test whether the resulting partial allocation remains EF1. If assigning the item to some agent preserves EF1, the algorithm fixes this assignment and proceeds to the next round.

If none of the tentative assignments preserves EF1, the algorithm exploits the information revealed by these failed attempts. Specifically, the EF1 violations induced by adding the new item allow the algorithm to infer a set of directed envy relations that is consistent with the envy relations under the previous-round allocation \(\tilde{A}^{(t-1)}\). We write \(E_{\mathrm{envy}}\) for the resulting set of directed pairs and \(G_{\mathrm{envy}} = (N, E_{\mathrm{envy}})\) for the induced directed graph. Intuitively, since \(\tilde{A}^{(t-1)}\) was EF1 and all tentative assignments fail after the addition of item \(t\), each agent must be involved in some observed EF1 violation, implying that every agent has at least one incoming envy relation in \(G_{\mathrm{envy}}\) and thus that \(G_{\mathrm{envy}}\) contains a directed cycle.

When \(G_{\mathrm{envy}}\) contains a directed cycle \(i_1 \to i_2 \to \cdots \to i_k \to i_1\), the algorithm performs a single cycle-rotation step: each agent \(i_\ell\) on the cycle receives the bundle \(\tilde{A}^{(t-1)}_{i_{\ell+1}}\), where indices are taken modulo \(k\). All bundles outside the cycle remain unchanged. This operation updates the partial allocation while preserving the multiset of bundles, and enables the algorithm to restore progress when no tentative assignment of the current item preserves EF1.

Using this procedure, the algorithm identifies an agent to whom the current item can be assigned without violating EF1, restores the invariant, and advances to the next round. Repeating this process for all items yields a complete EF1 allocation.

The algorithm is formally given as Algorithm 3.

8 Conclusion and Open Problems↩︎

We defined an interactive model in which an algorithm must repeatedly propose allocations, and receives feedback either indicating that the proposed allocation is fair, or providing a specific fairness violation. We have shown that under this model, for additive valuations, an algorithm can find an EF1 or PROP1 allocation in polynomial time. When the valuations are merely monotone, an algorithm can still find an EF1 allocation in a polynomial number of interactions, but the internal computations are currently not polynomial-time.

This naturally raises the question whether an EF1 almost-contiguous allocation — whose existence we showed non-constructively — can be found efficiently given explicit access to each agent’s valuation of each almost-interval bundle. The question parallels a question of [8]: they proved non-constructively that an interval EF2 allocation always exists, but finding such an allocation in polynomial time is also left as an open question. Another closely related question was also left open by [8]: whether there always exists an interval EF1 allocation for monotone valuations. The existence of such a valuation would improve the (already polynomial) number of interactions required by our algorithm for monotone valuations, by further narrowing down the search space.

Relatedly, while in Appendix [sec:direct-almost-contiguous], we showed NP-hardness of deciding whether a given blacklist of tuples still allows for an almost-contiguous allocation, the problem shown NP-hard is a slight generalization of the one faced by an algorithm trying to obtain an EF1 allocation. Specifically, when the tuple \((i,B_1,B_2)\) is added to the blacklist, signifying that agent \(i\), being given bundle \(B_1\), would EF1-envy any agent given bundle \(B_2\), this also implies that the same would be true for any tuple \((i,B'_1,B'_2)\) with \(B'_1 \subseteq B_1, B'_2 \supseteq B_2\); the instances constructed in our reduction can violate this closure property, so it is conceivable that a more narrow definition of the problem that needs to be solved is not NP-hard. After all, the existence of an EF1 almost-contiguous allocation is guaranteed, so the answer to the decision question for all instances created over the execution of a search algorithms is “Yes”. Nonetheless, we view our NP-hardness result as strong evidence that the problem of finding an allocation avoiding all tuples of the blacklist may be computationally hard for a suitable complexity class of search problems.

Another related question is whether there is an alternative approach for interactively finding an EF1 allocation under general monotone valuation functions with single-witness feedback. While our approach of embedding the objects linearly leads to a polynomial number of interactions, it certainly need not be the unique approach achieving this goal, and perhaps an alternative would lead to less challenging computational problems.

While we showed the existence of almost-contiguous allocations for monotone allocations of goods, our result does not extend to chores. To the best of our knowledge, the existence of such allocations is open, as is the existence of interval EF2 allocations of chores. The immediate adaptations of the Sperner-based proof of [8] do not appear to work, though it is conceivable that a Sperner-based argument with more fundamental modifications could succeed.

More fundamentally, other questions in the general realm of fairness and social choice could benefit from being studied through the lens of interactive learning. Doing so would pose a natural, and in many cases practically relevant, alternative to either assuming full access to inputs or specific types of interactions.

9 Naive Local-Adjustment Algorithms under the Single-Witness EF1 Model↩︎

A natural question is whether EF1 under the Single-Witness Model can be achieved by a simple local-adjustment rule that directly responds to revealed envy. Specifically, upon observing a violating pair \((i,j)\), one may transfer a single item from agent \(j\) to agent \(i\) and repeat this procedure until no further violations are reported.

We begin by analyzing this approach in the pure-goods setting with identical additive valuations. In this case, we show that the local-adjustment algorithm terminates and outputs an EF1 allocation. However, we can only establish an exponential upper bound on the number of iterations required by the local-adjustment process. Furthermore, when valuations are not identical, the same procedure may fail to terminate. The latter result implies that purely local adjustments are insufficient for obtaining efficient algorithms under the Single-Witness Model.

The convergence argument above critically relies on the valuations being identical. When valuations differ across agents, the local adjustment rule of Algorithm 4 no longer guarantees progress, as illustrated by a simple counterexample.

Consider two agents \(1,2\) and three items \(x_1,x_2,x_3\) with additive valuations: \[\begin{array}{c|ccc} & x_1 & x_2 & x_3 \\ \hline v_1 & 1 & 5 & 2 \\ v_2 & 5 & 1 & 2 \\ \end{array}\] Suppose the current allocation is \(A_1=\left\{ x_1,x_3 \right\}\) and \(A_2=\left\{ x_2 \right\}\). In this allocation, agent \(2\) envies \(1\) by more than one item. Transferring \(x_3\) from \(1\) to \(2\) reverses the envy, making \(1\) envy \(2\); moving \(x_3\) back restores the original allocation, creating a cycle. Thus, under non-identical valuations, the process may oscillate indefinitely.

Intuitively, when agents evaluate bundles differently, both may regard the other’s bundle as more desirable, so single-item transfers cannot eliminate mutual envy. One might attempt a bundle-swap variant that performs a full swap between \(A_i\) and \(A_j\) once a previously visited allocation reoccurs. However, even this modification can enter cycles. Tables 4 and 5 present a concrete instance⁵ with non-identical additive valuations, involving 6 agents and 12 items, whose execution under the bundle-swap variant of the local-adjustment dynamics forms a cycle.

This example highlights a clear distinction between identical and heterogeneous additive valuations. Under identical valuations, Algorithm 4 is guaranteed to terminate, since each one-item transfer decreases a natural potential function. When valuations differ across agents, this structural monotonicity is lost. Even allowing full bundle swaps is insufficient to prevent cycling, indicating that heterogeneous additive valuations admit fundamentally more complex local-improvement behavior than their identical counterparts. This separation helps explain why purely local adjustment rules are insufficient in general, and motivates the use of more structured methods that ensure global progress with polynomial interaction, as developed in the main body of the paper.

5pt

4pt

10 Another Instantiation of the Ellipsoid Framework: EFX with Charity↩︎

We present another instantiation of the ellipsoid-based framework for a relaxation of envy-freeness, namely EFX-with-charity.

We begin by briefly recalling the notion of envy-freeness up to any good (EFX). An allocation is EFX if no agent envies another agent after the removal of any single good from the other agent’s bundle (rather than a carefully chosen single good). EFX is strictly stronger than EF1 and is regarded as one of the most compelling relaxations of envy-freeness for indivisible goods. However, unlike EF1, it is not known whether EFX allocations always exist, even for relatively simple valuation classes. To address this, [27] introduced a relaxation that allows a small number of goods to remain unallocated, or equivalently, donated to charity. This leads to the notion of EFX-with-charity.

[27] showed that under additive valuations, there exists an EFX-with-charity allocation that achieves a Nash social welfare at least half of the optimal Nash social welfare achievable on the full set of goods \(M\). Subsequently, [28] strengthened this result by introducing the notion of EFX-with-bounded-charity. In this variant, the goal is to compute EFX-with-charity allocations that satisfy explicit bounds on the charity set \(C\), including both a bound on its cardinality and a bound on its value. In particular, they showed that for general monotone valuations, there always exists an EFX-with-charity allocation satisfying \(|C| < n\) and \(v_i(C) \le v_i(A_i)\) for all agents \(i\). Their proof is constructive and yields a pseudo-polynomial-time algorithm for computing such allocations.

Having defined the notion of EFX with charity, we now describe the interactive feedback model for EFX, analogous to the single-witness models introduced in Section 2.2 for EF1 and PROP1.

Compared to EF1 and PROP1, the EFX condition is more demanding in that a violation depends not only on a pair of agents, but also on the specific good whose removal fails to eliminate envy. Therefore, identifying an EFX violation requires specifying a concrete witness good \(x \in A_j\), which is essential for deriving a valid separating hyperplane in the ellipsoid-based framework.

Under this feedback model, the resulting Algorithm 5 differs from Algorithm 1 only in the type of witness feedback and the corresponding separating constraints. Since we focus on the pure-goods setting, each agent’s valuation vector lies in \([0,1]^m\) rather than \([-1,1]^m\). In addition, the allocation step now invokes the pseudo-polynomial-time EFX-with-bounded-charity algorithm of [28] as a black box. Correctness and termination follow by the same ellipsoid-based argument as for EF1 and PROP1.

11 Direct Search over Almost-Contiguous Allocations↩︎

In Section 5.2, we showed that by restricting attention to almost-contiguous allocations, each strong EF1 violation rules out a distinct local configuration, which we record as a forbidden tuple in a blacklist \(\mathcal{B}\). This observation yields a polynomial bound on the number of EF1 interactions, but does not by itself lead to a polynomial-time algorithm due to the search procedure of knife positions.

We now describe an alternative, purely combinatorial approach that avoids the ellipsoid framework, and with it the search for knife positions. The algorithm directly maintains the blacklist \(\mathcal{B}\) of forbidden tuples and iteratively proposes almost-contiguous allocations that avoid all tuples blacklisted so far. The algorithm fixes an arbitrary ordering of the items as \(1,2,\dots,m\) and considers only allocations that respect this order.

In each round \(t\), the algorithm (Algorithm 6) proposes an allocation \(A^{(t)}\). If the allocation is certified as EF1, the algorithm terminates. Otherwise, the feedback returns a violating ordered pair \((i,j)\), which induces a new forbidden tuple that is added to \(\mathcal{B}\). The process continues until an EF1 allocation is found or all feasible tuples have been excluded.

The correctness and interaction complexity of Algorithm 6 follow exactly the same reasoning as in Theorem 4 for the ellipsoid-based algorithm. In particular, each violation feedback rules out a distinct forbidden tuple, and the total number of iterations is therefore bounded by the number of such tuples. This is captured by the following theorem:

While Algorithm 6 avoids the search over knife positions implicit in the algorithm of Section 5 due to its non-constructive existence proof of an EF1 allocation, it replaces the problem with another difficult problem: finding an almost-contiguous allocation avoiding all blacklisted tuples. In fact, we show that a (slightly generalized) decision version of this new problem is NP-hard.

12 Proof of Lemma 4↩︎

13 Achieving \(O(\log m)\) interactions for Two Agents under All-Witness EF1 Feedback↩︎

We saw that for any constant number of agents, EF1 allocations can be found in polynomial time even under the Membership EF1 Model.

Here, we show that under the All-Witness Model, for \(n=2\) agents, it is possible to find an EF1 allocation using only \(O(\log m)\) rounds of interaction. Our approach is based on [5], who showed that, given access to EF feedback, their Algorithm 1 finds a contiguous-interval EF1 allocation using \(O(\log m)\) queries.

In our setting, the feedback consists only of all-witness EF1 violation information. Nevertheless, we show that the same binary-search idea can be implemented using only EF1 feedback, yielding an \(O(\log m)\) interaction and time bound.

References↩︎

---

1. Simply consider two agents and one desirable item.↩︎

3. In our setting, the separating inequalities are sums of item values and have coefficients in \(\{0,1\}\); thus \(L\) can be taken polynomial in the input description of item values.↩︎

4. A somewhat weaker polynomial upper bound on the number of interactions can be obtained by simply noting that the total number of variables encoding the valuations is \(O(nm^3)\). The properties of the ellipsoid method alluded to before imply termination in a polynomial number of iterations. We introduce the blacklist-based analysis in part because it serves as the point of departure for a different approach discussed in Appendix [sec:direct-almost-contiguous].↩︎

5. This instance was obtained by generating random additive valuations and running the bundle-swap variant of the local-adjustment dynamics. It is included solely as a concrete counterexample, and the details of the generating process are therefore omitted.↩︎