| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 8, 2015 |
| Latest Amendment Date: | June 8, 2015 |
| Award Number: | 1525932 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Tracy Kimbrel
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | June 15, 2015 |
| End Date: | May 31, 2020 (Estimated) |
| Total Intended Award Amount: | $450,000.00 |
| Total Awarded Amount to Date: | $450,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
5000 FORBES AVE PITTSBURGH PA US 15213-3815 (412)268-8746 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
PA US 15213-3890 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
The mathematical study of fair division dates back to the 1940s. Nowadays the literature encompasses provably fair solutions for a wide variety of problems, many of them relevant to society at large. But, to date, very few fair division methods have been implemented. Building on its rich history, the field of fair division is poised to impact society on a grander scale, for example, via Spliddit (www.spliddit.org), a fair division website created by the PI. The overarching theme of this proposal is that the advent of fairness at scale gives rise to novel algorithmic challenges, revolving around the design of methods that are practical, widely applicable, and provably fair. Solutions to these challenges call for a synthesis of ideas from theoretical computer science and microeconomic theory.
The evolution of Spliddit plays a key role in the project: Insights arising from the research will be implemented to improve Spliddit's publicly accessible methods. Moreover, new applications will be added in order to further widen the website's reach. The project also includes plans to enhance Spliddit's educational content through the creation of instructive videos, thereby making the website a valuable learning and teaching resource. Finally, the project contains plans to make a societal impact that extends beyond Spliddit. In particular, the PI will work with California school districts to develop a fair method for allocating unused space.
On a technical level, the thrust of the project is twofold. (i) Dividing indivisible goods: One of five applications currently available on Spliddit, the division of indivisible goods is a notoriously difficult problem from a fair division perspective. To obtain a provably fair method, Spliddit relies on the notion of maximin share (MMS) guarantee. While exact MMS allocations may be infeasible, the project explores several notions of approximation. The project also explores the feasibility boundary of MMS allocations. Foundational algorithmic challenges lie at the heart of these research directions. (ii) Sharing credit: Spliddit's credit calculator fairly determines the contribution of each individual to a group project, using a method developed by de Clippel et al. Perhaps the method's most compelling guarantee is impartiality: a player's report does not affect her own share of the credit. Dividing credit for a scientific paper, with the goal of fairly ordering the authors by contribution, is an especially attractive potential application; but there is no guarantee that players will not be able to affect their position in the resultant ranking. The project aims to circumvent this obstacle via randomization and approximation.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The goal of the project was to identify new fairness properties that can be guaranteed in real-world allocation problems, design algorithms that provably achieve such properties, and make these algorithms publicly accessible for large-scale use by ordinary people.
Research supported by the project has led to significant advances in computational fair division, including the following highlights:
1. Computationally efficient algorithms for dividing rent in a way that is envy free, i.e., the algorithm produces an assignment of the rooms and division of the rent so that no participant would want to swap rooms with another participant.
2. Practical algorithms for computing allocations of indivisible goods (such as artworks or jewelry) that are "almost" envy free and Pareto optimal (it is impossible to reallocate the goods in a way that benefits some participants without harming other participants).
3. Methods for fairly allocating goods that arrive over time, which can compete with the best solution in hindsight despite having no knowledge of future arrivals.
4. Fundamental connections between fair division and fairness in machine learning, including the use of envy freeness as a notion of fairness for classification, and the application of axioms from fair division to uncover paradoxes in fair machine learning.
The vehicle by which this research was made available to the public is Spliddit.org, a not-for-profit fair division website founded by the PI in 2014, which has attracted hundreds of thousands of users to date. The abovementioned new algorithms for the division of rent and indivisible goods have been implemented and deployed on Spliddit. Moreover, two new applications (division of fare and chores) have been added to Spliddit.
Another major outreach activity has been the publication of opinion pieces. The PI has written more than a dozen opinion pieces in highly visible outlets during the lifetime of the project, including some dealing with applications of computational fair division to political redistricting and to the selection of citizens' assemblies.
Last Modified: 07/27/2020
Modified by: Ariel D Procaccia
Please report errors in award information by writing to: awardsearch@nsf.gov.
