Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Axiomatic Approach to Routing
126
0
0.0
(
0
)
Added by
EPTCS
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Authors
Omer Lev
Ask ChatGPT about the research
No Arabic abstract
Information delivery in a network of agents is a key issue for large, complex systems that need to do so in a predictable, efficient manner. The delivery of information in such multi-agent systems is typically implemented through routing protocols that determine how information flows through the network. Different routing protocols exist each with its own benefits, but it is generally unclear which properties can be successfully combined within a given algorithm. We approach this problem from the axiomatic point of view, i.e., we try to establish what are the properties we would seek to see in such a system, and examine the different properties which uniquely define common routing algorithms used today. We examine several desirable properties, such as robustness, which ensures adding nodes and edges does not change the routing in a radical, unpredictable ways; and properties that depend on the operating environment, such as an economic model, where nodes choose their paths based on the cost they are charged to pass information to the next node. We proceed to fully characterize minimal spanning tree, shortest path, and weakest link routing algorithms, showing a tight set of axioms for each.
rate research
Read More
Proof-of-work blockchains reward each miner for one completed block by an amount that is, in expectation, proportional to the number of hashes the miner contributed to the mining of the block. Is this proportional allocation rule optimal? And in what sense? And what other rules are possible? In particular, what are the desirable properties that any good allocation rule should satisfy? To answer these questions, we embark on an axiomatic theory of incentives in proof-of-work blockchains at the time scale of a single block. We consider desirable properties of allocation rules including: symmetry; budget balance (weak or strong); sybil-proofness; and various grades of collusion-proofness. We show that Bitcoins proportional allocation rule is the unique allocation rule satisfying a certain system of properties, but this does not hold for slightly weaker sets of properties, or when the miners are not risk-neutral. We also point out that a rich class of allocation rules can be approximately implemented in a proof-of-work blockchain.
In this paper, a novel framework for normative modeling of the spectrum sensing and sharing problem in cognitive radios (CRs) as a transferable utility (TU) cooperative game is proposed. Secondary users (SUs) jointly sense the spectrum and cooperatively detect the primary user (PU) activity for identifying and accessing unoccupied spectrum bands. The games are designed to be balanced and super-additive so that resource allocation is possible and provides SUs with an incentive to cooperate and form the grand coalition. The characteristic function of the game is derived based on the worths of SUs, calculated according to the amount of work done for the coalition in terms of reduction in uncertainty about PU activity. According to her worth in the coalition, each SU gets a pay-off that is computed using various one-point solutions such as Shapley value, tau-value and Nucleolus. Depending upon their data rate requirements for transmission, SUs use the earned pay-off to bid for idle channels through a socially optimal Vickrey-Clarke-Groves (VCG) auction mechanism. Simulation results show that, in comparison with other resource allocation models, the proposed cooperative game-theoretic model provides the best balance between fairness, cooperation and performance in terms of data rates achieved by each SU.
Complex black-box machine learning models are regularly used in critical decision-making domains. This has given rise to several calls for algorithmic explainability. Many explanation algorithms proposed in literature assign importance to each feature individually. However, such explanations fail to capture the joint effects of sets of features. Indeed, few works so far formally analyze high-dimensional model explanations. In this paper, we propose a novel high dimension model explanation method that captures the joint effect of feature subsets. We propose a new axiomatization for a generalization of the Banzhaf index; our method can also be thought of as an approximation of a black-box model by a higher-order polynomial. In other words, this work justifies the use of the generalized Banzhaf index as a model explanation by showing that it uniquely satisfies a set of natural desiderata and that it is the optimal local approximation of a black-box model. Our empirical evaluation of our measure highlights how it manages to capture desirable behavior, whereas other measures that do not satisfy our axioms behave in an unpredictable manner.
Perpetual voting was recently introduced as a framework for long-term collective decision making. In this framework, we consider a sequence of subsequent approval-based elections and try to achieve a fair overall outcome. To achieve fairness over time, perpetual voting rules take the history of previous decisions into account and identify voters that were dissatisfied with previous decisions. In this paper, we look at perpetual voting rules from an axiomatic perspective and study two main questions. First, we ask how simple such rules can be while still meeting basic desiderata. For two simple but natural classes, we fully characterize the axiomatic possibilities. Second, we ask how proportionality can be formalized in perpetual voting. We study proportionality on simple profiles that are equivalent to the apportionment setting and show that lower and upper quota axioms can be used to distinguish (and sometimes characterize) perpetual voting rules. Furthermore, we show a surprising connection between a perpetual rule called Perpetual Consensus and Freges apportionment method.
Mass surveillance of the population by state agencies and corporate parties is now a well-known fact. Journalists and whistle-blowers still lack means to circumvent global spying for the sake of their investigations. With Spores, we propose a way for journalists and their sources to plan a posteriori file exchanges when they physically meet. We leverage on the multiplication of personal devices per capita to provide a lightweight, robust and fully anonymous decentralised file transfer protocol between users. Spores hinges on our novel concept of e-squads: ones personal devices, rendered intelligent by gossip communication protocols, can provide private and dependable services to their user. Peoples e-squads are federated into a novel onion routing network, able to withstand the inherent unreliability of personal appliances while providing reliable routing. Spores performances are competitive, and its privacy properties of the communication outperform state of the art onion routing strategies.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
