909:"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".
917:"a housemate who is assigned a room with a negative room rent is subsidized by some of other housemates. In such a situation, some housemates may prefer to leave the room with negative room rent unused and to exclude the housemate who is assigned that room, because they may receive larger discount. In order to avoid such a situation, negative room rents must be avoided".
1379:, i.e., allocate (1,2) with price to agents (1,2) for half a year and reverse the allocation for the other half, and charge each agent 500. They show a linear program for finding a fractional EF allocation if it exists. They show that finding an EF allocation with a smallest amount of total switches is NP-hard (by reduction from
832:
There can be 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 least a certain number of items", or "some items
1325:
functions - their utility is the room value minus the price. But in reality, agents have budget constraints - if the room price is above their budget, the utility drops much faster than linearly. In fact, an agent always prefers any room with a price at most his budget, to a room with a price larger
1260:
The solution of Sung and Vlach seems to have all the desirable properties of the previous protocols, i.e.: PE and EF and NN (if possible) and polynomial run-time, and in addition, it guarantees that every envious partner gets a free room. provides an implementation of a similar solution, also based
996:
In practice, it is not necessary to change the price continuously, since the only interesting prices are prices in which the demand-sets of one or more partners change. It is possible to calculate the set of interesting prices in advance, and convert the continuous-price auction to a discrete-price
462:
Su suggests to weaken this assumption in the following way: each partner never chooses the most expensive room if there is a free room available. This does not require the person to choose the free room. In particular, this will hold if a person always prefers a free room to a room costing at least
1281:
website, note that envy-freeness alone is insufficient to guarantee the satisfaction of the participants. Therefore they build an algorithmic framework, based on linear programming, for calculating allocations that are both envy-free and optimize some criterion. Based on theoretic and experimental
848:
Find a maxsum (utilitarian) 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
458:
Both Su's solution and
Azrieli&Shmaya's solution make a "Miserly tenants" assumption - they assume that a tenant always prefers a free room to a non-free room. This assumption is strong and not always realistic. If one of the rooms is very bad, it is possible that some tenants will not want to
891:
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
754:
Note that this example does not occur in the ordinal version, since the ordinal protocols make the "Miserly
Partners" assumption - partners always prefer free rooms. When this assumption holds, there always exists an EF+NN allocation. But, in the above example, the assumption does not hold and an
429:
In both Su's solution and
Azrieli&Shmaya's solution, the preference relation of each partner is allowed (but not obliged) to depend on the entire price-vector. I.e, a partner may say "if room A costs 1000, then I prefer room B to room C, but if room A costs only 700, then I prefer room C to
896:
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
662:
In this example, the sum of valuations is more than the total cost. If the sum of valuations equals the total cost, and there are two or three partners, then there always exists an EF and NN allocation. But if there are four or more partners, then again EF and NN might be incompatible, as in the
355:
for cake-cutting: for every vertex of a triangulation of the dual simplex, which corresponds to a certain price scheme, it asks the owning partner "which room do you prefer in that pricing scheme?". This results in a
Sperner coloring of the dual simplex, and thus there exists a small sub-simplex
804:
Moreover, the Gap
Procedure may return non-envy-free allocations, even when EF allocations exist. Brams relates to this problem saying that: "Gap prices do take into account the competitiveness of bidding for goods, which makes the pricing mechanism market-oriented. Although envy-freeness is a
1329:
In this case, there may not exist a price-vector that is both EF and affordable. For example, suppose the total rent is 1000, there are two rooms and two agents with identical valuations: 800 and 200, and identical budget: 600. There is a single price-vector in which both agents have the same
522:. Rental harmony exists whenever there exists a price that is too high for all agents. This assumption is weaker than the miserly tenants assumption, and weaker than quasilinearity. It is an open question, whether there is an even weaker assumption that guarantees existence of rental harmony.
2396:. The ENEF criterion seems more appropriate than the GPEF criterion, because it measures not only the probability of entire envy-freeness, but also the quality of the cases in which the allocation is not entirely envy-free. The maximum ENEF of a truthful-in-expectation mechanism is at most
2581:
A possible relaxation of the strategyproofness requirement is to try to minimize the "degree of manipulability". This is defined by counting, for each profile, the number of agents who can manipulate the rule. Maximally-preferred fair allocation rules are the minimally (individually and
2518:
to calculate a maxsum assignment and payments. Select one partner at random. Ignore that partner and use VCG again. Combine the outcomes in a way which guarantees that the total payment equals the total cost (see the paper for details). It is possible to show that: (a) the mechanism is
2033:
There is a variant of the problem in which, instead of assuming that the total house cost is fixed, we assume that there is a maximum cost for each room. In this variant, a strategyproof mechanism exists: the deterministic allocation-rule selecting the min-sum cost is strategyproof.
901:. These cycles can be removed by moving bundles along the cycle. 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.
1442:
Velez studies the strategic properties of these algorithms. He shows that, the complete-information non-cooperative outcomes of each of the algorithms are exactly the EF allocations w.r.t. true preferences, iff the number of allowed disutilities is bounded.
1210:
Decrease only the positive prices in a constant rate, until the sum equals the total cost. Here, the prices do not change by the same amount, so some partners will necessarily envious, as in the solution of Brams and
Kilgour. However, in this solution,
2582:
coalitionally) manipulable fair and budget-balanced allocation rules according to this new concept. Such rules choose allocations with the maximal number of agents for whom the utility is maximized among all fair and budget-balanced allocations.
1336:
Procaccia, Velez and Yu present an efficient algorithm for finding whether there exists an allocation that is both EF and affordable. If so, it finds an allocation that, among all EF affordable allocations, maximizes the smallest utility (as in
74:-room house for cost fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view to the main road, etc. The following two problems should be solved simultaneously:
1000:
The returned allocation is always envy-free. The prices may be negative, like in the procedure of Haake et al. However, in contrast to that procedure, the prices are non-negative if there exists an EF allocation with non-negative prices.
836:
The total "cost" can also be positive, which means that there is also some money to share. This is characteristic of inheritance division scenarios. Similarly, the "items" can have negative utility (e.g., they can represent indivisible
437:
Future planning. Suppose the partner thinks that room A is best, then B, then C. If A is expensive, the partner settles on B. But if A is cheaper, the partner might buy C (which is the cheapest), and then save some money and switch to
451:. If room B and room C are of the same quality and have the same price, then the partner may buy A. But, if room B becomes more expensive, then the partner may switch to C, thinking that "it is the same as B but in bargain price..".
105:
a given room if he believes that the parcel of room+rent is weakly better than all other parcels. EF means that every partner prefers his allotted room. I.e, no partner would like to take another room at the rent assigned to that
220:
The cardinal assumption implies the ordinal assumption, since given a valuation vector it is always possible to construct a preference relation. The ordinal assumption is more general and puts less mental burden on the partners.
788:
The idea behind the last step is that the next-lowest valuations represent the "competition" on the rooms. If there a room is more wanted by the next-highest bidder, then it should cost more. This is similar in spirit to the
904:
The
Compensation Procedure might charge some partners a negative payment (i.e., give the partners a positive amount of money). This means that the Compensation Procedure is EF (hence also PE) but not NN. The authors say:
800:
The Gap
Procedure always assigns non-negative prices. Because the assignment is maxsum, it is obviously also Pareto-efficient. However, some partners may be envious. I.e, the Gap procedure satisfies NN and PE but not EF.
530:
As explained above, the input to the cardinal version is a matrix of bids: every partner has to submit a bid to each room, saying how much (in dollars) this room is worth for him. It is usually assumed that agents have
2321:. This is not encouraging, since the probability of envy-freeness converges to 0 when the number of partners grows. But it is impossible to do better: in every truthful-in-expectation mechanism, the GPEF is at most
459:
live in that room even for free. This is easy to see in the cardinal version: if you believe that room A is worth 0 and room B is worth 100, and room A is free and room B costs 50, then you certainly prefer room B.
2093:
of the total cost. But this condition is not appealing, since there is a large chance that in the final outcome, many partners will be envious. They may not be comforted by the fact that the lottery has been fair.
2064:
means that no partner envies the lottery of any other partner. This condition is trivial to achieve in a truthful mechanism: randomise over all possible allocations with equal probability and charge each partner
1427:). He presents an algorithm that find an EF rent division that is, moreover, egalitarian (max min utility), or money-Rawlsian (min-max rent), or satisfies one of other similar conditions. The run-time is in O(
888:
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.
123:
Suppose by contradiction that there exists an alternative assignment, with the same price-vector, that is strictly better for at least one partner. Then, in the current allocation, that partner is envious.
793:. However, while in the Vickrey auction the payment is entirely independent of the partner's bid, in the Gap procedure the payment is only partially independent. Therefore, the Gap procedure is not
1503:: there is no deterministic strategyproof protocol that always returns an envy-free allocation. This is true even when there are only two partners and when the prices are allowed to be negative.
1333:
Note that the condition of "price too high" still holds in this case, but the preferences are not continuous (the agents prefer only room 2 when p1>600 and only room 1 when p1<=600).
146:
version, each partner has a vector of monetary valuations. The partner should say, for each room, exactly how much money he is willing to pay for that room. The partner is assumed to have
1330:
quasilinear utility: (800,200); but the agent in room 1 does not have enough budget to pay. In contrast, there are affordable price-vectors, e.g. (600,400), but they are not envy-free.
659:
Here, the only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. In order to make sure partner 2 does not envy, partner 1 must pay 115 and partner 2 must pay -15.
359:
Su's protocol returns a sequence of allocations which converges to an envy-free allocation. The prices are always non-negative. Hence, the outcome satisfies the NN and EF requirements.
1269:
Aragones presented a polytime algorithm for finding an EF solution that, among all EF solutions, maximizes the smallest payment by an agent (it is called the Money
Rawlsian solution).
2376:
such that, if we average the number of partners who do not envy in all possible outcomes of the mechanism, then regardless of the partners' valuations, the expectation is at least
2217:
1569:
349:
1205:
1135:
1750:
1709:
370:
Azriely and Shmaya generalize Su's solution to a situation in which the capacity of each room may be larger than one (i.e., several partners can live in the same room).
2239:
rooms to the right. This randomized mechanism is truthful-in-expectation, since every partner has an equal probability to land in each room and the expected payment is
1668:
1372:
for computing a BF-EF allocation if it exists. They also show a polytime algorithm for a fixed price-vector, and a pseudopolytime algorithm for a fixed room assignment.
1255:
590:
2434:
501:
2486:
855:
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
3349:
1780:
1635:
755:
EF+NN allocation does not exist. Therefore, the protocols in the cardinal version have to compromise between EF and NN. Each protocol makes a different compromise.
300:
2571:
2543:
2512:
2460:
2347:
2319:
2291:
2265:
2167:
2091:
2020:
1952:
1924:
1856:
1531:
964:
886:
214:
2394:
2374:
2237:
2139:
2119:
1992:
1972:
1896:
1876:
610:
320:
188:
168:
72:
52:
1828:
774:
If the max-sum is less than the total cost, then the problem is unsolvable, since the partners do not want to pay the total amount required by the houseowner.
620:
The two requirements of envy-freeness and non-negative payments are not always compatible. For example, suppose the total cost is 100 and the valuations are:
2733:
Potthoff, Richard F. (2002). "Use of Linear Programming to Find an Envy-Free Solution Closest to the Brams–Kilgour Gap Solution for the Housemates Problem".
1451:
Arunachaleswaran, Barman and Rathi study a setting substantially more general than quasilinear, in which the utility of each agent from each room can be any
1059:
Find a minsum price-vector (a vector in which the sum of prices is minimized), subject to the envy-freeness constraint. Such price-vector is a solution of a
2892:
Haake, Claus-Jochen; Raith, Matthias G.; Su, Francis Edward (2002). "Bidding for envy-freeness: A procedural approach to n-player fair-division problems".
1411:
Both these relaxations significantly enlarge the set of EF allocations. However, even with each of these relaxations, an EF allocation might not exist.
3269:
1073:
If the min-sum is less than the total cost, then increase all prices in a constant rate until the sum equals the total cost (i.e., add to each price:
548:) allocation. This is an allocation of partners to rooms, that maximizes the sum of bids. The problem of finding a maxsum allocation is known as the
115:: No other assignment of partners to rooms is weakly better for all partners and strictly better for at least one partner (given the price-vector).
817:
Haake, Raith and Su present the Compensation Procedure. The problem it solves is more general than the rental-harmony problem in certain aspects:
976:
Calculate the set of over-demanded rooms (rooms that are demanded by more partners than the number of rooms; see the paper for exact definition).
418:
Their solution is constructive in the same sense as Su's solution - there is a procedure that approximates the solution to any given precision.
982:
Simultaneously, decrease the price of all other rooms in the same rate, such that the sum of prices of all rooms always equals the total cost.
3328:
1455:
of the rent. This setting generalizes the soft budget constraint. As there is a too-high price, an EF allocation always exists. They show an
1140:
If the min-sum is more than the total cost, then there is no solution satisfying both NN and EF. There are several possible ways to proceed:
444:
Neighbors. The price-vector may allow the partner to predict, to some extent, what kind of people are going to live in the neighboring rooms.
1423:. Each agent reports their values for rooms, their budget, and their marginal disutility from having to pay more than the budget (e.g. the
2057:
of his utility by mis-reporting his valuations to the rooms. The fairness of a randomized mechanism can be measured in several ways:
3244:
2955:
1344:
Airiau, Gilbert, Grandi, Lang and Wilczynski suggest two solutions to overcome the non-existence problem with budget constraints:
2037:
This result can be generalized for greater flexibility on the indivisible objects, and a proof of coalitional strategy-proofness.
3620:
139:
on bundles . Given a price-vector, the partner should only be able to say which room (or rooms) he prefers to rent at that price.
2972:
2049:. A randomized mechanism returns a probability distribution over room-assignments and rent-divisions. A randomized mechanism is
2645:
1368:'s budget. A BF-EF allocation is more likely to exist than an EF allocation, but still not guaranteed to exist. They show a
3000:
3615:
2603:- each agent should get a single object (house); randomization is not allowed. The goals are efficiency and/or fairness.
2609:- each agent should get at most one object; the goal is to maximize the number of assignments subject to envy-freeness.
2267:
of the total cost, regardless of the partner's bid. The probability of having an EF allocation is the probability that
1384:
1338:
1064:
362:
Su's Rental Harmony protocol has been popularized in several news articles, and has several online implementations.
3516:
Andersson, Tommy; Svensson, Lars-Gunnar (2008). "Non-manipulable assignment of individuals to positions revisited".
3307:
Airiau, Sté phane; Gilbert, Hugo; Grandi, Umberto; Lang, Jé rô me; Wilczynski, Anaë lle (2023),
805:
desirable property, I prefer a marketlike mechanism when there is a conflict between these two properties; partners
2858:
989:
411:
3483:
2817:
Abdulkadiroğlu, Atila; Sönmez, Tayfun; Utku Ünver, M. (2004). "Room assignment-rent division: A market approach".
3049:
1452:
777:
If the max-sum exactly equals the total cost, then the rooms are allocated and the partners pay their valuations.
352:
251:: The preference relation of each partner depends on the rooms and the rents, but not on choices made by others.
3163:
2600:
2621:- each agent should get a single object; the goal is to maximize the total value, or minimize the total cost.
1479:>2 is some constant. They also show that the problem lines in the intersection of the complexity classes
1143:
Decrease all prices in a constant rate until the sum equals the total cost (i.e., subtract from each price:
266:: A partner who prefers a room for a convergent sequence of prices, prefers that room at the limiting price.
2590:
There are several problems in which there are only indivisible items to share, with no monetary transfers:
2172:
1308:
Peters, Procaccia and Zhu study a practical setting in which agents may be unsure about their valuations.
841:
There is a "qualification requirement" for a partner: the sum of his bids must be at least the total cost.
2901:
2826:
2594:
1396:
852:
Charge from each partner the value of the bundle allocated to him. This creates the initial pool of money.
127:
The rental-harmony problem has been studied under two different assumptions on the partners' preferences:
503:
of the total rent. However, even this weakened assumption might be unrealistic, as in the above example.
2545:. Simulations show that in about 80% of the cases, the GPEF of this mechanism is also at its maximum of
1536:
1070:
If the min-sum equals the total cost, implement the maxsum allocation with the minsum prices and finish.
441:
Incomplete information. The price-vector may give the partner some indication on the quality of rooms.
325:
81:(b) Determine the amount each partner should pay, such that the sum of payments equals the fixed cost.
3080:
2612:
2519:
truthful-in-expectation; (b) all partners except the ignored partner do not envy. Hence, the ENEF is
1146:
1076:
401:
261:
23:
problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The
2906:
2831:
1714:
1673:
1388:
1322:
1277:
Gal, Mash, Procaccia and Zick, based on their experience with the rent division application in the
553:
532:
147:
136:
1495:
All protocols surveyed so far assume that the partners reveal their true valuations. They are not
3446:
3250:
3145:
3092:
3054:
2977:
2919:
2794:
2750:
2715:
2697:
2665:
2618:
2606:
1286:- maximizing the minimum utility of an agent subject to envy-freeness - attains optimal results.
1060:
931:
549:
518:
if, whenever some room costs T and some other room is free, no room prefers the room that costs
1640:
3464:
3403:
3384:
3343:
3324:
3240:
3209:
3110:
2951:
1480:
1380:
1278:
1224:
927:
559:
110:
2399:
833:
must be bundled together" (e.g. because they are land-plots that must remain connected), etc.
612:
is the number of partners). Every EF allocation is maxsum and every maxsum allocation is PE.
506:
Segal-Halevi shows that the assumption can be weakened even further. Let us say that a price
466:
3589:
3579:
3525:
3498:
3456:
3434:
3415:
3376:
3316:
3232:
3201:
3137:
3102:
2911:
2836:
2786:
2742:
2707:
2657:
2465:
1484:
1283:
143:
2488:, there is a truthful-in-expectation mechanism that almost attains this bound: the ENEF is
1758:
1613:
1407:). They conjecture that minimizing the largest amount of switches per agent is NP-hard too.
273:
245:: In any partition of the rent, each person finds at least one room+rent parcel acceptable.
790:
132:
2548:
2522:
2491:
2439:
2324:
2296:
2270:
2242:
2144:
2068:
1997:
1929:
1901:
1833:
1510:
941:
865:
193:
1137:). Changing all prices by the same amount ensures that the assignment remains envy-free.
257:: every tenant weakly prefers a free room (a room with a rent of 0) over any other room.
3365:"A polynomial algorithm for maxmin and minmax envy-free rent division on a soft budget"
2379:
2359:
2222:
2124:
2104:
2054:
1977:
1957:
1881:
1861:
849:
least one item per partner"), then a maxsum allocation might be more difficult to find.
595:
448:
351:. Su's protocol operates on a dualized version of this simplex in a similar way to the
305:
173:
153:
57:
37:
3502:
1785:
1610:
The only maxsum allocation is giving room 1 to partner 1 and room 2 to partner 2. Let
1221:
The runtime complexity of both finding maxsum allocation and finding minsum prices is
1207:). Some prices will necessarily be negative, as in the solution of Haake Raith and Su.
985:
At each instant, update the demand of each partner and the set of over-demanded rooms.
3609:
3529:
3149:
2754:
2515:
1507:: Assume that the total cost is 100 and the partners' valuations are as below (where
1496:
1424:
794:
780:
If the max-sum is more than the total cost, then the prices are lowered based on the
405:
96:
20:
3315:, Frontiers in Artificial Intelligence and Applications, IOS Press, pp. 52–59,
3308:
3254:
2798:
2719:
2022:(and thus push his own payment down). Hence, the mechanism cannot be strategyproof.
784:
between these prices and the next-lowest valuations (see the book for more details).
535:, so that their utility to a room is their value for the room minus the room price.
3544:
2923:
2866:
Proceedings of the IJCAI-2011 Workshop on Social Choice and Artificial Intelligence
1456:
3106:
2597:- each agent should get a single object; fairness is attained using randomization.
1475:
is the number of different disutility values (e.g. different interest rates), and
1435:
is the number of different disutility values (e.g. different interest rates), and
926:
AbdulkadiroÄźlu et al. suggest a market-based approach. It is a combination of an
101:: Given a pricing scheme (an assignment of rent to rooms), we say that a partner
3227:
Gal, Ya'akov (Kobi); Mash, Moshe; Procaccia, Ariel D.; Zick, Yair (2016-07-21).
3380:
3294:
2948:
Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures
1289:
Note that, since their solution is always EF, it might return negative prices.
373:
They prove the existence of envy-free allocations in the following conditions:
3419:
2840:
2790:
2746:
2711:
2045:
Going back to the original rental-harmony problem, it is possible to consider
973:
of each partner: the room or set of rooms he likes most at the current prices.
235:
3468:
3433:
Arunachaleswaran, Eshwar Ram; Barman, Siddharth; Rathi, Nidhi (August 2022).
3388:
3364:
3213:
3114:
3025:
2121:
such that, regardless of the partners' valuations, with probability at least
356:
which corresponds to an approximate envy-free assignment of rooms and rents.
3236:
809:
pay more when bids are competitive, even at the sacrifice of causing envy".
3460:
2141:, the final outcome will be envy-free. It is possible to achieve a GPEF of
997:
auction. This discrete-price auction stops after a finite number of steps.
85:
There are several properties that we would like the assignment to satisfy.
2915:
270:
Normalize the total rent to 1. Then each pricing scheme is a point in an
3594:
3128:
Brams, Steven J.; Kilgour, D. Marc (2001). "Competitive Fair Division".
2777:
Sung, Shao Chin; Vlach, Milan (2004). "Competitive envy-free division".
380:: Every partner likes at least one of the rooms given each price vector.
92:: all prices must be 0 or more: no partner should be paid to get a room.
3320:
3205:
2669:
2688:
Azrieli, Yaron; Shmaya, Eran (2014). "Rental harmony with roommates".
2577:
Andersson and Ehlers and Svensson: Attaining partial-strategyproofness
2169:
in the following way: find an envy-free assignment; choose an integer
1261:
on solving a linear-programming problem but citing a different paper.
1009:
Sung and Vlach prove the following general properties of allocations:
3189:
913:
However, other authors claim that, in the usual housemates scenario:
540:
3435:"Fully Polynomial-Time Approximation Schemes for Fair Rent Division"
3167:
2661:
1293:
238:
makes the following assumptions on the preferences of the partners:
3584:
3567:
3451:
3141:
3097:
862:
Eliminate envy by compensating envious partners. There are at most
2702:
1052:
Based on these properties, they propose the following algorithm:
1369:
3268:
Peters, Dominik; Procaccia, Ariel D.; Zhu, David (2022-12-06).
979:
Increase the price of all over-demanded rooms in the same rate;
3566:
Andersson, Tommy; Ehlers, Lars; Svensson, Lars-Gunnar (2014).
3545:"A general strategy-proof fair allocation mechanism revisited"
1954:, then partner 1 has an incentive to report a higher value of
1858:, then partner 2 has an incentive to report a lower value of
988:
When the set of over-demanded rooms is empty, stop and apply
934:. It is simplest to describe as a continuous-price auction:
2025:
Researchers have coped with this impossibility in two ways.
1499:- a partner can gain by reporting false valuations. Indeed,
1459:- an algorithm that finds an allocation that is EF up to (1+
1297:
1321:
Most papers in the cardinal model assume that agents have
922:
Abdulkadiroglu and Sonmez and Unver: EF and NN if possible
433:
There are several reasons such generality can be useful.
1994:, in order to push the payment of partner 2 up towards
1637:
be the price of room 2 (so that the price of room 1 is
992:
to allocate to each partner a room in their demand-set.
3568:"Budget balance, fairness, and minimal manipulability"
3293:
Ariel D. Procaccia, Rodrigo A. Velez and Dingli Yu. "
2551:
2525:
2494:
2468:
2442:
2402:
2382:
2362:
2327:
2299:
2273:
2245:
2225:
2175:
2147:
2127:
2107:
2071:
2000:
1980:
1960:
1932:
1904:
1884:
1864:
1836:
1788:
1761:
1717:
1676:
1643:
1616:
1539:
1513:
1227:
1149:
1079:
944:
868:
598:
562:
469:
328:
308:
276:
196:
176:
156:
60:
40:
3484:"A general strategy proof fair allocation mechanism"
3001:"Fair division and the whining philosophers problem"
2615:- each agent may get an arbitrary number of objects.
1501:
strategyproofness is incompatible with envy-freeness
1032:
Max-sum implies envy-freeness: given a price-vector
1670:). To ensure partner 1 does not envy, we must have
2646:"Rental Harmony: Sperner's Lemma in Fair Division"
2565:
2537:
2506:
2480:
2454:
2428:
2388:
2368:
2341:
2313:
2285:
2259:
2231:
2211:
2161:
2133:
2113:
2085:
2014:
1986:
1966:
1946:
1918:
1890:
1870:
1850:
1822:
1774:
1744:
1711:. To ensure partner 2 does not envy, we must have
1703:
1662:
1629:
1563:
1525:
1249:
1199:
1129:
1013:Envy-freeness implies maxsum: given an allocation
958:
880:
604:
584:
495:
343:
314:
294:
208:
182:
162:
66:
46:
3274:Advances in Neural Information Processing Systems
3229:Which Is the Fairest (Rent Division) of Them All?
1273:Mash, Gal, Procaccia and Zick: EF and egalitarian
1755:Suppose a deterministic protocol sets the price
2099:Guaranteed Probability of Envy-Freeness (GPEF)
3190:"A derivation of the money Rawlsian solution"
2950:. Princeton, NJ: Princeton University Press.
8:
2354:Expected Number of Envy-Free partners (ENEF)
2219:at random; and move each partner cyclically
2206:
2182:
1898:, in order to push his payment down towards
1213:the envious partners get their room for free
844:The procedure works in the following steps.
538:A key notion in the cardinal solutions is a
3348:: CS1 maint: numeric names: authors list (
2973:"To Divide the Rent, Start With a Triangle"
1292:The maximin solution is implemented in the
821:The number of indivisible items to divide (
392:: The preferences are continuous in prices.
31:are alternative names to the same problem.
3404:"Equitable rent division on a soft budget"
3309:"Fair Rent Division on a Budget Revisited"
2859:"Randomised Room Assignment-Rent Division"
2514:. The general idea is as follows. Use the
2436:. It is possible to attain this bound for
2101:means that there is a certain probability
825:) may differ than the number of partners (
3593:
3583:
3450:
3096:
2905:
2830:
2701:
2555:
2550:
2524:
2493:
2467:
2441:
2418:
2401:
2381:
2361:
2331:
2326:
2303:
2298:
2272:
2249:
2244:
2224:
2174:
2151:
2146:
2126:
2106:
2075:
2070:
2004:
1999:
1979:
1959:
1936:
1931:
1908:
1903:
1883:
1863:
1840:
1835:
1809:
1795:
1787:
1766:
1760:
1734:
1722:
1716:
1693:
1681:
1675:
1654:
1642:
1621:
1615:
1538:
1512:
1238:
1226:
1189:
1148:
1119:
1078:
1036:, if there is an allocation x with which
948:
943:
867:
597:
573:
561:
473:
468:
335:
331:
330:
327:
307:
275:
195:
175:
155:
119:Envy-freeness implies Pareto-efficiency.
59:
39:
3164:"Assign Rooms and Share Rent - Spliddit"
1573:
665:
622:
2887:
2885:
2883:
2857:Lachlan Dufton and Kate Larson (2011).
2812:
2810:
2808:
2631:
2356:means that there is a certain integer
1926:. Similarly, if the price is less than
422:General properties of ordinal protocols
3341:
2941:
2939:
2937:
2935:
2933:
2852:
2850:
2772:
2770:
2768:
2766:
2764:
2683:
2681:
2679:
2639:
2637:
2635:
2041:Dufton and Larson: Using randomization
1387:), but can be solved in time O*(2) by
396:The main tools used in the proof are:
3289:
3287:
3074:
3072:
2212:{\displaystyle i\in \{0,\dots ,n-1\}}
1419:Velez studies EF rent division under
1005:Sung and Vlach: EF and NN if possible
938:Initialize the price of each room to
813:Haake and Raith and Su: EF but not NN
7:
1431:), where n is the number of agents,
1304:Peters, Procaccia and Zhu: Robust EF
1063:problem, and it can be found by the
663:following example (see for proof):
1471:, where n is the number of agents,
3439:Mathematics of Operations Research
3188:Aragones, Enriqueta (1995-06-01).
2029:Sun and Yang: Changing the problem
1564:{\displaystyle 0<x<y<100}
78:(a) Assign a room to each partner,
34:In the typical setting, there are
14:
3085:The American Mathematical Monthly
3079:Segal-Halevi, Erel (2022-05-28).
3026:"Francis Su's Fair Division Page"
2650:The American Mathematical Monthly
892:that may be considered "fairer").
150:, i.e., if he values the room as
3530:10.1016/j.mathsocsci.2008.05.004
3363:Velez, Rodrigo A. (2022-07-01).
759:Brams and Kilgour: NN but not EF
344:{\displaystyle \mathbb {R} ^{n}}
3482:Sun, Ning; Yang, Zaifu (2003).
2999:Procaccia, Ariel (2012-08-15).
2053:if no partner can increase the
1265:Aragones: EF and money-Rawlsian
1200:{\displaystyle (minsum-cost)/n}
1130:{\displaystyle (cost-minsum)/n}
386:: All partners like free rooms.
3295:Fair Rent Division on a Budget
2735:Group Decision and Negotiation
1817:
1789:
1282:tests, they conclude that the
1244:
1231:
1186:
1150:
1116:
1080:
771:Calculate a maxsum allocation.
763:Brams and Kilgour suggest the
579:
566:
552:, and it can be solved by the
490:
478:
366:Azriely and Shmaya: room-mates
289:
277:
54:partners who rent together an
1:
3503:10.1016/s0165-1765(03)00151-4
3107:10.1080/00029890.2022.2037988
2971:Sun, Albert (28 April 2014).
1745:{\displaystyle p_{2}\leq y/2}
1704:{\displaystyle p_{2}\geq x/2}
1017:, if there is a price-vector
29:room-assignment-rent-division
3518:Mathematical Social Sciences
3130:Journal of Political Economy
3081:"Generalized Rental Harmony"
1830:. If the price is more than
1312:Agents with a limited budget
616:Incompatibility of EF and NN
447:Irrationality effects, e.g.
135:version, each partner has a
3408:Games and Economic Behavior
1463:), in time polynomial in 1/
1339:egalitarian item allocation
3637:
3402:Velez, Rodrigo A. (2023).
3381:10.1007/s00355-021-01386-z
2690:Journal of Economic Theory
1447:Piecewise linear utilities
404:- a generalization of the
302:-dimensional simplex with
3543:Andersson, Tommy (2009).
3420:10.1016/j.geb.2023.01.008
3369:Social Choice and Welfare
3194:Social Choice and Welfare
3050:"Divide Your Rent Fairly"
2894:Social Choice and Welfare
2841:10.1007/s00355-003-0231-0
2819:Social Choice and Welfare
2791:10.1007/s00355-003-0240-z
2779:Social Choice and Welfare
2712:10.1016/j.jet.2014.06.006
1663:{\displaystyle 100-p_{2}}
1453:piecewise linear function
1356:is allowed to envy agent
1352:, which means that agent
1056:Find a maxsum allocation.
2946:Steven J. Brams (2008).
2601:House allocation problem
1491:Strategic considerations
1439:>2 is some constant.
1250:{\displaystyle O(n^{3})}
966:of the total house cost.
585:{\displaystyle O(n^{3})}
3621:Fair division protocols
3237:10.1145/2940716.2940724
3231:. ACM. pp. 67–84.
3005:Turing's Invisible Hand
2868:. IJCAI. pp. 34–39
2747:10.1023/A:1020485018300
2429:{\displaystyle n-1+1/n}
2051:truthful in expectation
1974:, which is still below
1878:, which is still above
1421:soft budget constraints
1415:Soft budget constraints
1317:Hard budget constraints
990:Hall's marriage theorem
496:{\displaystyle 1/(n-1)}
412:Hall's marriage theorem
230:Su: one person per room
3461:10.1287/moor.2021.1196
3270:"Robust Rent Division"
2595:Fair random assignment
2567:
2539:
2508:
2482:
2481:{\displaystyle n>2}
2456:
2430:
2390:
2370:
2343:
2315:
2287:
2261:
2233:
2213:
2163:
2135:
2115:
2087:
2016:
1988:
1968:
1948:
1920:
1892:
1872:
1852:
1824:
1776:
1746:
1705:
1664:
1631:
1565:
1527:
1397:Birkhoff decomposition
1251:
1201:
1131:
1065:Bellman–Ford algorithm
960:
882:
606:
586:
497:
345:
316:
296:
210:
184:
164:
68:
48:
3572:Theoretical Economics
2916:10.1007/s003550100149
2568:
2540:
2509:
2483:
2457:
2431:
2391:
2371:
2344:
2316:
2288:
2262:
2234:
2214:
2164:
2136:
2116:
2088:
2062:Ex-ante Envy-Freeness
2047:randomized mechanisms
2017:
1989:
1969:
1949:
1921:
1893:
1873:
1853:
1825:
1777:
1775:{\displaystyle p_{2}}
1747:
1706:
1665:
1632:
1630:{\displaystyle p_{2}}
1566:
1528:
1377:fractional allocation
1252:
1202:
1132:
961:
883:
607:
587:
533:quasilinear utilities
498:
346:
317:
297:
295:{\displaystyle (n-1)}
211:
190:, his net utility is
185:
165:
69:
49:
3616:Fair item allocation
2613:Fair item allocation
2549:
2523:
2492:
2466:
2440:
2400:
2380:
2360:
2325:
2297:
2271:
2243:
2223:
2173:
2145:
2125:
2105:
2069:
1998:
1978:
1958:
1930:
1902:
1882:
1862:
1834:
1786:
1759:
1715:
1674:
1641:
1614:
1537:
1511:
1294:spliddit.org website
1225:
1147:
1077:
942:
866:
596:
560:
467:
353:Simmons–Su protocols
326:
306:
274:
262:Topologically closed
194:
174:
154:
58:
38:
2566:{\displaystyle 1/n}
2538:{\displaystyle n-1}
2507:{\displaystyle n-1}
2455:{\displaystyle n=2}
2342:{\displaystyle 1/n}
2314:{\displaystyle 1/n}
2293:, which is exactly
2286:{\displaystyle i=0}
2260:{\displaystyle 1/n}
2162:{\displaystyle 1/n}
2086:{\displaystyle 1/n}
2015:{\displaystyle y/2}
1947:{\displaystyle y/2}
1919:{\displaystyle x/2}
1851:{\displaystyle x/2}
1533:are parameters and
1526:{\displaystyle x,y}
1395:is the size of the
1389:dynamic programming
1323:Quasilinear utility
1040:is envy-free, then
1025:is envy-free, then
959:{\displaystyle 1/n}
881:{\displaystyle n-1}
554:Hungarian algorithm
209:{\displaystyle v-p}
148:quasilinear utility
137:preference relation
90:Non-negativity (NN)
3549:Economics Bulletin
3321:10.3233/FAIA230253
3206:10.1007/BF00179981
3055:The New York Times
2978:The New York Times
2644:Su, F. E. (1999).
2619:Assignment problem
2607:Envy-free matching
2563:
2535:
2504:
2478:
2452:
2426:
2386:
2366:
2339:
2311:
2283:
2257:
2229:
2209:
2159:
2131:
2111:
2083:
2012:
1984:
1964:
1944:
1916:
1888:
1868:
1848:
1820:
1772:
1742:
1701:
1660:
1627:
1561:
1523:
1350:budget-friendly EF
1326:than his budget.
1298:pref.tools website
1247:
1197:
1127:
1061:linear programming
1048:maxsum allocation.
956:
932:descending auction
878:
602:
582:
550:assignment problem
493:
341:
312:
292:
206:
180:
160:
64:
44:
25:housemates problem
3491:Economics Letters
3330:978-1-64368-436-9
2389:{\displaystyle N}
2369:{\displaystyle N}
2232:{\displaystyle i}
2134:{\displaystyle p}
2114:{\displaystyle p}
1987:{\displaystyle y}
1967:{\displaystyle x}
1891:{\displaystyle x}
1871:{\displaystyle y}
1782:to some value in
1608:
1607:
1381:Partition problem
1044:is envy-free for
928:ascending auction
752:
751:
657:
656:
605:{\displaystyle n}
315:{\displaystyle n}
183:{\displaystyle p}
163:{\displaystyle v}
111:Pareto-efficiency
67:{\displaystyle n}
47:{\displaystyle n}
3628:
3600:
3599:
3597:
3587:
3563:
3557:
3556:
3540:
3534:
3533:
3513:
3507:
3506:
3488:
3479:
3473:
3472:
3454:
3445:(3): 1970–1998.
3430:
3424:
3423:
3399:
3393:
3392:
3360:
3354:
3353:
3347:
3339:
3338:
3337:
3304:
3298:
3291:
3282:
3281:
3265:
3259:
3258:
3224:
3218:
3217:
3185:
3179:
3178:
3176:
3175:
3166:. Archived from
3160:
3154:
3153:
3125:
3119:
3118:
3100:
3076:
3067:
3066:
3064:
3063:
3046:
3040:
3039:
3037:
3036:
3022:
3016:
3015:
3013:
3011:
2996:
2990:
2989:
2987:
2985:
2968:
2962:
2961:
2943:
2928:
2927:
2909:
2889:
2878:
2877:
2875:
2873:
2863:
2854:
2845:
2844:
2834:
2814:
2803:
2802:
2774:
2759:
2758:
2730:
2724:
2723:
2705:
2685:
2674:
2673:
2641:
2572:
2570:
2569:
2564:
2559:
2544:
2542:
2541:
2536:
2513:
2511:
2510:
2505:
2487:
2485:
2484:
2479:
2461:
2459:
2458:
2453:
2435:
2433:
2432:
2427:
2422:
2395:
2393:
2392:
2387:
2375:
2373:
2372:
2367:
2348:
2346:
2345:
2340:
2335:
2320:
2318:
2317:
2312:
2307:
2292:
2290:
2289:
2284:
2266:
2264:
2263:
2258:
2253:
2238:
2236:
2235:
2230:
2218:
2216:
2215:
2210:
2168:
2166:
2165:
2160:
2155:
2140:
2138:
2137:
2132:
2120:
2118:
2117:
2112:
2092:
2090:
2089:
2084:
2079:
2021:
2019:
2018:
2013:
2008:
1993:
1991:
1990:
1985:
1973:
1971:
1970:
1965:
1953:
1951:
1950:
1945:
1940:
1925:
1923:
1922:
1917:
1912:
1897:
1895:
1894:
1889:
1877:
1875:
1874:
1869:
1857:
1855:
1854:
1849:
1844:
1829:
1827:
1826:
1823:{\displaystyle }
1821:
1813:
1799:
1781:
1779:
1778:
1773:
1771:
1770:
1751:
1749:
1748:
1743:
1738:
1727:
1726:
1710:
1708:
1707:
1702:
1697:
1686:
1685:
1669:
1667:
1666:
1661:
1659:
1658:
1636:
1634:
1633:
1628:
1626:
1625:
1574:
1570:
1568:
1567:
1562:
1532:
1530:
1529:
1524:
1385:salesman problem
1383:or from Hamming
1284:egalitarian rule
1256:
1254:
1253:
1248:
1243:
1242:
1206:
1204:
1203:
1198:
1193:
1136:
1134:
1133:
1128:
1123:
965:
963:
962:
957:
952:
887:
885:
884:
879:
666:
623:
611:
609:
608:
603:
591:
589:
588:
583:
578:
577:
526:Cardinal version
502:
500:
499:
494:
477:
390:Miserly partners
384:No externalities
350:
348:
347:
342:
340:
339:
334:
321:
319:
318:
313:
301:
299:
298:
293:
249:No externalities
234:The protocol by
215:
213:
212:
207:
189:
187:
186:
181:
169:
167:
166:
161:
144:cardinal utility
73:
71:
70:
65:
53:
51:
50:
45:
3636:
3635:
3631:
3630:
3629:
3627:
3626:
3625:
3606:
3605:
3604:
3603:
3565:
3564:
3560:
3555:(3): 1719–1724.
3542:
3541:
3537:
3515:
3514:
3510:
3486:
3481:
3480:
3476:
3432:
3431:
3427:
3401:
3400:
3396:
3362:
3361:
3357:
3340:
3335:
3333:
3331:
3306:
3305:
3301:
3292:
3285:
3267:
3266:
3262:
3247:
3226:
3225:
3221:
3187:
3186:
3182:
3173:
3171:
3162:
3161:
3157:
3127:
3126:
3122:
3078:
3077:
3070:
3061:
3059:
3058:. 28 April 2014
3048:
3047:
3043:
3034:
3032:
3024:
3023:
3019:
3009:
3007:
2998:
2997:
2993:
2983:
2981:
2970:
2969:
2965:
2958:
2945:
2944:
2931:
2891:
2890:
2881:
2871:
2869:
2861:
2856:
2855:
2848:
2816:
2815:
2806:
2776:
2775:
2762:
2732:
2731:
2727:
2687:
2686:
2677:
2662:10.2307/2589747
2656:(10): 930–942.
2643:
2642:
2633:
2628:
2588:
2579:
2547:
2546:
2521:
2520:
2490:
2489:
2464:
2463:
2438:
2437:
2398:
2397:
2378:
2377:
2358:
2357:
2323:
2322:
2295:
2294:
2269:
2268:
2241:
2240:
2221:
2220:
2171:
2170:
2143:
2142:
2123:
2122:
2103:
2102:
2067:
2066:
2043:
2031:
1996:
1995:
1976:
1975:
1956:
1955:
1928:
1927:
1900:
1899:
1880:
1879:
1860:
1859:
1832:
1831:
1784:
1783:
1762:
1757:
1756:
1718:
1713:
1712:
1677:
1672:
1671:
1650:
1639:
1638:
1617:
1612:
1611:
1535:
1534:
1509:
1508:
1493:
1449:
1417:
1364:pays more than
1348:Relaxing EF to
1319:
1314:
1306:
1275:
1267:
1234:
1223:
1222:
1145:
1144:
1075:
1074:
1007:
940:
939:
924:
864:
863:
815:
791:Vickrey auction
761:
618:
594:
593:
569:
558:
557:
528:
514:for some agent
465:
464:
449:framing effects
424:
402:K-K-M-S theorem
368:
329:
324:
323:
304:
303:
272:
271:
264:preference sets
255:Miserly tenants
232:
227:
225:Ordinal version
192:
191:
172:
171:
152:
151:
133:ordinal utility
56:
55:
36:
35:
19:is a kind of a
12:
11:
5:
3634:
3632:
3624:
3623:
3618:
3608:
3607:
3602:
3601:
3585:10.3982/te1346
3558:
3535:
3508:
3474:
3425:
3394:
3355:
3329:
3299:
3283:
3280:: 13864–13876.
3260:
3245:
3219:
3200:(3): 267–276.
3180:
3155:
3142:10.1086/319550
3120:
3091:(5): 403–414.
3068:
3041:
3017:
2991:
2963:
2956:
2929:
2907:10.1.1.26.8883
2879:
2846:
2832:10.1.1.198.186
2804:
2760:
2725:
2675:
2630:
2629:
2627:
2624:
2623:
2622:
2616:
2610:
2604:
2598:
2587:
2584:
2578:
2575:
2562:
2558:
2554:
2534:
2531:
2528:
2503:
2500:
2497:
2477:
2474:
2471:
2451:
2448:
2445:
2425:
2421:
2417:
2414:
2411:
2408:
2405:
2385:
2365:
2338:
2334:
2330:
2310:
2306:
2302:
2282:
2279:
2276:
2256:
2252:
2248:
2228:
2208:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2178:
2158:
2154:
2150:
2130:
2110:
2082:
2078:
2074:
2055:expected value
2042:
2039:
2030:
2027:
2011:
2007:
2003:
1983:
1963:
1943:
1939:
1935:
1915:
1911:
1907:
1887:
1867:
1847:
1843:
1839:
1819:
1816:
1812:
1808:
1805:
1802:
1798:
1794:
1791:
1769:
1765:
1741:
1737:
1733:
1730:
1725:
1721:
1700:
1696:
1692:
1689:
1684:
1680:
1657:
1653:
1649:
1646:
1624:
1620:
1606:
1605:
1602:
1599:
1595:
1594:
1591:
1588:
1584:
1583:
1580:
1577:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1522:
1519:
1516:
1492:
1489:
1448:
1445:
1416:
1413:
1409:
1408:
1373:
1318:
1315:
1313:
1310:
1305:
1302:
1274:
1271:
1266:
1263:
1246:
1241:
1237:
1233:
1230:
1219:
1218:
1217:
1216:
1208:
1196:
1192:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1138:
1126:
1122:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1071:
1068:
1057:
1050:
1049:
1030:
1006:
1003:
994:
993:
986:
983:
980:
977:
974:
969:Calculate the
967:
955:
951:
947:
923:
920:
919:
918:
911:
910:
894:
893:
889:
877:
874:
871:
860:
853:
850:
839:
838:
834:
830:
814:
811:
786:
785:
778:
775:
772:
760:
757:
750:
749:
746:
743:
740:
737:
733:
732:
729:
726:
723:
720:
716:
715:
712:
709:
706:
703:
699:
698:
695:
692:
689:
686:
682:
681:
678:
675:
672:
669:
655:
654:
651:
648:
644:
643:
640:
637:
633:
632:
629:
626:
617:
614:
601:
581:
576:
572:
568:
565:
527:
524:
492:
489:
486:
483:
480:
476:
472:
453:
452:
445:
442:
439:
423:
420:
416:
415:
409:
394:
393:
387:
381:
367:
364:
338:
333:
311:
291:
288:
285:
282:
279:
268:
267:
258:
252:
246:
231:
228:
226:
223:
218:
217:
205:
202:
199:
179:
159:
140:
117:
116:
107:
93:
83:
82:
79:
63:
43:
17:Rental harmony
13:
10:
9:
6:
4:
3:
2:
3633:
3622:
3619:
3617:
3614:
3613:
3611:
3596:
3591:
3586:
3581:
3577:
3573:
3569:
3562:
3559:
3554:
3550:
3546:
3539:
3536:
3531:
3527:
3523:
3519:
3512:
3509:
3504:
3500:
3496:
3492:
3485:
3478:
3475:
3470:
3466:
3462:
3458:
3453:
3448:
3444:
3440:
3436:
3429:
3426:
3421:
3417:
3413:
3409:
3405:
3398:
3395:
3390:
3386:
3382:
3378:
3375:(1): 93–118.
3374:
3370:
3366:
3359:
3356:
3351:
3345:
3332:
3326:
3322:
3318:
3314:
3310:
3303:
3300:
3297:". AAAI 2018.
3296:
3290:
3288:
3284:
3279:
3275:
3271:
3264:
3261:
3256:
3252:
3248:
3246:9781450339360
3242:
3238:
3234:
3230:
3223:
3220:
3215:
3211:
3207:
3203:
3199:
3195:
3191:
3184:
3181:
3170:on 2016-03-05
3169:
3165:
3159:
3156:
3151:
3147:
3143:
3139:
3135:
3131:
3124:
3121:
3116:
3112:
3108:
3104:
3099:
3094:
3090:
3086:
3082:
3075:
3073:
3069:
3057:
3056:
3051:
3045:
3042:
3031:
3027:
3021:
3018:
3006:
3002:
2995:
2992:
2980:
2979:
2974:
2967:
2964:
2959:
2957:9780691133218
2953:
2949:
2942:
2940:
2938:
2936:
2934:
2930:
2925:
2921:
2917:
2913:
2908:
2903:
2899:
2895:
2888:
2886:
2884:
2880:
2867:
2860:
2853:
2851:
2847:
2842:
2838:
2833:
2828:
2824:
2820:
2813:
2811:
2809:
2805:
2800:
2796:
2792:
2788:
2784:
2780:
2773:
2771:
2769:
2767:
2765:
2761:
2756:
2752:
2748:
2744:
2740:
2736:
2729:
2726:
2721:
2717:
2713:
2709:
2704:
2699:
2695:
2691:
2684:
2682:
2680:
2676:
2671:
2667:
2663:
2659:
2655:
2651:
2647:
2640:
2638:
2636:
2632:
2625:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2592:
2591:
2585:
2583:
2576:
2574:
2560:
2556:
2552:
2532:
2529:
2526:
2517:
2516:VCG mechanism
2501:
2498:
2495:
2475:
2472:
2469:
2449:
2446:
2443:
2423:
2419:
2415:
2412:
2409:
2406:
2403:
2383:
2363:
2355:
2350:
2336:
2332:
2328:
2308:
2304:
2300:
2280:
2277:
2274:
2254:
2250:
2246:
2226:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2179:
2176:
2156:
2152:
2148:
2128:
2108:
2100:
2095:
2080:
2076:
2072:
2063:
2058:
2056:
2052:
2048:
2040:
2038:
2035:
2028:
2026:
2023:
2009:
2005:
2001:
1981:
1961:
1941:
1937:
1933:
1913:
1909:
1905:
1885:
1865:
1845:
1841:
1837:
1814:
1810:
1806:
1803:
1800:
1796:
1792:
1767:
1763:
1753:
1739:
1735:
1731:
1728:
1723:
1719:
1698:
1694:
1690:
1687:
1682:
1678:
1655:
1651:
1647:
1644:
1622:
1618:
1603:
1600:
1597:
1596:
1592:
1589:
1586:
1585:
1581:
1578:
1576:
1575:
1572:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1520:
1517:
1514:
1506:
1502:
1498:
1497:strategyproof
1490:
1488:
1486:
1482:
1478:
1474:
1470:
1466:
1462:
1458:
1454:
1446:
1444:
1440:
1438:
1434:
1430:
1426:
1425:interest rate
1422:
1414:
1412:
1406:
1402:
1398:
1394:
1390:
1386:
1382:
1378:
1374:
1371:
1367:
1363:
1359:
1355:
1351:
1347:
1346:
1345:
1342:
1340:
1334:
1331:
1327:
1324:
1316:
1311:
1309:
1303:
1301:
1299:
1295:
1290:
1287:
1285:
1280:
1272:
1270:
1264:
1262:
1258:
1239:
1235:
1228:
1214:
1209:
1194:
1190:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1142:
1141:
1139:
1124:
1120:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1072:
1069:
1066:
1062:
1058:
1055:
1054:
1053:
1047:
1043:
1039:
1035:
1031:
1028:
1024:
1020:
1016:
1012:
1011:
1010:
1004:
1002:
998:
991:
987:
984:
981:
978:
975:
972:
968:
953:
949:
945:
937:
936:
935:
933:
929:
921:
916:
915:
914:
908:
907:
906:
902:
900:
890:
875:
872:
869:
861:
858:
854:
851:
847:
846:
845:
842:
835:
831:
828:
824:
820:
819:
818:
812:
810:
808:
802:
798:
796:
795:strategyproof
792:
783:
779:
776:
773:
770:
769:
768:
766:
765:Gap Procedure
758:
756:
747:
744:
741:
738:
735:
734:
730:
727:
724:
721:
718:
717:
713:
710:
707:
704:
701:
700:
696:
693:
690:
687:
684:
683:
679:
676:
673:
670:
668:
667:
664:
660:
652:
649:
646:
645:
641:
638:
635:
634:
630:
627:
625:
624:
621:
615:
613:
599:
574:
570:
563:
555:
551:
547:
543:
542:
536:
534:
525:
523:
521:
517:
513:
509:
504:
487:
484:
481:
474:
470:
460:
457:
450:
446:
443:
440:
436:
435:
434:
431:
428:
421:
419:
413:
410:
407:
406:K-k-m theorem
403:
399:
398:
397:
391:
388:
385:
382:
379:
376:
375:
374:
371:
365:
363:
360:
357:
354:
336:
309:
286:
283:
280:
265:
263:
259:
256:
253:
250:
247:
244:
241:
240:
239:
237:
229:
224:
222:
203:
200:
197:
177:
157:
149:
145:
141:
138:
134:
130:
129:
128:
125:
122:
114:
112:
108:
104:
100:
98:
97:Envy-freeness
94:
91:
88:
87:
86:
80:
77:
76:
75:
61:
41:
32:
30:
26:
22:
21:fair division
18:
3595:10419/150236
3575:
3571:
3561:
3552:
3548:
3538:
3521:
3517:
3511:
3494:
3490:
3477:
3442:
3438:
3428:
3411:
3407:
3397:
3372:
3368:
3358:
3334:, retrieved
3312:
3302:
3277:
3273:
3263:
3228:
3222:
3197:
3193:
3183:
3172:. Retrieved
3168:the original
3158:
3133:
3129:
3123:
3088:
3084:
3060:. Retrieved
3053:
3044:
3033:. Retrieved
3030:Math.hmc.edu
3029:
3020:
3008:. Retrieved
3004:
2994:
2982:. Retrieved
2976:
2966:
2947:
2897:
2893:
2870:. Retrieved
2865:
2822:
2818:
2782:
2778:
2738:
2734:
2728:
2693:
2689:
2653:
2649:
2589:
2580:
2353:
2351:
2098:
2096:
2061:
2059:
2050:
2046:
2044:
2036:
2032:
2024:
1754:
1609:
1504:
1500:
1494:
1476:
1472:
1468:
1464:
1460:
1450:
1441:
1436:
1432:
1428:
1420:
1418:
1410:
1404:
1400:
1392:
1376:
1365:
1361:
1357:
1353:
1349:
1343:
1335:
1332:
1328:
1320:
1307:
1291:
1288:
1276:
1268:
1259:
1220:
1212:
1051:
1045:
1041:
1037:
1033:
1026:
1022:
1018:
1014:
1008:
999:
995:
970:
925:
912:
903:
898:
895:
856:
843:
840:
826:
822:
816:
806:
803:
799:
787:
781:
764:
762:
753:
661:
658:
619:
545:
539:
537:
529:
519:
515:
511:
507:
505:
461:
455:
454:
432:
426:
425:
417:
395:
389:
383:
377:
372:
369:
361:
358:
322:vertices in
269:
260:
254:
248:
242:
233:
219:
126:
120:
118:
109:
102:
95:
89:
84:
33:
28:
24:
16:
15:
3414:(C): 1–14.
1296:and in the
1021:with which
899:envy-cycles
546:utilitarian
3610:Categories
3578:(3): 753.
3524:(3): 350.
3452:1807.04163
3336:2024-07-28
3174:2016-03-05
3136:(2): 418.
3098:1912.13249
3062:2017-01-05
3035:2017-01-05
2900:(4): 723.
2825:(3): 515.
2741:(5): 405.
2626:References
1029:is maxsum.
971:demand-set
378:Good house
243:Good house
236:Francis Su
3469:0364-765X
3389:1432-217X
3313:ECAI 2023
3214:1432-217X
3150:154200252
3115:0002-9890
3010:26 August
2984:26 August
2902:CiteSeerX
2827:CiteSeerX
2755:122452727
2703:1406.6672
2530:−
2499:−
2407:−
2201:−
2192:…
2180:∈
1729:≤
1688:≥
1648:−
1598:Partner 2
1587:Partner 1
1375:Allowing
1172:−
1096:−
897:contains
873:−
736:Partner 4
719:Partner 3
702:Partner 2
685:Partner 1
647:Partner 2
636:Partner 1
485:−
430:room B".
284:−
201:−
170:and pays
3344:citation
3255:53223944
2799:11638306
2720:12129179
2586:See also
1391:, where
1279:Spliddit
837:chores).
556:in time
512:too high
2924:2784141
2872:5 March
2696:: 128.
2670:2589747
1582:Room 2
857:surplus
680:Room 4
631:Room 2
592:(where
142:In the
131:In the
103:prefers
3497:: 73.
3467:
3387:
3327:
3253:
3243:
3212:
3148:
3113:
2954:
2922:
2904:
2829:
2797:
2753:
2718:
2668:
2462:. For
1579:Room 1
930:and a
807:should
677:Room 3
674:Room 2
671:Room 1
628:Room 1
541:maxsum
121:Proof:
3487:(PDF)
3447:arXiv
3251:S2CID
3146:S2CID
3093:arXiv
2920:S2CID
2862:(PDF)
2795:S2CID
2751:S2CID
2716:S2CID
2698:arXiv
2666:JSTOR
1505:Proof
1457:FPTAS
544:(aka
106:room.
3465:ISSN
3385:ISSN
3350:link
3325:ISBN
3241:ISBN
3210:ISSN
3111:ISSN
3012:2014
2986:2014
2952:ISBN
2874:2016
2473:>
1556:<
1550:<
1544:<
1483:and
1481:PPAD
1467:and
1370:MILP
1341:).
400:The
113:(PE)
99:(EF)
27:and
3590:hdl
3580:doi
3526:doi
3499:doi
3457:doi
3416:doi
3412:139
3377:doi
3317:doi
3233:doi
3202:doi
3138:doi
3134:109
3103:doi
3089:129
2912:doi
2837:doi
2787:doi
2743:doi
2708:doi
2694:153
2658:doi
2654:106
2352:3.
2097:2.
2060:1.
1645:100
1601:100
1590:100
1571:):
1559:100
1485:PLS
1360:if
1046:any
782:gap
653:10
650:140
639:150
510:is
427:A.
3612::
3588:.
3574:.
3570:.
3553:29
3551:.
3547:.
3522:56
3520:.
3495:81
3493:.
3489:.
3463:.
3455:.
3443:47
3441:.
3437:.
3410:.
3406:.
3383:.
3373:59
3371:.
3367:.
3346:}}
3342:{{
3323:,
3311:,
3286:^
3278:35
3276:.
3272:.
3249:.
3239:.
3208:.
3198:12
3196:.
3192:.
3144:.
3132:.
3109:.
3101:.
3087:.
3083:.
3071:^
3052:.
3028:.
3003:.
2975:.
2932:^
2918:.
2910:.
2898:19
2896:.
2882:^
2864:.
2849:^
2835:.
2823:22
2821:.
2807:^
2793:.
2785:.
2783:23
2781:.
2763:^
2749:.
2739:11
2737:.
2714:.
2706:.
2692:.
2678:^
2664:.
2652:.
2648:.
2634:^
2573:.
2349:.
1752:.
1604:y
1593:x
1487:.
1403:≤
1300:.
1257:.
829:).
797:.
767::
748:0
745:35
742:33
739:32
731:0
728:36
725:30
722:34
714:0
711:33
708:36
705:31
697:0
694:30
691:34
688:36
642:0
456:B.
438:A.
3598:.
3592::
3582::
3576:9
3532:.
3528::
3505:.
3501::
3471:.
3459::
3449::
3422:.
3418::
3391:.
3379::
3352:)
3319::
3257:.
3235::
3216:.
3204::
3177:.
3152:.
3140::
3117:.
3105::
3095::
3065:.
3038:.
3014:.
2988:.
2960:.
2926:.
2914::
2876:.
2843:.
2839::
2801:.
2789::
2757:.
2745::
2722:.
2710::
2700::
2672:.
2660::
2561:n
2557:/
2553:1
2533:1
2527:n
2502:1
2496:n
2476:2
2470:n
2450:2
2447:=
2444:n
2424:n
2420:/
2416:1
2413:+
2410:1
2404:n
2384:N
2364:N
2337:n
2333:/
2329:1
2309:n
2305:/
2301:1
2281:0
2278:=
2275:i
2255:n
2251:/
2247:1
2227:i
2207:}
2204:1
2198:n
2195:,
2189:,
2186:0
2183:{
2177:i
2157:n
2153:/
2149:1
2129:p
2109:p
2081:n
2077:/
2073:1
2010:2
2006:/
2002:y
1982:y
1962:x
1942:2
1938:/
1934:y
1914:2
1910:/
1906:x
1886:x
1866:y
1846:2
1842:/
1838:x
1818:]
1815:2
1811:/
1807:y
1804:,
1801:2
1797:/
1793:x
1790:[
1768:2
1764:p
1740:2
1736:/
1732:y
1724:2
1720:p
1699:2
1695:/
1691:x
1683:2
1679:p
1656:2
1652:p
1623:2
1619:p
1553:y
1547:x
1541:0
1521:y
1518:,
1515:x
1477:c
1473:k
1469:n
1465:ε
1461:ε
1437:c
1433:k
1429:n
1405:n
1401:k
1399:(
1393:k
1366:i
1362:j
1358:j
1354:i
1245:)
1240:3
1236:n
1232:(
1229:O
1215:.
1195:n
1191:/
1187:)
1184:t
1181:s
1178:o
1175:c
1169:m
1166:u
1163:s
1160:n
1157:i
1154:m
1151:(
1125:n
1121:/
1117:)
1114:m
1111:u
1108:s
1105:n
1102:i
1099:m
1093:t
1090:s
1087:o
1084:c
1081:(
1067:.
1042:p
1038:p
1034:p
1027:x
1023:x
1019:p
1015:x
954:n
950:/
946:1
876:1
870:n
859:.
827:n
823:m
600:n
580:)
575:3
571:n
567:(
564:O
520:T
516:i
508:T
491:)
488:1
482:n
479:(
475:/
471:1
414:.
408:.
337:n
332:R
310:n
290:)
287:1
281:n
278:(
216:.
204:p
198:v
178:p
158:v
62:n
42:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.