Title:
Axiomatic and Optimal Design of Algorithm Competitions with a Surprise
Speaker:
Karl Lieberherr,
College of Computer and Information Science, Northeastern University, Boston.
Abstract
Algorithm competitions are productive systems to push
the state-of-the-art of solving a computational problem.
TopCoder and similar platforms are prominent examples.
Our competition design is optimal from two viewpoints.
(1) We minimize the effort on the competition administration
by distributing the work of evaluation among participants
while avoiding abuse of the reputation system.
(2) We minimize collusion so that the strong participants
cannot be outnumbered by colluding participants.
Our design is axiomatic in that we formulate
axioms (including a collusion-resistant axiom)
for ranking functions and we prove a representation
theorem. It shows that all ranking functions satisfying
the axioms must have an elegant property useful for
collusion-resistant mechanism design.
Our design approach introduces a new class of games,
called side-choosing games, and advances our knowledge
about semantic games, a well-studied area in logic.
In addition to algorithm competitions, our system and
its theoretical foundation is also
useful to pushing the state-of-the-art in formal sciences
and in education in formal sciences. Indeed, the system was
developed in the context of education (Algorithms and Software Development Courses) to facilitate fair
peer grading and focused communication among students.
Our system is also a model of a Popperian scientific community where claims
are being made, attacked and refuted.
The educational benefits of semantic games have a direct implication
for the crowd workers: They get valuable feedback when they lose.
Short Bio of Speaker:
Karl Lieberherr
is a Professor in the College of Computer and
Information Science at Northeastern University.
He has contributed to
Algorithms (P-optimal Algorithms, Clause Learning for Satisfiability)
and
Modular Software Design (Law of Demeter and several systems
for Adaptive Programming, a kind of Aspect-Oriented Programming).
His latest interest is in systems and their foundations for
Human Computation for complex tasks, e.g., algorithm development.