2 citations · 2 across the 13 of their papers we have counts for
9 papers · 1 filter
Avoiding the Worst: The Computational Complexity of Not Worst-Responding
Mete Şeref Ahunbay, Paul W. Goldberg, Edwin Lock +3
Finding, counting, or determining the existence of pure Nash equilibria, where players must play optimally given the others' actions, are known to be computationally intractable pr…
Correlation of Rankings in Matching Markets
Rémi Castera, Patrick Loiseau, Bary S. R. Pradelski
We study the role of correlation in matching markets, where multiple decision-makers simultaneously face selection problems from the same pool of candidates. We propose a model in…
Characterizing the Convergence of Game Dynamics via Potentialness
Martin Bichler, Davide Legacci, Panayotis Mertikopoulos +2
Understanding the convergence landscape of multi-agent learning is a fundamental problem of great practical relevance in many applications of artificial intelligence and machine le…
No-regret learning in harmonic games: Extrapolation in the face of conflicting interests
Davide Legacci, Panayotis Mertikopoulos, Christos H. Papadimitriou +2
The long-run behavior of multi-agent learning - and, in particular, no-regret learning - is relatively well-understood in potential games, where players have aligned interests. By…
Bridging the Gap Between Central and Local Decision-Making: The Efficacy of Collaborative Equilibria in Altruistic Congestion Games
Bryce L Ferguson, Dario Paccagnan, Bary S R Pradelski +1
Congestion games are popular models often used to study the system-level inefficiencies caused by selfish agents, typically measured by the price of anarchy. One may expect that al…
A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights
Davide Legacci, Panayotis Mertikopoulos, Bary Pradelski
In view of the complexity of the dynamics of learning in games, we seek to decompose a game into simpler components where the dynamics' long-run behavior is well understood. A natu…
Collaborative Decision-Making and the k-Strong Price of Anarchy in Common Interest Games
Bryce L. Ferguson, Dario Paccagnan, Bary S. R. Pradelski +1
The control of large-scale, multi-agent systems often entails distributing decision-making across the system components. However, with advances in communication and computation tec…
Collaborative Coalitions in Multi-Agent Systems: Quantifying the Strong Price of Anarchy for Resource Allocation Games
Bryce L. Ferguson, Dario Paccagnan, Bary S. R. Pradelski +1
The emergence of new communication technologies allows us to expand our understanding of distributed control and consider collaborative decision-making paradigms. With collaborativ…
Quick or cheap? Breaking points in dynamic markets
Panayotis Mertikopoulos, Heinrich H. Nax, Bary S. R. Pradelski
We examine two-sided markets where players arrive stochastically over time and are drawn from a continuum of types. The cost of matching a client and provider varies, so a social p…