Misplaced Pages

#872127

53-500: EF1 may refer to: EF1 item allocation - a rule for fair allocation of indivisible objects among people with different preferences. A tornado intensity rating on the Enhanced Fujita scale . Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title EF1 . If an internal link led you here, you may wish to change

106-464: A countable union of intervals. Intuition: consider the division procedure for piecewise-homogeneous cakes described above. In general, the cake is not piecewise-homogeneous. However, because the value measures are continuous, it is possible to divide the cake to smaller and smaller regions such that the regions become more and more homogeneous. When R → ∞ {\displaystyle R\to \infty } , this process converges to

159-442: A pie (a circular cake) in which each piece contains at most n -1 intervals; hence, at most 2 n -2 cuts are needed. See Stromquist–Woodall theorem . The number of cuts is essentially optimal for general weights. This theorem can be applied recursively to obtain an exact division for any k >1 and any weights, using O( n k ) cuts. The Stone–Tukey theorem states that given n measurable "objects" in n - dimensional space, it

212-574: A cake. Without this oracle, an EFm allocation can be computed in polynomial time in two special cases: two agents with general additive valuations, or any number of agents with piecewise-linear valuations. In contrast to EF1, which is compatible with Pareto-optimality, EFm may be incompatible with it. Rather than using a worst-case bound on the amount of envy, one can try to minimize the amount of envy in each particular instance. See envy minimization for details and references. The AL procedure finds an EF allocation for two agents. It may discard some of

265-438: A certain piece to two pieces. Suppose w.l.o.g. that the cutter is George and that he cuts piece X to two sub-pieces: X1 and X2. Now, the total number of subsets is 2 : half of them already existed and by assumption they are not exact, so the protocol's only chance of finding an exact subset is to look at the new subsets. Each new subset is made of an old subset in which the piece X has been replaced with either X1 or X2. Since George

318-509: A consensus division. However, the number of required cuts in the limit is infinite. Fremlin later showed that it is possible to construct such a division as a finite union of intervals. Suppose the cake is an interval made of n districts (sub-intervals), and each of the n partners values only a single district. Then, a consensus division of the cake into k subsets requires n ⋅ ( k − 1 ) {\displaystyle n\cdot (k-1)} cuts, since each of

371-462: A constant, two types of approximations can be computed in polynomial time. The algorithms work for general additive valuations (not necessarily piecewise-constant); the valuations are accessed using queries in the Robertson–Webb query model , including a mark -query to the sum of all n valuations. The following approximations can be attained: When the resource to divide is not a cake but rather

424-447: A division which is both near-exact and envy-free cake-cutting . A different explanation of the crumb-and-pack procedure is provided by Brams and Taylor. Most results for bounded number of cuts focus on the case in which the weights are equal. An ε -approximate consensus halving can be computed by an algorithm based on Tucker's lemma , which is the discrete version of Borsuk-Ulam theorem . An adaptation of this algorithm shows that

477-400: A division. They do not use a hyperplane knife but rather a more complicated polynomial surface. There are also discrete adaptations of these multi-dimensional results. It is impossible to compute an exact division with a finite number of queries, even when there are only n =2 agents and k =2 pieces the weights equal 1/2. This means that the best we can achieve using a discrete algorithm

530-436: A finite number of queries). In some cases, exact divisions can be found by moving-knife protocols. Near-exact divisions can be found by discrete protocols. Let w 1 , w 2 , … , w k {\displaystyle w_{1},w_{2},\ldots ,w_{k}} be k weights whose sum is 1. Assume there are n agents, all of whom value the cake C as 1. The value measure of agent i

583-405: A non-zero value to both partners. This is because, if Alice (for example) cuts a piece which she values as 0, it is possible that George also values the same piece as 0, so we can discard this piece and continue with the other pieces. The total number of different subsets now is 2 , and by the induction assumption none of them is exact. At step k , the protocol can ask either Alice or George to cut

SECTION 10

#1732802054873

636-418: A piece that both agents agree that its value is exactly 1 / n {\displaystyle 1/n} . By combining several such pieces, it is possible to achieve a consensus division with any ratios that are rational numbers. But this may require a large number of cuts. A better way to achieve a consensus division is to identify the two endpoints of the cake and treat it like a circle. I.e, when

689-480: A set of divisible resources, the problem becomes easier: From a computational perspective, not much is known about the computation of an exact division with ( k − 1 ) n {\displaystyle (k-1)n} cuts for k ≥ 3 {\displaystyle k\geq 3} . Note that the problem is not necessarily harder than for k ≥ 2 {\displaystyle k\geq 2} , since we are allowed to use

