able fairness properties. As one example, a representative of one of the
largest school districts in California
approached the Spliddit team about
a problem he was tasked with solving:
fairly allocating unused classrooms in
public schools to the district’s charter
schools. This led the Spliddit team,
in collaboration with the California
school district, to design a practical
new approach to classroom allocation
that guarantees envy-freeness as well
as several other desirable properties.
32
A Challenge Problem:
The Crowdsourcing Compiler
A concrete challenge problem for future research in social computing is
what might be called the “
Crowdsourcing Compiler:”i the development of
high-level programming languages for
specifying large-scale, distributed tasks
whose solution requires combining traditional computational and networking resources with volunteer (or paid)
human intelligence and contributions.
The hypothetical compiler would translate an abstract program into a more detailed organizational plan for machines
and people to jointly carry out the desired task. In the same way that today’s
Java programmer is relieved of low-level, machine-specific decisions (such
as which data to keep in fast registers,
and which in main memory or disk),
the future crowdsourcing programmer
would specify the goals of their system,
and leave many of the implementation
details to the Crowdsourcing Compiler.
Such details might include which components of the task are best carried out
by machine and which by human volunteers; whether the human volunteers
should be incentivized by payment, recognition, or entertainment; how their
contributions should be combined to
solve the overall task; and so on. While
a fully general Crowdsourcing Compiler
might well be unattainable, significant
progress toward it would imply a much
deeper scientific understanding of
crowdsourcing than we currently have,
which in turn should have great engineering benefits. Noteworthy research
efforts which can be viewed as steps on
the path to the Crowdsourcing Compiler
include Emery Berger’s AutoMan Proj-
i See http://bit.ly/20juYEX and http://bit.ly/
1nIyc3P.
search on (computational) fair division36 and comes with provable mathematical guarantees. For example, the
algorithm used for room assignment
and rent splitting relies on the fact that
there always exists an assignment of
rooms and a corresponding set of prices
that are envy-free: every roommate prefers the room he is assigned to any other
room given the prices. Each roommate
submits her own value for each of the
rooms, under the constraint that the total value of all rooms matches the total
rent for the apartment; viewed another
way, each roommate is essentially submitting a proposed set of prices for each
room such that she would be equally
happy obtaining any room at the specified price. The algorithm then maximizes the minimum utility (value of room
minus price) of any roommate subject
to the constraint that envy-freeness is
satisfied. The solution is also Pareto efficient, meaning there is no other allocation that would increase the utility of
any roommate without decreasing the
utility of another.
As another example, the credit assignment problem is solved using an
algorithm of de Clippel et al.
8 Each collaborator reports the relative portion
of credit that he believes should be assigned to each of the other collaborators. For example, on a project with four
collaborators, collaborator A might report that collaborators B and C should
receive equal credit while D should
receive twice as much credit. The algorithm takes these reports as input and
produces a credit assignment that is
impartial, meaning that an individual’s
share of credit is independent of his
own report, and consensual, meaning
that if there is a division of credit that
agrees with all collaborators’ reports
then this division is chosen. While these
conditions may not sound restrictive,
de Clippel et al.
8 show they are not simultaneously achievable with three collaborators. Their algorithm therefore
requires at least four.
In addition to providing a useful set
of tools, part of Spliddit’s mission is to
“communicate to the public the beauty
and value of theoretical research in
computer science, mathematics, and
economics, from an unusual perspective.” Indeed, the project has inspired
some members of the public to take
an interest in algorithms with prov-
Mathematical
and experimental
research are
complementary and
both are needed to
develop relevant
mathematical
foundations for
social computing.