Optimal Mechanism Design for Agents with DSL Strategies: The Case of Sybil Attacks in Combinatorial Auctions
Yotam Gafni and
Additional contact information
Yotam Gafni: Technion, Israel
Moshe Tennenholtz: Technion, Israel
Papers from arXiv.org
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: Track citations by RSS feed
Published in EPTCS 379, 2023, pp. 245-259
Downloads: (external link)
http://arxiv.org/pdf/2210.15181 Latest version (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
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 ().