Iterative Voting, Control and Sentiment Analysis

In multi-agent systems agents often need to take a collective decision based on the preferences of individuals. A voting rule is used to decide which decision to take, mapping the agents' preferences over the possible candidate decisions into a winning decision for the collection of agents. In these kind of scenarios acting strategically can be seen in two opposite way. On one hand it may be desirable that agents do not have any incentive to act strategically. That is, to misreport their preferences in order to influence the result of the voting rule in their favor or acting on the structure of the election to change the outcome. On the other hand manipulation can be used to improve the quality of the outcome by enlarging the consensus of the winner. These two different scenarios are studied in this thesis. The first one by modeling and describing a natural form of control named ``replacement control'' and characterizing for several voting rules its computational complexity. The second scenario is studied in the form of iterative voting frameworks where individuals are allowed to change their preferences to change the outcome of the election. Computational social choice techniques can be used in very different scenarios. This work reports a first attempt to introduce the use of voting procedures in the field of sentiment analysis. In this area computer scientists extract the opinion of the community about a specific item. This opinion is extracted aggregating the opinion expressed by each individual which leaves a text in a blog or social network about the given item. We studied and proposed a new aggregation method which can improve performances of sentiment analysis, this new technique is a new variance of a well-known voting rule called Borda.

Nei sistemi multi agente spesso nasce la necessità di prendere decisioni collettive basate sulle preferenze dei singoli individui. A tal fine può essere utilizzata una regola di voto che, aggregando le preferenze dei singoli agenti, trovi una soluzione che rappresenti la collettività. In questi scenari la possibilità di agire in modo strategico può essere vista da due diversi e opposti punti di vista. Da una parte può essere desiderabile che gli agenti non abbiano alcun incentivo ad agire strategicamente, ovvero che gli agenti non abbiano incentivi a riportare in modo scorretto le proprie preferenze per influenzare il risultato dell'elezione a proprio favore, oppure che non agiscano sulla struttura del sistema elettorale stesso per cambiarne il risultato finale. D'altra parte l'azione strategica può essere utilizzata per migliorare la qualità del risultato o per incrementare il consenso del vincitore. Questi due diversi scenari sono studiati ed analizzati nella tesi. Il primo modellando e descrivendo una forma naturale di controllo chiamato "replacement control" descrivendo la complessità computazione di tale azione strategica per diverse regole di voto. Il secondo scenario è studiato nella forma dei sistemi di voto iterativi nei quali i singoli individui hanno la possibilità di cambiare le proprie preferenze al fine di influenzare il risultato dell'elezione. Le tecniche di Computational Social Choice inoltre possono essere usate in diverse situazioni. Il lavoro di tesi riporta un primo tentativo di introdurre l'uso di sistemi elettorali nel campo dell'analisi del sentimento. In questo contesto i ricercatori estraggono le opinioni della comunità riguardanti un particolare elemento di interesse. L'opinione collettiva è estratta aggregando le opinioni espresse dai singoli individui che discutono o parlano dell'elemento di interesse attraverso testi pubblicati in blog o social network. Il lavoro di tesi studia una nuova procedura di aggregazione proponendo una nuova variante di una regola di voto ben conosciuta qual è Borda. Tale nuova procedura di aggregazione migliora le performance dell'analisi del sentimento classica.