My research is mainly about the interactions of agents and / or people in computing systems.
I'm interested in distributed systems from a multi-agent standpoint; distributed systems often mean decentralized control over distributed data, and I'm interested on how this data can be accessed and in issues of trust. I'm also interested in so-called social machines, where people and agents interact through computational systems. I am particularly interested in ethical dimensions of these interactions. I work with game theory, protocols, and I like building systems that work and do interesting things.
"Sociogrammes" project
(show)
Background :
A social machine [1] is a socio-technical system consisting of networked applications and their users. Many web and mobile applications generate social machines, such as Wikipedia, Twitter, Strava, Tinder, Waze, peer-to-peer networks, networked games like Pokemon go, etc.
Some social machines make use of existing systems (social networks, in particular): see for example the hashtag #icanhazpdf, which is used to coordinate the distribution of paywalled science papers.
Purpose:
The goal of this project is to democratize the creation of social machines, through a visual language that would allow novices to schematically describe a social interaction, and a system to automatically transform such a schema (a "sociagramme") into a functional infrastructure using existing applications (twitter messages, doodle polls, etc.).
The proposed work follows a project initiated with researchers from the Universities of Edinburgh and Oxford (SOCIAM project), and the basic ideas are described in two articles published in 2018 [2, 3].
Possible research topics:
-
Implementing and evaluating a 'sociagram' editor, which allows schemas to be drawn and saved in a format to be defined. The prototypes presented in [3] can be used as a starting point for the visual application.
-
Transform "sociagrams" into a functional social machine, using the model-driven development (MDD) approach. An important objective is to exploit as much as possible existing applications (Twitter, Slack, Doodle...) and combine them with simple agents.
-
Case study: creating a social machine for a real use case. One possibility is to create a decentralized wiki following the ideas of [4] (two prototypes exist, one in PHP is a Moodle extension, the other is a simple Ruby on Rails web application.
These topics can be treated at different levels of depth and be appropriate for an essay, a master's degree or a PhD (a PhD would probably combine all three).
[1] Smart, P. R., & Shadbolt,
N. R. (2015). Social machines. In Encyclopedia of Information Science and
Technology, Third Edition (pp. 6855-6862). IGI Global.
[2] Papapanagiotou, P., Davoust, A., Murray-Rust, D.,
Manataki, A., Van Kleek, M., Shadbolt, N., & Robertson, D. (2018, July).
Social Machines for All. In Proceedings of the 17th International Conference on
Autonomous Agents and MultiAgent Systems (pp. 1208-1212). International Foundation
for Autonomous Agents and Multiagent Systems.(pdf)
[3] Murray-Rust, D., Davoust, A., Papapanagiotou, P.,
Manataki, A., Van Kleek, M., Shadbolt, N., & Robertson, D. (2018, June). Towards executable representations
of social machines. In International Conference on Theory and Application of
Diagrams (pp. 765-769). Springer, Cham.(pdf)
Project: Social contracts for autonomous agents
(show)
Background:
The interaction of rational agents can be modelled by non-cooperative games, in the sense of game theory.
It is usually assumed that the outcome of the game will be a Nash equilibrium in the game. In many cases, Nash equilibria are inefficient, i.e. the sum of the utilities obtained by the players in equilibrium is less than the utility that could be obtained by the optimal (joint) action.
Purpose:
This project explores mechanisms for modifying games to encourage more efficient or desirable equilibria. There are several aspects to this project. First, there is a social choice problem: assuming that agents are dissatisfied with an existing game, they have to choose together how this game should be modified: for example, it can be modified to generate the maximum utility, or to distribute the utility as fairly as possible (for various definitions of fairness).
Our first study on the topic [4] has shown that any game can be modified by redistributing the payoffs, so that the total utility produced by the game is optimal, and the players rationally prefer the modified game to the original. On the other hand, for any other objective than maximal utility, there will be games where this is not feasible.
In future work we would like to implement transformation algorithms and to experiment with learning agents. We would also like to explore connections to cooperative game theory and bargaining.
Possible research topics:
-
Theoretical study of the social choice problem of choosing modifications to a game.
-
Theoretical study: how does this approach relate to relevant concepts from cooperative game theory (kernel) and/or partition function form games.
-
Practical case study with agents using multi-agent (reinforcement) learning.
-
Feasibility study: implementing a social contract using smart contracts on blockchain.
These topics can be treated at different levels of depth and are appropriate for an essay, a master's degree or a PhD. A PhD in this field requires a solid theoretical background.
[4] Davoust,A. and Rovatsos, M.: Social Contracts for Non-Cooperative Games. AIES 2020: 43-49.(pdf)
Project: Graph queries for the Semantic Web
(afficher)
Contexte :
The Semantic Web, the Linked Data on the Web movement, are movements to promote the sharing of data on the Web, mainly in RDF format. Graph formats such as RDF are the preferred format for knowledge representation. One of the fundamental mechanisms of graph queries is the traversal of edges following paths matching regular expressions -- Regular Path Queries (RPQs). A number of techniques have been proposed to evaluate RPQ queries in a centralised context, and a few have been proposed for distributed databases.
Goal
In this project we want to evaluate graph queries in the context of the Semantic Web.
Possible research topics:
- Adapting existing techniques (from graph databases) to SPARQL property path (PP) queries.
- Experimental evaluation of graph modeling techniques to assess the cost of web requests. (extension of [7])
- Adding PP queries to existing SPARQL / Semantic Web benchmarks.
-
Application of graph query evaluation techniques to security. See [5]. The project would consist in replicating these results and collaborating with a researcher in cryptography to try to obtain them using private multi-party computing [6]
These subjects may be more appropriate for a essay or master's degree. For a PhD, I'm open to discuss directions for expanding these projects.
[5] Chen, H., Dean, D., & Wagner, D. A. (2004, February). Model Checking One Million Lines of C Code. In NDSS (Vol. 4, pp. 171-185).
[6] Goldwasser, S. (1997, August). Multi party computations: past and present. In Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing (pp. 1-6). ACM.
[7] Davoust, A., & Esfandiari, B. (2016, October). Processing regular path queries on arbitrarily distributed data. In OTM Confederated International Conferences" On the Move to Meaningful Internet Systems" (pp. 844-861). Springer, Cham.
Project: Decentralised Collaboration for note-taking
(afficher)
Background:
Today many students use computers or tablets to take notes in class. However, this practice has changed very little in the past years, despite the potential of collaborative editing software to improve the students' experience.
One of the reasons for this could be that existing collaborative tools all implement the same collaboration model, where everyone edits a shared document, and there is only one version of the document, "one size fits all", whereas by taking their own notes, students get customized educational material. Teachers' experiences demonstrate weaknesses in the shared document model: it can be difficult to motivate students to participate, and they may also be uncomfortable editing, and thus destroying, text written by others. The difficulty for students to participate could be explained, in game theory, by the similarity of the situation with the classic "snowdrift game": if participating is costly, and the benefit may come from the work of others, then the rational attitude is to passively wait for others to work.
Goal:
In this project we aim to develop a collaborative editing tool (similar to a Wiki) where participants can benefit from collaboration while maintaining a personalized version of the resulting document?
We are currently developing this tool, implementing the "decentralized collaboration model" proposed in my PhD [8]. We will trial it in the fall term at UQO, then possibly in online courses (MOOC).
We are also developing an implementation purely in the browser, supported by peer-to-peer browser-to-browser connections.
[8] Davoust, A., Craig, A., Esfandiari, B. &Kazmierski, V. (2015). P2Pedia: a peer-to-peer wiki for decentralized collaboration. Concurrency and Computation: Practice and Experience.(pdf)
