8 citations · 40 across the 17 of their papers we have counts for
13 papers · 1 filter
Two-way Greedy: Algorithms for Imperfect Rationality
Diodato Ferraioli, Paolo Penna, Carmine Ventre
The realization that selfish interests need to be accounted for in the design of algorithms has produced many contributions in computer science under the umbrella of algorithmic me…
On the approximation guarantee of obviously strategyproof mechanisms
Diodato Ferraioli, Adrian Meier, Paolo Penna +1
Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms and approximation algorithms. O…
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…
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…
Sequential Solutions in Machine Scheduling Games
Cong Chen, Paul Giessler, Akaki Mamageishvili +2
We consider the classical machine scheduling, where jobs need to be scheduled on machines, and where job scheduled on machine contributes to…
Independent Lazy Better-Response Dynamics on Network Games
Paolo Penna, Laurent Viennot
We study an independent best-response dynamics on network games in which the nodes (players) decide to revise their strategies independently with some probability. We provide sever…
The price of anarchy and stability in general noisy best-response dynamics
Paolo Penna
Logit-response dynamics (Alos-Ferrer and Netzer, Games and Economic Behavior 2010) are a rich and natural class of noisy best-response dynamics. In this work we revise the price of…
Tighter Bounds on the Inefficiency Ratio of Stable Equilibria in Load Balancing Games
Akaki Mamageishvili, Paolo Penna
In this paper we study the inefficiency ratio of stable equilibria in load balancing games introduced by Asadpour and Saberi [3]. We prove tighter lower and upper bounds of 7/6 and…
Bribeproof mechanisms for two-values domains
Matúš Mihalák, Paolo Penna, Peter Widmayer
Schummer (Journal of Economic Theory 2000) introduced the concept of bribeproof mechanism which, in a context where monetary transfer between agents is possible, requires that mani…
Convergence to Equilibrium of Logit Dynamics for Strategic Games
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale +2
We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noi…
Imperfect best-response mechanisms
Diodato Ferraioli, Paolo Penna
Best-response mechanisms (Nisan, Schapira, Valiant, Zohar, 2011) provide a unifying framework for studying various distributed protocols in which the participants are instructed to…
Logit Dynamics with Concurrent Updates for Local-Interaction Games
Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale +2
Logit choice dynamics are a family of randomized best response dynamics based on the logit choice function [McFadden, 1974], used for modeling players with limited rationality and…