Effective Competition Organization to Obtain Effective Algorithmic Solutions from a Motivated, Possibly Colluding Community

Speaker: Karl Lieberherr, College of Computer and Information Science, Northeastern University, Boston.

Joint Work with Ahmed Abdelmeged (PhD Dissertation) and Ruiyang Xu.


Effective algorithmic solutions are in high demand in numerous domains, such as big data. 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 effective from two viewpoints. (1) We minimize the effort on the competition administration by distributing the work of evaluation among participants while guaranteeing a fair evaluation. (2) We minimize the effect of 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 competition 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 side-choosing 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.