While in two-player zero-sum games the Nash equilibrium is a well-established prescriptive notion of optimal play, its applicability as a prescriptive tool beyond that setting is limited. Consequently, the study of decentralized learning dynamics tha
t guarantee convergence to correlated solution concepts in multiplayer, general-sum extensive-form (i.e., tree-form) games has become an important topic of active research. The per-iteration complexity of the currently known learning dynamics depends on the specific correlated solution concept considered. For example, in the case of extensive-form correlated equilibrium (EFCE), all known dynamics require, as an intermediate step at each iteration, to compute the stationary distribution of multiple Markov chains, an expensive operation in practice. Oppositely, in the case of normal-form coarse correlated equilibrium (NFCCE), simple no-external-regret learning dynamics that amount to a linear-time traversal of the tree-form decision space of each agent suffice to guarantee convergence. This paper focuses on extensive-form coarse correlated equilibrium (EFCCE), an intermediate solution concept that is a subset of NFCCE and a superset of EFCE. Being a superset of EFCE, any learning dynamics for EFCE automatically guarantees convergence to EFCCE. However, since EFCCE is a simpler solution concept, this begs the question: do learning dynamics for EFCCE that avoid the expensive computation of stationary distributions exist? This paper answers the previous question in the positive. Our learning dynamics only require the orchestration of no-external-regret minimizers, thus showing that EFCCE is more akin to NFCCE than to EFCE from a learning perspective. Our dynamics guarantees that the empirical frequency of play after $T$ iteration is a $O(1/sqrt{T})$-approximate EFCCE with high probability, and an EFCCE almost surely in the limit.
Two-sided matching markets have long existed to pair agents in the absence of regulated exchanges. A common example is school choice, where a matching mechanism uses student and school preferences to assign students to schools. In such settings, form
ing preferences is both difficult and critical. Prior work has suggested various prediction mechanisms that help agents make decisions about their preferences. Although often deployed together, these matching and prediction mechanisms are almost always analyzed separately. The present work shows that at the intersection of the two lies a previously unexplored type of strategic behavior: agents returning to the market (e.g., schools) can attack future predictions by interacting short-term non-optimally with their matches. Here, we first introduce this type of strategic behavior, which we call an `adversarial interaction attack. Next, we construct a formal economic model that captures the feedback loop between prediction mechanisms designed to assist agents and the matching mechanism used to pair them. This economic model allows us to analyze adversarial interaction attacks. Finally, using school choice as an example, we build a simulation to show that, as the trust in and accuracy of predictions increases, schools gain progressively more by initiating an adversarial interaction attack. We also show that this attack increases inequality in the student population.
This volume contains the proceedings of the 12th International Symposium on Games, Automata, Logic and Formal Verification (GandALF 2021). The aim of GandALF 2021 symposium is to bring together researchers from academia and industry which are activel
y working in the fields of Games, Automata, Logics, and Formal Verification. The idea is to cover an ample spectrum of themes, ranging from theory to applications, and stimulate cross-fertilization.
We consider the learning task of prediction of formation of core stable coalition structure in hedonic games based on agents noisy preferences. We have considered two cases: complete information (noisy preferences of all the agents are entirely known
) and partial information (noisy preferences over some coalitions are only known). We introduce a noise model that probabilistically scales the valuations of coalitions. The performance metric is the probability of our prediction conditioned on all or few noisy preferences of the agents be correct. The nature of our results is that this prediction probability is relatively low, including being zero, and rarely it is one. In the complete information two-agent model, in which each agent `retains or `inflates the values of its coalitions, we identify the expressions of the prediction probabilities in terms of the noise probability. We identify the interval of the noise probability such that the prediction probability is at least a user-given threshold. It turned out that, for some noisy games, the noise probability interval does not exist for a threshold as low as 0.1481, thus demonstrating that the prediction probabilities are generally low even in this model. In the partial information setup, we consider $n$ agent games with $l$ support of noise values, and such noisy preferences are available for some coalitions only. We obtain the bounds on the prediction probability of a partition to be $epsilon$-PAC stable in the noise-free game in the cases when the realized noisy game has or hasnt $epsilon$-PAC stable outcome.
Internet of Things (IoT) devices and applications can have significant vulnerabilities, which may be exploited by adversaries to cause considerable harm. An important approach for mitigating this threat is remote attestation, which enables the defend
er to remotely verify the integrity of devices and their software. There are a number of approaches for remote attestation, and each has its unique advantages and disadvantages in terms of detection accuracy and computational cost. Further, an attestation method may be applied in multiple ways, such as various levels of software coverage. Therefore, to minimize both security risks and computational overhead, defenders need to decide strategically which attestation methods to apply and how to apply them, depending on the characteristic of the devices and the potential losses. To answer these questions, we first develop a testbed for remote attestation of IoT devices, which enables us to measure the detection accuracy and performance overhead of various attestation methods. Our testbed integrates two example IoT applications, memory-checksum based attestation, and a variety of software vulnerabilities that allow adversaries to inject arbitrary code into running applications. Second, we model the problem of finding an optimal strategy for applying remote attestation as a Stackelberg security game between a defender and an adversary. We characterize the defenders optimal attestation strategy in a variety of special cases. Finally, building on experimental results from our testbed, we evaluate our model and show that optimal strategic attestation can lead to significantly lower losses than naive baseline strategies.
Off-chain protocols constitute one of the most promising approaches to solve the inherent scalability issue of blockchain technologies. The core idea is to let parties transact on-chain only once to establish a channel between them, leveraging later
on the resulting channel paths to perform arbitrarily many peer-to-peer transactions off-chain. While significant progress has been made in terms of proof techniques for off-chain protocols, existing approaches do not capture the game-theoretic incentives at the core of their design, which led to overlooking significant attack vectors like the Wormhole attack in the past. This work introduces the first game-theoretic model that is expressive enough to reason about the security of off-chain protocols. We advocate the use of Extensive Form Games - EFGs and introduce two instances of EFGs to capture security properties of the closing and the routing of the Lightning Network. Specifically, we model the closing protocol, which relies on punishment mechanisms to disincentivize the uploading on-chain of old channel states, as well as the routing protocol, thereby formally characterizing the Wormhole attack, a vulnerability that undermines the fee-based incentive mechanism underlying the Lightning Network.
In this paper we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-free (EF) allocation is not guaranteed to exist, we consider the notion of
envy-freeness up to any item (EFX). In contrast to the fruitful results regarding the (approximation of) EFX allocations for goods, very little is known for the allocation of chores. Prior to our work, for the allocation of chores, it is known that EFX allocations always exist for two agents, or general number of agents with IDO cost functions. For general instances, no non-trivial approximation result regarding EFX allocation is known. In this paper we make some progress in this direction by showing that for three agents we can always compute a 5-approximation of EFX allocation in polynomial time. For n>=4 agents, our algorithm always computes an allocation that achieves an approximation ratio of O(n^2) regarding EFX.
JUBILEE is a securely computed mechanism for debt relief and forgiveness in a frictionless manner without involving trusted third parties, leading to more harmonious debt settlements by incentivising the parties to truthfully reveal their private inf
ormation. JUBILEE improves over all previous methods: - individually rational, incentive-compatible, truthful/strategy-proof, ex-post efficient, optimal mechanism for debt relief and forgiveness with private information - by the novel introduction of secure computation techniques to debt relief, the blessing of the debtor is hereby granted for the first time: debt settlements with higher expected profits and a higher probability of success than without using secure computation A simple and practical implementation is included for The Secure Spreadsheet. Another implementation is realised using Raziel smart contracts on a blockchain with Pravuil consensus.
To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient-donor pools. We consider a recent credit system where in each round, countries are
given an initial kidney transplant allocation which is adjusted by a credit function yielding a target allocation. The goal is to find a solution in the patient-donor compatibility graph that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We first give a polynomial-time algorithm for computing such matchings. We then perform, for the first time, a computational study for a large number of countries. For the initial allocations we use, besides two easy-to-compute solution concepts, two classical concepts: the Shapley value and nucleolus. These are hard to compute, but by using state-of-the-art software we show that they are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 52% more balanced.
Mobile Edge Caching is a promising technique to enhance the content delivery quality and reduce the backhaul link congestion, by storing popular content at the network edge or mobile devices (e.g. base stations and smartphones) that are proximate to
content requesters. In this work, we study a novel mobile edge caching framework, which enables mobile devices to cache and share popular contents with each other via device-to-device (D2D) links. We are interested in the following incentive problem of mobile device users: whether and which users are willing to cache and share what contents, taking the user mobility and cost/reward into consideration. The problem is challenging in a large-scale network with a large number of users. We introduce the evolutionary game theory, an effective tool for analyzing large-scale dynamic systems, to analyze the mobile users content caching and sharing strategies. Specifically, we first derive the users best caching and sharing strategies, and then analyze how these best strategies change dynamically over time, based on which we further characterize the system equilibrium systematically. Simulation results show that the proposed caching scheme outperforms the existing schemes in terms of the total transmission cost and the cellular load. In particular, in our simulation, the total transmission cost can be reduced by 42.5%-55.2% and the cellular load can be reduced by 21.5%-56.4%.
