"Strategy Proof Classification"

Speaker: Reshef Meir, The Hebrew University
Date: Wednesday, 25 March 2009
Time: 3pm
Place: Ross 201

Abstract:

We consider the following setting: a decision maker should classify a
finite set of data points with binary labels, minimizing the expected
error. Subsets of data points are controlled by different selfish
agents, which might misreport the labels in order to sway the decision
in their favor. We design mechanisms (both deterministic and
randomized) that reach an approximately optimal decision and are
Strategy-Proof, i.e., agents are best off when they tell the truth. We
examine the best approximation ratio that can be achieved using a
Strategy-Proof mechanism in various conditions, thereby matching our
upper bounds with lower ones.

This talk will concentrate on two special cases in which the
approximation ratio can be shown to be constant. In the first case the
concept class contains only two classifiers, while in the second the
class is not limited, but all the agents are labeling the same set of
data points. We show that in these case our results can be casted into
a classical machine learning classification framework, where the
decision maker must learn an approximately optimal classifier based
only on a sampled subset of the agents' points.