Two food banks catering to populations of different sizes with different needs must divide among themselves a donation of food items. What constitutes a \u201cfair\u201d allocation of the items among them?<\/p>\n
Competitive equilibrium from equal incomes (CEEI)\u00a0is a classic solution to the problem of fair and efficient allocation of goods among agents [Foley 1967, Varian 1974]. Every agent (foodbank) receives an equal endowment of artificial currency with which to \u201cpurchase\u201d\u00a0bundle of goods (food items). Prices for the goods are set high enough such that the agents can simultaneously get their favorite within-budget bundle,\u00a0and low enough such that all goods are allocated (no waste). ACEEI satisfies mathematical notions of fairness like fair-share, and also has built-in transparency\u2013prices can be published so the agents can verify they\u2019re being treated equally. However, a CEEI is not guaranteed to exist when the items are indivisible.<\/p>\n
We study competitive equilibrium from generic incomes (CEGI), which is based on the idea of slightly perturbed endowments and enjoys similar fairness,\u00a0efficiency, and transparency properties as CEEI. We show that when the two agents have almost equal endowments and additive preferences for the items, a CEGI always exists. We then consider agents who are a priori non-equal (like different-sized food banks); we formulate a new notion of fair allocation among non-equals satisfied by CEGI,\u00a0and show existence in cases of interest (like when the agents have identical preferences). Experiments on simulated and Spliddit data (a popular fair division website) indicate more general existence. Our results open opportunities for future research on fairness through genetic endowments, and on fair treatment of non-equals.<\/p>\n","protected":false},"excerpt":{"rendered":"
Two food banks catering to populations of different sizes with different needs must divide among themselves a donation of food items. What constitutes a \u201cfair\u201d allocation of the items among them? Competitive equilibrium from equal incomes (CEEI)\u00a0is a classic solution to the problem of fair and efficient allocation of goods among agents [Foley 1967, Varian […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"ACM","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"180","msr_page_range_end":"180","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"FAT* '19 Proceedings of the Conference on Fairness, Accountability, and Transparency","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2019-1-29","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"https:\/\/fatconference.org\/2019\/","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13548,13559],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-563808","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-economics","msr-research-area-social-sciences","msr-locale-en_us"],"msr_publishername":"ACM","msr_edition":"","msr_affiliation":"","msr_published_date":"2019-1-29","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2019\/01\/main-with-names.pdf","id":"564159","title":"main-with-names","label_id":"243132","label":0},{"type":"url","viewUrl":"false","id":"false","title":"http:\/\/10.1145\/3287560.3287582","label_id":"243106","label":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":564159,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2019\/01\/main-with-names.pdf"},{"id":563811,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2019\/01\/FAT-fairness-CE-generic-budgets.pdf"}],"msr-author-ordering":[{"type":"user_nicename","value":"Moshe Babaioff","user_id":33000,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Moshe Babaioff"},{"type":"text","value":"Noam Nisan","user_id":0,"rest_url":false},{"type":"text","value":"Inbal Talgam-Cohen","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[199563],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/563808","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/563808\/revisions"}],"predecessor-version":[{"id":563853,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/563808\/revisions\/563853"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=563808"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=563808"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=563808"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=563808"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=563808"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=563808"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=563808"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=563808"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=563808"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=563808"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=563808"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=563808"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=563808"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}