Wikipedia

Fair allocation of items and money

(Redirected from Knaster auction)

Fair allocation of items and money is a class of fair item allocation 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 allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

Two agents and one item

edit

With two agents and one item, it is possible to attain fairness using the following simple algorithm (which is a variant of cut and choose):

  • Alice says a price p that she is willing to pay for the item.
  • George chooses whether to take the item and pay p, or leave the item to Alice so that Alice pays p.

The algorithm always yields an envy-free allocation. If the agents have quasilinear utilities, that is, their utility is the value of items plus the amount of money that they have, then the allocation is also proportional. If George thinks that Alice's price is low (he is willing to pay more than p), then he takes the item and pay p, 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 p or more), then he leaves the item to Alice and does not envy, since Alice's utility in his eyes is negative.

The paid money p 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 p/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 entitlements, then the paid money p should be divided between the partners in proportion to their entitlements.

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 envy-freeness. In addition, some works consider a setting in which a benevolent third-party is willing to subsidize the allocation, but wants to minimize the amount of subsidy subject to envy-freeness. This problem is called the minimum-subsidy envy-free allocation.

Unit-demand agents

edit

Unit-demand agents are interested in at most a single item.

Rental harmony

edit

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 constant, which represents the total apartment rent. This is known as the Rental Harmony problem.

More general settings

edit

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 continuous and increasing in money. It does not have to be linear in money, but does have to be "Archimedean", i.e., there exists some value V such that, for every two objects j and k, the utility of object j plus V should be larger than the utility of object k (alternatively, the utility of getting object j for free is larger than the utility of getting object k and paying V). Quasilinear utility is a special case of Archimedean utility, in which V is the largest value-difference (for the same agent) between two objects.

Svensson[1] first proved that, when all agents are Archimedean, an envy-free allocation exists and is Pareto-optimal.

Demange, Gale and Sotomayor[2] showed a natural ascending auction that achieves an envy-free allocation using monetary payments for unit demand agents.

Maskin[3] proved the existence of a Pareto-optimal envy-free allocation when the total money endowment is more than (n-1)V. The proofs use competitive equilibrium.

Note that a subsidy of (n-1)V may be required: if all agents value a single object at V and the other objects at 0, then envy-freeness requires a subsidy of V for each agent who does not receive the object.

Tadenuma and Thomson[4] study several consistency properties of envy-free allocation rules.

Aragones[5] 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 the "money-Rawlsian solution" of Alkan, Demange and Gale.[6] It can be found in polynomial time, by finding a maximum-weight matching and then finding shortest paths in a certain induced graph.

Klijn[7] 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 envy graph characterizes the extreme points of this polytope. This implies a method for finding extreme envy-free allocations.

Additive agents

edit

Additive agents may receive several objects, so the allocation problem becomes more complex - there are many more possible allocations.

Knaster's auction

edit

The first procedure for fair allocation of items and money was invented by Bronislaw Knaster and published by Hugo Steinhaus.[8][9] This auction works as follows, for each item separately:

  • Each agent submits a bid over the item.
  • The item is given to the highest bidder (breaking ties arbitrarily).
  • The winner pays (n-1)/n of his bid;
  • Each of the other agents receives 1/n of his bid;
  • Since the winner is the highest bidder, there is a non-negative surplus; the surplus is divided equally among the agents.

The utility of every agent is at least 1/n of the value he attributes to the entire set of objects, so the allocation is proportional.[10] Moreover, the allocation maximizes the sum of utilities, so it is Pareto efficient.

Knaster's auction is not strategyproof. Some researchers analysed its performance when agents play strategically:

  • Essen[11] 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 ex-ante.
  • Fragnelli and Marina[12] 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.

Knaster's auction has been adapted to fair allocation of wireless channels.[13]

Raith's auction

edit