742-411: A single item (alternatively, one item remains in shared ownership). It requires the agents to report a numeric value for each item, and assumes that they have additive utilities . When each agent may get at most a single item, and the valuations are binary (each agent either likes or dislikes each item), there is a polynomial-time algorithm that finds an envy-free matching of maximum cardinality. If

795-415: A value of at most 1/ k for partner #1. Continue with partners #3, #4, …, # n . Finally all n partners value each resulting crumb as at most 1/ k . Packing step : the goal here is to partition the crumbs to n subsets, such that the sum of values in each subset j is near w j . Here is an intuitive explanation of the packing step for two partners (Alice and George) when the weights are 1/2. It

848-596: Is 2 ( k − 1 ) {\displaystyle 2(k-1)} . As of 2015, there is no known generalization of this moving-knife procedure to n >2 agents. For any given ε > 0 {\displaystyle \varepsilon >0} , one can give each partner a piece such that all partners believe that the values they have differ by less than ε {\displaystyle \varepsilon } , i.e., for every i and every j : The near-exact division procedure has two steps: crumbing and packing . Crumbing step :

901-399: Is PPA-hard . Hardness holds even with the following additional conditions: Next, assume that ε is a constant (does not depend on n ). Then, finding an ε -approximate consensus-halving is PPAD-hard , which is theoretically weaker than PPA-hard. The proof is by reduction from the ε -approximate Generalised Circuit problem . Hardness holds even in the following conditions: When ε is

954-403: Is a half-space whose value is exactly 1/2 to each partner. Hence there exists a consensus division using a single cut. The original version of this theorem works only if the number of dimensions of the cake is equal to the number of partners. E.g, it is not possible to use this theorem to divide a 3-dimensional sandwich to 4 or more partners. However, there are generalizations that enable such

1007-438: Is a near-exact division. Proof : When the protocol is at step k , it has a collection of at most k pieces. To provide an exact division, the protocol must find an exact subset – a subset of the pieces which both partners value as exactly 1/2. We are going to prove that, for every k , there are situations in which at step k there is no exact subset, and hence the protocol might have to continue endlessly. Initially, there

1060-400: Is also called a consensus division , since there is a consensus among all agents that the value of piece j is exactly w j {\displaystyle w_{j}} . Some special cases are: For every ε > 0 {\displaystyle \varepsilon >0} , An ε {\displaystyle \varepsilon } -near-exact division in

1113-567: Is denoted by V i {\displaystyle V_{i}} . It is assumed to be a nonatomic measure on C . An exact division in the ratios w 1 , w 2 , … , w k {\displaystyle w_{1},w_{2},\ldots ,w_{k}} is a partition of the cake into k pieces: C = X 1 ⊔ ⋯ ⊔ X k {\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{k}} , such that for every agent i and every piece j : It

SECTION 20

#1732802054873

1166-449: Is easy to prove the existence of an exact division when the agents have piecewise-constant valuations . This means that the cake can be partitioned into R regions, such that all agents agree that the value-density in each region is uniform. For example, consider a circular cake in which each of its 4 quarters has a different topping. The agents may value each of the toppings differently, but do not distinguish between different pieces having

1219-502: Is only one piece which both partners value as 1, so there is obviously no exact subset. After one step, at most one partner (say, Alice) has had an option to cut the cake. Even if Alice cuts the cake to two pieces that are equal in her opinion, they may be different in George's opinion, so again there is no exact subset. Suppose now that we are at step k and there are k pieces. Without loss of generality, we may assume that each piece has

1272-435: Is possible to divide all of them in half (with respect to their measure , i.e. volume) with a single ( n − 1) -dimensional hyperplane . Stated differently: if the cake is the space R n {\displaystyle \mathbb {R} ^{n}} , and the value measures of the partners are finite and vanish on any n − 1 {\displaystyle n-1} dimensional hyperplane, then there

1325-437: Is possible to lift the item-ranking to a partial bundle-ranking. For example, if the item-ranking is w>x>y>z, then responsiveness implies that {w,x}>{y,z} and {w,y}>{x,z}, but does not imply anything about the relation between {w,z} and {x,y}, between {x} and {y,z}, etc. Given an item-ranking: The following results are known: The empty allocation is always EF. But if we want some efficiency in addition to EF, then

