Research Repository

Obviously Strategyproof Single-Minded Combinatorial Auctions

De Keijzer, Bart and Kyropoulou, Maria and Ventre, Carmine (2020) Obviously Strategyproof Single-Minded Combinatorial Auctions. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020-07-08 - 2020-07-11, Saarbrücken, Germany [online].

LIPIcs-ICALP-2020-71.pdf - Published Version
Available under License Creative Commons Attribution.

Download (543kB) | Preview


We consider the setting of combinatorial auctions when the agents are single-minded and have no contingent reasoning skills. We are interested in mechanisms that provide the right incentives to these imperfectly rational agents, and therefore focus our attention to obviously strategyproof (OSP) mechanisms. These mechanisms require that at each point during the execution where an agent is queried to communicate information, it should be "obvious" for the agent what strategy to adopt in order to maximise her utility. In this paper we study the potential of OSP mechanisms with respect to the approximability of the optimal social welfare. We consider two cases depending on whether the desired bundles of the agents are known or unknown to the mechanism. For the case of known-bundle single-minded agents we show that OSP can actually be as powerful as (plain) strategyproofness (SP). In particular, we show that we can implement the very same algorithm used for SP to achieve a √m-approximation of the optimal social welfare with an OSP mechanism, m being the total number of items. Restricting our attention to declaration domains with two values, we provide a 2-approximate OSP mechanism, and prove that this approximation bound is tight. We also present a randomised mechanism that is universally OSP and achieves a finite approximation of the optimal social welfare for the case of arbitrary size finite domains. This mechanism also provides a bounded approximation ratio when the valuations lie in a bounded interval (even if the declaration domain is infinitely large). For the case of unknown-bundle single-minded agents, we show how we can achieve an approximation ratio equal to the size of the largest desired set, in an OSP way. We remark this is the first known application of OSP to multi-dimensional settings, i.e., settings where agents have to declare more than one parameter. Our results paint a rather positive picture regarding the power of OSP mechanisms in this context, particularly for known-bundle single-minded agents. All our results are constructive, and even though some known strategyproof algorithms are used, implementing them in an OSP way is a non-trivial task.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: Leibniz International Proceedings in Informatics (LIPIcs)
Uncontrolled Keywords: OSP Mechanisms; Extensive-form Mechanisms; Single-minded Combinatorial Auctions; Greedy algorithms
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: 20 Aug 2020 09:07
Last Modified: 15 Jan 2022 01:33

Actions (login required)

View Item View Item