Matthias G. Raith[14] 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:

  • Each agent winning an item pays his bid for this item;
  • The total amount of money paid by the agents is partitioned between them in proportion to their bids.

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:

Item 1 Item 2 Sum
Alice 10 10 20
George 60 120 180

In both auctions, George wins both items, but the payments are different:

  • 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.
  • 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.

In experiments with human subjects,[15] 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 are 90, 90).

Compensation procedure

edit

Haake, Raith and Su[16] 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 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.

  1. 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 least one item per partner"), then a maxsum allocation might be more difficult to find.
  2. Charge from each partner the value of the bundle allocated to him. This creates the initial pool of money.
  3. 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 surplus.
  4. Eliminate envy by compensating envious partners. There are at most   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.
  5. 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 that may be considered "fairer").

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 contains envy-cycles. These cycles can be removed by moving bundles along the cycle, as in the envy-graph procedure. 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.

The Compensation Procedure might charge some partners a negative payment (i.e., give the partners a positive amount of money). The authors say:

"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".[16]: 746 

MInimum subsidy procedures

edit

Some works assume that a benevolent third-party is willing to subsidize the allocation, but wants to minimize the amount of subsidy subject to envy-freeness. This problem is called the minimum-subsidy envy-free allocation.

Halpern and Shah[17] study subsidy minimization in the general item-allocation setting. They consider two cases:

  1. 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 envy-graph 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 i, a price equal to the maximum weight of a path emanating from i. The weight of each path is at most the sum of m 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 V, then the weight of each path is at most mV. 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 (n-1)mV. This subsidy may be necessary, for example when all goods are identical and one agent gets all of them.
  2. The allocation can be chosen. In this case, a subsidy of (n-1)V is sufficient in the following cases:
    • When the agents' valuations are binary (0 or 1). Then, any max-product allocation or leximin-optimal allocation requires at most (n-1)V subsidy, and can be found in polynomial time. Computing the minimum subsidy required to achieve EF is Turing-equivalent to checking the existence of an envy-free allocation, which is NP-hard when restricted to non-wasteful allocations.
    • When all agents have the same additive valuation. Then, every allocation is envy-freeable. An allocation that requires at most (n-1)V 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 algorithm.
    • When there are two agents, round-robin item allocation with a specific agent ordering finds an allocation that is envy-freeable with subsidy at most V.

Brustle, Dippel, Narayan, Suzuki and Vetta[18] improve the upper bounds on the required subsidy:

  • With additive valuations, a subsidy of at most V per agent, and at most (n-1)V 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 maximum-weight matching in the agents-objects bipartite graph.
  • With general monotone valuations, a subsidy of at most 2(n-1)V per agent, and at most O(n2V), 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.

Caragiannis and Ioannidis[19] study the computational problem of minimizing the subsidy:

  • For a constant number of agents, they present an algorithm that approximates the minimum amount of subsidies within any required accuracy. For any ε > 0, it finds an allocation with subsidy at most  , where S is the maximum value that an agent assigns to all objects. The algorithm uses dynamic programming and runs in time  .
  • For a variable number of agents, a trivial approximation algorithm attains  . However, attaining an approximation factor independent of n is hard: it is NP-hard to compute an allocation with subsidy at most  . The proof is by reduction from a restricted variant of maximum 3-dimensional matching, in which each vertex appears exactly twice.

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:

  • Charging each agent the average payment yields an envy-free allocation that is also budget-balanced. Minimizing the subsidy is equivalent to minimizing the maximum amount that any individual agent has to pay.
  • It is also possible to use negative subsidy (tax), while minimizing the total amount that all agents have to pay.

Additional procedures

edit

Alkan, Demange and Gale[6] 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.

Meertens, Potters and Reijnierse[20] prove the existence of envy-free and Pareto-optimal allocations under very mild assumptions on the valuations (not necessarily quasilinear).

Cavallo[21] 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 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 VCG mechanism is not a satisfactory candidate, but the redistribution mechanism of Bailey[22] and Cavallo[23] is.

