Online fair division

Last updated

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. [1] Some situations in which not all resources are available include:

Contents

Some situations in which not all participants are available include:

The online nature of the problem requires different techniques and fairness criteria than in the classic, offline fair division.

Online arrival of people

The party cake-cutting problem

Walsh [2] studies an online variant of fair cake-cutting, in which agents arrive and depart during the division process, like in a party. Well-known fair division procedures like divide and choose and the Dubins-Spanier moving-knife procedure can be adapted to this setting. They guarantee online variants of proportionality and envy-freeness. The online version of divide-and-choose is more robust to collusion, and has better empirical performance.

The secretive agent problem

Several authors studied fair division problems in which one agent is "secretive", i.e., unavailable during the division process. When this agent arrives, he is allowed to choose any part of the resource, and the remaining n-1 parts should be divided among the remaining n-1 agents such that the division is fair. Note that divide and choose satisfies these requirements for n=2 agents, but extending this to 3 or more agents is non-trivial. The following extensions are known:

The cake redivision problem

The cake redivision problem [8] is a variant of fair cake-cutting in which the cake is already divided in an unfair way (e.g. among a subset of the agents), and it should be re-divided in a fair way (among all the agents) while letting the incumbent owners keep a substantial fraction of their present value. The model problem is land reform.

Online arrival of resources

The food bank problem

The food bank problem is an online variant of fair allocation of indivisible goods. Each time, a single item arrives; each agent declares his/her value for this item; and the mechanism should decide which of the agents should receive it. The model application is a central food bank, which receives food donations and has to allocate each donation to one of the charities who want it. The donations are consumed immediately, and it is not known what donations are going to come next, so the decision must be made based only on the previous donations.

Binary valuations

Working with Foodbank Australia, Aleksandrov, Aziz, Gaspers and Walsh [9] have initiated the study of the food bank problem when all agents have binary valuations {0,1}, that is, for each arriving item, every agent states whether he likes the item or not. The mechanism should decide which of the agents who like the item should receive it. They study two simple mechanisms for this setting:

  • LIKE: each item is given uniformly at random to one of the agents who likes it. It is strategyproof and envy-free ex-ante, but does not guarantee even approximate envy-free ex-post. With binary valuations, it attains the optimal egalitarian and utilitarian social welfare. With additive valuations, its expected egalitarian and utilitarian social welfare are least 1/n of the optimal values attainable by an offline algorithm. The same is true whether the agents are sincere or strategic (i.e., its price of anarchy is n).
  • BALANCED-LIKE: each item is given uniformly at random to one of the agents who likes it, from among those who received the least number of items so far. It is envy-free ex-ante, and guarantees EF1 ex-post when all agents have binary valuations. It is strategyproof for two agents with binary valuations, but not strategyproof for three or more agents even with binary valuations. When agents bid sincerely, with binary valuations, it attains the optimal egalitarian and utilitarian social welfare. With additive valuations, its expected egalitarian and utilitarian social welfare do not attain any constant-factor approximation of the offline optimal values, even with two agents. When agents bid strategically, even with binary valuations, its price of anarchy is n.

Additive valuations

In a more general case of the food bank problem, agents can have additive valuations, which are normalized to [0,1].

Due to the online nature of the problem, it may be impossible to attain some fairness and efficiency guarantees that are possible in the offline setting. In particular, Kahana and Hazon [10] prove that no online algorithm always finds a PROP1 (proportional up to at most one good) allocation, even for two agents with additive valuations. Moreover, no online algorithm always finds any positive approximation of RRS (round-robin share).

To explain this, define the envy of agent i at agent j as the amount by which i believes that j's bundle is better, that is, . The max-envy of an allocation is the maximum of the envy among all ordered agent pairs. Suppose the values of all items are normalized to [0,1]. Then, in the offline setting, it is easy to attain an allocation in which the max-envy is at most 1, for example, by the round-robin item allocation (this condition is called EF1). However, in the online setting, the envy might grow with the number of items (T). Therefore, instead of EF1, some algorithms aim to attain vanishing envy—the expected value of the max-envy of the allocation of T items should be sublinear in T (assuming the value of every item is between 0 and 1).