1378-560: Is possible to prove by induction, that the difference in the valuation of the bowl between Alice and George is always at most 1/ k . Hence, when one of the partners receives the bowl, its value for both partners is between than 1/2-1/ k and 1/2+1/ k . Formally, each piece can be represented as a vector of values, one per partner. The length of each vector is bounded, i.e. for each such vector v : | | v | | ≤ n / k {\displaystyle ||v||\leq {\sqrt {n}}/k} . Our goal

1431-466: Is that the number of EFX allocations can be as few as 2 (for any number of items), while the number of EF1 allocations is always exponential in the number of items. Some division scenarios involve both divisible and indivisible items, such as divisible lands and indivisible houses. An allocation is called EFm if for every two agents A and B: An EFm allocation exists for any number of agents. However, finding it requires an oracle for exact division of

1484-432: Is the cutter, he can cut in a way which makes one of these subsets an exact subset for him (e.g. if a certain subset containing piece X had a value of 3/4, George can cut X such that X1 has a value of 1/4 in his opinion, so that the new subset has a value of exactly 1/2). But, George does not know Alice's valuation and cannot take it into account when cutting. Therefore, there is an uncountable infinity of different values that

1537-485: Is to create, for each partner j , a vector all whose elements are near w j . To do this, we have to divide the vectors to subsets, such that the sum of vectors in each subset j is sufficiently close to a vector all whose elements are w j . This is possible thanks to a theorem by V.Bergström, The Crumb-and-Pack procedure is a subroutine in the Robertson-Webb protocol . The latter protocol generates

1590-429: Is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy. One way to attain fairness is to use monetary transfers . When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations. The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires

1643-476: The agents have additive utility functions that are drawn from probability distributions satisfying some independence criteria, and the number of items is sufficiently large relative to the number of agents, then an EF allocation exists with high probability . Particularly: On the other hand, if the number of items is not sufficiently large, then, with high probability, an EF allocation does not exist. See Fair item allocation for details and references. Below,

EF1 - Misplaced Pages Continue

1696-498: The agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' preference relations are strictly monotone, but does not need to assume that they are responsive preferences . In the worst case, the agents may have to rank all possible bundles, so the run-time might be exponential in the number of items. It is usually easier for people to rank individual items than to rank bundles. Assuming all agents have responsive preferences , it

1749-448: The bundle of B, then A does not envy B. An EF1 allocation always exists and can be found efficiently by various procedures, particularly: An allocation is called EFx if for every two agents A and B, if we remove any item from the bundle of B, then A does not envy B. EFx is strictly stronger than EF1: EF1 lets us eliminate envy by removing the item most valuable (for A) from B's bundle; EFx requires that we eliminate envy by removing

1802-437: The cake value. This is done as follows. One agent moves two knives over the cake from left to right, always keeping the value between the knives as exactly 1/2. It is possible to prove (by the intermediate value theorem ) that at some point, the value of the piece between the knives to the other partner will also be exactly 1/2. The other agent calls "stop!" at that point and the piece is cut. The same protocol can be used to cut

