On the Hardness of Lying under Egalitarian Social Welfare

Jonathan Carrero, Ismael Rodríguez and Fernando Rubio
Additional contact information
Jonathan Carrero: Departamento Sistemas Informáticos y Computación, Facultad Informática, Universidad Complutense, 28040 Madrid, Spain
Ismael Rodríguez: Departamento Sistemas Informáticos y Computación, Facultad Informática, Universidad Complutense, 28040 Madrid, Spain
Fernando Rubio: Departamento Sistemas Informáticos y Computación, Facultad Informática, Universidad Complutense, 28040 Madrid, Spain

Mathematics, 2021, vol. 9, issue 14, 1-15

Abstract: When it comes to distributing resources among different agents, there are different objectives that can be maximized. In the case of egalitarian social welfare, the goal is to maximize the utility of the least satisfied agent. Unfortunately, this goal can lead to strategic behaviors on the part of the agents: if they lie about their utility functions, then the dealer might grant them more goods than they would be entitled to. In this work, we study the computational complexity of obtaining the optimal lie in this context. We show that although it is extremely easy to obtain the optimal lie when we do not impose any restrictions on the lies used, the problem becomes ? 2 P -complete by imposing simple limits on the usable lies. Thus, we prove that we can easily make it hard to lie in the context of egalitarian social welfare.

Keywords: social welfare; complexity; multi-agent systems (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/14/1599/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/14/1599/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:14:p:1599-:d:589999

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().