Benade, Kazachkov, Procaccia and Psomas [11] show that the LIKE algorithm (allocating each item uniformly at random) attains vanishing envy - the envy after T items is in . They also present a deterministic algorithm with a similar envy-bound, using the method of pessimistic estimators. They show that this envy-bound is asymptotically optimal (up to logarithmic factors) in the worst case, when the valuations are chosen by an adaptive adversary (an adversary who chooses an item after seeing the allocation at time T-1). In particular, in contrast to the case of binary valuations, no algorithm can guarantee EF1. They also study a more general setting in which the items come in batches of m each time, rather than 1 at a time. In this case, there is a deterministic algorithm with envy in .

Jiang, Kulkarni and Singla [12] improve their envy bound using an algorithm for online two-dimensional discrepancy minimization.

Zeng and Psomas [13] study the trade-off between efficiency and fairness under five adversary models, from weak to strong. Below, vit denotes the value of the item arriving at time t to agent i.

  1. Identical independent agents: the adversary picks a probability distribution D0. On each round t, vit is drawn independently from D0.
  2. Different independent agents: The adversary picks a probability distribution Di for each agent i. On each round t, vit is drawn independently from Di.
  3. Correlated agents: The adversary picks a joint probability distribution D. On each round t, the vector (v1t, ..., vnt) is drawn independently from D.
  4. Non-adaptive adversary: After seeing the algorithm code, the adversary picks the valuations of all n agents to all T items.
  5. Adaptive adversary: After seeing the algorithm code, and after seeing the allocation of the first t-1 items, the adversary picks the valuations of item t (In [13] this is the model).

For adversary 3 (hence also 2 and 1), they show an allocation strategy that guarantees, to each pair of agents, either EF1, or EF with high probability, and in addition, guarantees ex-post Pareto efficiency. They show that the "EF1 or EF w.h.p." guarantee cannot be improved even for adversary 1 (hence also for 2 and 3). For adversary 4 (hence also 5), they show that every algorithm attaining vanishing envy can be at most 1/n ex-ante Pareto-efficient.

Sinclair, Bannerjee and Yu [14] present an algorithm that attains the optimal fairness-efficiency threshold.

The costly reallocation problem

In some cases, items that were previously allocated may be reallocated, but reallocation is costly, so the number of adjustments should be as small as possible. An example is the allocation of expensive scientific equipment among different university departments. Each piece of equipment is allocated as soon as it arrives, but some previously allocated equipment may be reallocated in order to attain a fairer overall allocation.

He, Procaccia and Psomas [15] show that, with two agents, algorithms that are informed about values of future items can attain EF1 without any adjustments, whereas uninformed algorithms require Θ(T) adjustments. With three or more agents, even informed algorithms must use Ω(T) adjustments, and there is an uninformed algorithm that attains EF1 with O(T3/2) adjustments.

Uncertain supply

In many fair division problems, such as production of energy from solar cells, the exact amount of available resource may not be known at the time the allocation is decided. Buermann, Gerding and Rastegari [16] study fair division of a homogeneous divisible resource, such as electricity, where the available amount is given by a probability distribution, and the agents' valuations are not linear (for example, each agent has a cap on the amount of the resource he can use; above this cap, his utility does not increase by getting more of the resource). They compare two fairness criteria: ex-post envy-freeness and ex-ante envy-freeness. The latter criterion is weaker (since envy-freeness holds only in expectation), but it allows a higher social welfare. The price of ex-ante envy-freeness is still high: it is at least Ø(n), where n is the number of agents. Moreover, maximizing ex-ante social welfare subject to ex-ante envy-freeness is strongly NP-hard, but there is an integer program to calculate the optimal ex-ante envy-free allocation for a special class of valuation functions - linear functions with a saturation cap.

Uncertain demand

In many fair division problems, there are agents or groups of agents whose demand for resources is not known when the resources are allocated. For example, [17] suppose there are two villages who are susceptible to power outages. Each village has a different probability distribution over storms:

The government has two generators, each of which can supply electricity to a single house. It has to decide how to allocate the generators between the villages. Two important considerations are utilization and fairness:

Donahue and Kleinberg [17] prove upper and lower bounds on the price of fairness—the maximum possible utilization, divided by the maximum utilization of a fair allocation. The bounds are weak in general, but stronger bounds are possible for some specific probability distributions that are commonly used to model demand.

