One fairness criterion is
envy-freeness: We should find an allocation such
that every agent prefers her bundle
(that is, the tasks or resources allocated to her) to each other agent’s bundle.
When resources are not divisible, an
envy-free allocation is not always possible, and deciding whether one exists
is NP-hard. 22 Moreover, one can argue
that envy-freeness alone is not sufficient: even if an allocation is envy-free,
it is possible that reallocating the tasks
or resources can make everyone better
off, in which case we say that the original allocation is not Pareto efficient.
For example, consider a situation
where one agent owns two left shoes,
and another agent owns two right
shoes. Neither agent envies the other’s
situation, but both agents can be made
better off by trading a left shoe for a
right shoe. Pareto efficiency is generally
considered to be of paramount importance. There has been work characterizing the computational complexity of
finding an allocation that is both envy-free and Pareto efficient. 5
In a context where every resource
is initially owned by one of the agents,
it makes sense to use an exchange—
even if, for some reason, payments
are not possible. The following is one
such example of an exchange without
payments.
Kidney exchanges. In most exchanges, the participants can make payments
to each other, which facilitates trade.
However, there are some exchanges in
which no payments can be made, so
that only items change hands. These
are known as barter exchanges. An example is a kidney exchange. 27
Buying and selling kidneys is illegal in most countries; however, this
is not the case for swapping kidneys.
As an example, suppose a patient is in
need of a kidney transplant, and there
is a donor who is willing to give up her
kidney for this particular patient, but
unfortunately they are not compatible.
There may be a second patient-donor
pair in the same situation; moreover, it
may be the case that the second patient
is compatible with the first donor, and
the first patient is compatible with the
second donor. In this case, it is beneficial for the two patient-donor pairs to
swap their donors’ kidneys.
It is helpful to think of each patient-donor pair as a single agent, so that
the key benefit
of using an auction
is that the resource
ends up with
the agent who
values it the most
(or the task ends
up with the agent
who minds doing
it the least).
In this case, we
say that the auction
results in an
efficient allocation.
each agent has a kidney and needs
a(nother) kidney. This makes it easier
to see that more complex trades can
be beneficial: agent 1’s kidney can go
to agent 2, agent 2’s kidney to agent 3,
and agent 3’s kidney to agent 1—this is
known as a cycle of length 3. Of course,
we can also have cycles of length 4, and
so on—but it is preferable to not have
very long cycles (all the operations in
a cycle have to be performed simultaneously so that nobody will back out,
which poses a logistical problem for
long cycles; also, if last-minute testing
discovers an incompatibility in the cycle, the entire cycle collapses).
Kidney exchanges are a reality, and
computer scientists are involved in
them. 1 Indeed, they have started working on the computational problem of
clearing the exchange: the input describes which patients are compatible
with which of the donors’ kidneys, and
the output specifies which cycles will
be used. Using matching algorithms,
the problem can be solved in polynomial time if there are no restrictions
on how long cycles can be, or if only
cycles of length two are allowed. However, if the maximum cycle length is
three or more, then the problem is NP-hard. Nevertheless, in practice, large
exchanges can be solved to optimality,
using optimization techniques including column generation and branch-and-price search. 1
Setting with Payments
We now move on to settings where
agents can make or receive payments.
Payments are useful because they allow
us to quantify agents’ preferences. Informally, agents now need to put their
money where their mouths are. Payments also allow us to transfer happiness (utility) from one agent to another.
Auctions and exchanges. In many
problems that require us to decide on
an allocation of tasks or resources, it
makes sense to also determine payments that some agents should make
to other agents. Returning to our example of allocating chores, imagine that
the inhabitants are roommates who
each pay a share of the rent, and we
end up assigning a disproportionate
number of chores to one of the roommates. It seems fair that this roommate
should pay a smaller share of the rent,
which effectively represents a mon-
