  We design a mechanism for Fair and Efficient Distribution of Resources
(FEDoR) in the presence of strategic agents. We consider a multiple-instances,
Bayesian setting, where in each round the preference of an agent over the set
of resources is a private information. We assume that in each of r rounds n
agents are competing for k non-identical indivisible goods, (n > k). In each
round the strategic agents declare how much they value receiving any of the
goods in the specific round. The agent declaring the highest valuation receives
the good with the highest value, the agent with the second highest valuation
receives the second highest valued good, etc. Hence we assume a decision
function that assigns goods to agents based on their valuations. The novelty of
the mechanism is that no payment scheme is required to achieve truthfulness in
a setting with rational/strategic agents. The FEDoR mechanism takes advantage
of the repeated nature of the framework, and through a statistical test is able
to punish the misreporting agents and be fair, truthful, and socially
efficient. FEDoR is fair in the sense that, in expectation over the course of
the rounds, all agents will receive the same good the same amount of times.
FEDoR is an eligible candidate for applications that require fair distribution
of resources over time. For example, equal share of bandwidth for nodes through
the same point of access. But further on, FEDoR can be applied in less trivial
settings like sponsored search, where payment is necessary and can be given in
the form of a flat participation fee. To this extent we perform a comparison
with traditional mechanisms applied to sponsored search, presenting the
advantage of FEDoR.
