<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of hal-03384439</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-16T10:02:53+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Preference Aggregation in the Generalised Unavailable Candidate Model</title>
            <author role="aut">
              <persName>
                <forename type="first">Arnaud</forename>
                <surname>Grivet Sébert</surname>
              </persName>
              <email type="md5">c6f66f23a3ee70afbf9a2ed9fcaab814</email>
              <email type="domain">cea.fr</email>
              <idno type="idhal" notation="numeric">1091110</idno>
              <idno type="halauthorid" notation="string">1398069-1091110</idno>
              <idno type="IDREF">https://www.idref.fr/272150754</idno>
              <affiliation ref="#struct-560489"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Nicolas</forename>
                <surname>Maudet</surname>
              </persName>
              <email type="md5">c77a464ca9f9a6c9279c3a40b6fe3c66</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="string">nicolas-maudet</idno>
              <idno type="idhal" notation="numeric">4473</idno>
              <idno type="halauthorid" notation="string">26051-4473</idno>
              <idno type="ARXIV">https://arxiv.org/a/maudet_n_1</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-4232-069X</idno>
              <idno type="IDREF">https://www.idref.fr/061744549</idno>
              <idno type="VIAF">https://viaf.org/viaf/65208532</idno>
              <idno type="ISNI">http://isni.org/isni/0000000044579115</idno>
              <idno type="RESEARCHERID">http://www.researcherid.com/rid/GDJ-2592-2022</idno>
              <idno type="RESEARCHERID">http://www.researcherid.com/rid/http://www.researcherid.com/rid/GDJ-2592-2022</idno>
              <orgName ref="#struct-93591"/>
              <affiliation ref="#struct-541716"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Patrice</forename>
                <surname>Perny</surname>
              </persName>
              <email type="md5">660fbf2ed2d2fd691694f8feb494f838</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="string">patrice-perny</idno>
              <idno type="idhal" notation="numeric">9264</idno>
              <idno type="halauthorid" notation="string">20708-9264</idno>
              <idno type="IDREF">https://www.idref.fr/11341689X</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-5741-2861</idno>
              <affiliation ref="#struct-541708"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Paolo</forename>
                <surname>Viappiani</surname>
              </persName>
              <email type="md5">298067a5df53fb7e2be61a7a24474b42</email>
              <email type="domain">dauphine.psl.eu</email>
              <idno type="idhal" notation="string">paolo-viappiani</idno>
              <idno type="idhal" notation="numeric">9572</idno>
              <idno type="halauthorid" notation="string">20709-9572</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-7922-3877</idno>
              <idno type="IDREF">https://www.idref.fr/178446521</idno>
              <affiliation ref="#struct-541708"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Paolo</forename>
                <surname>Viappiani</surname>
              </persName>
              <email type="md5">298067a5df53fb7e2be61a7a24474b42</email>
              <email type="domain">dauphine.psl.eu</email>
            </editor>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2021-10-18 22:42:39</date>
              <date type="whenModified">2024-12-03 13:12:02</date>
              <date type="whenReleased">2021-10-21 09:46:00</date>
              <date type="whenProduced">2021-11-03</date>
              <date type="whenEndEmbargoed">2021-10-18</date>
              <ref type="file" target="https://hal.sorbonne-universite.fr/hal-03384439v1/document">
                <date notBefore="2021-10-18"/>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal.sorbonne-universite.fr/hal-03384439v1/file/paper_44%20%282%29.pdf" id="file-3384439-2971362">
                <date notBefore="2021-10-18"/>
              </ref>
              <ref type="externalLink" target="https://hal.sorbonne-universite.fr/hal-03384439/document"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="57004">
                <persName>
                  <forename>Paolo</forename>
                  <surname>Viappiani</surname>
                </persName>
                <email type="md5">298067a5df53fb7e2be61a7a24474b42</email>
                <email type="domain">dauphine.psl.eu</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">hal-03384439</idno>
            <idno type="halUri">https://hal.sorbonne-universite.fr/hal-03384439</idno>
            <idno type="halBibtex">grivetsebert:hal-03384439</idno>
            <idno type="halRefHtml">&lt;i&gt;7th International Conference on Algorithmic Decision Theory&lt;/i&gt;, University of Toulouse, Nov 2021, Toulouse, France. pp.35-50, &lt;a target="_blank" href="https://dx.doi.org/10.1007/978-3-030-87756-9_3"&gt;&amp;#x27E8;10.1007/978-3-030-87756-9_3&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">7th International Conference on Algorithmic Decision Theory, University of Toulouse, Nov 2021, Toulouse, France. pp.35-50, &amp;#x27E8;10.1007/978-3-030-87756-9_3&amp;#x27E9;</idno>
            <availability status="restricted">
              <licence target="https://about.hal.science/hal-authorisation-v1/">HAL Authorization<ref corresp="#file-3384439-2971362"/></licence>
            </availability>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CEA">CEA - Commissariat à l'énergie atomique</idno>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="LIP6" corresp="SORBONNE-UNIVERSITE">Laboratoire d'Informatique de Paris 6</idno>
            <idno type="stamp" n="DRT" corresp="CEA">Direction de la recherche technologique</idno>
            <idno type="stamp" n="CEA-UPSAY" corresp="CEA">CEA - Université Paris-Saclay</idno>
            <idno type="stamp" n="UNIV-PARIS-SACLAY">Université Paris-Saclay</idno>
            <idno type="stamp" n="LIST" corresp="CEA">Laboratoire d'Intégration des Systèmes et des Technologies</idno>
            <idno type="stamp" n="SORBONNE-UNIVERSITE">Sorbonne Université</idno>
            <idno type="stamp" n="SORBONNE-UNIV" corresp="SORBONNE-UNIVERSITE">Sorbonne Université 01/01/2018</idno>
            <idno type="stamp" n="SU-SCIENCES" corresp="SORBONNE-UNIVERSITE">Faculté des Sciences de Sorbonne Université</idno>
            <idno type="stamp" n="DM2I" corresp="LIST">Département Métrologie Instrumentation &amp; Information</idno>
            <idno type="stamp" n="TEST-HALCNRS">Collection test HAL CNRS</idno>
            <idno type="stamp" n="UNIVERSITE-PARIS-SACLAY" corresp="UNIV-PARIS-SACLAY">Université Paris-Saclay</idno>
            <idno type="stamp" n="SU-TI">Sorbonne Université - Texte Intégral</idno>
            <idno type="stamp" n="GS-ENGINEERING">Graduate School Sciences de l'Ingénierie et des Systèmes</idno>
            <idno type="stamp" n="GS-COMPUTER-SCIENCE">Graduate School Computer Science</idno>
            <idno type="stamp" n="GS-SPORT-HUMAN-MOVEMENT">Graduate School Sport, Mouvement, Facteurs Humains</idno>
            <idno type="stamp" n="ALLIANCE-SU"> Alliance Sorbonne Université</idno>
            <idno type="stamp" n="DIN" corresp="DRT">Département d'Instrumentation Numérique</idno>
            <idno type="stamp" n="SUPRA_MATHS_INFO">Mathématiques + Informatique</idno>
          </seriesStmt>
          <notesStmt>
            <note type="commentary">ISBN 978-3-030-87755-2</note>
            <note type="audience" n="2">International</note>
            <note type="invited" n="0">No</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
            <note type="proceedings" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Preference Aggregation in the Generalised Unavailable Candidate Model</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Arnaud</forename>
                    <surname>Grivet Sébert</surname>
                  </persName>
                  <email type="md5">c6f66f23a3ee70afbf9a2ed9fcaab814</email>
                  <email type="domain">cea.fr</email>
                  <idno type="idhal" notation="numeric">1091110</idno>
                  <idno type="halauthorid" notation="string">1398069-1091110</idno>
                  <idno type="IDREF">https://www.idref.fr/272150754</idno>
                  <affiliation ref="#struct-560489"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Nicolas</forename>
                    <surname>Maudet</surname>
                  </persName>
                  <email type="md5">c77a464ca9f9a6c9279c3a40b6fe3c66</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="string">nicolas-maudet</idno>
                  <idno type="idhal" notation="numeric">4473</idno>
                  <idno type="halauthorid" notation="string">26051-4473</idno>
                  <idno type="ARXIV">https://arxiv.org/a/maudet_n_1</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-4232-069X</idno>
                  <idno type="IDREF">https://www.idref.fr/061744549</idno>
                  <idno type="VIAF">https://viaf.org/viaf/65208532</idno>
                  <idno type="ISNI">http://isni.org/isni/0000000044579115</idno>
                  <idno type="RESEARCHERID">http://www.researcherid.com/rid/GDJ-2592-2022</idno>
                  <idno type="RESEARCHERID">http://www.researcherid.com/rid/http://www.researcherid.com/rid/GDJ-2592-2022</idno>
                  <orgName ref="#struct-93591"/>
                  <affiliation ref="#struct-541716"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Patrice</forename>
                    <surname>Perny</surname>
                  </persName>
                  <email type="md5">660fbf2ed2d2fd691694f8feb494f838</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="string">patrice-perny</idno>
                  <idno type="idhal" notation="numeric">9264</idno>
                  <idno type="halauthorid" notation="string">20708-9264</idno>
                  <idno type="IDREF">https://www.idref.fr/11341689X</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-5741-2861</idno>
                  <affiliation ref="#struct-541708"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Paolo</forename>
                    <surname>Viappiani</surname>
                  </persName>
                  <email type="md5">298067a5df53fb7e2be61a7a24474b42</email>
                  <email type="domain">dauphine.psl.eu</email>
                  <idno type="idhal" notation="string">paolo-viappiani</idno>
                  <idno type="idhal" notation="numeric">9572</idno>
                  <idno type="halauthorid" notation="string">20709-9572</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-7922-3877</idno>
                  <idno type="IDREF">https://www.idref.fr/178446521</idno>
                  <affiliation ref="#struct-541708"/>
                </author>
              </analytic>
              <monogr>
                <meeting>
                  <title>7th International Conference on Algorithmic Decision Theory</title>
                  <date type="start">2021-11-03</date>
                  <date type="end">2021-11-05</date>
                  <settlement>Toulouse</settlement>
                  <country key="FR">France</country>
                </meeting>
                <respStmt>
                  <resp>conferenceOrganizer</resp>
                  <name>University of Toulouse</name>
                </respStmt>
                <editor>Dimitris Fotakis</editor>
                <editor>David Ríos Insua</editor>
                <imprint>
                  <publisher>Springer</publisher>
                  <biblScope unit="serie">Lecture Notes in Computer Science</biblScope>
                  <biblScope unit="volume">13023</biblScope>
                  <biblScope unit="pp">35-50</biblScope>
                </imprint>
              </monogr>
              <idno type="doi">10.1007/978-3-030-87756-9_3</idno>
              <ref type="publisher">https://www.irit.fr/ADT2021/</ref>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">voting rule</term>
                <term xml:lang="en">dissatisfaction</term>
                <term xml:lang="en">scoring rule</term>
                <term xml:lang="en">Machine learning</term>
                <term xml:lang="en">Artificial intelligence</term>
                <term xml:lang="en">Polynomial-Time Approximation Scheme</term>
                <term xml:lang="en">Unavailable Candidate Model</term>
                <term xml:lang="en">Preference Aggregation</term>
                <term xml:lang="en">Computational Social Choice</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-lg">Computer Science [cs]/Machine Learning [cs.LG]</classCode>
              <classCode scheme="halDomain" n="info.info-ai">Computer Science [cs]/Artificial Intelligence [cs.AI]</classCode>
              <classCode scheme="halTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halOldTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halTreeTypology" n="COMM">Conference papers</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>While traditional social choice models assume that the set of candidates is known and fixed in advance, recently several researchers have proposed to reject this hypothesis. In particular, the unavailable candidate model of Lu and Boutilier considers voting situations in which some candidates may not be available and focuses on minimising the number of binary disagreements between the voters and the consensus ranking. In this paper, we extend this model and present two new voting rules based on a finer notion of disagreement, called dissatisfaction. The dissatisfaction of a voter is defined as the disutility gap between its preferred available candidate and the candidate elected by the consensus ranking. In the first approach, called ex ante dissatisfaction rule, the disutility is independent of the set of available candidates whereas the second approach, called ex post dissatisfaction rule, assumes that the disutility depends on which candidates are actually available. We provide several results for the two rules. On the one hand, we show that the ex ante rule actually coincides with standard positional scoring rules; therefore, a consensus ranking can be computed in polynomial time. On the other hand, we exhibit strong links between ex post rule and Kemeny rule and we provide a polynomial-time approximation scheme (PTAS) for the ex post problem.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-560489" status="OLD">
          <orgName>Intelligence Artificielle et Apprentissage Automatique (CEA, LIST)</orgName>
          <orgName type="acronym">LI3A (CEA, LIST)</orgName>
          <date type="end">2022-12-31</date>
          <desc>
            <address>
              <addrLine>Artificial Intelligence and Automatic Learning (LI3A)91191 - Gif sur Yvette cedexanciennement Laboratoire Analyse des Données et Intelligence des Systèmes (LADIS), Laboratoire Information Modèles et Apprentissage (LIMA), Laboratoire Intelligence Multi-capteurs et Apprentissage (LIMA)</addrLine>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation name="DRT/LIST/DM2I/SID/LI3A" active="#struct-528161" type="direct"/>
            <relation name="DRT/LIST/DM2I" active="#struct-40217" type="indirect"/>
            <relation name="DRT/LIST" active="#struct-440043" type="indirect"/>
            <relation name="DRT" active="#struct-300016" type="indirect"/>
            <relation active="#struct-419361" type="indirect"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-541716" status="VALID">
          <orgName>Systèmes Multi-Agents</orgName>
          <orgName type="acronym">SMA</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-541703" type="direct"/>
            <relation active="#struct-413221" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-541708" status="VALID">
          <orgName>DECISION</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-541703" type="direct"/>
            <relation active="#struct-413221" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="department" xml:id="struct-528161" status="OLD">
          <idno type="RNSR">200822621H</idno>
          <orgName>Département Métrologie Instrumentation &amp; Information (CEA, LIST)</orgName>
          <orgName type="acronym">DM2I (CEA, LIST)</orgName>
          <date type="start">2013-04-01</date>
          <date type="end">2022-12-31</date>
          <desc>
            <address>
              <addrLine>ex DCSI.ex DETECS.CEA LIST</addrLine>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation name="DRT/LIST/DM2I" active="#struct-40217" type="direct"/>
            <relation name="DRT/LIST" active="#struct-440043" type="indirect"/>
            <relation name="DRT" active="#struct-300016" type="indirect"/>
            <relation active="#struct-419361" type="direct"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-40217" status="VALID">
          <idno type="IdRef">156836882</idno>
          <idno type="ISNI">0000 0004 0405 1788</idno>
          <idno type="RNSR">200118591H</idno>
          <idno type="ROR">https://ror.org/000dbcc61</idno>
          <idno type="Wikidata">Q30299467</idno>
          <orgName>Laboratoire d'Intégration des Systèmes et des Technologies</orgName>
          <orgName type="acronym">LIST (CEA)</orgName>
          <desc>
            <address>
              <addrLine>DRT/LISTNano-INNOVAvenue de la Vauve91120 Palaiseau</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www-list.cea.fr/</ref>
          </desc>
          <listRelation>
            <relation name="DRT/LIST" active="#struct-440043" type="direct"/>
            <relation name="DRT" active="#struct-300016" type="indirect"/>
          </listRelation>
        </org>
        <org type="regrouplaboratory" xml:id="struct-440043" status="VALID">
          <idno type="IdRef">067087930</idno>
          <idno type="ISNI">0000000121157881</idno>
          <idno type="RNSR">199018589D</idno>
          <idno type="ROR">https://ror.org/02ggzyd20</idno>
          <idno type="Wikidata">Q30299418</idno>
          <orgName>Direction de Recherche Technologique (CEA)</orgName>
          <orgName type="acronym">DRT (CEA)</orgName>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.drt-cea.com/</ref>
          </desc>
          <listRelation>
            <relation name="DRT" active="#struct-300016" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-300016" status="VALID">
          <idno type="IdRef">026372061</idno>
          <idno type="ISNI">0000000122998025</idno>
          <idno type="ROR">https://ror.org/00jjx8s55</idno>
          <idno type="Wikidata">Q868550</idno>
          <orgName>Commissariat à l'énergie atomique et aux énergies alternatives</orgName>
          <orgName type="acronym">CEA</orgName>
          <desc>
            <address>
              <addrLine>Centre de SaclayCentre de GrenobleCentre de Cadaracheetc</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.cea.fr/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-419361" status="VALID">
          <idno type="IdRef">241345251</idno>
          <idno type="ROR">https://ror.org/03xjwb503</idno>
          <orgName>Université Paris-Saclay</orgName>
          <desc>
            <address>
              <addrLine>Bâtiment Bréguet, 3 Rue Joliot Curie 2e ét, 91190 Gif-sur-Yvette</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.universite-paris-saclay.fr/fr</ref>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-541703" status="VALID">
          <idno type="IdRef">13558292X</idno>
          <idno type="RNSR">199712651U</idno>
          <idno type="ROR">https://ror.org/05krcen59</idno>
          <orgName>LIP6</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.lip6.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-413221" type="direct"/>
            <relation name="UMR7606" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="regroupinstitution" xml:id="struct-413221" status="VALID">
          <idno type="IdRef">221333754</idno>
          <idno type="ROR">https://ror.org/02en5vm52</idno>
          <orgName>Sorbonne Université</orgName>
          <orgName type="acronym">SU</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>21 rue de l’École de médecine - 75006 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.sorbonne-universite.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>