Jens Witkowski – Publications
(Show all abstracts)
(Hide all abstracts)
2013
-
Jens Witkowski, Yoram Bachrach, Peter Key and David C. Parkes.
Dwelling on the Negative: Incentivizing Effort in Peer Prediction.
In
Proceedings of the 1st AAAI Conference on Human Computation and Crowdsourcing (HCOMP 2013).
2013.
(Show abstract)
(Hide abstract)
(PDF)
Agents are asked to rank two objects in a setting where effort
is costly and agents differ in quality (which is the probability
that they can identify the correct, ground truth, ranking). We
study simple output-agreement mechanisms that pay an agent in
the case she agrees with the report of another, and potentially
penalizes for disagreement through a negative payment. Assuming
access to a quality oracle, able to determine whether an agent's
quality is above a given threshold, we design a payment scheme
that aligns incentives so that agents whose quality is above
this threshold participate and invest effort. Precluding
negative payments leads the expected cost of this quality-oracle
mechanism to increase by a factor of 2 to 5 relative to allowing
both positive and negative payments. Dropping the assumption
about access to a quality oracle, we further show that negative
payments can be used to make agents with quality lower than the
quality threshold choose to not to participate, while those
above continue to participate and invest effort. Through the
appropriate choice of payments, any design threshold can be
achieved. This self-selection mechanism has the same expected
cost as the cost-minimal quality-oracle mechanism, and thus when
using the self-selection mechanism, perfect screening comes for
free.
-
Jens Witkowski and David C. Parkes.
Learning the Prior in Minimal Peer Prediction.
In
Proceedings of the 3rd Workshop on Social Computing and User Generated Content (SC 2013).
2013.
(Show abstract)
(Hide abstract)
(PDF)
Many crowdsourcing applications rely on the truthful elicitation
of information from workers; e.g., voting on the quality of an
image label, or whether a website is inappropriate for an
advertiser. Peer prediction provides a theoretical mechanism for
eliciting truthful reports. However, its application depends on
knowledge of a full probabilistic model: both a distribution on
votes, and a posterior for each possible single vote
received. In earlier work, Witkowski and Parkes [2012b], relax
this requirement at the cost of “non-minimality,” i.e., users
would need to both vote and report a belief about the vote of
others. Other methods insist on minimality but still require
knowledge of the distribution on votes, i.e., the signal prior
but not the posterior [Jurca and Faltings 2008, 2011; Witkowski
and Parkes 2012a]. In this paper, we develop the theoretical
foundation for learning the signal prior in combination with
these minimal peer-prediction methods. To score an agent, our
mechanism uses the empirical frequency of reported signals
against which to “shadow” [Witkowski and Parkes 2012a], delaying
payments until the empirical frequency is accurate enough. We
provide a bound on the number of samples required for the
resulting mechanism to provide strict incentives for truthful
reporting.
2012
-
Jens Witkowski and David C. Parkes.
A Robust Bayesian Truth Serum for Small Populations.
In
Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012).
2012.
(Show abstract)
(Hide abstract)
(PDF)
Peer prediction mechanisms allow the truthful elicitation of
private signals (e.g., experiences, or opinions) in regard to a
true world state when this ground truth is unobservable. The
original peer prediction method is incentive compatible for any
number of agents n ≥ 2, but relies on a common prior, shared by
all agents and the mechanism. The Bayesian Truth Serum (BTS)
relaxes this assumption. While BTS still assumes that agents
share a common prior, this prior need not be known to the
mechanism. However, BTS is only incentive compatible for a
large enough number of agents, and the particular number of
agents required is uncertain because it depends on this private
prior. In this paper, we present a robust BTS for the
elicitation of binary information which is incentive compatible
for every n ≥ 3, taking advantage of a particularity of the
quadratic scoring rule. The robust BTS is the first peer
prediction mechanism to provide strict incentive compatibility
for every n ≥ 3 without relying on knowledge of the common
prior. Moreover, and in contrast to the original BTS, our
mechanism is numerically robust and ex post individually
rational.
-
Jens Witkowski and David C. Parkes.
Peer Prediction without a Common Prior.
In
Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012).
2012.
Supersedes the SC'11 paper "Peer Prediction with Private Beliefs".
(Show abstract)
(Hide abstract)
(PDF)
Reputation mechanisms at online opinion forums, such as Amazon
Reviews, elicit ratings from users about their experience with
different products. Crowdsourcing applications, such as image
tagging on Amazon Mechanical Turk, elicit votes from users as to
whether or not a job was duly completed. An important property
in both settings is that the feedback received from users
(agents) is truthful. The peer prediction method introduced by
Miller et al. [2005] is a prominent theoretical mechanism for
the truthful elicitation of reports. However, a significant
obstacle to its application is that it critically depends on the
assumption of a common prior amongst both the agents and the
mechanism. In this paper, we develop a peer prediction mechanism
for settings where the agents hold subjective and private
beliefs about the state of the world and the likelihood of a
positive signal given a particular state. Our shadow peer
prediction mechanism exploits temporal structure in order to
elicit two reports, a belief report and then a signal report,
and it provides strict incentives for truthful reporting as long
as the effect an agent’s signal has on her posterior belief is
bounded away from zero. Alternatively, this technical
requirement on beliefs can be dispensed with by a modification
in which the second report is a belief report rather than a
signal report.
2011
-
Jens Witkowski, Sven Seuken and David C. Parkes.
Incentive-Compatible Escrow Mechanisms.
In
Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011).
2011.
(Show abstract)
(Hide abstract)
(PDF)
The most prominent way to establish trust between buyers and sellers on online auction sites are reputation mechanisms. Two drawbacks of this approach are the reliance on the seller
being long-lived and the susceptibility to whitewashing. In this paper, we introduce so-called escrow mechanisms that avoid these problems by installing a trusted intermediary
which forwards the payment to the seller only if the buyer acknowledges that the good arrived in the promised condition.
We address the incentive issues that arise and design an escrow mechanism that is incentive compatible, efficient, interim individually rational and ex ante budget-balanced. In
contrast to previous work on trust and reputation, our approach does not rely on knowing the sellers' cost functions or the distribution of buyer valuations.
-
Jens Witkowski.
Incentive-Compatible Trust Mechanisms (Extended Abstract).
In
Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011).
2011.
16th AAAI/SIGART Doctoral Consortium.
(PDF)
-
Jens Witkowski.
Trust Mechanisms for Online Systems (Extended Abstract).
In
Proceedings of the 22nd International Joint Conference
on Artificial Intelligence (IJCAI 2011).
2011.
IJCAI 2011 Doctoral Consortium.
(PDF)
-
Jens Witkowski and David C. Parkes.
Peer Prediction with Private Beliefs.
In
Proceedings of the 1st Workshop on Social Computing and User Generated Content (SC 2011).
2011.
Superseded by the EC'12 paper "Peer Prediction without a Common Prior".
(Show abstract)
(Hide abstract)
(PDF)
Reputation mechanisms at online opinion forums, such as Amazon
Reviews, elicit ratings from their users about the experiences with
products of unknown quality and critically rely on these ratings
being truthful. The peer prediction method by Miller, Resnick and
Zeckhauser is arguably the most prominent truthful feedback
mechanism in the literature. An obstacle with regard to its
application are the strong common knowledge assumptions. Especially
the commonly held prior belief about a product's quality, although
prevailing in economic theory, is too strict for this setting. Two
issues stand out in particular: first, that different buyers hold
different beliefs and, second, that the buyers' beliefs are often
unknown to the mechanism. In this paper, we develop an
incentive-compatible peer prediction mechanism for these reputation
settings where the buyers have private beliefs about the product's
inherent quality and the likelihood of a positive experience given a
particular quality. We show how to exploit the temporal structure
and truthfully elicit two reports: one before and one after the
buyer's experience with the product. The key idea is to infer the
experience from the direction of the belief change and to use this
direction as the event that another buyer is asked to predict.
2010
2009
-
Jens Witkowski.
Eliciting Honest Reputation Feedback in a Markov Setting.
In
Proceedings of the 21th International Joint Conference
on Artificial Intelligence (IJCAI 2009).
2009.
(Show abstract)
(Hide abstract)
(PDF)
Recently, online reputation mechanisms have been proposed that
reward agents for honest feedback about products and services
with fixed quality. Many real-world settings, however, are
inherently dynamic. As an example, consider a web service that
wishes to publish the expected download speed of a file
mirrored on different server sites. In contrast to the models
of Miller, Resnick and Zeckhauser and of Jurca and Faltings,
the quality of the service (e.g., a server's available
bandwidth) changes over time and future agents are solely
interested in the present quality levels. We show that
hidden Markov models (HMM) provide natural generalizations of
these static models and design a payment scheme that elicits
honest reports from the agents after they have experienced the
quality of the service.
-
Jens Witkowski.
Truthful Feedback for Reputation Mechanisms.
Diploma thesis,
Albert-Ludwigs-Universität,
Freiburg, Germany 2009.
(Show abstract)
(Hide abstract)
(PDF)
Reputation mechanisms such as those employed by Amazon and
eBay offer an effective way to prevent market failure in
online economies. However, most of these mechanisms assume
that the privately monitored transaction outcomes are honestly
reported. This clearly is a simplification since buyers may
have incentives to misreport. While it has been shown that the
truthful elicitation of these outcomes is feasible in settings
with pure adverse selection, i.e. with a purely
stochastic seller, we study whether honest feedback can
be elicited in settings with moral hazard, i.e. with a
strategic seller. For a pure moral hazard setting
motivated by the one at eBay, we find that there is no
feedback mechanism that makes honest reporting a best response
to truthful play by all other players. For a combined setting
with both adverse selection and moral hazard, however, we
retrieve a positive result and construct a payment scheme that
can be used as a "feedback plug-in" for reputation mechanisms.
2008
-
Jens Witkowski.
Eliciting honest reputation feedback in a Markov setting.
Student project,
Albert-Ludwigs-Universität,
Freiburg, Germany 2008.
(PDF)