1855-618: The chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division (with k  = 3 and n  = 2), as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms: When both n and k are finite, Consensus divisions always exist. However, they cannot be found by discrete protocols (with

1908-425: The decision problem becomes computationally hard: The decision problem may become tractable when some parameters of the problem are considered fixed small constants: Many procedures find an allocation that is "almost" envy-free, i.e., the level of envy is bounded. There are various notions of "almost" envy-freeness: An allocation is called EF1 if for every two agents A and B, if we remove at most one item from

1961-461: The districts must be cut into k pieces which are equal in the eyes of the partner that values this district. This raises the question of whether there always exists a consensus division with this exact number of cuts. This question was studied extensively, focusing mainly on a one-dimensional cake (an interval). Consider first the consensus halving case: k = 2 {\displaystyle k=2} and equal weights. The lower bound on

2014-502: The following result. There are n {\displaystyle n} different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure i {\displaystyle i} , is k ⋅ a i {\displaystyle k\cdot a_{i}} . Then it is possible to partition the interval into k {\displaystyle k} parts (not necessarily contiguous), such that

2067-427: The following shorthands are used: With submodular utilities, allocation is PE and MEF1. Exact division Consensus splitting , also called exact division , is a partition of a continuous resource (" cake ") into some k pieces, such that each of n people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only

2120-413: The goal is to cut the cake to tiny bits ("crumbs") such that each partner assigns a sufficiently small value to each crumb. This is done in the following way. Let k be a certain constant. Ask partner #1 cut the cake to k pieces that he values as 1/ k . Ask partner #2 to trim pieces as needed (using at most k -1 cuts) such that each piece has a value of at most 1/ k . These new pieces of course still have

2173-526: The item least valuable (for A). An EFx allocation is known to exist in some special cases: Some approximations are known: It is an open question whether an EFx allocation exists in general. The smallest open case is 4 agents with additive valuations. In contrast to EF1, which requires a number of queries logarithmic in the number of items, computing an EFx allocation may require a linear number of queries even when there are two agents with identical additive valuations. Another difference between EF1 and EFx

EF1 - Misplaced Pages Continue

2226-469: The items, but, the final allocation is Pareto efficient in the following sense: no other EF allocation is better for one and weakly better for the other. The AL procedure only requires the agents to rank individual items. It assumes that the agents have responsive preferences and returns an allocation that is necessarily envy-free (NEF). The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to cut

2279-480: The knives cyclically around the cake, always keeping the value between them at exactly p . It is possible to prove that at some point, the value of the piece between the knives to the other partner will also be exactly p . The other agent calls "stop!" at that point and the piece is cut. This requires only two cuts. By repeatedly applying the above procedure, it is possible to achieve a consensus division among n =2 partners and any k >1 subsets. The number of cuts

2332-447: The link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=EF1&oldid=1148090242 " Category : Disambiguation pages Hidden categories: Short description is different from Wikidata All article disambiguation pages All disambiguation pages EF1 item allocation Since the items are indivisible, an EF assignment may not exist. The simplest case

2385-423: The measure of each part, according to measure i {\displaystyle i} , is exactly a i {\displaystyle a_{i}} . At most ( k − 1 ) n {\displaystyle (k-1)n} cuts are needed, and this is optimal. Consider now the case k =2 and arbitrary weights. Stromquist and Woodall proved that there exists an exact division of

2438-456: The more general setting in which agents have countably-additive nonatomic measures . This is a corollary of the Dubins–Spanier convexity theorem (the existence of a consensus 1/ k -division was previously noted by Jerzy Neyman ). However, this theorem says nothing about the number of required cuts. Woodall showed that it is possible to construct an exact division of an interval cake as

2491-515: The number of cuts is n ⋅ ( k − 1 ) = n {\displaystyle n\cdot (k-1)=n} . Indeed, a consensus halving with at most n cuts always exists. This is a direct corollary of the Hobby–Rice theorem . It can also be proved using the Borsuk-Ulam theorem : Although the agents' preferences are modeled with measures, the proofs do not require

2544-402: The pieces X1 and X2 can have for Alice. Since the number of new subsets is finite, there is an infinite number of cases in which no new subset has a value of 1/2 for Alice, hence no new subset is exact. Two agents can achieve a consensus division using Austin moving-knife procedure . The simplest case is when the weights are 1/2, i.e. they want to cut a piece that both of them agree to be half

2597-443: The problem is in the complexity class PPA . This holds even for arbitrary bounded and non-atomic valuations. However, the run-time of this algorithm may be exponential in the problem parameters. In fact, consensus halving is computationally hard in several respects. First, assumed that ε is allowed to be inverse-exponential in n (that is, 1/ ε is an exponential function of n ). Then, finding an ε -approximate consensus-halving

2650-476: The ratios w 1 , w 2 , … , w k {\displaystyle w_{1},w_{2},\ldots ,w_{k}} is a division in which: That is, there is a consensus among all partners that the value of piece j is nearly-exactly w j {\displaystyle w_{j}} , where the difference is less than ε {\displaystyle \varepsilon } . Some special cases are: It

2703-400: The right knife gets to the right side, it immediately goes to the left side, and the piece-between-the-knives is now actually the union of the piece to the right of the right knife and the piece to the left of the left knife. This way, it is possible to find a consensus division for every p ∈ [ 0 , 1 ] {\displaystyle p\in [0,1]} . One agent moves

SECTION 50

#1732802054873

2756-408: The same topping: the value of each piece to each agent only depends on the amount they get from each region. An exact division can be achieved in the following way: The number of required cuts is k ⋅ R {\displaystyle k\cdot R} , where R is the number of regions. This algorithm can be generalized to piecewise-linear valuations . An exact division exists in

2809-452: The value functions to be positive or additive over subsets; they may be any continuous set functions defined on the Borel sigma-algebra. Thus it is not required that partners' valuations over subsets of the cake be additively separable. Consider now the consensus 1/ k -division case: any k >1 and equal weights. Noga Alon , in his 1987 paper about the necklace splitting problem , proved

#872127