High-Level Introduction to Ahmed Abdelmeged's Dissertation

16 months after Ahmed started working full-time on Organizing Computational Problem Solving and less than a year since his thesis proposal, his final dissertation draft is now ready: Dissertation Draft

New Knowledge

What is the new knowledge that he contributes? He pushed at the boundary of the current knowledge about semantic games. Semantic games have been studied at least for a hundred years by logicians, including my academic grandfather Paul Bernays in the context of intuitionistic logic. Ahmed found his niche by studying tournaments of semantic games. He found a useful algebraic structure in the game results and their mappings into rankings of the participants. He defined an illusive property, called collusion-resistance, and showed that there are collusion-resistant ranking functions. Then he showed that collusion-resistance plays a central role in the theory of semantic game tournaments. He gives the first of its kind representation theorem of ranking functions which are collusion-resistant and satisfy other basic correctness properties. Those ranking functions must be based on counting certain losses.

Relevance of New Knowledge

  1. It helps to better organize computational problem solving communities. Collusion resilience is important because we want the price money to be distributed fairly.
  2. Related to (1), the new knowledge provides a foundation for the emerging field of Human Computation/Crowd Sourcing for complex problems. The theory of collusion-resistant ranking functions applies not only to semantic games but also to their more general cousin: side-choosing games. They are a useful component of mechanism design problems for human computation for complex problems.
  3. It helps to better organize debates in (virtual) class rooms. The interaction between the students helps with learning and collusion-resistance prevents the students from gaming the game and focus on learning the skills in the domain.
  4. It opens a new chapter in Social Choice Theory in the context of voting with justification. To our knowledge, the axiom of collusion-resistance based on the side-choosing aspect of semantic games, has not been studied before. Ahmed has the beginning of a social choice theory for voting with justification with axioms, an impossibility result and a characterization theorem.
  5. This is the Programming Research Lab view: Ahmed has developed a programming system for the global brain. The programs involve interpreted logical sentences, structures, and different kinds of semantic games. The program executions involve tournaments with schedulers and the mappings of tournament results to rankings. He proves that certain unsafe executions of the programs are impossible when they follow certain axioms.

Other New Knowledge

There are several other conceptual contributions in Abdelmeged's dissertation but the above theoretical result stands out. Other contributions: Linking competitions and semantic games and stating the advantages of semantic games for crowdsourcing/human computation (e.g., simplifying the work of the competition administrator by distributing the evaluation work). Inventing simplified semantic games and showing the equivalence to standard semantic games. Stating the tradeoffs involved in lab design.

Karl J. Lieberherr, advisor, April 2014