Optimal Mechanism Design for Agents with DSL Strategies: The Case of Sybil Attacks in Combinatorial Auctions

Yotam Gafni and Moshe Tennenholtz
Additional contact information
Yotam Gafni: Technion, Israel
Moshe Tennenholtz: Technion, Israel

Papers from arXiv.org

Abstract: In robust decision making under uncertainty, a natural choice is to go with safety (aka security) level strategies. However, in many important cases, most notably auctions, there is a large multitude of safety level strategies, thus making the choice unclear. We consider two refined notions: (i) a term we call DSL (distinguishable safety level), and is based on the notion of ``discrimin'', which uses a pairwise comparison of actions while removing trivial equivalencies. This captures the fact that when comparing two actions an agent should not care about payoffs in situations where they lead to identical payoffs. (ii) The well-known Leximin notion from social choice theory, which we apply for robust decision-making. In particular, the leximin is always DSL but not vice-versa. We study the relations of these notions to other robust notions, and illustrate the results of their use in auctions and other settings. Economic design aims to maximize social welfare when facing self-motivated participants. In online environments, such as the Web, participants' incentives take a novel form originating from the lack of clear agent identity -- the ability to create Sybil attacks, i.e., the ability of each participant to act using multiple identities. It is well-known that Sybil attacks are a major obstacle for welfare-maximization. Our main result proves that when DSL attackers face uncertainty over the auction's bids, the celebrated VCG mechanism is welfare-maximizing even under Sybil attacks. Altogether, our work shows a successful fundamental synergy between robustness under uncertainty, economic design, and agents' strategic manipulations in online multi-agent systems.

Date: 2022-10, Revised 2023-07
New Economics Papers: this item is included in nep-cbe, nep-des, nep-evo, nep-mic and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in EPTCS 379, 2023, pp. 245-259

Downloads: (external link)
http://arxiv.org/pdf/2210.15181 Latest version (application/pdf)

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:arx:papers:2210.15181

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().