Source author record

Francisco J. Marmolejo-Cossío

Francisco J. Marmolejo-Cossío appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Data Structures and Algorithms Cryptography and Security Machine Learning

Catalog footprint

What is connected

4works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Decentralised Update Selection with Semi-Strategic Experts

Motivated by governance models adopted in blockchain applications, we study the problem of selecting appropriate system updates in a decentralised way. Contrary to most existing voting approaches, we use the input of a set of motivated experts of varying levels of expertise. In particular, we develop an approval voting inspired selection mechanism through which the experts approve or disapprove the different updates according to their perception of the quality of each alternative. Given their opinions, and weighted by their expertise level, a single update is then implemented and evaluated, and the experts receive rewards based on their choices. We show that this mechanism always has approximate pure Nash equilibria and that these achieve a constant factor approximation with respect to the quality benchmark of the optimal alternative. Finally, we study the repeated version of the problem, where the weights of the experts are adjusted after each update, according to their performance. Under mild assumptions about the weights, the extension of our mechanism still has approximate pure Nash equilibria in this setting.

preprint2021arXiv

RPPLNS: Pay-per-last-N-shares with a Randomised Twist

"Pay-per-last-$N$-shares" (PPLNS) is one of the most common payout strategies used by mining pools in Proof-of-Work (PoW) cryptocurrencies. As with any payment scheme, it is imperative to study issues of incentive compatibility of miners within the pool. For PPLNS this question has only been partially answered; we know that reasonably-sized miners within a PPLNS pool prefer following the pool protocol over employing specific deviations. In this paper, we present a novel modification to PPLNS where we randomise the protocol in a natural way. We call our protocol "Randomised pay-per-last-$N$-shares" (RPPLNS), and note that the randomised structure of the protocol greatly simplifies the study of its incentive compatibility. We show that RPPLNS maintains the strengths of PPLNS (i.e., fairness, variance reduction, and resistance to pool hopping), while also being robust against a richer class of strategic mining than what has been shown for PPLNS.

preprint2020arXiv

Optimally Deceiving a Learning Leader in Stackelberg Games

Recent results in the ML community have revealed that learning algorithms used to compute the optimal strategy for the leader to commit to in a Stackelberg game, are susceptible to manipulation by the follower. Such a learning algorithm operates by querying the best responses or the payoffs of the follower, who consequently can deceive the algorithm by responding as if his payoffs were much different than what they actually are. For this strategic behavior to be successful, the main challenge faced by the follower is to pinpoint the payoffs that would make the learning algorithm compute a commitment so that best responding to it maximizes the follower's utility, according to his true payoffs. While this problem has been considered before, the related literature only focused on the simplified scenario in which the payoff space is finite, thus leaving the general version of the problem unanswered. In this paper, we fill in this gap, by showing that it is always possible for the follower to compute (near-)optimal payoffs for various scenarios about the learning interaction between leader and follower.

preprint2016arXiv

Logarithmic Query Complexity for Approximate Nash Computation in Large Games

We investigate the problem of equilibrium computation for "large" $n$-player games. Large games have a Lipschitz-type property that no single player's utility is greatly affected by any other individual player's actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players' payoffs to change by at most $\frac{1}{n}$. We study algorithms having query access to the game's payoff function, aiming to find $ε$-Nash equilibria. We seek algorithms that obtain $ε$ as small as possible, in time polynomial in $n$. Our main result is a randomised algorithm that achieves $ε$ approaching $\frac{1}{8}$ for 2-strategy games in a {\em completely uncoupled} setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players' payoffs/actions. $O(\log n)$ rounds/queries are required. We also show how to obtain a slight improvement over $\frac{1}{8}$, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters.