821:(fPO). They prove that, if the agents' valuations are non-degenerate, the number of fPO allocations is polynomial in the number of objects (for a fixed number of agents). Therefore, it is possible to enumerate all of them in polynomial time, and find an allocation that is fair and fPO with the smallest number of sharings. In contrast, of the valuations are degenerate, the problem becomes NP-hard. They present empirical evidence that, in realistic cases, there often exists an allocation with substantially fewer sharings than the worst-case bound.
1130:, except that in multiwinner voting the number of elected candidates is usually much smaller than the number of voters, while in public goods allocation the number of chosen goods is usually much larger than the number of agents. An example is a public library that has to decide which books to purchase, respecting the preferences of the readers; the number of books is usually much larger than the number of readers.
291:: each partner reports a value for each bundle of size at most 2. The value of a bundle is calculated by summing the values for the individual items in the bundle and adding the values of pairs in the bundle. Typically, when there are substitute items, the values of pairs will be negative, and when there are complementary items, the values of pairs will be positive. This idea can be generalized to
2592:
946:(envy-freeness for mixed items), which generalizes both envy-freeness for divisible items and EF1 for indivisible items. They prove that an EFM allocation always exists for any number of agents with additive valuations. They present efficient algorithms to compute EFM allocations for two agents with general additive valuations, and for
1244:
corresponds to the special case in which each issue corresponds to an item, each decision option corresponds to giving that item to a particular agent, and the agents' utilities are zero for all options in which the item is given to someone else. In this case, proportionality means that the utility of each agent is at least 1/
736:: a simple protocol where the agents take turns in selecting items, based on some pre-specified sequence of turns. The goal is to design the picking-sequence in a way that maximizes the expected value of a social welfare function (e.g. egalitarian or utilitarian) under some probabilistic assumptions on the agents' valuations.
1519:
2294:
2797:
588:
competitive equilibrium is reached when the supply matches the demand. The fairness argument is straightforward: prices and budgets are the same for everyone. CEEI implies EF regardless of additivity. When the agents' preferences are additive and strict (each bundle has a different value), CEEI implies
976:
for EFM. They show that, in general, no truthful EFM algorithm exists, even if there is only one indivisible good and one divisible good and only two agents. But, when agents have binary valuations on indivisible goods and identical valuations on a single divisible good, an EFM and truthful mechanism
554:
Every agent weakly prefers his own bundle to any other bundle. Every envy-free allocation of all items is mFS-fair; this follows directly from the ordinal definitions and does not depend on additivity. If the valuations are additive, then an EF allocation is also proportional and MMS-fair. Otherwise,
423:
if all agents receive a bundle that they weakly prefer over their mFS. mFS-fairness can be described as the result of the following negotiation process. A certain allocation is suggested. Each agent can object to it by demanding that a different allocation be made by another agent, letting him choose
1266:
Often, the same items are allocated repeatedly. For example, recurring house chores. If the number of repetitions is a multiple of the number of agents, then it is possible to find in polynomial time a sequence of allocations that is envy-free and complete, and to find in exponential time a sequence
996:
and max Nash welfare). They assume that all agents have binary valuations. It is known that, if only divisible goods or only indivisible goods exist, the problem is polytime solvable. They show that, with mixed goods, the problem is NP-hard even when all indivisible goods are identical. In contrast,
761:
Several works assume that all objects can be divided if needed (e.g. by shared ownership or time-sharing), but sharing is costly or undesirable. Therefore, it is desired to find a fair allocation with the smallest possible number of shared objects, or of sharings. There are tight upper bounds on the
418:
The min-max-fair-share of an agent is the minimal utility that she can hope to get from an allocation if all the other agents have the same preferences as her, when she always receives the best share. It is also the minimal utility that an agent can get for sure in the allocation game “Someone cuts,
2127:
980:
Nishimura and Sumita study the properties of the maximum Nash welfare allocation (MNW) for mixed goods. They prove that, when all agents' valuations are binary and linear for each good, an MNW allocation satisfies a property stronger than EFM, which they call "envy-freeness up to any good for mixed
1091:
In this variant, bundles are given not to individual agents but to groups of agents. Common use-cases are: dividing inheritance among families, or dividing facilities among departments in a university. All agents in the same group consume the same bundle, though they may value it differently. The
1000:
Bei, Liu and Lu study a more general setting, in which the same object can be divisible for some agents and indivisible for others. They show that the best possible appproximation for MMS is 2/3, even for two agents; and present algorithms attaining this bound for 2 or 3 agents. For any number of
969:(objects with negative utilities) and a divisible cake (with positive utility). They present an algorithm for finding an EFM allocation in two special cases: when each agent has the same preference ranking over the set of chores, and when the number of items is at most the number of agents plus 1.
1004:
Li, Li, Liu and Wu study a setting in which each agent may have a different "indivisibility ratio" (= proportion of items that are indivisible). Each agent is guaranteed an allocation that is EF/PROP up to a fraction of an item, where the fraction depends on the agent's indivisibility ratio. The
266:
In the ordinal approach, additivity allows us to infer some rankings between bundles. For example, if a person prefers w to x to y to z, then he necessarily prefers {w,x} to {w,y} or to {x,y}, and {w,y} to {x}. This inference is only partial, e.g., we cannot know whether the agent prefers {w} to
1065:
In this variant, different agents are entitled to different fractions of the resource. A common use-case is dividing cabinet ministries among parties in the coalition. It is common to assume that each party should receive ministries according to the number of seats it has in the parliament. The
587:
This criterion is based on the following argument: the allocation process should be considered as a search for an equilibrium between the supply (the set of objects, each one having a public price) and the demand (the agents’ desires, each agent having the same budget for buying the objects). A
1243:
In this variant, several agents have to accept decisions on several issues. A common use-case is a family that has to decide what activity to do each day (here each issue is a day). Each agent assigns different utilities to the various options in each issue. The classic item allocation setting
283:
have been developed as a compromise between the full expressiveness of combinatorial preferences to the simplicity of additive preferences. They provide a succinct representation to some natural classes of utility functions that are more general than additive utilities (but not as general as
271:
The additivity implies that each partner can always choose a "preferable item" from the set of items on the table, and this choice is independent of the other items that the partner may have. This property is used by some fair assignment algorithms that will be described next.
981:
goods". Their results hold not only for max Nash welfare, but also for a general fairness notion based on minimizing a symmetric strictly convex function. For general additive valuations, they prove that an MNW allocation satisfies an EF approximation that is weaker than EFM.
114:
A naive way to determine the preferences is asking each partner to supply a numeric value for each possible bundle. For example, if the items to divide are a car and a bicycle, a partner may value the car as 800, the bicycle as 200, and the bundle {car, bicycle} as 900 (see
2262:
828:
is not fixed, even for non-degenerate valuations, it is NP-hard to decide whether there exists an fPO envy-free allocation with 0 sharings. They also demonstrate an alterate approach to enumerating distinct consumption graph for allocations with a small number of
59:
The indivisibility of the items implies that a fair division may not be possible. As an extreme example, if there is only a single item (e.g. a house), it must be given to a single partner, but this is not fair to the other partners. This is in contrast to the
565:: for each two agents A and B, if we remove from the bundle of B the item most valuable for A, then A does not envy B (in other words, the "envy level" of A in B is at most the value of a single item). Under monotonicity, an EF1 allocation always exists.
1674:
1303:
372:
is a criterion that should hold for each individual partner, as long as the partner truthfully reports his preferences. Five such criteria are presented below. They are ordered from the weakest to the strongest (assuming the valuations are additive):
961:
fairness. They propose an algorithm that computes an alpha-approximate MMS allocation for any number of agents, where alpha is a constant between 1/2 and 1, which is monotonically increasing with the value of the divisible goods relative to the MMS
1117:
In this variant, each item provides utility not only to a single agent but to all agents. Different agents may attribute different utilities to the same item. The group has to choose a subset of items satisfying some constraints, for example:
872:
necessary for consensus halving when agents' utilities are drawn from probabilistic distributions. For agents with non-additive monotone utilities, consensus halving is PPAD-hard, but there are polynomial-time algorithms for a fixed number of
428:
partitions, there is a bundle that he strongly prefers over his current bundle. An allocation is mFS-fair iff no agent objects to it, i.e., for every agent there exists a partition in which all bundles are weakly worse than his current share.
2587:{\displaystyle \sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d^{*}}(A)\cdot u_{i}(A)\right)=\sum _{A\in {\mathcal {A}}}p_{d^{*}}(A)\sum _{i=1}^{n}u_{i}(A)\leq \max _{A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}\sum _{i=1}^{n}u_{i}(A)}
1267:
that is proportional and Pareto-optimal. But, an envy-free and Pareto-optimal sequence may not exist. With two agents, if the number of repetitions is even, it is always possible to find a sequence that is envy-free and Pareto-optimal.
620:
if it attains the maximum possible egalitarian welfare, i.e., it maximizes the utility of the poorest agent. Since there can be several different allocations maximizing the smallest utility, egalitarian optimality is often refined to
2651:
41:
rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:
1988:
752:
Traditional papers on fair allocation either assume that all items are divisible, or that all items are indivisible. Some recent papers study settings in which the distinction between divisible and indivisible is more fuzzy.
1915:
1224:. This idea can be formalized to show a general reduction from private-goods allocation to public-goods allocation that retains the maximum Nash welfare allocation, as well as a similar reduction that retains the
1785:
1731:
343:
formula, and may assign a value for each formula. For example, a partner may say: "For (x or (y and z)), my value is 5". This means that the agent has a value of 5 for any of the bundles: x, xy, xz, yz,
212:
different bundles, i.e., say which bundle is the best, which is the second-best, and so on. This may be easier than calculating exact numbers, but it is still difficult if the number of items is large.
2799:
In contrast to the utilitarian rule, here, the stochastic setting allows society to achieve higher value — as an example, consider the case where are two identical agents and only one item that worth
231:
the preferences on items to preferences on bundles. Then, the agents report their valuations/rankings on individual items, and the algorithm calculates for them their valuations/rankings on bundles.
2140:
977:
exists. When agents have binary valuations over both divisible and indivisible goods, an EFM and truthful mechanism exists when there are only two agents, or when there is a single divisible good.
3395:
Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Computational complexity and approximability of social welfare optimization in multiagent resource allocation".
1012:
in both indivisible and mixed item allocation. They provide bounds for the price of EF1, EFx, EFM and EFxM. They provide tight bounds for two agents and asymptotically tight bounds for
3350:
Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation".
2642:
1979:
1514:{\displaystyle {\mathcal {A}}=\{(A^{1},\dots ,A^{n})\mid \forall i\in \colon A^{i}\subseteq ,\quad \forall i\neq j\in \colon A^{i}\cap A^{j}=\emptyset ,\quad \cup _{i=1}^{n}A^{i}=\}}
625:: from the subset of allocations maximizing the smallest utility, it selects those allocations that maximize the second-smallest utility, then the third-smallest utility, and so on.
1554:
1081:
2861:
1140:
The number of items should be as small as possible, subject to that all agents must agree that the chosen set is better than the non-chosen set. This variant is known as the
730:
Nash-optimal allocation: and prove hardness of calculating utilitarian-optimal and Nash-optimal allocations. present an approximation procedure for Nash-optimal allocations.
1546:
1248:
of his "dictatorship utility", i.e., the utility he could get by picking the best option in each issue. Proportionality might be unattainable, but PROP1 is attainable by
707:
2289:
1812:
210:
171:
2792:{\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\min _{i=1,\ldots ,n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}
263:
utility function). Once the agent reports a value for each individual item, it is easy to calculate the value of each bundle by summing up the values of its items.
3762:
1048:
More generally: does there always exist an EFM allocation when both divisible items and indivisible items may be positive for some agents and negative for others?
500:
465:
144:
2122:{\displaystyle d^{*}={\underset {d\in {\mathcal {D}}}{\operatorname {argmax} }}\sum _{i=1}^{n}\sum _{A\in {\mathcal {A}}}\left(p_{d}(A)\cdot u_{i}(A)\right)}
1293:
agents. Formally, in the deterministic setting, a solution describes a feasible allocation of the items to the agents — a partition of the set of items into
718:
4381:
Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017). "Fair public decision making". In
Daskalakis, Constantinos; Babaioff, Moshe; Moulin, Hervé (eds.).
3549:. In Bureš, Tomáš; Dondi, Riccardo; Gamper, Johann; Guerrini, Giovanna; Jurdziński, Tomasz; Pahl, Claus; Sikora, Florian; Wong, Prudence W.H. (eds.).
64:
problem, where the dividend is divisible and a fair division always exists. In some cases, the indivisibility problem can be mitigated by introducing
1820:
383:
The maximin-share (also called: max-min-fair-share guarantee) of an agent is the most preferred bundle he could guarantee himself as divider in
3500:
Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut (2022). "Consensus
Halving for Sets of Items".
116:
305:: for each partner, there is a graph that represents the dependencies between different items. In the cardinal approach, a common tool is the
223:
In the ordinal approach, each partner should report a ranking over the items, i.e., say which item is the best, which is the second-best, etc.
4408:
4357:
4309:
3746:
3566:
3293:
1235:(which implies both Pareto-efficiency and proportionality), maximum Nash welfare, leximin optimality and proportionality up to one item.
3193:
Bouveret, Sylvain; Lemaître, Michel (2015). "Characterizing conflicts in fair division of indivisible goods using a scale of criteria".
3990:
Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal (2017-03-23). "Competitive
Equilibrium with Indivisible Goods and Generic Budgets".
3334:
3036:
1738:
1684:
813:
This raises the question of whether it is possible to attain fair allocations with fewer sharings than the worst-case upper bound:
4424:
Igarashi, Ayumi; Lackner, Martin; Nardi, Oliviero; Novaro, Arianna (2023-04-04). "Repeated Fair
Allocation of Indivisible Items".
173:
possible bundles. For example, if there are 16 items then each partner will have to present their preferences using 65536 numbers.
575:
valuable for A, then A does not envy B. EFx is strictly stronger than EF1. It is not known whether EFx allocations always exist.
2936:- a fair division problem in which each agent should get exactly one object, with neither monetary transfers nor randomization.
2257:{\displaystyle A^{*}={\underset {A\in {\mathcal {A}}\colon p_{d^{*}}(A)>0}{\operatorname {argmax} }}\sum _{i=1}^{n}u_{i}(A)}
1039:
2873:
Kawase and Sumita present an algorithm that, given an algorithm for finding a deterministic allocation that approximates the
884:. They study the run-time complexity of deciding the existence of a fair allocation with s sharings or shared objects, where
2129:
Kawase and Sumita show that maximization of the utilitarian welfare in the stochastic setting can always be achieved with a
1548:. That is, the set of all stochastic allocations (i.e., all feasible solutions to the problem) can be described as follows:
4501:
4203:
Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2021-11-15). "Fair-Share
Allocations for Agents with Arbitrary Entitlements".
3276:
Heinen, Tobias; Nguyen, Nhan-Tam; Rothe, Jörg (2015). "Fairness and Rank-Weighted
Utilitarianism in Resource Allocation".
3058:
2952:- a general measure of the trade-off between fairness and efficiency, with some results about the item assignment setting.
877:
1163:
Allocation of private goods can be seen as a special case of allocating public goods: given a private-goods problem with
950:
agents with piecewise linear valuations over the divisible goods. They also present an efficient algorithm that finds an
2960:
1134:
818:
771:
666:
52:
49:
Several lecturers want to divide the courses given in their faculty. Each lecturer can teach one or more whole courses.
46:
Several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings.
1249:
993:
881:
783:
724:
532:
Every allocation which gives the first and second items to Bob and Carl and the third item to Alice is proportional.
3228:
Budish, E. (2011). "The
Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes".
1107:
876:
Bismuth, Makarov, Shapira and Segal-Halevi study fair allocation with identical valuations, which is equivalent to
4383:
Proceedings of the 2017 ACM Conference on
Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017
4288:
41st IARCS Annual
Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
3553:. Lecture Notes in Computer Science. Vol. 12607. Cham: Springer International Publishing. pp. 421–430.
2915:
2823:
775:
712:
644:
An advantage of global optimization criteria over individual criteria is that welfare-maximizing allocations are
3023:
Sylvain
Bouveret and Yann Chevaleyre and Nicolas Maudet, "Fair Allocation of Indivisible Goods". Chapter 12 in:
3312:
Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016).
2933:
1279:
1066:
various fairness notions have to be adapted accordingly. Several classes of fairness notions were considered:
2610:
1947:
1669:{\displaystyle {\mathcal {D}}=\{d\mid p_{d}\colon {\mathcal {A}}\to ,\sum _{A\in {\mathcal {A}}}p_{d}(A)=1\}}
2955:
2912:, respectively. Many techniques used for these problems are useful in the case of fair item allocation, too.
2603:
says that society should choose the solution that maximize the utility of the poorest. That is, to choose a
1225:
1001:
agents, they present a 1/2-MMS approximation. They also show that EFM is incompatible with non-wastefulness.
605:
580:
2924:- a fair division problem where indivisible items and a fixed total cost have to be divided simultaneously.
3607:
3359:
3237:
3148:
2927:
1020:
Liu, Lu, Suzuki and Walsh survey some recent results on mixed items, and identify several open questions:
502:. Hence, every proportional allocation is MMS-fair. Both inclusions are strict, even when every agent has
739:
Competitive equilibrium: various algorithms for finding a CE allocation are described in the article on
468:
395:
351:
4224:
Segal-Halevi, Erel; Suksompong, Warut (2019-12-01). "Democratic fair allocation of indivisible goods".
4019:. Aamas '18. International Foundation for Autonomous Agents and Multiagent Systems. pp. 1267–1275.
2831:
4088:
3085:. Proceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence
1940:
says that society should choose the solution that maximize the sum of utilities. That is, to choose a
640:
if it maximizes the product of utilities. Nash-optimal allocations have some nice fairness properties.
3104:
Brams, Steven J.; Edelman, Paul H.; Fishburn, Peter C. (2003). "Fair Division of Indivisible Items".
2897:
2874:
2130:
1156:
1152:
4282:
Garg, Jugal; Kulkarni, Pooja; Murhekar, Aniket (2021). Bojańczy, Miko\laj; Chekuri, Chandra (eds.).
3364:
3242:
3153:
1527:
1297:
subsets (one for each agent). The set of all deterministic allocations can be described as follows:
1092:
classic item allocation setting corresponds to the special case in which all groups are singletons.
2901:
1148:
833:
794:
433:
248:
4477:
4425:
4386:
4363:
4315:
4259:
4233:
4204:
4185:
4157:
4126:
4100:
4069:
4043:
3991:
3972:
3909:
3877:
3853:
3829:
3805:
3781:
3756:
3660:
3619:
3587:
3546:
3527:
3509:
3461:
3412:
3377:
3255:
3210:
3166:
3121:
2943:
2864:
1256:
1232:
1127:
973:
779:
656:
Various algorithms for fair item allocation are surveyed in pages on specific fairness criteria:
350:: many languages for representing combinatorial preferences have been studied in the context of
1929:
that are suggested for deterministic setting can also be considered in the stochastic setting:
817:
Sandomirskiy and Segal-Halevi study sharing minimization in allocations that are both fair and
4404:
4353:
4305:
4251:
4177:
4118:
4061:
3927:
3742:
3678:
3562:
3479:
3330:
3289:
3032:
3001:
2949:
2939:
1025:
1009:
589:
384:
340:
240:
61:
3321:. Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. p. 305.
3082:
Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods
2930:- a fair division problem without money, in which fairness is attained through randomization.
2881:, finds a stochastic allocation that approximates the egalitarian welfare to the same factor
679:
4467:
4396:
4345:
4295:
4243:
4167:
4110:
4053:
3962:
3954:
3919:
3734:
3705:
3670:
3629:
3554:
3519:
3471:
3449:
3404:
3369:
3322:
3281:
3247:
3202:
3158:
3113:
2993:
2828:
and also, that it is NP-hard to approximate the eqalitarian welfare to a factor better than
2818:
2600:
1937:
1141:
1133:
The total cost of all items must not exceed a fixed budget. This variant is often known as
1032:
837:
733:
645:
503:
256:
244:
182:
3025:
Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016).
2267:
1790:
188:
149:
3731:
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
3710:
3697:
989:
543:
The above implications do not hold when the agents' valuations are not sub/superadditive.
216:
The second problem is often handled by working with individual items rather than bundles:
178:
4145:
3897:
3432:
Envy-ratio and average-nash social welfare optimization in multiagent resource allocation
3117:
988:
allocation of mixed goods, where the utility vector should minimize a symmetric strictly-
762:
number of shared objects / sharings required for various kinds of fair allocations among
477:
442:
2921:
1045:
Does there always exist an EFM allocation when there are indivisible chores and a cake?
832:
Goldberg, Hollender, Igarashi, Manurangsi and Suksompong study sharing minimization in
239:
To make the item-assignment problem simpler, it is common to assume that all items are
220:
In the cardinal approach, each partner should report a numeric valuation for each item;
129:
4283:
2981:
840:, there is a polynomial-time algorithm for computing a consensus halving with at most
27:
Fair division problem in which the items to divide are discrete rather than continuous
4495:
4481:
4319:
4263:
4189:
4130:
4073:
3976:
3582:
Bismuth, Samuel; Makarov, Vladislav; Segal-Halevi, Erel; Shapira, Dana (2023-11-08),
3531:
3259:
3170:
3125:
2997:
958:
939:
869:
740:
673:
660:
547:
377:
34:
4344:. EC '18. New York, NY, USA: Association for Computing Machinery. pp. 575–592.
4294:. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 22:1–22:19.
4012:
3214:
1679:
There are two functions related to each agent, a utility function associated with a
17:
4367:
3381:
3139:
Brams, S. J. (2005). "Efficient Fair Division: Help the Worst off or Avoid Envy?".
632:
social welfare is the product of the utilities of the agents. An assignment called
309:(Generalized Additive Independence). In the ordinal approach, a common tool is the
72:, or by discarding some of the items. But such solutions are not always available.
4300:
4030:
Chakraborty, Mithun; Igarashi, Ayumi; Suksompong, Warut; Zick, Yair (2021-08-16).
3416:
2918:- including some case-studies and lab experiments related to fair item assignment.
616:
social welfare is minimum utility of a single agent. An item assignment is called
123:
It may be difficult for a person to calculate exact numeric values to the bundles.
4247:
4114:
3872:
Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai; Tao, Yichen (2024-01-02),
3633:
3558:
3285:
3026:
1524:
In the stochastic setting, a solution is a probability distribution over the set
1038:
Are there bounded or even finite algorithms for computing EFM allocations in the
672:
Minimax-share item allocation: The problem of calculating the mFS of an agent is
4087:
Chakraborty, Mithun; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2021-12-01).
3802:
Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods
3778:
Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods
3044:
2817:
Kawase and Sumita prove that finding a stochastic allocation that maximizes the
3727:"Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods"
3674:
3313:
2803:. It is easy to see that in the deterministic setting the egalitarian value is
3923:
3738:
3408:
3373:
3206:
2904:- two well-studied optimization problems that can be seen as special cases of
1099:(fairness in the eyes of all agents in each group), so it is often relaxed to
809:−1) sharings/shared objects are always sufficient, and may be necessary.
4472:
4455:
4255:
4181:
4172:
4122:
4065:
3958:
3931:
3682:
3648:
3483:
3162:
3005:
1051:
Is there a truthful EFM algorithm for agents with binary additive valuations?
790:−1 sharings/shared objects are always sufficient, and may be necessary;
410:
if every agent receives a bundle worth at least his proportional-fair-share.
4400:
4349:
3326:
3080:
1005:
results are tight up to a constant for EF and asymptotically tight for PROP.
185:. In the ordinal model, each partner should only express a ranking over the
3523:
3475:
4337:
3726:
1910:{\displaystyle E_{i}(d)=\sum _{A\in {\mathcal {A}}}p_{d}(A)\cdot u_{i}(A)}
571:: For each two agents A and B, if we remove from the bundle of B the item
4144:
Chakraborty, Mithun; Segal-Halevi, Erel; Suksompong, Warut (2022-06-28).
3698:"On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources"
1735:
and an expected utility function associated with a stochastic allocation
467:. Hence, every mFS-fair allocation is proportional. For every agent with
3850:
Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio
892:−1. They prove that, for sharings, the problem is NP-hard for any
354:. Some of these languages can be adapted to the item assignment setting.
3967:
3896:
Liu, Shengxin; Lu, Xinhang; Suzuki, Mashbat; Walsh, Toby (2024-03-24).
1103:(fairness in the eyes of e.g. at least half the agents in each group).
3945:
Brams, Steven J.; Kaplan, Todd R. (2004). "Dividing the Indivisible".
3606:
Bei, Xiaohui; Li, Zihao; Liu, Shengxin; Lu, Xinhang (5 January 2021).
934:
Bei, Li, Liu, Liu and Lu study a mixture of indivisible and divisible
864:
sharings and an instance that requires 0 sharings. Probabilistically,
391:
if every agent receives a bundle that he weakly prefers over his MMS.
3647:
Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang; Wang, Hongao (2021-06-30).
406:
of his utility from the entire set of items. An allocation is called
4057:
3725:
Li, Zihao; Liu, Shengxin; Lu, Xinhang; Tao, Biaoshuai (2023-08-19).
4430:
4391:
4342:
Proceedings of the 2018 ACM Conference on Economics and Computation
4238:
4209:
4162:
4105:
4048:
3996:
3914:
3882:
3858:
3834:
3810:
3786:
3665:
3624:
3592:
3514:
3466:
3251:
4031:
3280:. Lecture Notes in Computer Science. Vol. 9346. p. 521.
1278:
is a type of fair item allocation in which a solution describes a
997:
if all divisible goods are identical, a polytime algorithm exists.
938:(objects with positive utiliies). They define an approximation to
860:, it is NP-hard to distinguish between an instance that requires
676:. The problem of deciding whether an mFS allocation exists is in
4456:"On the Max-Min Fair Stochastic Allocation of Indivisible Goods"
3800:
Kawase, Yasushi; Nishimura, Koichi; Sumita, Hanna (2023-11-08),
521:
Carl values the items as 3,2,1. For him, MMS=1, PFS=2 and mFS=3.
424:
first. Hence, an agent would object to an allocation only if in
4284:"On Fair and Efficient Allocations of Indivisible Public Goods"
824:
Misra and Sethia complement their result by proving that, when
529:
Every allocation which gives an item to each agent is MMS-fair.
518:
Bob values the items as 3,2,1. For him, MMS=1, PFS=2 and mFS=3.
119:
for more examples). There are two problems with this approach:
4089:"Picking sequences and monotonicity in weighted fair division"
1780:{\displaystyle E_{i}\colon {\mathcal {D}}\to \mathbb {R} _{+}}
1726:{\displaystyle u_{i}\colon {\mathcal {A}}\to \mathbb {R} _{+}}
4460:
Proceedings of the AAAI Conference on Artificial Intelligence
4290:. Leibniz International Proceedings in Informatics (LIPIcs).
4150:
Proceedings of the AAAI Conference on Artificial Intelligence
3902:
Proceedings of the AAAI Conference on Artificial Intelligence
3649:"Maximin fairness with mixed divisible and indivisible goods"
4336:
Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (2018-06-11).
2731:
2682:
2629:
2502:
2413:
2332:
2171:
2061:
2019:
1966:
1859:
1757:
1703:
1631:
1592:
1560:
1533:
1309:
965:
Bhaskar, Sricharan and Vaish study a mixture of indivisible
4146:"Weighted Fairness Notions for Indivisible Items Revisited"
555:
an EF allocation may be not proportional and even not MMS.
3848:
Li, Bo; Li, Zihao; Liu, Shengxin; Wu, Zekai (2024-04-28),
1126:
items can be selected. This variant is closely related to
957:
Bei, Liu, Lu and Wang study the same setting, focusing on
709:, but its exact computational complexity is still unknown.
3702:
DROPS-IDN/V2/Document/10.4230/LIPIcs.APPROX/RANDOM.2021.1
1231:
Common solution concepts for public goods allocation are
856:
cuts. But sharing minimization is NP-hard: for any fixed
126:
The number of possible bundles can be huge: if there are
3608:"Fair division of mixed divisible and indivisible goods"
515:
Alice values the items as 2,2,2. For her, MMS=PFS=mFS=2.
4032:"Weighted Envy-freeness in Indivisible Item Allocation"
3824:
Bei, Xiaohui; Liu, Shengxin; Lu, Xinhang (2023-10-02),
3696:
Bhaskar, Umang; Sricharan, A. R.; Vaish, Rohit (2021).
387:
against adversarial opponents. An allocation is called
93:
Based on the preferences and the fairness criterion, a
2842:
3704:. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
2834:
2654:
2613:
2297:
2270:
2143:
1991:
1950:
1823:
1793:
1741:
1687:
1557:
1530:
1306:
1082:
Proportional cake-cutting with different entitlements
682:
480:
445:
191:
152:
132:
3551:
SOFSEM 2021: Theory and Practice of Computer Science
3448:
Sandomirskiy, Fedor; Segal-Halevi, Erel (May 2022).
3079:
Sylvain Bouveret; Ulle Endriss; Jérôme Lang (2010).
75:
An item assignment problem has several ingredients:
3874:
A Complete Landscape for the Price of Envy-Freeness
3733:. IJCAI '23. Macao, P.R.China. pp. 2808–2816.
3057:Barberà, S.; Bossert, W.; Pattanaik, P. K. (2004).
2133:. The reason is that the utilitarian value of the
2855:
2791:
2636:
2586:
2283:
2256:
2121:
1973:
1909:
1806:
1779:
1725:
1668:
1540:
1513:
1070:Notions based on weighted competitive equilibrium;
701:
494:
459:
204:
165:
138:
3352:Annals of Mathematics and Artificial Intelligence
3315:The Unreasonable Fairness of Maximum Nash Welfare
1216:essentially represents the decision to give item
101:These ingredients are explained in detail below.
4013:"Competitive Equilibrium For almost All Incomes"
3547:"Fair Division is Hard Even for Amicable Agents"
2980:Demko, Stephen; Hill, Theodore P. (1988-10-01).
2691:
2490:
506:. This is illustrated in the following example:
97:should be executed to calculate a fair division.
3776:Nishimura, Koichi; Sumita, Hanna (2023-08-13),
2982:"Equitable distribution of indivisible objects"
2821:is NP-hard even when agents' utilities are all
1095:With groups, it may be impossible to guarantee
1016:agents, for both scaled and unscaled utilities.
3450:"Efficient Fair Division with Minimal Sharing"
1031:Are there efficient algorithms for maximizing
924:is not fixed, the problem is strongly NP-hard.
888:is smaller than the worst-case upper bound of
339:: each partner describes some bundles using a
313:(Conditional Preferences) and its extensions:
227:Under suitable assumptions, it is possible to
4338:"Fair Allocation of Indivisible Public Goods"
4036:ACM Transactions on Economics and Computation
402:The proportional-fair-share of an agent is 1/
284:combinatorial utilities). Some examples are:
8:
2942:- a fair division problem in which seats in
1663:
1568:
1508:
1317:
719:Efficient approximately fair item allocation
255:In the cardinal approach, each agent has an
3307:
3305:
1282:over the set of deterministic allocations.
1276:Stochastic allocations of indivisible goods
1271:Stochastic allocations of indivisible goods
281:Compact preference representation languages
276:Compact preference representation languages
3826:Fair Division with Subjective Divisibility
3761:: CS1 maint: location missing publisher (
3019:
3017:
3015:
929:Mixture of divisible and indivisible goods
4471:
4429:
4390:
4299:
4237:
4208:
4171:
4161:
4104:
4047:
3995:
3966:
3913:
3881:
3857:
3833:
3809:
3785:
3709:
3664:
3653:Autonomous Agents and Multi-Agent Systems
3623:
3591:
3513:
3465:
3397:Autonomous Agents and Multi-Agent Systems
3363:
3241:
3195:Autonomous Agents and Multi-Agent Systems
3152:
2841:
2833:
2769:
2747:
2730:
2729:
2722:
2694:
2681:
2680:
2668:
2659:
2653:
2628:
2627:
2618:
2612:
2569:
2559:
2548:
2519:
2514:
2501:
2500:
2493:
2471:
2461:
2450:
2429:
2424:
2412:
2411:
2404:
2377:
2353:
2348:
2331:
2330:
2323:
2313:
2302:
2296:
2275:
2269:
2239:
2229:
2218:
2188:
2183:
2170:
2169:
2157:
2148:
2142:
2099:
2077:
2060:
2059:
2052:
2042:
2031:
2018:
2017:
2005:
1996:
1990:
1965:
1964:
1955:
1949:
1892:
1870:
1858:
1857:
1850:
1828:
1822:
1798:
1792:
1771:
1767:
1766:
1756:
1755:
1746:
1740:
1717:
1713:
1712:
1702:
1701:
1692:
1686:
1642:
1630:
1629:
1622:
1591:
1590:
1581:
1559:
1558:
1556:
1532:
1531:
1529:
1490:
1480:
1469:
1449:
1436:
1383:
1346:
1327:
1308:
1307:
1305:
690:
681:
526:The possible allocations are as follows:
484:
479:
449:
444:
196:
190:
157:
151:
131:
37:problem in which the items to divide are
3545:Misra, Neeldhara; Sethia, Aditi (2021).
2807:, while in the stochastic setting it is
1186:, construct a public-goods problem with
1073:Notions based on weighted envy-freeness;
844:sharings, and for computing a consensus
512:There are three agents and three items:
4454:Kawase, Yasushi; Sumita, Hanna (2020).
3430:Trung Thanh Nguyen; Jörg Rothe (2013).
3271:
3269:
3028:Handbook of Computational Social Choice
2972:
2637:{\displaystyle d^{*}\in {\mathcal {D}}}
1974:{\displaystyle d^{*}\in {\mathcal {D}}}
880:, and also the more general setting of
177:The first problem motivates the use of
4449:
4447:
4445:
4443:
4441:
3754:
3188:
3186:
3184:
3182:
3180:
1926:
604:evaluates a division based on a given
117:Utility functions on indivisible goods
4331:
4329:
4277:
4275:
4273:
3495:
3493:
3443:
3441:
2264:is at least the utilitarian value of
1076:Notions based on weighted fair share;
900:−2; but for shared objects and
7:
1289:items should be distributed between
3711:10.4230/LIPIcs.APPROX/RANDOM.2021.1
2863:even when all agents have the same
1008:Li, Liu, Lu, Tao and Tao study the
984:Kawase, Nishimura and Sumita study
904:≥ 3, the problem is polynomial for
836:. They prove that, for agents with
569:Envy-freeness-except-cheapest (EFx)
79:The partners have to express their
3584:Number Partitioning with Splitting
3502:Mathematics of Operations Research
3118:10.1023/B:THEO.0000024421.85722.0a
1458:
1405:
1358:
419:I choose first”. An allocation is
25:
4011:Segal-Halevi, Erel (2018-07-09).
2946:should be divided among students.
2856:{\displaystyle 1-{\tfrac {1}{e}}}
748:Between divisible and indivisible
3947:Journal of Theoretical Politics
3898:"Mixed Fair Division: A Survey"
1464:
1404:
1212:and the other items at 0. Item
912:−2 and NP-hard for any
558:Weaker versions of EF include:
83:for the different item-bundles.
3031:. Cambridge University Press.
2781:
2775:
2759:
2753:
2581:
2575:
2533:
2527:
2483:
2477:
2443:
2437:
2389:
2383:
2367:
2361:
2251:
2245:
2202:
2196:
2111:
2105:
2089:
2083:
1904:
1898:
1882:
1876:
1840:
1834:
1762:
1708:
1654:
1648:
1612:
1600:
1597:
1541:{\displaystyle {\mathcal {A}}}
1505:
1499:
1426:
1420:
1398:
1392:
1373:
1367:
1352:
1320:
992:(this is a generalization off
757:Bounding the amount of sharing
370:individual guarantee criterion
1:
4301:10.4230/LIPIcs.FSTTCS.2021.22
2910:indivisible chores allocation
878:Identical-machines scheduling
819:Fractionally Pareto efficient
661:Maximin-share item allocation
602:global optimization criterion
364:Individual guarantee criteria
333:(a simplification of CI net).
329:(Conditional Importance) and
267:{x,y} or even {w,z} to {x,y}.
86:The group should decide on a
4248:10.1016/j.artint.2019.103167
4115:10.1016/j.artint.2021.103578
3634:10.1016/j.artint.2020.103436
3559:10.1007/978-3-030-67731-2_31
3286:10.1007/978-3-319-23114-3_31
3230:Journal of Political Economy
2998:10.1016/0165-4896(88)90047-9
2986:Mathematical Social Sciences
2961:17-animal inheritance puzzle
2906:indivisible goods allocation
954:-approximate EFM allocation.
667:Proportional item allocation
596:Global optimization criteria
563:Envy-freeness-except-1 (EF1)
53:White elephant gift exchange
4385:. {ACM}. pp. 629–646.
3278:Algorithmic Decision Theory
1787:which defined according to
1250:Round-robin item allocation
994:Egalitarian item allocation
882:Uniform-machines scheduling
725:Egalitarian item allocation
295:for every positive integer
4518:
3675:10.1007/s10458-021-09517-7
3066:Handbook of utility theory
3059:"Ranking sets of objects."
1254:
1113:Allocation of public goods
1108:Fair division among groups
1105:
1079:
1040:Robertson–Webb query model
1033:Utilitarian social welfare
972:Li, Liu, Lu and Tao study
535:No allocation is mFS-fair.
4017:Proceedings of AAMAS 2018
3924:10.1609/aaai.v38i20.30274
3409:10.1007/s10458-013-9224-2
3374:10.1007/s10472-012-9328-4
3207:10.1007/s10458-015-9287-3
2916:Fair division experiments
1681:deterministic allocation
713:Envy-free item allocation
583:from Equal Incomes (CEEI)
110:Combinatorial preferences
95:fair assignment algorithm
4473:10.1609/AAAI.V34I02.5580
4173:10.1609/aaai.v36i5.20425
3959:10.1177/0951629804041118
3163:10.1177/1043463105058317
2934:House allocation problem
2131:deterministic allocation
1280:probability distribution
848:-division with at most (
414:Min-max fair-share (mFS)
4401:10.1145/3033274.3085125
4350:10.1145/3219166.3219174
4226:Artificial Intelligence
4093:Artificial Intelligence
3739:10.24963/ijcai.2023/313
3612:Artificial Intelligence
3327:10.1145/2940716.2940726
3141:Rationality and Society
2956:Fair subset sum problem
1135:participatory budgeting
1056:Variants and extensions
1024:Is EFM compatible with
702:{\displaystyle NP^{NP}}
606:social welfare function
581:Competitive equilibrium
259:function (also called:
3524:10.1287/moor.2021.1249
3476:10.1287/opre.2022.2279
2928:Fair random assignment
2857:
2793:
2638:
2588:
2564:
2466:
2318:
2285:
2258:
2234:
2123:
2047:
1975:
1911:
1808:
1781:
1727:
1670:
1542:
1515:
1239:Public decision making
1061:Different entitlements
1035:among EFM allocations?
703:
496:
461:
352:combinatorial auctions
293:k-additive preferences
289:2-additive preferences
206:
167:
140:
2858:
2794:
2639:
2589:
2544:
2446:
2298:
2286:
2284:{\displaystyle d^{*}}
2259:
2214:
2124:
2027:
1976:
1912:
1809:
1807:{\displaystyle u_{i}}
1782:
1728:
1671:
1543:
1516:
1147:There may be general
704:
652:Allocation algorithms
497:
469:superadditive utility
462:
432:For every agent with
337:Logic based languages
207:
205:{\displaystyle 2^{m}}
168:
166:{\displaystyle 2^{m}}
146:items then there are
141:
4502:Fair item allocation
2898:Bin covering problem
2832:
2652:
2611:
2295:
2268:
2141:
1989:
1948:
1821:
1791:
1739:
1685:
1555:
1528:
1304:
1228:optimal allocation.
1157:knapsack constraints
1153:matching constraints
1087:Allocation to groups
680:
638:Maximum-Nash-Welfare
478:
443:
235:Additive preferences
189:
150:
130:
31:Fair item allocation
18:Fair item assignment
3908:(20): 22641–22649.
3454:Operations Research
3106:Theory and Decision
3045:free online version
2902:Bin packing problem
2875:utilitarian welfare
2819:eqalitarian welfare
2646:egalitarian walfare
2644:that maximizes the
1983:utilitarian walfare
1981:that maximizes the
1485:
1262:Repeated allocation
1196:items, where agent
1171:items, where agent
1149:matroid constraints
1101:democratic fairness
974:truthful mechanisms
834:consensus splitting
795:Consensus splitting
618:egalitarian-optimal
495:{\displaystyle 1/n}
460:{\displaystyle 1/n}
436:, the mFS is worth
434:subadditive utility
249:complementary goods
70:time-based rotation
3618:103436. Elsevier.
2944:university courses
2865:submodular utility
2853:
2851:
2789:
2737:
2717:
2688:
2634:
2584:
2543:
2419:
2338:
2281:
2254:
2212:
2119:
2067:
2025:
1971:
1907:
1865:
1804:
1777:
1723:
1666:
1637:
1538:
1511:
1465:
1257:multi-issue voting
1159:on the chosen set.
1128:multiwinner voting
1097:unanimous fairness
838:additive utilities
699:
623:leximin-optimality
492:
471:, the MMSis worth
457:
202:
163:
136:
88:fairness criterion
4410:978-1-4503-4527-9
4359:978-1-4503-5829-3
4311:978-3-95977-215-0
4042:(3): 18:1–18:39.
3748:978-1-956792-03-4
3568:978-3-030-67731-2
3295:978-3-319-23113-6
2950:Price of fairness
2940:Course allocation
2850:
2718:
2690:
2669:
2597:Egalitarian rule:
2489:
2400:
2319:
2158:
2048:
2006:
1921:Fairness criteria
1846:
1618:
1200:values each item
1026:Pareto-efficiency
1010:price of fairness
590:Pareto efficiency
385:divide and choose
359:Fairness criteria
348:Bidding languages
341:first order logic
243:(so they are not
241:independent goods
139:{\displaystyle m}
66:monetary payments
62:fair cake-cutting
33:is a kind of the
16:(Redirected from
4509:
4486:
4485:
4475:
4466:(2): 2070–2078.
4451:
4436:
4435:
4433:
4421:
4415:
4414:
4394:
4378:
4372:
4371:
4333:
4324:
4323:
4303:
4279:
4268:
4267:
4241:
4221:
4215:
4214:
4212:
4200:
4194:
4193:
4175:
4165:
4156:(5): 4949–4956.
4141:
4135:
4134:
4108:
4084:
4078:
4077:
4051:
4027:
4021:
4020:
4008:
4002:
4001:
3999:
3987:
3981:
3980:
3970:
3942:
3936:
3935:
3917:
3893:
3887:
3886:
3885:
3869:
3863:
3862:
3861:
3845:
3839:
3838:
3837:
3821:
3815:
3814:
3813:
3797:
3791:
3790:
3789:
3773:
3767:
3766:
3760:
3752:
3722:
3716:
3715:
3713:
3693:
3687:
3686:
3668:
3644:
3638:
3637:
3627:
3603:
3597:
3596:
3595:
3579:
3573:
3572:
3542:
3536:
3535:
3517:
3508:(4): 3357–3379.
3497:
3488:
3487:
3469:
3460:(3): 1762–1782.
3445:
3436:
3435:
3427:
3421:
3420:
3392:
3386:
3385:
3367:
3347:
3341:
3340:
3320:
3309:
3300:
3299:
3273:
3264:
3263:
3245:
3236:(6): 1061–1103.
3225:
3219:
3218:
3190:
3175:
3174:
3156:
3136:
3130:
3129:
3101:
3095:
3094:
3092:
3090:
3076:
3070:
3069:
3063:
3054:
3048:
3042:
3021:
3010:
3009:
2977:
2884:
2880:
2862:
2860:
2859:
2854:
2852:
2843:
2810:
2806:
2802:
2798:
2796:
2795:
2790:
2788:
2784:
2774:
2773:
2752:
2751:
2736:
2735:
2734:
2716:
2689:
2687:
2686:
2685:
2664:
2663:
2643:
2641:
2640:
2635:
2633:
2632:
2623:
2622:
2593:
2591:
2590:
2585:
2574:
2573:
2563:
2558:
2542:
2526:
2525:
2524:
2523:
2506:
2505:
2476:
2475:
2465:
2460:
2436:
2435:
2434:
2433:
2418:
2417:
2416:
2396:
2392:
2382:
2381:
2360:
2359:
2358:
2357:
2337:
2336:
2335:
2317:
2312:
2290:
2288:
2287:
2282:
2280:
2279:
2263:
2261:
2260:
2255:
2244:
2243:
2233:
2228:
2213:
2211:
2195:
2194:
2193:
2192:
2175:
2174:
2153:
2152:
2128:
2126:
2125:
2120:
2118:
2114:
2104:
2103:
2082:
2081:
2066:
2065:
2064:
2046:
2041:
2026:
2024:
2023:
2022:
2001:
2000:
1980:
1978:
1977:
1972:
1970:
1969:
1960:
1959:
1934:Utilitarian rule
1916:
1914:
1913:
1908:
1897:
1896:
1875:
1874:
1864:
1863:
1862:
1833:
1832:
1813:
1811:
1810:
1805:
1803:
1802:
1786:
1784:
1783:
1778:
1776:
1775:
1770:
1761:
1760:
1751:
1750:
1734:
1732:
1730:
1729:
1724:
1722:
1721:
1716:
1707:
1706:
1697:
1696:
1675:
1673:
1672:
1667:
1647:
1646:
1636:
1635:
1634:
1596:
1595:
1586:
1585:
1564:
1563:
1547:
1545:
1544:
1539:
1537:
1536:
1520:
1518:
1517:
1512:
1495:
1494:
1484:
1479:
1454:
1453:
1441:
1440:
1388:
1387:
1351:
1350:
1332:
1331:
1313:
1312:
1296:
1292:
1288:
1195:
1142:agreeable subset
734:Picking sequence
708:
706:
705:
700:
698:
697:
646:Pareto efficient
504:additive utility
501:
499:
498:
493:
488:
466:
464:
463:
458:
453:
398:fair-share (PFS)
303:Graphical models
257:additive utility
245:substitute goods
211:
209:
208:
203:
201:
200:
183:cardinal utility
172:
170:
169:
164:
162:
161:
145:
143:
142:
137:
21:
4517:
4516:
4512:
4511:
4510:
4508:
4507:
4506:
4492:
4491:
4490:
4489:
4453:
4452:
4439:
4423:
4422:
4418:
4411:
4380:
4379:
4375:
4360:
4335:
4334:
4327:
4312:
4281:
4280:
4271:
4223:
4222:
4218:
4202:
4201:
4197:
4143:
4142:
4138:
4086:
4085:
4081:
4058:10.1145/3457166
4029:
4028:
4024:
4010:
4009:
4005:
3989:
3988:
3984:
3944:
3943:
3939:
3895:
3894:
3890:
3871:
3870:
3866:
3847:
3846:
3842:
3823:
3822:
3818:
3799:
3798:
3794:
3775:
3774:
3770:
3753:
3749:
3724:
3723:
3719:
3695:
3694:
3690:
3646:
3645:
3641:
3605:
3604:
3600:
3581:
3580:
3576:
3569:
3544:
3543:
3539:
3499:
3498:
3491:
3447:
3446:
3439:
3429:
3428:
3424:
3394:
3393:
3389:
3365:10.1.1.671.3497
3349:
3348:
3344:
3337:
3318:
3311:
3310:
3303:
3296:
3275:
3274:
3267:
3243:10.1.1.357.9766
3227:
3226:
3222:
3192:
3191:
3178:
3154:10.1.1.118.9114
3138:
3137:
3133:
3103:
3102:
3098:
3088:
3086:
3078:
3077:
3073:
3061:
3056:
3055:
3051:
3039:
3024:
3022:
3013:
2979:
2978:
2974:
2969:
2894:
2882:
2878:
2830:
2829:
2824:budget-additive
2808:
2804:
2800:
2765:
2743:
2742:
2738:
2673:
2655:
2650:
2649:
2614:
2609:
2608:
2565:
2515:
2510:
2467:
2425:
2420:
2373:
2349:
2344:
2343:
2339:
2293:
2292:
2271:
2266:
2265:
2235:
2184:
2179:
2162:
2144:
2139:
2138:
2095:
2073:
2072:
2068:
2010:
1992:
1987:
1986:
1951:
1946:
1945:
1923:
1888:
1866:
1824:
1819:
1818:
1794:
1789:
1788:
1765:
1742:
1737:
1736:
1711:
1688:
1683:
1682:
1680:
1638:
1577:
1553:
1552:
1526:
1525:
1486:
1445:
1432:
1379:
1342:
1323:
1302:
1301:
1294:
1290:
1286:
1273:
1264:
1259:
1241:
1209:
1187:
1184:
1115:
1110:
1089:
1084:
1063:
1058:
990:convex function
931:
920:−3. When
759:
750:
686:
678:
677:
654:
598:
585:
552:
476:
475:
441:
440:
416:
400:
381:
366:
361:
278:
237:
192:
187:
186:
179:ordinal utility
153:
148:
147:
128:
127:
112:
107:
28:
23:
22:
15:
12:
11:
5:
4515:
4513:
4505:
4504:
4494:
4493:
4488:
4487:
4437:
4416:
4409:
4373:
4358:
4325:
4310:
4269:
4216:
4195:
4136:
4079:
4022:
4003:
3982:
3937:
3888:
3864:
3840:
3816:
3792:
3768:
3747:
3717:
3688:
3639:
3598:
3574:
3567:
3537:
3489:
3437:
3422:
3387:
3358:(1–3): 65–90.
3342:
3335:
3301:
3294:
3265:
3252:10.1086/664613
3220:
3176:
3147:(4): 387–421.
3131:
3096:
3071:
3068:. Springer US.
3049:
3037:
3011:
2992:(2): 145–158.
2971:
2970:
2968:
2965:
2964:
2963:
2958:
2953:
2947:
2937:
2931:
2925:
2922:Rental harmony
2919:
2913:
2893:
2890:
2889:
2888:
2887:
2886:
2868:
2849:
2846:
2840:
2837:
2787:
2783:
2780:
2777:
2772:
2768:
2764:
2761:
2758:
2755:
2750:
2746:
2741:
2733:
2728:
2725:
2721:
2715:
2712:
2709:
2706:
2703:
2700:
2697:
2693:
2684:
2679:
2676:
2672:
2667:
2662:
2658:
2631:
2626:
2621:
2617:
2594:
2583:
2580:
2577:
2572:
2568:
2562:
2557:
2554:
2551:
2547:
2541:
2538:
2535:
2532:
2529:
2522:
2518:
2513:
2509:
2504:
2499:
2496:
2492:
2488:
2485:
2482:
2479:
2474:
2470:
2464:
2459:
2456:
2453:
2449:
2445:
2442:
2439:
2432:
2428:
2423:
2415:
2410:
2407:
2403:
2399:
2395:
2391:
2388:
2385:
2380:
2376:
2372:
2369:
2366:
2363:
2356:
2352:
2347:
2342:
2334:
2329:
2326:
2322:
2316:
2311:
2308:
2305:
2301:
2278:
2274:
2253:
2250:
2247:
2242:
2238:
2232:
2227:
2224:
2221:
2217:
2210:
2207:
2204:
2201:
2198:
2191:
2187:
2182:
2178:
2173:
2168:
2165:
2161:
2156:
2151:
2147:
2117:
2113:
2110:
2107:
2102:
2098:
2094:
2091:
2088:
2085:
2080:
2076:
2071:
2063:
2058:
2055:
2051:
2045:
2040:
2037:
2034:
2030:
2021:
2016:
2013:
2009:
2004:
1999:
1995:
1968:
1963:
1958:
1954:
1922:
1919:
1918:
1917:
1906:
1903:
1900:
1895:
1891:
1887:
1884:
1881:
1878:
1873:
1869:
1861:
1856:
1853:
1849:
1845:
1842:
1839:
1836:
1831:
1827:
1801:
1797:
1774:
1769:
1764:
1759:
1754:
1749:
1745:
1720:
1715:
1710:
1705:
1700:
1695:
1691:
1677:
1676:
1665:
1662:
1659:
1656:
1653:
1650:
1645:
1641:
1633:
1628:
1625:
1621:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1594:
1589:
1584:
1580:
1576:
1573:
1570:
1567:
1562:
1535:
1522:
1521:
1510:
1507:
1504:
1501:
1498:
1493:
1489:
1483:
1478:
1475:
1472:
1468:
1463:
1460:
1457:
1452:
1448:
1444:
1439:
1435:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1403:
1400:
1397:
1394:
1391:
1386:
1382:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1349:
1345:
1341:
1338:
1335:
1330:
1326:
1322:
1319:
1316:
1311:
1272:
1269:
1263:
1260:
1240:
1237:
1233:core stability
1207:
1182:
1161:
1160:
1145:
1138:
1131:
1114:
1111:
1088:
1085:
1078:
1077:
1074:
1071:
1062:
1059:
1057:
1054:
1053:
1052:
1049:
1046:
1043:
1036:
1029:
1018:
1017:
1006:
1002:
998:
982:
978:
970:
963:
955:
930:
927:
926:
925:
874:
830:
822:
811:
810:
791:
758:
755:
749:
746:
745:
744:
737:
731:
728:
722:
716:
710:
696:
693:
689:
685:
670:
664:
653:
650:
642:
641:
626:
597:
594:
584:
578:
577:
576:
566:
551:
545:
541:
540:
539:
538:
537:
536:
533:
530:
524:
523:
522:
519:
516:
491:
487:
483:
456:
452:
448:
415:
412:
399:
393:
380:
375:
365:
362:
360:
357:
356:
355:
345:
334:
300:
277:
274:
269:
268:
264:
236:
233:
225:
224:
221:
199:
195:
175:
174:
160:
156:
135:
124:
111:
108:
106:
103:
99:
98:
91:
84:
57:
56:
50:
47:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
4514:
4503:
4500:
4499:
4497:
4483:
4479:
4474:
4469:
4465:
4461:
4457:
4450:
4448:
4446:
4444:
4442:
4438:
4432:
4427:
4420:
4417:
4412:
4406:
4402:
4398:
4393:
4388:
4384:
4377:
4374:
4369:
4365:
4361:
4355:
4351:
4347:
4343:
4339:
4332:
4330:
4326:
4321:
4317:
4313:
4307:
4302:
4297:
4293:
4289:
4285:
4278:
4276:
4274:
4270:
4265:
4261:
4257:
4253:
4249:
4245:
4240:
4235:
4231:
4227:
4220:
4217:
4211:
4206:
4199:
4196:
4191:
4187:
4183:
4179:
4174:
4169:
4164:
4159:
4155:
4151:
4147:
4140:
4137:
4132:
4128:
4124:
4120:
4116:
4112:
4107:
4102:
4098:
4094:
4090:
4083:
4080:
4075:
4071:
4067:
4063:
4059:
4055:
4050:
4045:
4041:
4037:
4033:
4026:
4023:
4018:
4014:
4007:
4004:
3998:
3993:
3986:
3983:
3978:
3974:
3969:
3964:
3960:
3956:
3952:
3948:
3941:
3938:
3933:
3929:
3925:
3921:
3916:
3911:
3907:
3903:
3899:
3892:
3889:
3884:
3879:
3875:
3868:
3865:
3860:
3855:
3851:
3844:
3841:
3836:
3831:
3827:
3820:
3817:
3812:
3807:
3803:
3796:
3793:
3788:
3783:
3779:
3772:
3769:
3764:
3758:
3750:
3744:
3740:
3736:
3732:
3728:
3721:
3718:
3712:
3707:
3703:
3699:
3692:
3689:
3684:
3680:
3676:
3672:
3667:
3662:
3658:
3654:
3650:
3643:
3640:
3635:
3631:
3626:
3621:
3617:
3613:
3609:
3602:
3599:
3594:
3589:
3585:
3578:
3575:
3570:
3564:
3560:
3556:
3552:
3548:
3541:
3538:
3533:
3529:
3525:
3521:
3516:
3511:
3507:
3503:
3496:
3494:
3490:
3485:
3481:
3477:
3473:
3468:
3463:
3459:
3455:
3451:
3444:
3442:
3438:
3433:
3426:
3423:
3418:
3414:
3410:
3406:
3402:
3398:
3391:
3388:
3383:
3379:
3375:
3371:
3366:
3361:
3357:
3353:
3346:
3343:
3338:
3336:9781450339360
3332:
3328:
3324:
3317:
3316:
3308:
3306:
3302:
3297:
3291:
3287:
3283:
3279:
3272:
3270:
3266:
3261:
3257:
3253:
3249:
3244:
3239:
3235:
3231:
3224:
3221:
3216:
3212:
3208:
3204:
3200:
3196:
3189:
3187:
3185:
3183:
3181:
3177:
3172:
3168:
3164:
3160:
3155:
3150:
3146:
3142:
3135:
3132:
3127:
3123:
3119:
3115:
3111:
3107:
3100:
3097:
3084:
3083:
3075:
3072:
3067:
3060:
3053:
3050:
3046:
3040:
3038:9781107060432
3034:
3030:
3029:
3020:
3018:
3016:
3012:
3007:
3003:
2999:
2995:
2991:
2987:
2983:
2976:
2973:
2966:
2962:
2959:
2957:
2954:
2951:
2948:
2945:
2941:
2938:
2935:
2932:
2929:
2926:
2923:
2920:
2917:
2914:
2911:
2907:
2903:
2899:
2896:
2895:
2891:
2876:
2872:
2869:
2866:
2847:
2844:
2838:
2835:
2827:
2825:
2820:
2816:
2813:
2812:
2785:
2778:
2770:
2766:
2762:
2756:
2748:
2744:
2739:
2726:
2723:
2719:
2713:
2710:
2707:
2704:
2701:
2698:
2695:
2677:
2674:
2670:
2665:
2660:
2656:
2647:
2624:
2619:
2615:
2606:
2602:
2598:
2595:
2578:
2570:
2566:
2560:
2555:
2552:
2549:
2545:
2539:
2536:
2530:
2520:
2516:
2511:
2507:
2497:
2494:
2486:
2480:
2472:
2468:
2462:
2457:
2454:
2451:
2447:
2440:
2430:
2426:
2421:
2408:
2405:
2401:
2397:
2393:
2386:
2378:
2374:
2370:
2364:
2354:
2350:
2345:
2340:
2327:
2324:
2320:
2314:
2309:
2306:
2303:
2299:
2276:
2272:
2248:
2240:
2236:
2230:
2225:
2222:
2219:
2215:
2208:
2205:
2199:
2189:
2185:
2180:
2176:
2166:
2163:
2159:
2154:
2149:
2145:
2136:
2135:deterministic
2132:
2115:
2108:
2100:
2096:
2092:
2086:
2078:
2074:
2069:
2056:
2053:
2049:
2043:
2038:
2035:
2032:
2028:
2014:
2011:
2007:
2002:
1997:
1993:
1984:
1961:
1956:
1952:
1943:
1939:
1935:
1932:
1931:
1930:
1928:
1927:same criteria
1920:
1901:
1893:
1889:
1885:
1879:
1871:
1867:
1854:
1851:
1847:
1843:
1837:
1829:
1825:
1817:
1816:
1815:
1799:
1795:
1772:
1752:
1747:
1743:
1718:
1698:
1693:
1689:
1660:
1657:
1651:
1643:
1639:
1626:
1623:
1619:
1615:
1609:
1606:
1603:
1587:
1582:
1578:
1574:
1571:
1565:
1551:
1550:
1549:
1502:
1496:
1491:
1487:
1481:
1476:
1473:
1470:
1466:
1461:
1455:
1450:
1446:
1442:
1437:
1433:
1429:
1423:
1417:
1414:
1411:
1408:
1401:
1395:
1389:
1384:
1380:
1376:
1370:
1364:
1361:
1355:
1347:
1343:
1339:
1336:
1333:
1328:
1324:
1314:
1300:
1299:
1298:
1283:
1281:
1277:
1270:
1268:
1261:
1258:
1253:
1251:
1247:
1238:
1236:
1234:
1229:
1227:
1223:
1219:
1215:
1211:
1203:
1199:
1194:
1190:
1185:
1178:
1174:
1170:
1166:
1158:
1154:
1150:
1146:
1143:
1139:
1136:
1132:
1129:
1125:
1121:
1120:
1119:
1112:
1109:
1104:
1102:
1098:
1093:
1086:
1083:
1075:
1072:
1069:
1068:
1067:
1060:
1055:
1050:
1047:
1044:
1041:
1037:
1034:
1030:
1027:
1023:
1022:
1021:
1015:
1011:
1007:
1003:
999:
995:
991:
987:
983:
979:
975:
971:
968:
964:
960:
959:maximin-share
956:
953:
949:
945:
941:
940:envy-freeness
937:
933:
932:
928:
923:
919:
915:
911:
907:
903:
899:
895:
891:
887:
883:
879:
875:
871:
870:almost surely
868:sharings are
867:
863:
859:
855:
851:
847:
843:
839:
835:
831:
827:
823:
820:
816:
815:
814:
808:
804:
800:
796:
792:
789:
785:
781:
777:
773:
769:
768:
767:
765:
756:
754:
747:
742:
741:Fisher market
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
694:
691:
687:
683:
675:
674:coNP-complete
671:
668:
665:
662:
659:
658:
657:
651:
649:
647:
639:
635:
631:
627:
624:
619:
615:
611:
610:
609:
607:
603:
595:
593:
591:
582:
579:
574:
570:
567:
564:
561:
560:
559:
556:
549:
548:Envy-freeness
546:
544:
534:
531:
528:
527:
525:
520:
517:
514:
513:
511:
510:
509:
508:
507:
505:
489:
485:
481:
474:
470:
454:
450:
446:
439:
435:
430:
427:
422:
413:
411:
409:
405:
397:
394:
392:
390:
386:
379:
378:Maximin share
376:
374:
371:
363:
358:
353:
349:
346:
342:
338:
335:
332:
328:
324:
320:
316:
312:
308:
304:
301:
298:
294:
290:
287:
286:
285:
282:
275:
273:
265:
262:
258:
254:
253:
252:
250:
246:
242:
234:
232:
230:
222:
219:
218:
217:
214:
197:
193:
184:
180:
158:
154:
133:
125:
122:
121:
120:
118:
109:
104:
102:
96:
92:
89:
85:
82:
78:
77:
76:
73:
71:
67:
63:
54:
51:
48:
45:
44:
43:
40:
36:
35:fair division
32:
19:
4463:
4459:
4419:
4382:
4376:
4341:
4291:
4287:
4229:
4225:
4219:
4198:
4153:
4149:
4139:
4096:
4092:
4082:
4039:
4035:
4025:
4016:
4006:
3985:
3950:
3946:
3940:
3905:
3901:
3891:
3873:
3867:
3849:
3843:
3825:
3819:
3801:
3795:
3777:
3771:
3730:
3720:
3701:
3691:
3656:
3652:
3642:
3615:
3611:
3601:
3583:
3577:
3550:
3540:
3505:
3501:
3457:
3453:
3431:
3425:
3400:
3396:
3390:
3355:
3351:
3345:
3314:
3277:
3233:
3229:
3223:
3198:
3194:
3144:
3140:
3134:
3109:
3105:
3099:
3087:. Retrieved
3081:
3074:
3065:
3052:
3027:
2989:
2985:
2975:
2909:
2905:
2877:to a factor
2870:
2822:
2814:
2645:
2604:
2596:
2137:allocation
2134:
1982:
1941:
1933:
1924:
1814:as follows:
1678:
1523:
1285:Assume that
1284:
1275:
1274:
1265:
1245:
1242:
1230:
1221:
1217:
1213:
1205:
1201:
1197:
1192:
1188:
1180:
1176:
1175:values item
1172:
1168:
1164:
1162:
1123:
1116:
1100:
1096:
1094:
1090:
1064:
1019:
1013:
985:
966:
951:
947:
943:
935:
921:
917:
913:
909:
905:
901:
897:
893:
889:
885:
865:
861:
857:
853:
849:
845:
841:
825:
812:
806:
802:
798:
787:
786:allocation,
772:proportional
763:
760:
751:
655:
643:
637:
634:Nash-optimal
633:
629:
622:
617:
613:
601:
599:
586:
572:
568:
562:
557:
553:
542:
472:
437:
431:
425:
420:
417:
408:proportional
407:
403:
401:
396:Proportional
388:
382:
369:
367:
347:
336:
330:
326:
322:
318:
314:
310:
306:
302:
296:
292:
288:
280:
279:
270:
260:
238:
228:
226:
215:
181:rather than
176:
113:
100:
94:
87:
80:
74:
69:
65:
58:
38:
30:
29:
3968:10036/26974
3434:. AAMAS 13.
2607:allocation
1944:allocation
1167:agents and
784:egalitarian
614:egalitarian
105:Preferences
81:preferences
4431:2304.01644
4392:1611.04034
4239:1709.02564
4232:: 103167.
4210:2103.04304
4163:2112.04166
4106:2104.14347
4099:: 103578.
4049:1909.10502
3997:1703.08150
3953:(2): 143.
3915:2306.09564
3883:2401.01516
3859:2404.18132
3835:2310.00976
3811:2306.05986
3787:2302.13342
3666:2002.05245
3625:1911.07048
3593:2204.11753
3515:2007.06754
3467:1908.01669
3403:(2): 256.
3201:(2): 259.
3112:(2): 147.
2967:References
2871:Algorithm:
2605:stochastic
1942:stochastic
1255:See also:
1106:See also:
1080:See also:
251:). Then:
4482:214407880
4320:236154847
4264:203034477
4256:0004-3702
4190:244954009
4182:2374-3468
4131:233443832
4123:0004-3702
4074:202719373
4066:2167-8375
3977:154854134
3932:2374-3468
3757:cite book
3683:1573-7454
3659:(2): 34.
3532:246764981
3484:0030-364X
3360:CiteSeerX
3260:154703357
3238:CiteSeerX
3171:154808734
3149:CiteSeerX
3126:153943630
3089:26 August
3006:0165-4896
2867:function.
2839:−
2815:Hardness:
2763:⋅
2727:∈
2720:∑
2708:…
2678:∈
2661:∗
2625:∈
2620:∗
2546:∑
2521:∗
2508::
2498:∈
2487:≤
2448:∑
2431:∗
2409:∈
2402:∑
2371:⋅
2355:∗
2328:∈
2321:∑
2300:∑
2277:∗
2216:∑
2190:∗
2177::
2167:∈
2150:∗
2093:⋅
2057:∈
2050:∑
2029:∑
2015:∈
1998:∗
1962:∈
1957:∗
1886:⋅
1855:∈
1848:∑
1763:→
1753::
1709:→
1699::
1627:∈
1620:∑
1598:→
1588::
1575:∣
1467:∪
1459:∅
1443:∩
1430::
1418:∈
1412:≠
1406:∀
1390:⊆
1377::
1365:∈
1359:∀
1356:∣
1337:…
1220:to agent
852:−1)
829:sharings.
780:equitable
776:envy-free
323:CP theory
4496:Category
3215:16041218
2892:See also
1144:problem.
1122:At most
766:agents:
438:at least
421:mFS-fair
389:MMS-fair
39:discrete
4368:3331859
3382:6864410
1936:: this
1226:leximin
1191:·
986:optimal
962:values.
952:epsilon
942:called
873:agents.
801:parts,
473:at most
331:SCI net
319:UCP net
315:TCP net
307:GAI net
261:modular
55:parties
4480:
4407:
4366:
4356:
4318:
4308:
4262:
4254:
4188:
4180:
4129:
4121:
4072:
4064:
3975:
3930:
3745:
3681:
3565:
3530:
3482:
3417:442666
3415:
3380:
3362:
3333:
3292:
3258:
3240:
3213:
3169:
3151:
3124:
3035:
3004:
2883:α
2879:α
2671:argmax
2160:argmax
2008:argmax
967:chores
327:CI net
311:CP net
4478:S2CID
4426:arXiv
4387:arXiv
4364:S2CID
4316:S2CID
4260:S2CID
4234:arXiv
4205:arXiv
4186:S2CID
4158:arXiv
4127:S2CID
4101:arXiv
4070:S2CID
4044:arXiv
3992:arXiv
3973:S2CID
3910:arXiv
3878:arXiv
3854:arXiv
3830:arXiv
3806:arXiv
3782:arXiv
3661:arXiv
3620:arXiv
3588:arXiv
3528:S2CID
3510:arXiv
3462:arXiv
3413:S2CID
3378:S2CID
3319:(PDF)
3256:S2CID
3211:S2CID
3167:S2CID
3122:S2CID
3062:(PDF)
2599:this
936:goods
797:into
573:least
4405:ISBN
4354:ISBN
4306:ISBN
4252:ISSN
4178:ISSN
4119:ISSN
4062:ISSN
3928:ISSN
3763:link
3743:ISBN
3679:ISSN
3563:ISBN
3480:ISSN
3331:ISBN
3290:ISBN
3091:2016
3033:ISBN
3002:ISSN
2908:and
2900:and
2601:rule
2537:>
2206:>
1938:rule
1925:The
793:For
782:and
770:For
630:Nash
628:The
612:The
550:(EF)
344:xyz.
247:nor
229:lift
4468:doi
4397:doi
4346:doi
4296:doi
4292:213
4244:doi
4230:277
4168:doi
4111:doi
4097:301
4054:doi
3963:hdl
3955:doi
3920:doi
3735:doi
3706:doi
3671:doi
3630:doi
3616:293
3555:doi
3520:doi
3472:doi
3405:doi
3370:doi
3323:doi
3282:doi
3248:doi
3234:119
3203:doi
3159:doi
3114:doi
2994:doi
2801:100
2692:min
2491:max
1214:i,j
1204:at
1202:i,j
1179:at
1155:or
944:EFM
636:or
426:all
368:An
68:or
4498::
4476:.
4464:34
4462:.
4458:.
4440:^
4403:.
4395:.
4362:.
4352:.
4340:.
4328:^
4314:.
4304:.
4286:.
4272:^
4258:.
4250:.
4242:.
4228:.
4184:.
4176:.
4166:.
4154:36
4152:.
4148:.
4125:.
4117:.
4109:.
4095:.
4091:.
4068:.
4060:.
4052:.
4038:.
4034:.
4015:.
3971:.
3961:.
3951:16
3949:.
3926:.
3918:.
3906:38
3904:.
3900:.
3876:,
3852:,
3828:,
3804:,
3780:,
3759:}}
3755:{{
3741:.
3729:.
3700:.
3677:.
3669:.
3657:35
3655:.
3651:.
3628:.
3614:.
3610:.
3586:,
3561:.
3526:.
3518:.
3506:47
3504:.
3492:^
3478:.
3470:.
3458:70
3456:.
3452:.
3440:^
3411:.
3401:28
3399:.
3376:.
3368:.
3356:68
3354:.
3329:.
3304:^
3288:.
3268:^
3254:.
3246:.
3232:.
3209:.
3199:30
3197:.
3179:^
3165:.
3157:.
3145:17
3143:.
3120:.
3110:55
3108:.
3064:.
3014:^
3000:.
2990:16
2988:.
2984:.
2811:.
2809:50
2648::
2291::
1985::
1252:.
1208:ij
1183:ij
1151:,
916:≤
908:=
896:≤
778:,
774:,
648:.
608::
600:A
592:.
325:,
321:,
317:,
4484:.
4470::
4434:.
4428::
4413:.
4399::
4389::
4370:.
4348::
4322:.
4298::
4266:.
4246::
4236::
4213:.
4207::
4192:.
4170::
4160::
4133:.
4113::
4103::
4076:.
4056::
4046::
4040:9
4000:.
3994::
3979:.
3965::
3957::
3934:.
3922::
3912::
3880::
3856::
3832::
3808::
3784::
3765:)
3751:.
3737::
3714:.
3708::
3685:.
3673::
3663::
3636:.
3632::
3622::
3590::
3571:.
3557::
3534:.
3522::
3512::
3486:.
3474::
3464::
3419:.
3407::
3384:.
3372::
3339:.
3325::
3298:.
3284::
3262:.
3250::
3217:.
3205::
3173:.
3161::
3128:.
3116::
3093:.
3047:)
3043:(
3041:.
3008:.
2996::
2885:.
2848:e
2845:1
2836:1
2826:;
2805:0
2786:)
2782:)
2779:A
2776:(
2771:i
2767:u
2760:)
2757:A
2754:(
2749:d
2745:p
2740:(
2732:A
2724:A
2714:n
2711:,
2705:,
2702:1
2699:=
2696:i
2683:D
2675:d
2666:=
2657:d
2630:D
2616:d
2582:)
2579:A
2576:(
2571:i
2567:u
2561:n
2556:1
2553:=
2550:i
2540:0
2534:)
2531:A
2528:(
2517:d
2512:p
2503:A
2495:A
2484:)
2481:A
2478:(
2473:i
2469:u
2463:n
2458:1
2455:=
2452:i
2444:)
2441:A
2438:(
2427:d
2422:p
2414:A
2406:A
2398:=
2394:)
2390:)
2387:A
2384:(
2379:i
2375:u
2368:)
2365:A
2362:(
2351:d
2346:p
2341:(
2333:A
2325:A
2315:n
2310:1
2307:=
2304:i
2273:d
2252:)
2249:A
2246:(
2241:i
2237:u
2231:n
2226:1
2223:=
2220:i
2209:0
2203:)
2200:A
2197:(
2186:d
2181:p
2172:A
2164:A
2155:=
2146:A
2116:)
2112:)
2109:A
2106:(
2101:i
2097:u
2090:)
2087:A
2084:(
2079:d
2075:p
2070:(
2062:A
2054:A
2044:n
2039:1
2036:=
2033:i
2020:D
2012:d
2003:=
1994:d
1967:D
1953:d
1905:)
1902:A
1899:(
1894:i
1890:u
1883:)
1880:A
1877:(
1872:d
1868:p
1860:A
1852:A
1844:=
1841:)
1838:d
1835:(
1830:i
1826:E
1800:i
1796:u
1773:+
1768:R
1758:D
1748:i
1744:E
1733:;
1719:+
1714:R
1704:A
1694:i
1690:u
1664:}
1661:1
1658:=
1655:)
1652:A
1649:(
1644:d
1640:p
1632:A
1624:A
1616:,
1613:]
1610:1
1607:,
1604:0
1601:[
1593:A
1583:d
1579:p
1572:d
1569:{
1566:=
1561:D
1534:A
1509:}
1506:]
1503:m
1500:[
1497:=
1492:i
1488:A
1482:n
1477:1
1474:=
1471:i
1462:,
1456:=
1451:j
1447:A
1438:i
1434:A
1427:]
1424:n
1421:[
1415:j
1409:i
1402:,
1399:]
1396:m
1393:[
1385:i
1381:A
1374:]
1371:n
1368:[
1362:i
1353:)
1348:n
1344:A
1340:,
1334:,
1329:1
1325:A
1321:(
1318:{
1315:=
1310:A
1295:n
1291:n
1287:m
1246:n
1222:i
1218:j
1210:,
1206:v
1198:i
1193:m
1189:n
1181:v
1177:j
1173:i
1169:m
1165:n
1137:.
1124:k
1042:?
1028:?
1014:n
948:n
922:n
918:n
914:s
910:n
906:s
902:n
898:n
894:s
890:n
886:s
866:n
862:n
858:n
854:n
850:k
846:k
842:n
826:n
807:n
805:(
803:n
799:k
788:n
764:n
743:.
727:;
721:;
715:;
695:P
692:N
688:P
684:N
669:;
663:;
490:n
486:/
482:1
455:n
451:/
447:1
404:n
299:.
297:k
198:m
194:2
159:m
155:2
134:m
90:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.