Other applications with uncertain demands are allocation of orders in service supply chains, [18] allocation of aircraft to routes, [19] allocation of doctors to surgeries, [20] and more. [21] [22] [23] [24]

Uncertain value

Morgan [25] studies a partnership dissolution setting, where the partnership assets have the same value for all partners, but this value is not known. Each partner has a noisy signal about the value, but the signals are different. He shows that Divide and choose is not fair - it favors the chooser. He presents another mechanism that can be considered fair in this setting.

See also

Related Research Articles

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into parts and taking the part with the minimum value. An allocation of items among agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-n maximin-share. MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split ( of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different.

Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.

In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

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.

References

  1. ↑ Aleksandrov, Martin; Walsh, Toby (2020-04-03). "Online Fair Division: A Survey". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (9): 13557–13562. doi: 10.1609/aaai.v34i09.7081 . ISSN   2374-3468.
  2. ↑ Walsh, Toby (2011). Brafman, Ronen I.; Roberts, Fred S.; Tsoukiàs, Alexis (eds.). "Online Cake Cutting". Algorithmic Decision Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6992: 292–305. doi:10.1007/978-3-642-24873-3_22. ISBN   978-3-642-24873-3. S2CID   501890.
  3. ↑ Meunier, Frédéric; Su, Francis Edward (2019-01-01). "Multilabeled Versions of Sperner's and Fan's Lemmas and Applications". SIAM Journal on Applied Algebra and Geometry. 3 (3): 391–411. arXiv: 1801.02044 . doi:10.1137/18M1192548. S2CID   3762597.
  4. ↑ Frick, Florian; Houston-Edwards, Kelsey; Meunier, Frédéric (2019-01-02). "Achieving Rental Harmony with a Secretive Roommate". The American Mathematical Monthly. 126 (1): 18–32. arXiv: 1702.07325 . doi:10.1080/00029890.2019.1528127. ISSN   0002-9890. S2CID   119601896.
  5. ↑ Segal-Halevi, Erel (2022). "Generalized Rental Harmony". The American Mathematical Monthly. 129 (5): 403–414. arXiv: 1912.13249 . doi:10.1080/00029890.2022.2037988. S2CID   211678363.
  6. ↑ Chèze, Guillaume (2019-07-01). "How to share a cake with a secret agent". Mathematical Social Sciences. 100: 13–15. arXiv: 1810.06913 . doi:10.1016/j.mathsocsci.2019.04.001. ISSN   0165-4896. S2CID   53115454.
  7. ↑ Arunachaleswaran, Eshwar Ram; Barman, Siddharth; Rathi, Nidhi (2019-07-17). "Fair Division with a Secretive Agent". Proceedings of the AAAI Conference on Artificial Intelligence. 33 (1): 1732–1739. doi: 10.1609/aaai.v33i01.33011732 . ISSN   2374-3468.
  8. ↑ Segal-Halevi, Erel (2022). "Redividing the cake". Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI'18. Stockholm, Sweden: AAAI Press. 36: 498–504. arXiv: 1603.00286 . doi:10.1007/s10458-022-09545-x. ISBN   978-0-9992411-2-7. S2CID   246493020.
  9. ↑ Aleksandrov, Martin; Aziz, Haris; Gaspers, Serge; Walsh, Toby (2015-07-25). "Online fair division: analysing a food bank problem". Proceedings of the 24th International Conference on Artificial Intelligence. IJCAI'15. Buenos Aires, Argentina: AAAI Press: 2540–2546. arXiv: 1502.07571 . ISBN   978-1-57735-738-4.
  10. ↑ Kahana, Ido; Hazon, Noam (2023), "The Leximin Approach for a Sequence of Collective Decisions", ECAI 2023, IOS Press, pp. 1198–1206, doi:10.3233/faia230396 , retrieved 2023-12-17
  11. ↑ Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Christos-Alexandros (2018-06-11). "How to Make Envy Vanish over Time". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. Ithaca, NY, USA: Association for Computing Machinery. pp. 593–610. doi: 10.1145/3219166.3219179 . ISBN   978-1-4503-5829-3. S2CID   3340196.
  12. ↑ Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). "Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization". arXiv: 1910.01073 [cs.DS].
  13. 1 2 Zeng, David; Psomas, Alexandros (2020-07-13). "Fairness-Efficiency Tradeoffs in Dynamic Fair Division". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 911–912. arXiv: 1907.11672 . doi:10.1145/3391403.3399467. ISBN   978-1-4503-7975-5. S2CID   198953099.
  14. ↑ Sinclair, Sean R.; Banerjee, Siddhartha; Yu, Christina Lee (2021-10-29). "Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve". arXiv: 2105.05308 [cs.GT].
  15. ↑ He, Jiafan; Procaccia, Ariel D.; Psomas, Alexandros; Zeng, David (2019-01-01). "Achieving a Fairer Future by Changing the Past".{{cite journal}}: Cite journal requires |journal= (help)
  16. ↑ Buermann, Jan; Gerding, Enrico H.; Rastegari, Baharak (2020-05-05). "Fair Allocation of Resources with Uncertain Availability". Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '20. Auckland, New Zealand: International Foundation for Autonomous Agents and Multiagent Systems: 204–212. ISBN   978-1-4503-7518-4.
  17. 1 2 Donahue, Kate; Kleinberg, Jon (2020-01-27). "Fairness and utilization in allocating resources with uncertain demand". Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. FAT* '20. Barcelona, Spain: Association for Computing Machinery. pp. 658–668. arXiv: 1906.09050 . doi: 10.1145/3351095.3372847 . ISBN   978-1-4503-6936-7.
  18. ↑ Wang, Di; Liu, Weihua; Shen, Xinran; Wei, Wanying (2019-10-01). "Service order allocation under uncertain demand: Risk aversion, peer competition, and relationship strength". Transportation Research Part E: Logistics and Transportation Review. 130: 293–311. doi:10.1016/j.tre.2019.09.005. ISSN   1366-5545. S2CID   204451097.
  19. ↑ Ferguson, Allen R.; Dantzig, George B. (1956-10-01). "The Allocation of Aircraft to Routes—An Example of Linear Programming Under Uncertain Demand". Management Science. 3 (1): 45–73. doi:10.1287/mnsc.3.1.45. ISSN   0025-1909.
  20. ↑ Gerchak, Yigal; Gupta, Diwakar; Henig, Mordechai (1996-03-01). "Reservation Planning for Elective Surgery Under Uncertain Demand for Emergency Surgery". Management Science. 42 (3): 321–334. doi:10.1287/mnsc.42.3.321. ISSN   0025-1909.
  21. ↑ Chen, Yefen; Zhao, Xiaobo (2015). "Decision Bias in Capacity Allocation Games with Uncertain Demand". Production and Operations Management. 24 (4): 634–646. doi:10.1111/poms.12257. ISSN   1937-5956.
  22. ↑ Banks, Jeffrey S.; Ledyard, John O.; Porter, David P. (1989). "Allocating Uncertain and Unresponsive Resources: An Experimental Approach". The RAND Journal of Economics. 20 (1): 1–25. doi:10.2307/2555648. ISSN   0741-6261. JSTOR   2555648. PMID   10296624.
  23. ↑ Xue, Jingyi (2018-06-01). "Fair division with uncertain needs". Social Choice and Welfare. 51 (1): 105–136. doi:10.1007/s00355-018-1109-5. ISSN   1432-217X. S2CID   48362407.
  24. ↑ Elzayn, Hadi; Jabbari, Shahin; Jung, Christopher; Kearns, Michael; Neel, Seth; Roth, Aaron; Schutzman, Zachary (2019-01-29). "Fair Algorithms for Learning in Allocation Problems". Proceedings of the Conference on Fairness, Accountability, and Transparency. FAT* '19. Atlanta, GA, USA: Association for Computing Machinery. pp. 170–179. arXiv: 1808.10549 . doi:10.1145/3287560.3287571. ISBN   978-1-4503-6125-5. S2CID   52143168.
  25. ↑ Morgan, John (2004-05-01). "Dissolving a partnership (un)fairly". Economic Theory. 23 (4): 909–923. doi:10.1007/s00199-003-0409-9. ISSN   1432-0479. S2CID   153828369.
  26. ↑ Bateni, Mohammad Hossein; Chen, Yiwei; Ciocan, Dragos; Mirrokni, Vahab (2018-10-21). "Fair Resource Allocation in a Volatile Marketplace". Rochester, NY. doi:10.2139/ssrn.2789380. S2CID   21230521. SSRN   2789380.{{cite journal}}: Cite journal requires |journal= (help)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.