Det strategisäkra klassificeringsproblemet handlar om en inställning där en beslutsfattare måste klassificera en uppsättning inmatningspunkter med binära etiketter, samtidigt som det förväntade felet minimeras. Etiketterna på inmatningspunkterna rapporteras av egenintresserade agenter, som kanske ljuger för att få en klassificering som närmare matchar deras egna etiketter och därigenom skapar en partiskhet i uppgifterna; detta motiverar utformningen av sanningsenliga mekanismer som motverkar falska rapporter. I detta dokument ger vi strategisäkra mekanismer för klassificeringsproblem i två begränsade inställningar: i) det finns bara två klassificeringar, och ii) alla agenter är intresserade av en gemensam uppsättning inmatningspunkter. Vi visar att dessa rimliga antaganden leder till starka positiva resultat. Framför allt visar vi att variationer i en slumpmässig diktatorisk mekanism, som är sanningsenlig, kan garantera ungefär optimala resultat när det gäller alla kategorier av kategorier. Dessutom är dessa resultat snäva i den meningen att de motsvarar bästa möjliga approximationsgrad som kan garanteras genom någon sanningsenlig mekanism. Vi visar vidare hur våra mekanismer kan användas för att lära klassificerare från provdata, och ge PAC-stil generalisering gränser på deras förväntade fel. Intressant nog kan våra resultat tillämpas på problem i samband med olika områden utöver klassificering, inklusive anläggningsplacering och bedömningsaggregation.
Meir m.fl. REF ger starka positiva resultat för utformning av strategisäkra klassificeringar när det antingen bara finns två klassificeringar, eller så är agenterna intresserade av en delad uppsättning inmatningspunkter.
Algorithms for strategyproof classification
{'venue': 'Artif. Intell.', 'journal': 'Artif. Intell.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}