1392:
An allocation is fPO if-and-only-if it is non-malicious, and its directed consumption graph as no directed cycle in which the product of weights is smaller than 1. This equivalence was proved for goods in the context of cake-cutting by
Barbanel. It was extended for bads by Branzei and Sandomirskiy.
264:
The following example shows the "price" of fPO. The integral allocation maximizing the product of utilities (also called the Nash welfare) is PE but not fPO. Moreover, the product of utilities in any fPO allocation is at most 1/3 of the maximum product. There are five goods
1805:), then the consumption graph of the resulting allocation is acyclic. Alternatively, it is possible to remove cycles from the resulting consumption graph in polynomial time. They also present an algorithm that converts a fractional fPO+WPROP allocation to a discrete
235:
is (discrete) Pareto-efficient. To see this, consider the other possible discrete allocations: their utility profiles are (7,0) or (0,3) or (2,4). In any case, the utility of at least one agent is smaller, so no discrete allocation dominates
1728:
1525:. Therefore, if the divider claims that an allocation is fPO, the agents can efficiently verify this claim; but if the divider claims that an allocation is PO, it may be impossible to verify this claim efficiently.
1842:
allocation of goods always exists and can be computed in polynomial time. This strengthens previous results which showed similar results for binary (0,1) valuations, and for PO+EFx. They show similar results for
1207:
1835:
different values for the goods), the above two results can be computed in polynomial time. Similarly, when the number of agents is a constant, the above two results can be computed in polynomial time.
1118:
1042:
929:
500:
1602:
is weighted-proportional (proportional for agents with different entitlements). This implies an efficient algorithm for finding a fractional WPROP+fPO allocation with at most
970:
1237:. The proof was extended for bads by Branzei and Sandomirskiy. It was later extended to general valuations (mixtures of goods and bads) by Sandomirskiy and Segal-Halevi.
592:
1257:
in which the nodes on one side are agents, the nodes on the other side are objects, and the directed edges represent exchanges: an edge incoming into agent
1624:
1609:
Combining the above lemma with more advanced algorithms can yield, in strongly-polynomial time, allocations that are fPO and envy-free, with at most
1941:
with high probability. This implies that, with high probability (under suitable conditions on the utility distributions), there exists a discrete
1537:: agent 1 takes all objects for which he has positive value; then agent 2 takes all remaining objects for which he has positive value; and so on.
1770:
Several recent works have considered the existence and computation of a discrete allocation that is both fPO and satisfies a certain notion of
2337:
2297:
2220:
2013:
2210:
1123:
251:
giving to Alice 1/2 of the first item and the whole second item, and the other 1/2 of the first item to George; the utility profile of
1590:
is proportional. Therefore, the above lemma implies an efficient algorithm for finding a fractional PROP+fPO allocation, with at most
1621:
There is an algorithm that enumerates all consumption graphs that correspond to fPO allocations. The run-time of the algorithm is
2682:
Bai, Yushi; Gölz, Paul (2022-02-11). "Envy-Free and Pareto-Optimal
Allocations for Agents with Asymmetric Random Valuations".
2661:
Garg, Jugal; Murhekar, Aniket; Qin, John (2021-10-18). "Fair and
Efficient Allocations of Chores under Bivalued Preferences".
2604:
Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (2021-04-08).
1062:
1873:>0. They prove that, even for such instances (when there are at least 3 different valuations), there may be no discrete
1854:
allocation of chores always exists and can be computed in polynomial time. The also prove that, in this case, a fractional
1823:
allocation of goods can be found in pseudo-polynomial time. They also prove that, when all values are positive, a discrete
793:)). This allocation is PO but not fPO, since it is dominated by the fractional allocation giving to agent 2 the bundle {g
735:). This allocation is PO but not fPO, since it is dominated by the fractional allocation giving to agent 1 the bundle {g
1850:
Garg, Murhekar and Qin prove that, when the valuation matrix contains only two different (negative) values, a discrete
71:
allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.
1441:
2709:
2278:"On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences"
1899:
are drawn randomly and independently from a distribution (which may be different for different agents), each agent
975:
1838:
Garg and
Murhekar prove that, when the valuation matrix contains only two different (positive) values, a discrete
2324:. Lecture Notes in Computer Science. Vol. 12885. Cham: Springer International Publishing. pp. 345–359.
1938:
1861:
Freeman, Sikdar, Vaish and Xia present a polynomial-time algorithm for computing a discrete allocation that is
220:
Suppose there are two agents and two items. Alice values the items at 3, 2 and George values them at 4, 1. Let
1798:
1782:
allocation of goods can be computed in strongly-polynomial time. They show a similar result for a discrete
1393:
It was later extended to general valuations (mixtures of goods and bads) by
Sandomirskiy and Segal-Halevi.
2030:
2583:. AAMAS '18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 7–13.
2249:
1406:
888:
846:
An allocation is fPO if-and-only-if it maximizes a weighted sum of the agents' utilities. Formally, let
457:
2605:
2537:
2421:
1812:
Barman, Krishnamurthy and Vaish prove that there always exists a discrete allocation of goods that is
199:
is not Pareto-dominated by any allocation at all - whether discrete or fractional - then it is called
1771:
1249:
does not contain cycles with product smaller than 1. The directed consumption graph of an allocation
48:
2284:. Lecture Notes in Computer Science. Vol. 5783. Berlin, Heidelberg: Springer. pp. 98–110.
2120:
Brânzei, Simina; Sandomirskiy, Fedor (2019-07-03). "Algorithms for
Competitive Division of Chores".
1534:
936:
224:
be the allocation giving the first item to Alice and the second to George. The utility profile of
2683:
2662:
2643:
2617:
2584:
2518:
2490:
2459:
2433:
2402:
2374:
2343:
2317:
2191:
2165:
2121:
1999:
1794:
2277:
2153:
1926:
1786:
allocation, where EF11 means "envy-free up to addition of one good and removal of another good".
2422:"A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation"
558:
2635:
2557:
2510:
2451:
2394:
2333:
2293:
2216:
2183:
2099:
2050:
2009:
1802:
60:
44:
17:
2627:
2581:
Proceedings of the 17th
International Conference on Autonomous Agents and MultiAgent Systems
2549:
2500:
2443:
2384:
2325:
2285:
2175:
2089:
2081:
2042:
1560:
objects with mixed (positive and negative) valuations, in strongly-polynomial time, using O(
32:
2237:
2262:
1265:
would like to accept (goods he does not own, or bads he own); an edge incoming from agent
1254:
1230:
2478:
2362:
2046:
1515:
2069:
1750:=0 for non-degenerate valuations, where for every two agents, the value-ratios of all
535:- otherwise a similar trade can be done. Therefore, a max-product fPO allocation is {g
2703:
2647:
2576:
2522:
2463:
2347:
2195:
2085:
1991:
1522:
1402:
1377:≥ 0. Clearly, every malicious allocation can be Pareto-improved by moving the object
610:
The following example shows that fPO is incompatible with a fairness notion known as
502:. It is not fPO, since it is dominated by a fractional allocation: agent 3 can give g
2406:
1405:, when all agents have linear utilities, any market equilibrium is fPO. This is the
59:
if some objects are split among two or more agents. A discrete allocation is called
2389:
2329:
1996:
Proceedings of the 28th
International Joint Conference on Artificial Intelligence
829:
The same instance shows that fPO is incompatible with a fairness notion known as
138:
are either 0 or 1; that is, each object is allocated entirely to a single agent.
2289:
1723:{\displaystyle O(3^{{\frac {(n-1)n}{2}}\cdot D}\cdot m^{{\frac {(n-1)n}{2}}+2})}
2553:
2631:
2447:
1789:
Aziz, Moulin and
Sandomirskiy present an algorithm that computes a fractional
1234:
2639:
2561:
2514:
2505:
2455:
2398:
2187:
2103:
2054:
2031:"Welfare economics and existence of an equilibrium for a competitive economy"
1968:
1422:
The following algorithm can be used to decide whether a given an allocation
63:(PO) if it is not Pareto-dominated by any discrete allocation; it is called
28:
2575:
Barman, Siddharth; Krishnamurthy, Sanath Kumar; Vaish, Rohit (2018-07-09).
2179:
1973:
EC '18: Proceedings of the 2018 ACM Conference on
Economics and Computation
2276:
de Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009).
518:/2. This trade strictly improves the welfare of both agents. Moreover, in
2538:"Maximizing Nash product social welfare in allocating indivisible goods"
2094:
1990:
Freeman, Rupert; Sikdar, Sujoy; Vaish, Rohit; Xia, Lirong (2019-08-10).
1273:
can pay by (goods he owns, or bads he does not own). The weight of edge
247:
is not fractionally-Pareto-efficient. It is dominated by the allocation
107:
is a real number between 0 and 1. It represents the fraction that agent
1229:
of strictly-positive weights. This equivalence was proved for goods by
1827:
allocation can exists and can be found in pseudo-polynomial time. For
1575:)) operations. Moreover, in the computed allocation there are at most
1533:
Finding an fPO allocation is easy. For example, it can be found using
180:
is not Pareto-dominated by any discrete allocation, then it is called
1797:
that maximizes the sum of utilities subject to proportionality. If a
1858:
allocation of (divisible) chores can be computed in polynomial time.
2688:
2667:
2622:
2589:
2495:
2438:
2379:
2170:
2126:
2004:
1521:
In contrast, deciding whether a given discrete allocation is PO is
1202:{\displaystyle u_{i}(\mathbf {z} ):=\sum _{o}v_{i,o}\cdot z_{i,o}=}
2318:"Computing Fair and Efficient Allocations with Few Utility Values"
1544:(that may be fractional, and not be fPO), find an fPO allocation
1389:. Therefore, non-maliciousness is a necessary condition for fPO.
55:
if each item is wholly allocated to a single agent; it is called
1884:
Bai and Golz present an algorithm for computing a weight-vector
2320:. In Caragiannis, Ioannis; Hansen, Kristoffer Arnsfelt (eds.).
873:-maximal if one of the following (equivalent) properties hold:
2420:
Aziz, Haris; Moulin, Hervé; Sandomirskiy, Fedor (2020-09-01).
1491:
the number of agents. Therefore, fPO can be decided in time O(
2483:
Proceedings of the AAAI Conference on Artificial Intelligence
2367:
Proceedings of the AAAI Conference on Artificial Intelligence
2361:
Barman, Siddharth; Krishnamurthy, Sanath Kumar (2019-07-17).
1540:
A more interesting challenge is: given an initial allocation
1929:, that a vector of equalizing weights always exists. When
1793:
allocation of mixed objects (goods and chores). It uses a
1762:=0, the run-time of the algorithm is strongly-polynomial.
1865:, for instances in which all valuations are powers of (1+
1440:
Use an algorithm for finding a negative cycle, e.g., the
602:
is sufficiently small, the product ratio approaches 1/3.
255:
is (3.5, 2), so it gives a higher utility to both agents.
2479:"On Fair and Efficient Allocations of Indivisible Goods"
1113:{\displaystyle \sum _{i}w_{i}\cdot u_{i}(\mathbf {z} )}
614:- equitability up to any good. There are three goods {g
2577:"Greedy Algorithms for Maximizing Nash Social Welfare"
2363:"On the Proximity of Markets with Integral Equilibria"
2152:
Sandomirskiy, Fedor; Segal-Halevi, Erel (2022-05-01).
1627:
1126:
1065:
978:
939:
891:
561:
460:
1967:Barman, S., Krishnamurthy, S. K., & Vaish, R.,
2606:"Maximum Nash welfare and other stories about EFX"
1722:
1201:
1112:
1036:
964:
923:
626:} and two agents with the following values (where
586:
494:
2536:Darmann, Andreas; Schauer, Joachim (2015-12-01).
1451:is fPO if-and-only-if no negative cycle is found.
2280:. In Rossi, Francesca; Tsoukias, Alexis (eds.).
522:integral fPO allocation, there exists an agent A
285:} and 3 agents with the following values (where
123:equals 1, since the entire object is allocated.
1998:. IJCAI'19. Macao, China: AAAI Press: 280–286.
1778:Barman and Krishnamurthy prove that a discrete
1241:No improvements cycles in the consumption graph
2154:"Efficient Fair Division with Minimal Sharing"
1586:is the equal split, then the final allocation
1366:< 0, even though there is some other agent
67:if it is not Pareto-dominated by any discrete
1506:An alternative algorithm is to find a vector
1037:{\displaystyle w_{i}v_{i,o}\geq w_{j}v_{j,o}}
8:
2477:Murhekar, Aniket; Garg, Jugal (2021-05-18).
1992:"Equitable allocations of indivisible goods"
1754:objects are different). In particular, when
1514:-maximizing. This can be done by solving a
1340:≤ 0, even though there is some other agent
1245:An allocation is fPO if-and-only-if it its
1430:Compute the directed consumption graph of
1418:Deciding whether a given allocation is fPO
1221:An allocation is fPO if-and-only-if it is
1120:, is maximal among all allocations, where
2687:
2666:
2621:
2588:
2504:
2494:
2437:
2388:
2378:
2169:
2125:
2093:
2003:
1682:
1681:
1639:
1638:
1626:
1184:
1165:
1155:
1140:
1131:
1125:
1102:
1093:
1080:
1070:
1064:
1022:
1012:
993:
983:
977:
944:
938:
909:
896:
890:
578:
560:
465:
459:
2542:European Journal of Operational Research
2070:"Two problems in the theory of fairness"
1969:"Finding Fair and Efficient Allocations"
1819:Murhekar and Garg prove that a discrete
1809:allocation, in strongly-polynomial-time.
817:}, in which the utility profile is (2+2
632:
295:
2212:The Geometry of Efficient Fair Division
1955:
1933:is a vector of equalizing weights, the
1831:-ary instances (each agent has at most
1437:Replace each weight with its logarithm;
708:Only two discrete allocations are EQx:
434:A max-product integral allocation is {h
2316:Garg, Jugal; Murhekar, Aniket (2021).
2258:
2247:
1925:of all other agents. They show, using
842:Maximizing a weighted sum of utilities
759:}, in which the utility profile is ((
2311:
2309:
1518:. The run-time is weakly-polynomial.
1447:Based on the above characterization,
606:No fPO allocation is almost-equitable
528:who receives only (at most) the good
510:utility) in return to a fraction of h
51:. An allocation of objects is called
7:
2147:
2145:
2143:
2141:
2139:
2137:
2115:
2113:
1985:
1983:
1981:
1963:
1961:
1959:
1455:The run-time of the algorithm is O(|
161:, and the utility of some agents in
119:, the sum of all elements in column
1552:. This challenge can be solved for
1529:Finding a dominating fPO allocation
65:fractionally Pareto-efficient (fPO)
49:fair allocation of discrete objects
2209:Barbanel, Julius B. (2005-01-24).
2047:10.1111/j.1467-999X.1960.tb00275.x
1510:such that the given allocation is
924:{\displaystyle w_{i}\cdot v_{i,o}}
153:, if the utility of all agents in
41:Fractional Pareto optimality (fPO)
25:
1548:that is a Pareto-improvement of
495:{\displaystyle C^{2}\cdot (3-2d)}
169:. In this case, we also say that
1766:Finding fair and fPO allocations
1141:
1103:
833:- envy-freeness up to any good.
2029:Negishi, Takashi (1960-06-01).
1617:Enumerating the fPO allocations
1059:The weighted sum of utilities,
630:is a small positive constant):
293:is a small positive constant):
2215:. Cambridge University Press.
1903:has an equal probability that
1888:such that, when the utilities
1717:
1697:
1685:
1654:
1642:
1631:
1397:Relation to market equilibrium
1269:represents objects that agent
1261:represents objects that agent
1145:
1137:
1107:
1099:
805:} and to agent 1 the bundle {g
747:} and to agent 2 the bundle {g
575:
562:
489:
474:
1:
2068:Varian, Hal R. (1976-04-01).
1746:-1 for identical valuations;
1487:is the number of objects and
785:}; the utility profile is (2+
201:fractionally Pareto-efficient
18:Fractionally Pareto efficient
2610:Theoretical Computer Science
2390:10.1609/aaai.v33i01.33011748
2330:10.1007/978-3-030-85947-3_23
2086:10.1016/0047-2727(76)90018-9
965:{\displaystyle z_{i,o}>0}
865:. We say that an allocation
727:}; the utility profile is ((
514:that both agents value at 1-
37:Fractional Pareto efficiency
2426:Operations Research Letters
2290:10.1007/978-3-642-04428-1_9
2282:Algorithmic Decision Theory
2236:Mas-Colell, Andreu (1995).
2074:Journal of Public Economics
1877:allocation and no discrete
1594:-1 sharings. Similarly, if
881:is assigned only to agents
165:is strictly larger than in
157:is at least as large as in
2726:
2554:10.1016/j.ejor.2015.05.071
1598:is an unequal split, then
1582:If the initial allocation
1355:is consumed by some agent
1329:is consumed by some agent
1247:directed consumption graph
598:is sufficiently large and
2632:10.1016/j.tcs.2021.02.020
2448:10.1016/j.orl.2020.07.005
1801:is found (e.g. using the
1303:| and the weight of edge
1225:-maximal for some vector
587:{\displaystyle (C+1)^{2}}
182:discrete Pareto-efficient
2506:10.1609/aaai.v35i6.16703
1351:> 0; or, some object
1321:An allocation is called
289:is a large constant and
126:An allocation is called
2322:Algorithmic Game Theory
1937:-maximal allocation is
1799:basic feasible solution
47:used in the setting of
2257:Cite journal requires
2238:"Microeconomic theory"
2180:10.1287/opre.2022.2279
1724:
1442:Bellman-Ford algorithm
1288:|, The weight of edge
1203:
1114:
1038:
966:
925:
588:
496:
1863:fPO+approximately-EQ1
1725:
1407:first welfare theorem
1209:the utility of agent
1204:
1115:
1039:
967:
926:
885:for whom the product
854:, assigning a weight
719:} and agent 2 gets {g
589:
506:to agent 1 (losing 1-
497:
216:PO does not imply fPO
203:(usually abbreviated
188:(usually abbreviated
103:, where each element
1869:) for some constant
1625:
1124:
1063:
976:
937:
889:
850:be a vector of size
778:} and agent 2 gets {
559:
458:
171:y Pareto-dominates z
134:if all its elements
91:is determined by an
83:agents and a set of
2158:Operations Research
1914:is larger than the
1535:serial dictatorship
115:. For every object
1720:
1213:in the allocation
1199:
1160:
1110:
1075:
1034:
962:
921:
584:
492:
147:Pareto improvement
79:There is a set of
75:Formal definitions
2710:Pareto efficiency
2339:978-3-030-85947-3
2299:978-3-642-04428-1
2222:978-1-139-44439-2
2015:978-0-9992411-4-1
1803:simplex algorithm
1738:of the instance (
1734:is the degree of
1707:
1664:
1151:
1066:
706:
705:
636:Agents ↓ Goods ⇒
432:
431:
299:Agents ↓ Goods ⇒
176:If an allocation
149:of an allocation
111:gets from object
45:Pareto efficiency
16:(Redirected from
2717:
2694:
2693:
2691:
2679:
2673:
2672:
2670:
2658:
2652:
2651:
2625:
2601:
2595:
2594:
2592:
2572:
2566:
2565:
2533:
2527:
2526:
2508:
2498:
2489:(6): 5595–5602.
2474:
2468:
2467:
2441:
2417:
2411:
2410:
2392:
2382:
2373:(1): 1748–1755.
2358:
2352:
2351:
2313:
2304:
2303:
2273:
2267:
2266:
2260:
2255:
2253:
2245:
2233:
2227:
2226:
2206:
2200:
2199:
2173:
2164:(3): 1762–1782.
2149:
2132:
2131:
2129:
2117:
2108:
2107:
2097:
2065:
2059:
2058:
2026:
2020:
2019:
2007:
1987:
1976:
1965:
1758:is constant and
1729:
1727:
1726:
1721:
1716:
1715:
1708:
1703:
1683:
1673:
1672:
1665:
1660:
1640:
1208:
1206:
1205:
1200:
1195:
1194:
1176:
1175:
1159:
1144:
1136:
1135:
1119:
1117:
1116:
1111:
1106:
1098:
1097:
1085:
1084:
1074:
1043:
1041:
1040:
1035:
1033:
1032:
1017:
1016:
1004:
1003:
988:
987:
971:
969:
968:
963:
955:
954:
930:
928:
927:
922:
920:
919:
901:
900:
837:Characterization
801:)) fraction of g
743:)) fraction of g
633:
593:
591:
590:
585:
583:
582:
555:}, with product
501:
499:
498:
493:
470:
469:
454:}, with product
296:
260:The price of fPO
186:Pareto-efficient
61:Pareto-efficient
43:is a variant of
33:computer science
21:
2725:
2724:
2720:
2719:
2718:
2716:
2715:
2714:
2700:
2699:
2698:
2697:
2681:
2680:
2676:
2660:
2659:
2655:
2603:
2602:
2598:
2574:
2573:
2569:
2535:
2534:
2530:
2476:
2475:
2471:
2419:
2418:
2414:
2360:
2359:
2355:
2340:
2315:
2314:
2307:
2300:
2275:
2274:
2270:
2256:
2246:
2235:
2234:
2230:
2223:
2208:
2207:
2203:
2151:
2150:
2135:
2119:
2118:
2111:
2067:
2066:
2062:
2028:
2027:
2023:
2016:
1989:
1988:
1979:
1966:
1957:
1952:
1927:Sperner's lemma
1923:
1919:
1912:
1908:
1893:
1768:
1684:
1677:
1641:
1634:
1623:
1622:
1619:
1531:
1420:
1415:
1399:
1375:
1364:
1349:
1338:
1325:if some object
1316:
1301:
1286:
1255:bipartite graph
1243:
1180:
1161:
1127:
1122:
1121:
1089:
1076:
1061:
1060:
1044:for all agents
1018:
1008:
989:
979:
974:
973:
940:
935:
934:
905:
892:
887:
886:
861:to every agent
859:
844:
839:
816:
813:) fraction of g
808:
804:
796:
784:
777:
773:
770:Agent 1 gets {g
758:
755:) fraction of g
750:
746:
738:
726:
722:
718:
686:
662:
654:
648:
642:
625:
621:
617:
608:
574:
557:
556:
554:
550:
546:
542:
538:
533:
526:
513:
505:
461:
456:
455:
453:
449:
445:
441:
437:
403:
370:
337:
329:
323:
317:
311:
305:
284:
280:
276:
272:
268:
262:
218:
213:
77:
23:
22:
15:
12:
11:
5:
2723:
2721:
2713:
2712:
2702:
2701:
2696:
2695:
2674:
2653:
2596:
2567:
2548:(2): 548–559.
2528:
2469:
2432:(5): 573–578.
2412:
2353:
2338:
2305:
2298:
2268:
2259:|journal=
2228:
2221:
2201:
2133:
2109:
2080:(3): 249–260.
2060:
2041:(2–3): 92–97.
2035:Metroeconomica
2021:
2014:
1977:
1954:
1953:
1951:
1948:
1947:
1946:
1921:
1917:
1910:
1906:
1895:of each agent
1891:
1882:
1859:
1848:
1836:
1817:
1810:
1795:linear program
1787:
1767:
1764:
1719:
1714:
1711:
1706:
1702:
1699:
1696:
1693:
1690:
1687:
1680:
1676:
1671:
1668:
1663:
1659:
1656:
1653:
1650:
1647:
1644:
1637:
1633:
1630:
1618:
1615:
1530:
1527:
1523:co-NP-complete
1516:linear program
1453:
1452:
1445:
1438:
1435:
1419:
1416:
1414:
1411:
1398:
1395:
1373:
1362:
1347:
1336:
1314:
1299:
1284:
1242:
1239:
1219:
1218:
1198:
1193:
1190:
1187:
1183:
1179:
1174:
1171:
1168:
1164:
1158:
1154:
1150:
1147:
1143:
1139:
1134:
1130:
1109:
1105:
1101:
1096:
1092:
1088:
1083:
1079:
1073:
1069:
1057:
1031:
1028:
1025:
1021:
1015:
1011:
1007:
1002:
999:
996:
992:
986:
982:
961:
958:
953:
950:
947:
943:
932:
918:
915:
912:
908:
904:
899:
895:
857:
843:
840:
838:
835:
827:
826:
814:
806:
802:
794:
782:
775:
771:
768:
756:
748:
744:
736:
724:
720:
716:
712:Agent 1 gets {
704:
703:
697:
690:
687:
684:
680:
679:
676:
669:
663:
660:
656:
655:
652:
649:
646:
643:
640:
637:
623:
619:
615:
607:
604:
581:
577:
573:
570:
567:
564:
552:
548:
544:
540:
536:
531:
524:
511:
503:
491:
488:
485:
482:
479:
476:
473:
468:
464:
451:
447:
443:
439:
435:
430:
429:
426:
420:
414:
409:
404:
401:
397:
396:
390:
387:
381:
376:
371:
368:
364:
363:
357:
351:
348:
343:
338:
335:
331:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
282:
278:
274:
270:
266:
261:
258:
257:
256:
241:
217:
214:
212:
209:
141:An allocation
76:
73:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2722:
2711:
2708:
2707:
2705:
2690:
2685:
2678:
2675:
2669:
2664:
2657:
2654:
2649:
2645:
2641:
2637:
2633:
2629:
2624:
2619:
2615:
2611:
2607:
2600:
2597:
2591:
2586:
2582:
2578:
2571:
2568:
2563:
2559:
2555:
2551:
2547:
2543:
2539:
2532:
2529:
2524:
2520:
2516:
2512:
2507:
2502:
2497:
2492:
2488:
2484:
2480:
2473:
2470:
2465:
2461:
2457:
2453:
2449:
2445:
2440:
2435:
2431:
2427:
2423:
2416:
2413:
2408:
2404:
2400:
2396:
2391:
2386:
2381:
2376:
2372:
2368:
2364:
2357:
2354:
2349:
2345:
2341:
2335:
2331:
2327:
2323:
2319:
2312:
2310:
2306:
2301:
2295:
2291:
2287:
2283:
2279:
2272:
2269:
2264:
2251:
2243:
2239:
2232:
2229:
2224:
2218:
2214:
2213:
2205:
2202:
2197:
2193:
2189:
2185:
2181:
2177:
2172:
2167:
2163:
2159:
2155:
2148:
2146:
2144:
2142:
2140:
2138:
2134:
2128:
2123:
2116:
2114:
2110:
2105:
2101:
2096:
2091:
2087:
2083:
2079:
2075:
2071:
2064:
2061:
2056:
2052:
2048:
2044:
2040:
2036:
2032:
2025:
2022:
2017:
2011:
2006:
2001:
1997:
1993:
1986:
1984:
1982:
1978:
1974:
1970:
1964:
1962:
1960:
1956:
1949:
1944:
1940:
1936:
1932:
1928:
1924:
1913:
1902:
1898:
1894:
1887:
1883:
1880:
1876:
1872:
1868:
1864:
1860:
1857:
1853:
1849:
1846:
1841:
1837:
1834:
1830:
1826:
1822:
1818:
1815:
1811:
1808:
1804:
1800:
1796:
1792:
1788:
1785:
1781:
1777:
1776:
1775:
1773:
1765:
1763:
1761:
1757:
1753:
1749:
1745:
1741:
1737:
1733:
1712:
1709:
1704:
1700:
1694:
1691:
1688:
1678:
1674:
1669:
1666:
1661:
1657:
1651:
1648:
1645:
1635:
1628:
1616:
1614:
1613:-1 sharings.
1612:
1607:
1606:-1 sharings.
1605:
1601:
1597:
1593:
1589:
1585:
1580:
1579:-1 sharings.
1578:
1574:
1570:
1566:
1563:
1559:
1555:
1551:
1547:
1543:
1538:
1536:
1528:
1526:
1524:
1519:
1517:
1513:
1509:
1504:
1502:
1498:
1494:
1490:
1486:
1482:
1478:
1474:
1470:
1466:
1462:
1458:
1450:
1446:
1443:
1439:
1436:
1433:
1429:
1428:
1427:
1425:
1417:
1412:
1410:
1408:
1404:
1403:Fisher market
1396:
1394:
1390:
1388:
1384:
1380:
1376:
1369:
1365:
1358:
1354:
1350:
1343:
1339:
1332:
1328:
1324:
1319:
1317:
1310:
1306:
1302:
1295:
1291:
1287:
1280:
1276:
1272:
1268:
1264:
1260:
1256:
1252:
1248:
1240:
1238:
1236:
1232:
1228:
1224:
1216:
1212:
1196:
1191:
1188:
1185:
1181:
1177:
1172:
1169:
1166:
1162:
1156:
1152:
1148:
1132:
1128:
1094:
1090:
1086:
1081:
1077:
1071:
1067:
1058:
1055:
1051:
1047:
1029:
1026:
1023:
1019:
1013:
1009:
1005:
1000:
997:
994:
990:
984:
980:
959:
956:
951:
948:
945:
941:
933:
916:
913:
910:
906:
902:
897:
893:
884:
880:
876:
875:
874:
872:
868:
864:
860:
853:
849:
841:
836:
834:
832:
824:
820:
812:
800:
792:
788:
781:
769:
766:
762:
754:
742:
734:
730:
715:
711:
710:
709:
702:
698:
695:
691:
688:
682:
681:
677:
674:
670:
668:
664:
658:
657:
650:
644:
638:
635:
634:
631:
629:
613:
605:
603:
601:
597:
579:
571:
568:
565:
534:
527:
521:
517:
509:
486:
483:
480:
477:
471:
466:
462:
427:
425:
421:
419:
415:
413:
410:
408:
405:
399:
398:
395:
391:
388:
386:
382:
380:
377:
375:
372:
366:
365:
362:
358:
356:
352:
349:
347:
344:
342:
339:
333:
332:
325:
319:
313:
307:
301:
298:
297:
294:
292:
288:
259:
254:
250:
246:
242:
239:
234:
231:
230:
229:
227:
223:
215:
210:
208:
206:
202:
198:
193:
191:
187:
183:
179:
174:
172:
168:
164:
160:
156:
152:
148:
144:
139:
137:
133:
129:
124:
122:
118:
114:
110:
106:
102:
98:
94:
90:
86:
82:
74:
72:
70:
69:or fractional
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
19:
2677:
2656:
2613:
2609:
2599:
2580:
2570:
2545:
2541:
2531:
2486:
2482:
2472:
2429:
2425:
2415:
2370:
2366:
2356:
2321:
2281:
2271:
2250:cite journal
2241:
2231:
2211:
2204:
2161:
2157:
2095:1721.1/64180
2077:
2073:
2063:
2038:
2034:
2024:
1995:
1975:, June 2018.
1972:
1942:
1934:
1930:
1915:
1904:
1900:
1896:
1889:
1885:
1878:
1874:
1870:
1866:
1862:
1855:
1851:
1844:
1839:
1832:
1828:
1824:
1820:
1813:
1806:
1790:
1783:
1779:
1769:
1759:
1755:
1751:
1747:
1743:
1739:
1735:
1731:
1620:
1610:
1608:
1603:
1599:
1595:
1591:
1587:
1583:
1581:
1576:
1572:
1568:
1564:
1561:
1557:
1553:
1549:
1545:
1541:
1539:
1532:
1520:
1511:
1507:
1505:
1500:
1496:
1492:
1488:
1484:
1480:
1476:
1472:
1468:
1464:
1460:
1456:
1454:
1448:
1431:
1423:
1421:
1400:
1391:
1386:
1382:
1378:
1371:
1367:
1360:
1356:
1352:
1345:
1341:
1334:
1330:
1326:
1322:
1320:
1312:
1308:
1304:
1297:
1293:
1289:
1282:
1278:
1274:
1270:
1266:
1262:
1258:
1250:
1246:
1244:
1226:
1222:
1220:
1214:
1210:
1053:
1052:and objects
1049:
1045:
882:
878:
877:Each object
870:
866:
862:
855:
851:
847:
845:
830:
828:
822:
818:
810:
798:
790:
786:
779:
764:
760:
752:
740:
732:
728:
713:
707:
700:
693:
672:
666:
627:
611:
609:
599:
595:
529:
523:
519:
515:
507:
433:
423:
417:
411:
406:
393:
384:
378:
373:
360:
354:
345:
340:
290:
286:
263:
252:
248:
244:
237:
232:
225:
221:
219:
204:
200:
196:
194:
189:
185:
184:, or simply
181:
177:
175:
170:
166:
162:
158:
154:
150:
146:
145:is called a
142:
140:
135:
131:
127:
125:
120:
116:
112:
108:
104:
100:
96:
92:
88:
87:objects. An
84:
80:
78:
68:
64:
56:
52:
40:
36:
26:
1945:allocation.
1881:allocation.
1556:agents and
1463:|). Here, |
1381:from agent
931:is maximal.
2689:2109.08971
2668:2110.09601
2623:2001.09838
2590:1801.09046
2496:2204.14229
2439:1909.00740
2380:1811.08673
2171:1908.01669
2127:1907.01766
2005:1905.10656
1950:References
1807:fPO+WPROP1
1736:degeneracy
1413:Algorithms
228:is (3,1).
89:allocation
57:fractional
2648:232423008
2640:0304-3975
2616:: 69–85.
2562:0377-2217
2523:235306087
2515:2374-3468
2464:202541717
2456:0167-6377
2399:2374-3468
2348:237521642
2196:247922344
2188:0030-364X
2104:0047-2727
2055:0026-1386
1939:envy-free
1791:fPO+WPROP
1780:fPO+PROP1
1692:−
1675:⋅
1667:⋅
1649:−
1385:to agent
1323:malicious
1178:⋅
1153:∑
1087:⋅
1068:∑
1006:≥
903:⋅
481:−
472:⋅
243:However,
29:economics
2704:Category
2407:53793188
1784:fPO+EF11
1772:fairness
1730:, where
1483:, where
1426:is fPO:
972:implies
797:, (1-(1+
739:, (1-(1+
211:Examples
132:integral
128:discrete
53:discrete
1879:fPO+EFx
1875:fPO+EQx
1852:fPO+EF1
1840:fPO+EFx
1825:fPO+EQ1
1821:fPO+EF1
1814:fPO+EF1
1231:Negishi
594:. When
99:matrix
2646:
2638:
2560:
2521:
2513:
2462:
2454:
2405:
2397:
2346:
2336:
2296:
2219:
2194:
2186:
2102:
2053:
2012:
1943:fPO+EF
1856:fPO+EF
1845:PO+EQx
1311:is 1/|
1307:->
1292:->
1277:->
1235:Varian
763:), 2+2
2684:arXiv
2663:arXiv
2644:S2CID
2618:arXiv
2585:arXiv
2519:S2CID
2491:arXiv
2460:S2CID
2434:arXiv
2403:S2CID
2375:arXiv
2344:S2CID
2192:S2CID
2166:arXiv
2122:arXiv
2000:arXiv
1475:and |
1401:In a
1370:with
1359:with
1344:with
1333:with
1253:is a
809:, (1+
751:, (1+
731:), 2+
2636:ISSN
2558:ISSN
2511:ISSN
2452:ISSN
2395:ISSN
2334:ISBN
2294:ISBN
2263:help
2217:ISBN
2184:ISSN
2100:ISSN
2051:ISSN
2010:ISBN
1503:)).
1296:is |
1281:is |
1233:and
957:>
551:},{g
543:},{g
442:},{g
438:},{h
95:-by-
31:and
2628:doi
2614:863
2550:doi
2546:247
2501:doi
2444:doi
2385:doi
2326:doi
2286:doi
2176:doi
2090:hdl
2082:doi
2043:doi
1493:m n
1481:m n
1374:j,o
1363:i,o
1348:j,o
1337:i,o
1318:|.
1315:i,o
1300:i,o
1285:i,o
869:is
831:EFx
825:)).
823:1+e
791:1+e
789:, (
761:1+e
729:1+e
694:1+e
673:1+e
612:EQx
520:any
207:).
205:fPO
195:If
192:).
130:or
39:or
27:In
2706::
2642:.
2634:.
2626:.
2612:.
2608:.
2579:.
2556:.
2544:.
2540:.
2517:.
2509:.
2499:.
2487:35
2485:.
2481:.
2458:.
2450:.
2442:.
2430:48
2428:.
2424:.
2401:.
2393:.
2383:.
2371:33
2369:.
2365:.
2342:.
2332:.
2308:^
2292:.
2254::
2252:}}
2248:{{
2240:.
2190:.
2182:.
2174:.
2162:70
2160:.
2156:.
2136:^
2112:^
2098:.
2088:.
2076:.
2072:.
2049:.
2039:12
2037:.
2033:.
2008:.
1994:.
1980:^
1971:,
1958:^
1774:.
1600:z*
1588:z*
1546:z*
1479:|≤
1467:|=
1459:||
1409:.
1149::=
1048:,
819:e,
774:,g
767:).
723:,g
699:1+
696:)
689:1
678:1
675:)
665:1+
622:,g
618:,g
547:,h
539:,h
450:,g
446:,g
428:1
422:1-
416:1-
392:1-
389:1
383:1-
359:1-
353:1-
350:1
281:,g
277:,g
273:,g
269:,h
265:{h
190:PO
173:.
35:,
2692:.
2686::
2671:.
2665::
2650:.
2630::
2620::
2593:.
2587::
2564:.
2552::
2525:.
2503::
2493::
2466:.
2446::
2436::
2409:.
2387::
2377::
2350:.
2328::
2302:.
2288::
2265:)
2261:(
2244:.
2242:1
2225:.
2198:.
2178::
2168::
2130:.
2124::
2106:.
2092::
2084::
2078:5
2057:.
2045::
2018:.
2002::
1935:w
1931:w
1922:j
1920:u
1918:j
1916:w
1911:i
1909:u
1907:i
1905:w
1901:i
1897:i
1892:i
1890:u
1886:w
1871:e
1867:e
1847:.
1833:k
1829:k
1816:.
1760:D
1756:n
1752:m
1748:D
1744:m
1742:=
1740:D
1732:D
1718:)
1713:2
1710:+
1705:2
1701:n
1698:)
1695:1
1689:n
1686:(
1679:m
1670:D
1662:2
1658:n
1655:)
1652:1
1646:n
1643:(
1636:3
1632:(
1629:O
1611:n
1604:n
1596:z
1592:n
1584:z
1577:n
1573:m
1571:+
1569:n
1567:(
1565:m
1562:n
1558:m
1554:n
1550:z
1542:z
1512:w
1508:w
1501:n
1499:+
1497:m
1495:(
1489:n
1485:m
1477:E
1473:n
1471:+
1469:m
1465:V
1461:E
1457:V
1449:z
1444:.
1434:;
1432:z
1424:z
1387:j
1383:i
1379:o
1372:v
1368:j
1361:v
1357:i
1353:o
1346:v
1342:j
1335:v
1331:i
1327:o
1313:v
1309:i
1305:o
1298:v
1294:o
1290:i
1283:v
1279:o
1275:i
1271:i
1267:i
1263:i
1259:i
1251:z
1227:w
1223:w
1217:.
1215:z
1211:i
1197:=
1192:o
1189:,
1186:i
1182:z
1173:o
1170:,
1167:i
1163:v
1157:o
1146:)
1142:z
1138:(
1133:i
1129:u
1108:)
1104:z
1100:(
1095:i
1091:u
1082:i
1078:w
1072:i
1056:.
1054:o
1050:j
1046:i
1030:o
1027:,
1024:j
1020:v
1014:j
1010:w
1001:o
998:,
995:i
991:v
985:i
981:w
960:0
952:o
949:,
946:i
942:z
917:o
914:,
911:i
907:v
898:i
894:w
883:i
879:o
871:w
867:z
863:i
858:i
856:w
852:n
848:w
821:(
815:2
811:e
807:3
803:2
799:e
795:1
787:e
783:2
780:g
776:3
772:1
765:e
757:2
753:e
749:3
745:2
741:e
737:1
733:e
725:3
721:1
717:2
714:g
701:e
692:(
685:2
683:A
671:(
667:e
661:1
659:A
653:3
651:g
647:2
645:g
641:1
639:g
628:e
624:3
620:2
616:1
600:d
596:C
580:2
576:)
572:1
569:+
566:C
563:(
553:3
549:2
545:2
541:1
537:1
532:i
530:g
525:i
516:d
512:1
508:d
504:1
490:)
487:d
484:2
478:3
475:(
467:2
463:C
452:3
448:2
444:1
440:2
436:1
424:d
418:d
412:C
407:C
402:3
400:A
394:d
385:d
379:C
374:C
369:2
367:A
361:d
355:d
346:C
341:C
336:1
334:A
328:3
326:g
322:2
320:g
316:1
314:g
310:2
308:h
304:1
302:h
291:d
287:C
283:3
279:2
275:1
271:2
267:1
253:y
249:y
245:z
240:.
238:z
233:z
226:z
222:z
197:z
178:z
167:z
163:y
159:z
155:y
151:z
143:y
136:z
121:o
117:o
113:o
109:i
105:z
101:z
97:m
93:n
85:m
81:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.