Research Repository

Truthfulness on a Budget: Trading Money for Approximation through Monitoring

Serafino, P and Ventre, Carmine and Vidali, A (2020) Truthfulness on a Budget: Trading Money for Approximation through Monitoring. In: 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), 2019-05-13 - ?, Montreal. (In Press)

main.pdf - Accepted Version

Download (540kB) | Preview


Albeit a pervasive desideratum when computing a novel paradigm wherein agents’ declarations can be partially checked against their actual costs. in the presence of selfish agents, truthfulness typically imposes severe limitations to what can be implemented. The price of these limitations is typically paid either economically , in terms of the financial resources needed to enforce truthfulness, or algorithmically , in terms of restricting the set of implementable objective functions, which often leads to renouncing optimality and resorting to approximate allocations. In this paper, with regards to utilitarian problems, we ask two fundamental questions: (i) what is the a minimum sufficient budget needed by optimal truthful mechanisms, and (ii) whether it is possible to sacrifice optimality in order to achieve truthfulness with a lower budget. To answer these questions, we connect two streams of work on mechanism design and look at monitoring – a paradigm wherein agents’ actual costs are bound to their declarations. In this setting, we prove that the social cost is always a sufficient budget, even for collusion-resistant mechanisms, and, under mild conditions, also a necessary budget for a large class of utilitarian problems that encompass set system problems. Furthermore, for facility location, a well-studied problem outside of this class, we draw a novel picture about the relationship between approximation and frugality.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: Autonomous Agents and Multi-Agent Systems
Uncontrolled Keywords: Budget-feasible mechanisms; Auctions; Frugality; Set systems; Facility location; Obnoxious facility location
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 23 Jan 2019 14:38
Last Modified: 06 Jan 2022 13:57

Actions (login required)

View Item View Item