528:"we do not preclude the possibility that an individual may end up being paid by the others to take a bundle of goods. In the context of fair division, we do not find this problematic at all. Indeed, if a group does not wish to exclude any of its members, then there is no reason why the group should not subsidize a member for receiving an undesired bundle. Moreover, the qualification requirement guarantees that subsidization is never a consequence of a player's insufficient valuation of the complete set of objects to be distributed".
465:) allocation - an allocation with a highest sum-of-utilities that satisfies the constraints on bundles of items. If there are no constraints, then an allocation that gives each item to the partner with the highest valuation is maxsum. If there are constraints (such as "at least one item per partner"), then a maxsum allocation might be more difficult to find.
457:
least a certain number of items", or "some items must be bundled together" (e.g. because they are land-plots that must remain connected), etc. The "items" can have both positive or negative utilities. There is a "qualification requirement" for a partner: the sum of his bids must be at least the total cost. The procedure works in the following steps.
969:
generalizes the traditional binary criteria of envy-freeness, proportionality, and efficiency (welfare) to measures of degree that range between 0 and 1. In the canonical fair division settings, under any allocatively-efficient mechanism the worst-case welfare rate is 0 and disproportionality rate is
444:
In experiments with human subjects, it was found that participants prefer the Raith's auction (Adjusted
Knaster) to Divide-and-Choose and to Proportional Knaster (a variant in which each winner pays 1/n of the winning to each loser; in the above example, George pays 90 to Alice, and the net utilities
264:
characterizes the minimum amount of subsidy required for envy-freeness. The allocation that attains this minimum subsidy is almost unique: there is only one way to combine objects with agents, and all agents are indifferent among all minimum-subsidy allocations. It coincides with the solution called
135:
A special case of this setting is when dividing rooms in an apartment between tenants. It is characterized by three requirements: (a) the number of agents equals the number of items, (b) each agent must get exactly one item (room), (c) the total amount of money paid by the agents must equal a fixed
456:
present the
Compensation Procedure. Their procedure allows arbitrary constraints on bundles of items, as long as they are anonymous (do not differentiate between partners based on their identity). For example, there can be no constraint at all, or a constraint such as "each partner must receive at
23:
problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the
507:
The sum of compensations made in all rounds is the smallest sum that is required to eliminate envy, and it never exceeds the surplus. If some surplus remains, it can be divided in any way that does not create envy, e.g., by giving an equal amount to each partner (the paper discusses other options
512:
When there are many item and complex constraints, the initial step - finding a maxsum allocation - may be difficult to calculate without a computer. In this case, the
Compensation Procedure may start with an arbitrary allocation. In this case, the procedure might conclude with an allocation that
664:
in general, is always sufficient. Moreover, there is an allocation attaining this bound that is also EF1 and balanced (the cardinalities of the allocated bundles differ by at most one good). It can be computed in polynomial time by a simple algorithm: iteratively find a
271:
presents another polynomial-time algorithm for the same setting. His algorithm uses the polytope of side-payments that make a given allocation envy-free: this polytope is nonempty iff the original allocation is Pareto-efficient. Connectivity of the undirected
371:
Matthias G. Raith presented a variant on
Knaster's auction, which he called "Adjusted Knaster". As in Knaster's auction, each item is given to the highest bidder. However, the payments are different. The payments are determined as follows:
1050:
Finding an allocation that is EFEQ-convertible with minimum subsidy is NP-hard, and cannot be approximated within any positive factor. This is simply because checking the existence of an EF allocation (which requires 0 subsidy) is
355:
Essen proves that the equilibrium allocation is still Pareto-efficient, but may not be proportional ex-post. However, on average, agents receive the same outcome as if everyone were truthful. That is, the mechanism is proportional
970:
1; in other words, the worst-case results are as bad as possible. He looks for a mechanism that achieves high welfare, low envy, and low disproportionality in expectation across a spectrum of fair division settings. The
999:
either the seller's revenue, or the social welfare, subject to envy-freeness. Additionally, the number of objects may be different than the number of agents, and some objects may be discarded. This is known as the
150:
In general, in the economics literature, it is common to assume that each agent has a utility function on bundles (a bundle is a pair of an object and a certain amount of money). The utility function should be
521:. This strictly increases the total sum of utilities. Hence, after a bounded number of iterations, a maxsum allocation will be found, and the procedure can continue as above to create an envy-free allocation.
440:
In Raith's auction, George pays 180 and it is divided in ratio 20:180 = 1:9, that is, Alice gets 18 and George gets 162. Note that the payments are computed to all items at once - not for each item separately.
79:, and his utility is positive, so he does not envy Alice. Alice, too, does not envy George since his utility - in her eyes - is 0. Similarly, if George thinks that Alice's price is high (he is willing to pay
504:
rounds of compensation. The procedure is fully descriptive and says explicitly which compensations should be made, and in what order. Moreover, it is simple enough to be carried out without computer support.
628:
subsidy can be found in polynomial time. An allocation minimizes the subsidy iff it minimizes the maximum utility to any agent. Computing such an allocation is NP-hard, and can be solved by the max-product
934:
Note that an envy-free allocation with subsidy remains envy-free if a fixed amount is taken from every agent. Therefore, similar methods can be used to find allocations that are not subsidized:
691:), is always sufficient. In particular, the required subsidy does not depend on the number of objects. An allocation attaining this bound can be computed in polynomial time using value-queries.
265:
the "money-Rawlsian solution" of Alkan, Demange and Gale. It can be found in polynomial time, by finding a maximum-weight matching and then finding shortest paths in a certain induced graph.
555:
The allocation is given in advance. In this case, it is "envy-freeable" if and only if it maximizes the sum of utilities across all reassignments of its bundles to agents, if and only if its
359:
Fragnelli and Marina show that, even agents who are infinitely risk-averse, may a safe gain via a joint misreporting of their valuations, regardless of the declarations of the other agents.
813:
924:
742:
866:
1014:
Often, some other objectives have to be attained besides fairness. For example, when assigning tasks to agents, it is required both to avoid envy, and to minimize the
579:. Since we can always reduce the prices such that one agent gets zero subsidy, it follows that there always exists an envy-free allocation with a subsidy of at most (
559:
has no cycles. An envy-free price with minimum subsidy can be computed in strongly polynomial time, by constructing the weighted envy-graph and giving, to each agent
471:
Pay the cost from the initial pool. If all partners satisfy the qualification requirement, then the money in the pool is sufficient, and there may be some remaining
90:
can later be divided equally between the players, since an equal monetary transfer does not affect the relative utilities. Then, effectively, the buying agent pays
502:
957:
showed that an envy-free allocation always exists when the amount of money is sufficiently large. This is true even when items may have negative valuations.
1727:
Haake, Claus-Jochen; Raith, Matthias G.; Su, Francis Edward (2002). "Bidding for envy-freeness: A procedural approach to n-player fair-division problems".
1022:
presents a general framework for optimization problems with envy-freeness guarantee that naturally extends fair item allocations using monetary payments.
383:
To illustrate the difference between
Knaster's auction and Raith's auction, consider a setting with two items and two agents with the following values:
105:
There are various works extending this simple idea to more than two players and more complex settings. The main fairness criteria in these works is
702:
For a constant number of agents, they present an algorithm that approximates the minimum amount of subsidies within any required accuracy. For any
524:
The
Compensation Procedure might charge some partners a negative payment (i.e., give the partners a positive amount of money). The authors say:
963:
prove the existence of envy-free and Pareto-optimal allocations under very mild assumptions on the valuations (not necessarily quasilinear).
284:
Additive agents may receive several objects, so the allocation problem becomes more complex - there are many more possible allocations.
614:
437:
In
Knaster's auction, George pays 90, Alice receives 10, and the difference of 80 is divided equally, so the net utilities are 50, 130.
94:/2 to the selling agent. The total utility of each agent is at least 1/2 of his/her utility for the item. If the agents have different
111:. In addition, some works consider a setting in which a benevolent third-party is willing to subsidize the allocation, but wants to
571:
terms, each of which is the value of some agent to some good. In particular, if the value of each good for each agent is at most
620:
When all agents have the same additive valuation. Then, every allocation is envy-freeable. An allocation that requires at most (
2135:
1848:
1793:
1614:
1202:
32:
With two agents and one item, it is possible to attain fairness using the following simple algorithm (which is a variant of
24:
allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.
1047:
If a given allocation is EFEQ-convertible, then the minimum subsidy required to make it EF+EQ can be found in linear time.
328:
Since the winner is the highest bidder, there is a non-negative surplus; the surplus is divided equally among the agents.
215:
showed a natural ascending auction that achieves an envy-free allocation using monetary payments for unit demand agents.
1320:
Alkan, Ahmet; Demange, Gabrielle; Gale, David (1991). "Fair
Allocation of Indivisible Goods and Criteria of Justice".
1872:
Caragiannis, Ioannis; Ioannidis, Stavros (2020-02-06). "Computing envy-freeable allocations with limited subsidies".
276:
characterizes the extreme points of this polytope. This implies a method for finding extreme envy-free allocations.
67:, that is, their utility is the value of items plus the amount of money that they have, then the allocation is also
755:
617:
to checking the existence of an envy-free allocation, which is NP-hard when restricted to non-wasteful allocations.
159:
in money. It does not have to be linear in money, but does have to be "Archimedean", i.e., there exists some value
2112:. Lecture Notes in Computer Science. Vol. 12885. Cham: Springer International Publishing. pp. 376–390.
1780:. Lecture Notes in Computer Science. Vol. 11801. Cham: Springer International Publishing. pp. 374–389.
945:
It is also possible to use negative subsidy (tax), while minimizing the total amount that all agents have to pay.
1095:
Svensson, Lars-Gunnar (1983). "Large
Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness".
1040:
For superadditive utilities, there is a polynomial-time algorithm that attains envy-freeness, equitability, and
2004:
1989:
Proceedings of the fifth international joint conference on
Autonomous agents and multiagent systems - AAMAS '06
875:
2165:
942:. Minimizing the subsidy is equivalent to minimizing the maximum amount that any individual agent has to pay.
709:
83:
or more), then he leaves the item to Alice and does not envy, since Alice's utility in his eyes is negative.
337:
221:
proved the existence of a Pareto-optimal envy-free allocation when the total money endowment is more than (
1223:
Tadenuma, Koichi; Thomson, William (1991). "No-Envy and Consistency in Economies with Indivisible Goods".
468:
Charge from each partner the value of the bundle allocated to him. This creates the initial pool of money.
209:
first proved that, when all agents are Archimedean, an envy-free allocation exists and is Pareto-optimal.
633:
587:. This subsidy may be necessary, for example when all goods are identical and one agent gets all of them.
95:
1894:
1639:
821:
613:
subsidy, and can be found in polynomial time. Computing the minimum subsidy required to achieve EF is
1072:
1041:
939:
537:
Some works assume that a benevolent third-party is willing to subsidize the allocation, but wants to
379:
The total amount of money paid by the agents is partitioned between them in proportion to their bids.
1741:
1817:
Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (2020-07-13).
2105:
1933:
1773:
666:
230:
995:
When selling objects to buyers, the sum of payments is not fixed in advance, and the goal is to
1736:
927:
636:
with a specific agent ordering finds an allocation that is envy-freeable with subsidy at most
1033:
68:
64:
551:
study subsidy minimization in the general item-allocation setting. They consider two cases:
556:
518:
273:
20:
1895:"Envy-free and Pareto efficient allocations in economies with indivisible goods and money"
293:
8:
2048:
1365:"An algorithm for envy-free allocations in an economy with indivisible objects and money"
481:
196:
152:
1678:
2141:
2113:
2086:
2060:
1969:
1873:
1854:
1826:
1825:. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 23–39.
1799:
1754:
1706:
1698:
1620:
1571:
1501:
1466:
1419:
1392:
1345:
1299:
1291:
1248:
1163:
1155:
1120:
1029:
156:
1910:
1655:
2145:
2131:
2090:
2078:
2000:
1973:
1952:
Bailey, Martin J. (1997). "The demand revealing process: To distribute the surplus".
1914:
1858:
1844:
1803:
1789:
1659:
1610:
1552:
1505:
1458:
1384:
1337:
1303:
1283:
1240:
1198:
1167:
1112:
1001:
601:
When the agents' valuations are binary (0 or 1). Then, any max-product allocation or
348:
341:
1710:
1624:
1396:
938:
Charging each agent the average payment yields an envy-free allocation that is also
2123:
2070:
2029:
1992:
1961:
1906:
1836:
1781:
1758:
1746:
1690:
1651:
1602:
1542:
1532:
1493:
1450:
1376:
1329:
1275:
1232:
1190:
1147:
1104:
1028:
aims to attain, using monetary transfers, an allocation that is both envy-free and
462:
1679:"The Limitations of Fair Division: An Experimental Evaluation of Three Procedures"
2127:
1785:
1194:
1062:
is always sufficient, and may be necessary whether an allocation is given or not.
670:
1594:
1182:
297:
137:
33:
2033:
1965:
1606:
336:
of the value he attributes to the entire set of objects, so the allocation is
2159:
2082:
2074:
1918:
1694:
1663:
1599:
2013 IEEE 37th Annual Computer Software and Applications Conference Workshops
1556:
1462:
1388:
1341:
1287:
1244:
1116:
971:
602:
107:
71:. If George thinks that Alice's price is low (he is willing to pay more than
1996:
1840:
363:
Knaster's auction has been adapted to fair allocation of wireless channels.
351:. Some researchers analysed its performance when agents play strategically:
102:
should be divided between the partners in proportion to their entitlements.
2020:
Mu'alem A (2014). "Fair by design: Multidimensional envy-free mechanisms".
1266:
Aragones, Enriqueta (1995). "A derivation of the money rawlsian solution".
818:
For a variable number of agents, a trivial approximation algorithm attains
541:
the amount of subsidy subject to envy-freeness. This problem is called the
517:. These cycles can be removed by moving bundles along the cycle, as in the
292:
The first procedure for fair allocation of items and money was invented by
115:
the amount of subsidy subject to envy-freeness. This problem is called the
1818:
1750:
1380:
433:
In both auctions, George wins both items, but the payments are different:
203:
is the largest value-difference (for the same agent) between two objects.
136:
constant, which represents the total apartment rent. This is known as the
1987:
Cavallo, Ruggiero (2006). "Optimal decision-making with minimal waste".
1935:
Fairness and Welfare Through Redistribution When Utility is Transferable
1484:
Brams, Steven J.; Kilgour, D. Marc (2001). "Competitive Fair Division".
1364:
1295:
1702:
1547:
1470:
1438:
1423:
1349:
1279:
1252:
1159:
1124:
1595:"Knaster Procedure for Proportional Fair Wireless Channel Allocation"
1537:
1520:
974:
is not a satisfactory candidate, but the redistribution mechanism of
872:
is hard: it is NP-hard to compute an allocation with subsidy at most
248:
and the other objects at 0, then envy-freeness requires a subsidy of
60:
1454:
1333:
1236:
1108:
1032:. He studies not only additive positive utilities, but also for any
340:. Moreover, the allocation maximizes the sum of utilities, so it is
307:
The item is given to the highest bidder (breaking ties arbitrarily).
258:
study several consistency properties of envy-free allocation rules.
2118:
2065:
1878:
1831:
1823:
Proceedings of the 21st ACM Conference on Economics and Computation
1497:
1151:
1015:
478:
Eliminate envy by compensating envious partners. There are at most
2049:"Achieving Envy-freeness and Equitability with Monetary Transfers"
926:. The proof is by reduction from a restricted variant of maximum
752:
objects. The algorithm uses dynamic programming and runs in time
2108:. In Caragiannis, Ioannis; Hansen, Kristoffer Arnsfelt (eds.).
563:, a price equal to the maximum weight of a path emanating from
2106:"Two Birds with One Stone: Fairness and Welfare via Transfers"
1521:"An Equilibrium Analysis of Knaster's Fair Division Procedure"
1138:
Demange G, Gale D, Sotomayor M (1986). "Multi-Item Auctions".
2053:
Proceedings of the AAAI Conference on Artificial Intelligence
1893:
Meertens, Marc; Potters, Jos; Reijnierse, Hans (2002-12-01).
1572:"Strategic Manipulations and Collusions in Knaster Procedure"
127:
Unit-demand agents are interested in at most a single item.
868:. However, attaining an approximation factor independent of
2104:
Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (2021).
698:
study the computational problem of minimizing the subsidy:
300:. This auction works as follows, for each item separately:
1816:
1187:
Arrow and the Foundations of the Theory of Economic Policy
590:
The allocation can be chosen. In this case, a subsidy of (
1892:
1593:
Köppen, Mario; Ohnishi, Kei; Tsuru, Masato (2013-07-01).
676:
With general monotone valuations, a subsidy of at most 2(
1410:
Steinhaus, Hugo (1948). "The problem of fair division".
244:
may be required: if all agents value a single object at
376:
Each agent winning an item pays his bid for this item;
187:
for free is larger than the utility of getting object
1044:(it is easy to exchange budget-balance with subsidy).
878:
824:
758:
712:
484:
1871:
1776:. In Fotakis, Dimitris; Markakis, Evangelos (eds.).
1137:
706:> 0, it finds an allocation with subsidy at most
1189:, London: Palgrave Macmillan UK, pp. 341–349,
199:is a special case of Archimedean utility, in which
2103:
1677:Schneider, Gerald; Krämer, Ulrike Sabrina (2004).
1592:
918:
860:
807:
736:
648:improve the upper bounds on the required subsidy:
496:
1181:Maskin, Eric S. (1987), Feiwel, George R. (ed.),
2157:
1931:
1319:
567:. The weight of each path is at most the sum of
252:for each agent who does not receive the object.
51:, or leave the item to Alice so that Alice pays
47:George chooses whether to take the item and pay
1676:
1570:Fragnelli, Vito; Marina, Maria Erminia (2009).
1569:
1222:
1009:
652:With additive valuations, a subsidy of at most
748:is the maximum value that an agent assigns to
183:(alternatively, the utility of getting object
1183:"On the Fair Allocation of Indivisible Goods"
930:, in which each vertex appears exactly twice.
808:{\displaystyle O((m/\varepsilon )^{n^{2}+1})}
532:
1726:
1483:
179:should be larger than the utility of object
2019:
1771:
1018:(- the completion time of the last agent).
1403:
646:Brustle, Dippel, Narayan, Suzuki and Vetta
575:, then the weight of each path is at most
27:
2117:
2064:
1877:
1830:
1740:
1546:
1536:
1518:
1436:
1409:
1075:- the setting without monetary transfers.
919:{\displaystyle OPT+3\cdot 10^{-4}\cdot S}
448:
332:The utility of every agent is at least 1/
1722:
1720:
1265:
1094:
949:
145:
44:that she is willing to pay for the item.
1986:
737:{\displaystyle OPT+\varepsilon \cdot S}
304:Each agent submits a bid over the item.
2158:
1951:
1772:Halpern, Daniel; Shah, Nisarg (2019).
1180:
598:is sufficient in the following cases:
1717:
1637:
1362:
122:
2046:
1477:
1315:
1313:
1131:
990:
543:minimum-subsidy envy-free allocation
321:Each of the other agents receives 1/
287:
117:minimum-subsidy envy-free allocation
2013:
1980:
1945:
1925:
985:
13:
1683:The Journal of Conflict Resolution
366:
279:
75:), then he takes the item and pay
17:Fair allocation of items and money
14:
2177:
1819:"One Dollar Each Eliminates Envy"
1638:Raith, Matthias G. (2000-05-01).
1310:
508:that may be considered "fairer").
163:such that, for every two objects
130:
1036:, whether positive or negative:
961:Meertens, Potters and Reijnierse
861:{\displaystyle OPT+(n-1)\cdot S}
2097:
2040:
1886:
1865:
1810:
1765:
1670:
1631:
1586:
1563:
1512:
59:The algorithm always yields an
1519:Van Essen, Matt (2013-03-01).
1430:
1356:
1259:
1216:
1174:
1088:
849:
837:
802:
780:
765:
762:
1:
1911:10.1016/S0165-4896(02)00064-1
1656:10.1016/S0165-4896(99)00032-3
1640:"Fair-negotiation procedures"
1439:"Sur la division pragmatique"
1081:
605:allocation requires at most (
2128:10.1007/978-3-030-85947-3_25
1899:Mathematical Social Sciences
1786:10.1007/978-3-030-30473-7_25
1774:"Fair Division with Subsidy"
1644:Mathematical Social Sciences
1486:Journal of Political Economy
1195:10.1007/978-1-349-07357-3_12
1140:Journal of Political Economy
1010:Multi-dimensional objectives
7:
2022:Games and Economic Behavior
1066:
634:round-robin item allocation
632:When there are two agents,
213:Demange, Gale and Sotomayor
10:
2182:
2047:Aziz, Haris (2021-05-18).
1363:Klijn, Flip (2000-03-01).
533:MInimum subsidy procedures
2034:10.1016/j.geb.2014.08.001
1932:Ruggiero Cavallo (2012).
1729:Social Choice and Welfare
1607:10.1109/COMPSACW.2013.100
1369:Social Choice and Welfare
1268:Social Choice and Welfare
1073:Envy-free item allocation
696:Caragiannis and Ioannidis
684:per agent, and at most O(
347:Knaster's auction is not
236:Note that a subsidy of (
2075:10.1609/aaai.v35i6.16645
1695:10.1177/0022002704266148
656:per agent, and at most (
171:, the utility of object
2110:Algorithmic Game Theory
1997:10.1145/1160633.1160790
1966:10.1023/A:1017949922773
1841:10.1145/3391403.3399447
1778:Algorithmic Game Theory
1034:superadditive utilities
955:Alkan, Demange and Gale
667:maximum-weight matching
231:competitive equilibrium
28:Two agents and one item
1437:Steinhaus, H. (1949).
1054:A subsidy of at most (
928:3-dimensional matching
920:
862:
809:
738:
669:in the agents-objects
498:
449:Compensation procedure
98:, then the paid money
1751:10.1007/s003550100149
1576:Czech Economic Review
1381:10.1007/s003550050015
950:Additional procedures
921:
863:
810:
739:
499:
146:More general settings
65:quasilinear utilities
63:. If the agents have
2166:Fair item allocation
1601:. pp. 616–620.
876:
822:
756:
710:
519:envy-graph procedure
482:
256:Tadenuma and Thomson
61:envy-free allocation
21:fair item allocation
497:{\displaystyle n-1}
454:Haake, Raith and Su
387:
197:Quasilinear utility
40:Alice says a price
1280:10.1007/BF00179981
916:
858:
805:
734:
494:
386:
123:Unit-demand agents
2137:978-3-030-85947-3
1850:978-1-4503-7975-5
1795:978-3-030-30473-7
1616:978-1-4799-2159-1
1204:978-1-349-07357-3
1003:Envy-free Pricing
991:Envy-free pricing
615:Turing-equivalent
431:
430:
310:The winner pays (
296:and published by
294:Bronislaw Knaster
288:Knaster's auction
2173:
2150:
2149:
2121:
2101:
2095:
2094:
2068:
2059:(6): 5102–5109.
2044:
2038:
2037:
2017:
2011:
2010:
1984:
1978:
1977:
1949:
1943:
1942:
1940:
1929:
1923:
1922:
1890:
1884:
1883:
1881:
1869:
1863:
1862:
1834:
1814:
1808:
1807:
1769:
1763:
1762:
1744:
1724:
1715:
1714:
1674:
1668:
1667:
1635:
1629:
1628:
1590:
1584:
1583:
1567:
1561:
1560:
1550:
1540:
1538:10.3390/g4010021
1516:
1510:
1509:
1481:
1475:
1474:
1434:
1428:
1427:
1407:
1401:
1400:
1360:
1354:
1353:
1328:(4): 1023–1039.
1317:
1308:
1307:
1263:
1257:
1256:
1231:(6): 1755–1767.
1220:
1214:
1213:
1212:
1211:
1178:
1172:
1171:
1135:
1129:
1128:
1092:
986:Related problems
925:
923:
922:
917:
909:
908:
867:
865:
864:
859:
814:
812:
811:
806:
801:
800:
793:
792:
775:
743:
741:
740:
735:
549:Halpern and Shah
503:
501:
500:
495:
388:
385:
342:Pareto efficient
2181:
2180:
2176:
2175:
2174:
2172:
2171:
2170:
2156:
2155:
2154:
2153:
2138:
2102:
2098:
2045:
2041:
2018:
2014:
2007:
1991:. p. 882.
1985:
1981:
1950:
1946:
1938:
1930:
1926:
1891:
1887:
1870:
1866:
1851:
1815:
1811:
1796:
1770:
1766:
1725:
1718:
1675:
1671:
1636:
1632:
1617:
1591:
1587:
1568:
1564:
1517:
1513:
1482:
1478:
1455:10.2307/1907319
1435:
1431:
1408:
1404:
1361:
1357:
1334:10.2307/2938172
1318:
1311:
1264:
1260:
1237:10.2307/2938288
1221:
1217:
1209:
1207:
1205:
1179:
1175:
1136:
1132:
1109:10.2307/1912044
1093:
1089:
1084:
1069:
1012:
993:
988:
952:
940:budget-balanced
901:
897:
877:
874:
873:
823:
820:
819:
788:
784:
783:
779:
771:
757:
754:
753:
711:
708:
707:
671:bipartite graph
603:leximin-optimal
535:
483:
480:
479:
461:Find a maxsum (
451:
369:
367:Raith's auction
290:
282:
280:Additive agents
229:The proofs use
148:
133:
125:
86:The paid money
30:
12:
11:
5:
2179:
2169:
2168:
2152:
2151:
2136:
2096:
2039:
2012:
2005:
1979:
1960:(2): 107–126.
1944:
1924:
1905:(3): 223–233.
1885:
1864:
1849:
1809:
1794:
1764:
1742:10.1.1.26.8883
1716:
1689:(4): 506–524.
1669:
1650:(3): 303–322.
1630:
1615:
1585:
1562:
1511:
1498:10.1086/319550
1476:
1429:
1402:
1375:(2): 201–215.
1355:
1309:
1274:(3): 267–276.
1258:
1215:
1203:
1173:
1152:10.1086/261411
1146:(4): 863–872.
1130:
1103:(4): 939–954.
1086:
1085:
1083:
1080:
1079:
1078:
1076:
1068:
1065:
1064:
1063:
1052:
1048:
1045:
1042:budget balance
1011:
1008:
992:
989:
987:
984:
951:
948:
947:
946:
943:
932:
931:
915:
912:
907:
904:
900:
896:
893:
890:
887:
884:
881:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
816:
804:
799:
796:
791:
787:
782:
778:
774:
770:
767:
764:
761:
733:
730:
727:
724:
721:
718:
715:
693:
692:
674:
643:
642:
641:
640:
630:
618:
588:
534:
531:
530:
529:
510:
509:
505:
493:
490:
487:
476:
469:
466:
450:
447:
442:
441:
438:
429:
428:
425:
422:
419:
415:
414:
411:
408:
405:
401:
400:
397:
394:
391:
381:
380:
377:
368:
365:
361:
360:
357:
330:
329:
326:
319:
308:
305:
298:Hugo Steinhaus
289:
286:
281:
278:
147:
144:
139:Rental Harmony
132:
131:Rental harmony
129:
124:
121:
57:
56:
45:
34:cut and choose
29:
26:
19:is a class of
9:
6:
4:
3:
2:
2178:
2167:
2164:
2163:
2161:
2147:
2143:
2139:
2133:
2129:
2125:
2120:
2115:
2111:
2107:
2100:
2092:
2088:
2084:
2080:
2076:
2072:
2067:
2062:
2058:
2054:
2050:
2043:
2035:
2031:
2027:
2023:
2016:
2008:
2002:
1998:
1994:
1990:
1983:
1975:
1971:
1967:
1963:
1959:
1955:
1954:Public Choice
1948:
1937:
1936:
1928:
1920:
1916:
1912:
1908:
1904:
1900:
1896:
1889:
1880:
1875:
1868:
1860:
1856:
1852:
1846:
1842:
1838:
1833:
1828:
1824:
1820:
1813:
1805:
1801:
1797:
1791:
1787:
1783:
1779:
1775:
1768:
1760:
1756:
1752:
1748:
1743:
1738:
1734:
1730:
1723:
1721:
1712:
1708:
1704:
1700:
1696:
1692:
1688:
1684:
1680:
1673:
1665:
1661:
1657:
1653:
1649:
1645:
1641:
1634:
1626:
1622:
1618:
1612:
1608:
1604:
1600:
1596:
1589:
1582:(2): 143–153.
1581:
1577:
1573:
1566:
1558:
1554:
1549:
1544:
1539:
1534:
1530:
1526:
1522:
1515:
1507:
1503:
1499:
1495:
1491:
1487:
1480:
1472:
1468:
1464:
1460:
1456:
1452:
1448:
1444:
1440:
1433:
1425:
1421:
1417:
1413:
1406:
1398:
1394:
1390:
1386:
1382:
1378:
1374:
1370:
1366:
1359:
1351:
1347:
1343:
1339:
1335:
1331:
1327:
1323:
1316:
1314:
1305:
1301:
1297:
1293:
1289:
1285:
1281:
1277:
1273:
1269:
1262:
1254:
1250:
1246:
1242:
1238:
1234:
1230:
1226:
1219:
1206:
1200:
1196:
1192:
1188:
1184:
1177:
1169:
1165:
1161:
1157:
1153:
1149:
1145:
1141:
1134:
1126:
1122:
1118:
1114:
1110:
1106:
1102:
1098:
1091:
1087:
1077:
1074:
1071:
1070:
1061:
1057:
1053:
1049:
1046:
1043:
1039:
1038:
1037:
1035:
1031:
1027:
1023:
1021:
1017:
1007:
1005:
1004:
998:
983:
981:
977:
973:
972:VCG mechanism
968:
964:
962:
958:
956:
944:
941:
937:
936:
935:
929:
913:
910:
905:
902:
898:
894:
891:
888:
885:
882:
879:
871:
855:
852:
846:
843:
840:
834:
831:
828:
825:
817:
797:
794:
789:
785:
776:
772:
768:
759:
751:
747:
731:
728:
725:
722:
719:
716:
713:
705:
701:
700:
699:
697:
690:
687:
683:
679:
675:
672:
668:
663:
659:
655:
651:
650:
649:
647:
639:
635:
631:
627:
623:
619:
616:
612:
608:
604:
600:
599:
597:
593:
589:
586:
582:
578:
574:
570:
566:
562:
558:
554:
553:
552:
550:
546:
544:
540:
527:
526:
525:
522:
520:
516:
506:
491:
488:
485:
477:
474:
470:
467:
464:
460:
459:
458:
455:
446:
445:are 90, 90).
439:
436:
435:
434:
426:
423:
420:
417:
416:
412:
409:
406:
403:
402:
398:
395:
392:
390:
389:
384:
378:
375:
374:
373:
364:
358:
354:
353:
352:
350:
349:strategyproof
345:
343:
339:
335:
327:
324:
320:
317:
313:
309:
306:
303:
302:
301:
299:
295:
285:
277:
275:
270:
266:
263:
259:
257:
253:
251:
247:
243:
239:
234:
232:
228:
224:
220:
216:
214:
210:
208:
204:
202:
198:
194:
190:
186:
182:
178:
174:
170:
166:
162:
158:
154:
143:
141:
140:
128:
120:
118:
114:
110:
109:
108:envy-freeness
103:
101:
97:
93:
89:
84:
82:
78:
74:
70:
66:
62:
54:
50:
46:
43:
39:
38:
37:
35:
25:
22:
18:
2109:
2099:
2056:
2052:
2042:
2025:
2021:
2015:
1988:
1982:
1957:
1953:
1947:
1934:
1927:
1902:
1898:
1888:
1867:
1822:
1812:
1777:
1767:
1732:
1728:
1686:
1682:
1672:
1647:
1643:
1633:
1598:
1588:
1579:
1575:
1565:
1531:(1): 21–37.
1528:
1524:
1514:
1489:
1485:
1479:
1446:
1443:Econometrica
1442:
1432:
1418:(1): 101–4.
1415:
1412:Econometrica
1411:
1405:
1372:
1368:
1358:
1325:
1322:Econometrica
1321:
1271:
1267:
1261:
1228:
1225:Econometrica
1224:
1218:
1208:, retrieved
1186:
1176:
1143:
1139:
1133:
1100:
1097:Econometrica
1096:
1090:
1059:
1055:
1025:
1024:
1019:
1013:
1002:
996:
994:
979:
975:
966:
965:
960:
959:
954:
953:
933:
869:
749:
745:
703:
695:
694:
688:
685:
681:
677:
661:
657:
653:
645:
644:
637:
625:
621:
610:
606:
595:
591:
584:
580:
576:
572:
568:
564:
560:
548:
547:
542:
538:
536:
523:
514:
511:
472:
453:
452:
443:
432:
382:
370:
362:
346:
338:proportional
333:
331:
322:
315:
311:
291:
283:
268:
267:
261:
260:
255:
254:
249:
245:
241:
237:
235:
226:
222:
218:
217:
212:
211:
206:
205:
200:
192:
188:
184:
180:
176:
172:
168:
164:
160:
149:
138:
134:
126:
116:
112:
106:
104:
99:
96:entitlements
91:
87:
85:
80:
76:
72:
69:proportional
58:
52:
48:
41:
31:
16:
15:
1548:10419/98565
1449:: 315–319.
515:envy-cycles
463:utilitarian
325:of his bid;
318:of his bid;
191:and paying
2119:2106.00841
2066:2003.08125
2006:1595933034
1941:. AAAI-12.
1879:2002.02789
1832:1912.02797
1735:(4): 723.
1492:(2): 418.
1210:2021-02-16
1082:References
629:algorithm.
557:envy-graph
274:envy graph
157:increasing
153:continuous
2146:235294139
2091:212747875
2083:2374-3468
2028:: 29–46.
1974:152637454
1919:0165-4896
1859:208637311
1804:143425023
1737:CiteSeerX
1664:0165-4896
1557:2073-4336
1506:154200252
1463:0012-9682
1389:1432-217X
1342:0012-9682
1304:154215964
1288:0176-1714
1245:0012-9682
1168:154114302
1117:0012-9682
1030:equitable
1006:problem.
911:⋅
903:−
895:⋅
853:⋅
844:−
777:ε
729:⋅
726:ε
513:contains
489:−
142:problem.
2160:Category
1711:18162264
1625:14873917
1397:18544150
1296:41106132
1067:See also
1051:NP-hard.
1016:makespan
997:maximize
744:, where
539:minimize
356:ex-ante.
262:Aragones
207:Svensson
113:minimize
1759:2784141
1703:4149806
1471:1907319
1424:1914289
1350:2938172
1253:2938288
1160:1833206
1125:1912044
1020:Mu'alem
980:Cavallo
967:Cavallo
473:surplus
418:George
396:Item 2
393:Item 1
2144:
2134:
2089:
2081:
2003:
1972:
1917:
1857:
1847:
1802:
1792:
1757:
1739:
1709:
1701:
1662:
1623:
1613:
1555:
1504:
1469:
1461:
1422:
1395:
1387:
1348:
1340:
1302:
1294:
1286:
1251:
1243:
1201:
1166:
1158:
1123:
1115:
976:Bailey
404:Alice
219:Maskin
2142:S2CID
2114:arXiv
2087:S2CID
2061:arXiv
1970:S2CID
1939:(PDF)
1874:arXiv
1855:S2CID
1827:arXiv
1800:S2CID
1755:S2CID
1707:S2CID
1699:JSTOR
1621:S2CID
1525:Games
1502:S2CID
1467:JSTOR
1420:JSTOR
1393:S2CID
1346:JSTOR
1300:S2CID
1292:JSTOR
1249:JSTOR
1164:S2CID
1156:JSTOR
1121:JSTOR
269:Klijn
175:plus
2132:ISBN
2079:ISSN
2001:ISBN
1915:ISSN
1845:ISBN
1790:ISBN
1660:ISSN
1611:ISBN
1553:ISSN
1459:ISSN
1385:ISSN
1338:ISSN
1284:ISSN
1241:ISSN
1199:ISBN
1113:ISSN
1026:Aziz
982:is.
978:and
427:180
424:120
399:Sum
344:.
314:-1)/
167:and
155:and
2124:doi
2071:doi
2030:doi
1993:doi
1962:doi
1907:doi
1837:doi
1782:doi
1747:doi
1691:doi
1652:doi
1603:doi
1543:hdl
1533:doi
1494:doi
1490:109
1451:doi
1377:doi
1330:doi
1276:doi
1233:doi
1191:doi
1148:doi
1105:doi
1058:-1)
750:all
680:-1)
660:-1)
624:-1)
609:-1)
594:-1)
583:-1)
421:60
413:20
410:10
407:10
240:-1)
223:n-1
195:).
36:):
2162::
2140:.
2130:.
2122:.
2085:.
2077:.
2069:.
2057:35
2055:.
2051:.
2026:88
2024:.
1999:.
1968:.
1958:91
1956:.
1913:.
1903:44
1901:.
1897:.
1853:.
1843:.
1835:.
1821:.
1798:.
1788:.
1753:.
1745:.
1733:19
1731:.
1719:^
1705:.
1697:.
1687:48
1685:.
1681:.
1658:.
1648:39
1646:.
1642:.
1619:.
1609:.
1597:.
1578:.
1574:.
1551:.
1541:.
1527:.
1523:.
1500:.
1488:.
1465:.
1457:.
1447:17
1445:.
1441:.
1416:16
1414:.
1391:.
1383:.
1373:17
1371:.
1367:.
1344:.
1336:.
1326:59
1324:.
1312:^
1298:.
1290:.
1282:.
1272:12
1270:.
1247:.
1239:.
1229:59
1227:.
1197:,
1185:,
1162:.
1154:.
1144:94
1142:.
1119:.
1111:.
1101:51
1099:.
1060:mV
899:10
638:V.
585:mV
577:mV
545:.
233:.
227:V.
119:.
2148:.
2126::
2116::
2093:.
2073::
2063::
2036:.
2032::
2009:.
1995::
1976:.
1964::
1921:.
1909::
1882:.
1876::
1861:.
1839::
1829::
1806:.
1784::
1761:.
1749::
1713:.
1693::
1666:.
1654::
1627:.
1605::
1580:3
1559:.
1545::
1535::
1529:4
1508:.
1496::
1473:.
1453::
1426:.
1399:.
1379::
1352:.
1332::
1306:.
1278::
1255:.
1235::
1193::
1170:.
1150::
1127:.
1107::
1056:n
914:S
906:4
892:3
889:+
886:T
883:P
880:O
870:n
856:S
850:)
847:1
841:n
838:(
835:+
832:T
829:P
826:O
815:.
803:)
798:1
795:+
790:2
786:n
781:)
773:/
769:m
766:(
763:(
760:O
746:S
732:S
723:+
720:T
717:P
714:O
704:ε
689:V
686:n
682:V
678:n
673:.
662:V
658:n
654:V
626:V
622:n
611:V
607:n
596:V
592:n
581:n
573:V
569:m
565:i
561:i
492:1
486:n
475:.
334:n
323:n
316:n
312:n
250:V
246:V
242:V
238:n
225:)
201:V
193:V
189:k
185:j
181:k
177:V
173:j
169:k
165:j
161:V
100:p
92:p
88:p
81:p
77:p
73:p
55:.
53:p
49:p
42:p
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.