edit

Envy-free pricing

edit

When selling objects to buyers, the sum of payments is not fixed in advance, and the goal is to maximize 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 Envy-free Pricing problem.

Multi-dimensional objectives

edit

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 makespan (- the completion time of the last agent). Mu'alem presents a general framework for optimization problems with envy-freeness guarantee that naturally extends fair item allocations using monetary payments.[24]

Aziz[25] aims to attain, using monetary transfers, an allocation that is both envy-free and equitable. He studies not only additive positive utilities, but also for any superadditive utilities, whether positive or negative:

  • For superadditive utilities, there is a polynomial-time algorithm that attains envy-freeness, equitability, and budget balance (it is easy to exchange budget-balance with subsidy).
  • If a given allocation is EFEQ-convertible, then the minimum subsidy required to make it EF+EQ can be found in linear time.
  • 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 NP-hard.
  • A subsidy of at most (n-1)mV is always sufficient, and may be necessary whether an allocation is given or not.

See also

edit

References

edit
  1. ^ Svensson, Lars-Gunnar (1983). "Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness". Econometrica. 51 (4): 939–954. doi:10.2307/1912044. ISSN 0012-9682. JSTOR 1912044.
  2. ^ Demange G, Gale D, Sotomayor M (1986). "Multi-Item Auctions". Journal of Political Economy. 94 (4): 863–872. doi:10.1086/261411. JSTOR 1833206. S2CID 154114302.
  3. ^ Maskin, Eric S. (1987), Feiwel, George R. (ed.), "On the Fair Allocation of Indivisible Goods", Arrow and the Foundations of the Theory of Economic Policy, London: Palgrave Macmillan UK, pp. 341–349, doi:10.1007/978-1-349-07357-3_12, ISBN 978-1-349-07357-3, retrieved 2021-02-16
  4. ^ Tadenuma, Koichi; Thomson, William (1991). "No-Envy and Consistency in Economies with Indivisible Goods". Econometrica. 59 (6): 1755–1767. doi:10.2307/2938288. ISSN 0012-9682. JSTOR 2938288.
  5. ^ Aragones, Enriqueta (1995). "A derivation of the money rawlsian solution". Social Choice and Welfare. 12 (3): 267–276. doi:10.1007/BF00179981. ISSN 0176-1714. JSTOR 41106132. S2CID 154215964.
  6. ^ a b Alkan, Ahmet; Demange, Gabrielle; Gale, David (1991). "Fair Allocation of Indivisible Goods and Criteria of Justice". Econometrica. 59 (4): 1023–1039. doi:10.2307/2938172. ISSN 0012-9682. JSTOR 2938172.
  7. ^ Klijn, Flip (2000-03-01). "An algorithm for envy-free allocations in an economy with indivisible objects and money". Social Choice and Welfare. 17 (2): 201–215. doi:10.1007/s003550050015. ISSN 1432-217X. S2CID 18544150.
  8. ^ Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.
  9. ^ Steinhaus, H. (1949). "Sur la division pragmatique". Econometrica. 17: 315–319. doi:10.2307/1907319. ISSN 0012-9682. JSTOR 1907319.
  10. ^ Brams, Steven J.; Kilgour, D. Marc (2001). "Competitive Fair Division". Journal of Political Economy. 109 (2): 418. doi:10.1086/319550. S2CID 154200252.
  11. ^ Van Essen, Matt (2013-03-01). "An Equilibrium Analysis of Knaster's Fair Division Procedure". Games. 4 (1): 21–37. doi:10.3390/g4010021. hdl:10419/98565. ISSN 2073-4336.
  12. ^ Fragnelli, Vito; Marina, Maria Erminia (2009). "Strategic Manipulations and Collusions in Knaster Procedure". Czech Economic Review. 3 (2): 143–153.
  13. ^ Köppen, Mario; Ohnishi, Kei; Tsuru, Masato (2013-07-01). "Knaster Procedure for Proportional Fair Wireless Channel Allocation". 2013 IEEE 37th Annual Computer Software and Applications Conference Workshops. pp. 616–620. doi:10.1109/COMPSACW.2013.100. ISBN 978-1-4799-2159-1. S2CID 14873917.
  14. ^ Raith, Matthias G. (2000-05-01). "Fair-negotiation procedures". Mathematical Social Sciences. 39 (3): 303–322. doi:10.1016/S0165-4896(99)00032-3. ISSN 0165-4896.
  15. ^ Schneider, Gerald; Krämer, Ulrike Sabrina (2004). "The Limitations of Fair Division: An Experimental Evaluation of Three Procedures". The Journal of Conflict Resolution. 48 (4): 506–524. doi:10.1177/0022002704266148. JSTOR 4149806. S2CID 18162264.
  16. ^ a b Haake, Claus-Jochen; Raith, Matthias G.; Su, Francis Edward (2002). "Bidding for envy-freeness: A procedural approach to n-player fair-division problems". Social Choice and Welfare. 19 (4): 723. CiteSeerX 10.1.1.26.8883. doi:10.1007/s003550100149. S2CID 2784141.
  17. ^ Halpern, Daniel; Shah, Nisarg (2019). "Fair Division with Subsidy". In Fotakis, Dimitris; Markakis, Evangelos (eds.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 11801. Cham: Springer International Publishing. pp. 374–389. doi:10.1007/978-3-030-30473-7_25. ISBN 978-3-030-30473-7. S2CID 143425023.
  18. ^ Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (2020-07-13). "One Dollar Each Eliminates Envy". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 23–39. arXiv:1912.02797. doi:10.1145/3391403.3399447. ISBN 978-1-4503-7975-5. S2CID 208637311.
  19. ^ Caragiannis, Ioannis; Ioannidis, Stavros (2020-02-06). "Computing envy-freeable allocations with limited subsidies". arXiv:2002.02789 [cs.GT].
  20. ^ Meertens, Marc; Potters, Jos; Reijnierse, Hans (2002-12-01). "Envy-free and Pareto efficient allocations in economies with indivisible goods and money". Mathematical Social Sciences. 44 (3): 223–233. doi:10.1016/S0165-4896(02)00064-1. ISSN 0165-4896.
  21. ^ Ruggiero Cavallo (2012). Fairness and Welfare Through Redistribution When Utility is Transferable (PDF). AAAI-12.
  22. ^ Bailey, Martin J. (1997). "The demand revealing process: To distribute the surplus". Public Choice. 91 (2): 107–126. doi:10.1023/A:1017949922773. S2CID 152637454.
  23. ^ Cavallo, Ruggiero (2006). "Optimal decision-making with minimal waste". Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems - AAMAS '06. p. 882. doi:10.1145/1160633.1160790. ISBN 1595933034.
  24. ^ Mu'alem A (2014). "Fair by design: Multidimensional envy-free mechanisms". Games and Economic Behavior. 88: 29–46. doi:10.1016/j.geb.2014.08.001.
  25. ^ Aziz, Haris (2021-05-18). "Achieving Envy-freeness and Equitability with Monetary Transfers". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (6): 5102–5109. arXiv:2003.08125. doi:10.1609/aaai.v35i6.16645. ISSN 2374-3468. S2CID 212747875.
  26. ^ Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (2021). "Two Birds with One Stone: Fairness and Welfare via Transfers". In Caragiannis, Ioannis; Hansen, Kristoffer Arnsfelt (eds.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 12885. Cham: Springer International Publishing. pp. 376–390. arXiv:2106.00841. doi:10.1007/978-3-030-85947-3_25. ISBN 978-3-030-85947-3. S2CID 235294139.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Fair_allocation_of_items_and_money&oldid=1218555539"