8 citations · 40 across the 17 of their papers we have counts for
25 papers
On maximum-likelihood estimation in the all-or-nothing regime
Luca Corinzia, Paolo Penna, Wojciech Szpankowski +1
We study the problem of estimating a rank-1 additive deformation of a Gaussian tensor according to the \emph{maximum-likelihood estimator} (MLE). The analysis is carried out in the…
Statistical and computational thresholds for the planted -densest sub-hypergraph problem
Luca Corinzia, Paolo Penna, Wojciech Szpankowski +1
In this work, we consider the problem of recovery a planted -densest sub-hypergraph on -uniform hypergraphs. This fundamental problem appears in different contexts, e.g., com…
A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
Ioannis Anagnostides, Paolo Penna
In this work, we establish a frequency-domain framework for analyzing gradient-based algorithms in linear minimax optimization problems; specifically, our approach is based on the…
Solving Zero-Sum Games through Alternating Projections
Ioannis Anagnostides, Paolo Penna
In this work, we establish near-linear and strong convergence for a natural first-order iterative algorithm that simulates Von Neumann's Alternating Projections method in zero-sum…
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…
Exact Recovery for a Family of Community-Detection Generative Models
Luca Corinzia, Paolo Penna, Luca Mondada +1
Generative models for networks with communities have been studied extensively for being a fertile ground to establish information-theoretic and computational thresholds. In this pa…
Online scheduling of jobs with favorite machines
Cong Chen, Paolo Penna, Yinfeng Xu
This work introduces a natural variant of the online machine scheduling problem on unrelated machines, which we refer to as the favorite machine model. In this model, each job has…
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…
Optimal Sorting with Persistent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We consider the problem of sorting elements in the case of \emph{persistent} comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two eleme…
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…
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…
Sort well with energy-constrained comparisons
Barbara Geissmann, Paolo Penna
We study very simple sorting algorithms based on a probabilistic comparator model. In our model, errors in comparing two elements are due to (1) the energy or effort put in the com…
Energy-efficient Delivery by Heterogeneous Mobile Agents
Andreas Bärtschi, Jérémie Chalopin, Shantanu Das +4
We consider the problem of delivering messages between specified source-target pairs in a weighted undirected graph, by mobile agents initially located at distinct nodes of…
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…
Local Distributed Algorithms for Selfish Agents
Simon Collet, Pierre Fraigniaud, Paolo Penna
In the classical framework of local distributed network computing, it is generally assumed that the entities executing distributed algorithms are altruistic. However, in various sc…
On computing the total displacement number via weighted Motzkin paths
Andreas Bärtschi, Barbara Geissmann, Daniel Graf +3
Counting the number of permutations of a given total displacement is equivalent to counting weighted Motzkin paths of a given area (Guay-Paquet and Petersen, 2014). The former comb…
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…