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:
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
It helps to better organize computational problem solving communities.
Collusion resilience is important because we want the price money to be
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.
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.
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.
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,