[bull-ia] PhD thesis proposal on « Social Ranking Problems with Incomplete

PhD thesis propo=
sal on Computer Science / Artificial Intelligence

Social Ranking Problems with Inco=
mplete
Knowledge about Coalitions

Advisors: Se=CC=81bastien Konieczny (CRIL, CNRS and Artois University), Stefano More=
tti (LAMSADE,
CNRS and Paris-Dauphine University), Paolo Viappiani (LIP6, CNRS and Sorbon=
ne University)

Subject: =
The thesis project will focus on specific aspects related to the social ran=
king problem, that is
the problem of ordering the elements of a finite set given a ranking over t=
he elements of its power-set
(the set of all possible subsets), that represent possible coalitions of el=
ements [1, 2, 3, 4]. This
framework can model a variety of situations, including, for instance, evalu=
ations of the individual
influence in social networks, the responsibility of a formula in the incons=
istency of a belief base, the
importance of criteria in a multi-criteria decision-making process, and man=
y other situations where we
need to deduce evaluations about individual elements starting from the rela=
tive comparison of sets.

While most works assume that the order ov=
er coalitions is given as input, the information about the
relative strength of coalitions may not be readily available in practical s=
ituations, as it may be be costly
or even impossible to obtain. For this reason, the PhD candidate will inves=
tigate techniques
for determining an "optimal" single social ranking solution, or a=
set of solutions, given partial
information about the strength of coalitions. Moreover, the PhD candidate w=
ill design a framework for
interactive elicitation of information where, starting with a small partial=
order on coalitions, the system
repeatedly ask questions (that can either be: pairwise comparisons, evaluat=
ions on an ordinal scale,
ranking queries,…) to an expert in order to find a solution to social ran=
king problems (focusing on either
learning the full ranking, identifying the =E2=80=9Cmost in=
fluential=E2=80=9D individual, or the "top-k") as=
fast as possible;
questions are chosen to be as informative as possible according to a notion=
of value of information [5,
6].

Based on this initial phase, we will cons=
ider one or more of the following potential extensions:

=E2=97=8F  situations where the information about the coalitions has to be aggregated=
from several
experts [7].

=E2=97=8F  the analysis of the effects of the axioms on the strategic choice of actio=
ns within a coalition
and the design of social ranking mechanisms that resist the voluntary knock=
ing-out of
certain coalitions by some of their members, who can benefit from lowering =
the social
positions of other members. (This is along the lines of classical models of=
voting in social
choice and other classical models that study the manipulability of collecti=
ve decision-
making mechanisms).

=E2=97=8F  application, as a case study, of social ranking solutions to measure the i=
nfluence of criteria
for the selection of students in the national admissions platform like, in =
France, Parcoursup,
and/or to evaluate and compare the ordinal influence of agents in social ne=
tworks.

Desired qualifications: The ideal applicant has a Master Degree in computer science =
or in applied
mathematics and possesses a good background in game theory (preferably on c=
oalition formation) or
artificial intelligence (reasoning about uncertainty, recommender systems, =
knowledge representation and
inconsistency,…), and some basics in optimization (linear=
programming), in addition to general
programming skills.

The PhD position is at LAM=
SADE, a joint computer science laboratory of CNRS and Universite=CC=81 Pari=
s
Dauphine, located in Paris =E2=80=9Cintra muros=E2=80=9D, a=
nd it will be financed by the ANR project THEMIS (THeory
and Evidence to Measure Influence in Social structures).

https:=
//www.lamsade.dauphine.fr/themis/

Starting date of the PhD: September 2021
Interested candidates shall address their l=
etter of motivation, curriculum vitae, transcripts of

diploma and marks and the=
ir recommendation letters (max 2) to the following email addresses:

konieczny@cril.fr=

stefano.moretti@dauphine.fr
paolo.viappiani@lip6.fr

Deadline for application submission: May 31, 2021.

References

[1] Allouche T., Escoffier B., Moretti S.=
, O=CC=88ztu=CC=88rk M., Social ranking manipulability for the CP-majority,=
banzhaf
and lexicographic excellence solutions, In: Proceedings of the 29th Interna=
tional Joint Conference on Artificial
Intelligence (IJCAI 2019), 2020.

https://pdfs.semanticscholar.org/7c07/6250=
ef0f1adad7bec2223df83f728c9e83ea.pdf

[2] Bernardi G., Lucchetti R., Moretti S.=
, Ranking objects from a preference relation over their subsets, Social
Choice and Welfare, pp. 589-607, 2018.

https://link.springer.com/content/pdf/10.1007/s00355-=
018-1161-1.pdf

[3] Haret A., Khani H., S. Moretti S., O=
=CC=88ztu=CC=88rk M., Ceteris paribus majority for social ranking, In: Proceedings of
the 27th International Joint Conference on Artificial Intelligence (IJCAI 2=
018), pp. 303-309, 2018.

https://www.ijcai.org/Proceedings/2018/0042.pdf

[4] Khani H., Moretti S., O=CC=88ztu=CC=
=88rk M., An ordinal banzhaf index for social ranking, In: Proceedings of t=
he 28th
International Joint Conference on Artificial Intelligence (IJCAI 2019), pp.=
378-384, 2019.

https://www.ijcai.org/Proceedings/2019/0054.pdf

[5] Viappiani P., Boutilier C., Regret-ba=
sed optimal recommendation sets in conversational recommender
systems, In: Proceedings of the third ACM conference on Recommender systems=
, pp. 101=E2=80=93108, ACM, 2009.

https://dl.acm.org/doi/abs/10.1145/1639714.1639732

[6] Viappiani P., Boutilier C., On the eq=
uivalence of optimal recommendation sets and myopically optimal query
sets, Artificial Intelligence 286: 103328, 2020.

https://www.sciencedirect.com/science/article/abs/pii/S0004=
370220300849

[7] Xia L., Learning and Decision-Making =
from Rank Data, Synthesis Lectures on Artificial Intelligence and
Machine Learning, Morgan & Claypool Publishers, 2019.

https://www.morganclaypool.com/doi/10.2200/S00876ED1=
V01Y201810AIM040