8 citations · 40 across the 17 of their papers we have counts for
4 papers · 1 filter
No truthful mechanism can be better than approximate for two natural problems
Stefano Leucci, Akaki Mamageishvili, Paolo Penna
This work gives the first natural non-utilitarian problems for which the trivial approximation via VCG mechanisms is the best possible. That is, no truthful mechanism can be be…
Sorting with Recurrent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sort…
Selfish Jobs with Favorite Machines: Price of Anarchy vs Strong Price of Anarchy
Cong Chen, Paolo Penna, Yinfeng Xu
We consider the well-studied game-theoretic version of machine scheduling in which jobs correspond to self-interested users and machines correspond to resources. Here each user cho…
Truthful Mechanisms for Delivery with Mobile Agents
Andreas Bärtschi, Daniel Graf, Paolo Penna
We study the game-theoretic task of selecting mobile agents to deliver multiple items on a network. An instance is given by messages (physical objects) which have to be transpo…