Egalitarian item allocation (original) (raw)
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 (by the leximin order). Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.
| Property | Value |
|---|---|
| dbo:abstract | 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 (by the leximin order). Therefore, an egalitarian item allocation is sometimes called a leximin item allocation. The special case in which the value of each item j to each agent is either 0 or some constant vj is called the santa claus problem: santa claus has a fixed set of gifts, and wants to allocate them among children such that the least-happy child is as happy as possible. Some related problems are: * Multiway number partitioning with the max-min objective corresponds to a special case in which all agents have the same valuations. An even more special case is the partition problem, which corresponds to the case of two agents. Even this special case is NP-hard in general. * Unrelated-machines scheduling is a dual problem, in which the goal is to minimize the maximum value. * Maximin share item allocation is a different problem, in which the goal is not to attain an optimal solution, but rather to find any solution in which each agent receives a value above a certain threshold. (en) |
| dbo:wikiPageID | 65905792 (xsd:integer) |
| dbo:wikiPageLength | 20165 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110927302 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Envy-free_item_allocation dbr:Decreasing_Demand_procedure dbr:Leximin_order dbr:Proportional_item_allocation dbc:Combinatorial_optimization dbr:Matching_in_hypergraphs dbr:Egalitarian_social_choice_rule dbr:NP-hard dbr:Constraint_programming dbr:Partition_problem dbr:Maximin_share dbr:Additive_utility dbr:Adjusted_winner_procedure dbc:Fair_item_allocation dbr:Tree_(graph_theory) dbr:Linear_programming dbr:Basic_feasible_solution dbr:Fair_item_allocation dbr:Fractional_matching dbr:EFX_item_allocation dbc:Egalitarianism dbr:Lovász_local_lemma dbr:Multiway_number_partitioning dbr:Simultaneous_eating_algorithm dbr:Unrelated-machines_scheduling dbr:Submodular_set_function dbr:Ordinal_utilities dbr:Matroid_rank_function |
| dbp:wikiPageUsesTemplate | dbt:Multiple_issues dbt:Reflist dbt:Rp dbt:Technical dbt:Context |
| dct:subject | dbc:Combinatorial_optimization dbc:Fair_item_allocation dbc:Egalitarianism |
| rdfs:comment | 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 (by the leximin order). Therefore, an egalitarian item allocation is sometimes called a leximin item allocation. (en) |
| rdfs:label | Egalitarian item allocation (en) |
| owl:sameAs | wikidata:Egalitarian item allocation https://global.dbpedia.org/id/FVUbS |
| prov:wasDerivedFrom | wikipedia-en:Egalitarian_item_allocation?oldid=1110927302&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Egalitarian_item_allocation |
| is dbo:wikiPageRedirects of | dbr:Max-min_item_allocation dbr:Leximin_item_allocation |
| is dbo:wikiPageWikiLink of | dbr:Max-min_item_allocation dbr:Maximin_share dbr:Fair_item_allocation dbr:Unrelated-machines_scheduling dbr:Leximin_item_allocation |
| is foaf:primaryTopic of | wikipedia-en:Egalitarian_item_allocation |