Multiagent Systems (cs.MA)

  • PDF
    Agent-based IoT applications have recently been proposed in several domains, such as health care, smart cities and agriculture. Deploying these applications in specific settings has been very challenging for many reasons including the complex static and dynamic variability of the physical devices such as sensors and actuators, the software application behavior and the environment in which the application is embedded. In this paper, we propose a self-configurable IoT agent approach based on feedback-evaluative machine-learning. The approach involves: i) a variability model of IoT agents; ii) generation of sets of customized agents; iii) feedback evaluative machine learning; iv) modeling and composition of a group of IoT agents; and v) a feature-selection method based on manual and automatic feedback.
  • PDF
    Multi-agent Systems (MASs) have found a variety of industrial applications from economics to robotics, owing to their high adaptability, scalability and applicability. However, with the increasing complexity of MASs, multi-agent control has become a challenging problem to solve. Among different approaches to deal with this complex problem, game theoretic learning recently has received researchers' attention as a possible solution. In such learning scheme, by playing a game, each agent eventually discovers a solution on its own. The main focus of this paper is on enhancement of two types of game-theoretic learning algorithms: log linear learning and reinforcement learning. Each algorithm proposed in this paper, relaxes and imposes different assumptions to fit a class of MAS problems. Numerical experiments are also conducted to verify each algorithm's robustness and performance.
  • PDF
    A work zone bottleneck in a roadway network can cause traffic delays, emissions and safety issues. Accurate measurement and prediction of work zone travel time can help travelers make better routing decisions and therefore mitigate its impact. Historically, data used for travel time analyses comes from fixed loop detectors, which are expensive to install and maintain. With connected vehicle technology, such as Vehicle-to-Infrastructure, portable roadside unit (RSU) can be located in and around a work zone segment to communicate with the vehicles and collect traffic data. A PARAMICS simulation model for a prototypical freeway work zone in a connected vehicle environment was built to test this idea using traffic demand data from NY State Route 104. For the simulation, twelve RSUs were placed along the work zone segment and sixteen variables were extracted from the simulation results to explore travel time estimation and prediction. For the travel time analysis, four types of models were constructed, including linear regression, multivariate adaptive regression splines (MARS), stepwise regression and elastic net. The results show that the modeling approaches under consideration have similar performance in terms of the Root of Mean Square Error (RMSE), which provides an opportunity for model selection based on additional factors including the number and locations of the RSUs according to the significant variables identified in the various models. Among the four approaches, the stepwise regression model only needs variables from two RSUs: one placed sufficiently upstream of the work zone and one at the end of the work zone.
  • PDF
    In this paper, we investigate the problem of anti-coordination under rationality constraints in ad-hoc resource allocation settings. Inspired by human behavior, we propose a framework (CA3NONY) that enables fast convergence to efficient and fair allocations based on a simple convention of courtesy. We prove that following such convention induces a strategy which constitutes an approximate subgame-perfect equilibrium of the repeated resource allocation game with discounting. Simulation results highlight the effectiveness of CA3NONY as compared to state-of-the-art bandit algorithms, since it achieves more than two orders of magnitude faster convergence, higher efficiency, fairness, and average payoff for the agents.
  • PDF
    Most of the knowledge Representation formalisms developed for representing prescriptive norms can be categorized as either suitable for representing either low level or high level norms.We argue that low level norm representations do not advance the cause of autonomy in agents in the sense that it is not the agent itself that determines the normative position it should be at a particular time, on the account of a more general rule. In other words an agent on some external system for a nitty gritty prescriptions of its obligations and prohibitions. On the other hand, high level norms which have an explicit description of a norm's precondition and have some form of implication, do not as they exist in the literature do not support generalized inferences about violation like low level norm representations do. This paper presents a logical formalism for the representation of high level norms in open societies that enable violation inferences that detail the situation in which the norm violation took place and the identity of the norm violation. Norms are formalized as logic programs whose heads specify what an agent is obliged or permitted to do when a situation arises and within what time constraint of the situation.Each norm is also assigned an identity using some reification scheme. The body of each logic program describes the nature of the situation in which the agent is expected to act or desist from acting. This kind of violation is novel in the literature.
  • PDF
    Streets are large, diverse, and used for several (and possibly conflicting) transport modalities as well as social and cultural activities. Proper planning is essential and requires data. Manually fabricating data that represent streets (street reconstruction) is error-prone and time consuming. Automatising street reconstruction is a challenge because of the diversity, size, and scale of the details (few centimetres for cornerstone) required. The state-of-the-art focuses on roads (no context, no urban features) and is strongly determined by each application (simulation, visualisation, planning). We propose a unified framework that works on real Geographic Information System (GIS) data and uses a strong, yet simple modelling hypothesis when possible to robustly model streets at the city level or street level. Our method produces a coherent street-network model containing topological traffic information, road surface and street objects. We demonstrate the robustness and genericity of our method by reconstructing the entire city of Paris streets and exploring other similar reconstruction (airport driveway).
  • PDF
    The cornerstone underpinning deep learning is the guarantee that gradient descent on an objective converges to local minima. Unfortunately, this guarantee fails in settings, such as generative adversarial nets, where there are multiple interacting losses. The behavior of gradient-based methods in games is not well understood -- and is becoming increasingly important as adversarial and multi-objective architectures proliferate. In this paper, we develop new techniques to understand and control the dynamics in general games. The key result is to decompose the second-order dynamics into two components. The first is related to potential games, which reduce to gradient descent on an implicit function; the second relates to Hamiltonian games, a new class of games that obey a conservation law, akin to conservation laws in classical mechanical systems. The decomposition motivates Symplectic Gradient Adjustment (SGA), a new algorithm for finding stable fixed points in general games. Basic experiments show SGA is competitive with recently proposed algorithms for finding local Nash equilibria in GANs -- whilst at the same time being applicable to -- and having guarantees in -- much more general games.
  • PDF
    Existing multi-agent reinforcement learning methods are limited typically to a small number of agents. When the agent number increases largely, the learning becomes intractable due to the curse of the dimensionality and the exponential growth of user interactions. In this paper, we present Mean Field Reinforcement Learning where the interactions within the population of agents are approximated by those between a single agent and the average effect from the overall population or neighboring agents; the interplay between the two entities is mutually reinforced: the learning of the individual agent's optimal policy depends on the dynamics of the population, while the dynamics of the population change according to the collective patterns of the individual policies. We develop practical mean field Q-learning and mean field Actor-Critic algorithms and analyze the convergence of the solution. Experiments on resource allocation, Ising model estimation, and battle game tasks verify the learning effectiveness of our mean field approaches in handling many-agent interactions in population.
  • PDF
    Given a large number of homogeneous players that are distributed across three possible states, we consider the problem in which these players have to control their transition rates, while minimizing a cost. The optimal transition rates are based on the players' knowledge of their current state and of the distribution of all the other players, and this introduces mean-field terms in the running and the terminal cost. The first contribution involves a mean-field game model that brings together macroscopic and microscopic dynamics. We obtain the mean-field equilibrium associated with this model, by solving the corresponding initial-terminal value problem. We perform an asymptotic analysis to obtain a stationary equilibrium for the system. The second contribution involves the study of the microscopic dynamics of the system for a finite number of players that interact in a structured environment modeled by an interaction topology. The third contribution is the specialization of the model to describe honeybee swarms, virus propagation, and cascading failures in interconnected smart-grids. A numerical analysis is conducted which involves two types of cyber-attacks. We simulate in which ways failures propagate across the interconnected smart grids and the impact on the grids frequencies. We reframe our analysis within the context of Lyapunov's linearisation method and stability theory of nonlinear systems and Kuramoto coupled oscillators model.
  • PDF
    Multiple studies have illustrated the potential for dramatic societal, environmental and economic benefits from significant penetration of autonomous driving. However, all the current approaches to autonomous driving require the automotive manufacturers to shoulder the primary responsibility and liability associated with replacing human perception and decision making with automation, potentially slowing the penetration of autonomous vehicles, and consequently slowing the realization of the societal benefits of autonomous vehicles. We propose here a new approach to autonomous driving that will re-balance the responsibility and liabilities associated with autonomous driving between traditional automotive manufacturers, infrastructure players, and third-party players. Our proposed distributed intelligence architecture leverages the significant advancements in connectivity and edge computing in the recent decades to partition the driving functions between the vehicle, edge computers on the road side, and specialized third-party computers that reside in the vehicle. Infrastructure becomes a critical enabler for autonomy. With this Infrastructure Enabled Autonomy (IEA) concept, the traditional automotive manufacturers will only need to shoulder responsibility and liability comparable to what they already do today, and the infrastructure and third-party players will share the added responsibility and liabilities associated with autonomous functionalities. We propose a Bayesian Network Model based framework for assessing the risk benefits of such a distributed intelligence architecture. An additional benefit of the proposed architecture is that it enables "autonomy as a service" while still allowing for private ownership of automobiles.
  • PDF
    Eyal and Sirer's selfish mining strategy has demonstrated that Bitcoin system is not secure even if 50% of total mining power is held by altruistic miners. Since then, researchers have been investigating either to improve the efficiency of selfish mining, or how to defend against it, typically in a single selfish miner setting. Yet there is no research on a selfish mining strategies concurrently used by multiple miners in the system. The effectiveness of such selfish mining strategies and their required mining power under such multiple selfish miners setting remains unknown. In this paper, a preliminary investigation and our findings of selfish mining strategy used by multiple miners are reported. In addition, the conventional model of Bitcoin system is slightly redesigned to tackle its shortcoming: namely, a concurrency of individual mining processes. Although a theoretical analysis of selfish mining strategy under this setting is yet to be established, the current findings based on simulations is promising and of great interest. In particular, our work shows that a lower bound of power threshold required for selfish mining strategy decreases in proportion to a number of selfish miners. Moreover, there exist Nash equilibria where all selfish miners in the system do not change to an honest mining strategy and simultaneously earn their unfair amount of mining reward given that they equally possess sufficiently large mining power. Lastly, our new model yields a power threshold for mounting selfish mining strategy slightly greater than one from the conventional model.
  • PDF
    Designing mechanisms that leverage cooperation between agents has been a long-lasting goal in Multiagent Systems. The task is especially challenging when agents are selfish, lack common goals and face social dilemmas, i.e., situations in which individual interest conflicts with social welfare. Past works explored mechanisms that explain cooperation in biological and social systems, providing important clues for the aim of designing cooperative artificial societies. In particular, several works show that cooperation is able to emerge when specific network structures underlie agents' interactions. Notwithstanding, social dilemmas in which defection is highly tempting still pose challenges concerning the effective sustainability of cooperation. Here we propose a new redistribution mechanism that can be applied in structured populations of agents. Importantly, we show that, when implemented locally (i.e., agents share a fraction of their wealth surplus with their nearest neighbors), redistribution excels in promoting cooperation under regimes where, before, only defection prevailed.
  • PDF
    We study an optimal control problem for a multi-agent system modeled by an undirected formation graph with nodes describing the kinematics of each agent, given by a left invariant control system on a Lie group. The agents should avoid collision between them in the workspace. This is accomplished by introducing appropriate potential functions into the cost functional for the optimal control problem, corresponding to fictitious forces, induced by the formation constraint among agents, that break the symmetry of the individual agents and the cost functions, and render the optimal control problem partially invariant by a Lie group of symmetries. Reduced necessary conditions for the existence of normal extrema are obtained using techniques from variational calculus on manifolds. The Hamiltonian formalism associated with the optimal control problem is explored through an application of Pontryagin's maximum principle for left-invariant systems where necessary conditions for the existence of normal extrema are obtained as integral curves of a Hamiltonian vector field associated to a reduced Hamiltonian function. By means of the Legendre transformation we show the equivalence of both frameworks. The discrete-time version of optimal control for multi-agent systems is studied in order to develop a variational integrator based on the discretization of an augmented cost functional in analogy with the Hamiltonian picture of the problem through the Hamilton-Pontryagin variational principle. Such integrator defines a well defined (local) flow to integrate the necessary conditions for local extrema in the optimal control problem. As an application we study an optimal control problem for multiple unicycles.
  • PDF
    Nonlinear Markov chains are probabilistic models commonly used in physics, biology, and the social sciences. In "Markov influence systems" (MIS), the transition probabilities of the chains change as a function of the current state distribution. This work introduces a renormalization framework for analyzing the dynamics of MIS. It comes in two independent parts: first, we generalize the standard classification of Markov chain states to the dynamic case by showing how to parse graph sequences. We then use this framework to carry out the bifurcation analysis of a few important MIS families. We show that, in general, these systems can be chaotic but that irreducible MIS are almost always asymptotically periodic. We also give an example of "hyper-torpid" mixing, where a stationary distribution is reached in super-exponential time, a timescale that cannot be achieved by any Markov chain.
  • PDF
    We derive an (essentially) optimal bound of $O(1/\rho s)^{n-1}$ on the $s$-energy of an $n$-agent averaging system, where $\rho$ is a lower bound on the nonzero weights. The $s$-energy is a generating function with applications to opinion dynamics, synchronization, consensus, bird flocking, inhomogeneous products of stochastic matrices, etc. We discuss a few of the improvements one can derive from the new bounds.
  • PDF
    Understanding the mechanics behind the coordinated movement of mobile animal groups provides key insights into their biology and ecology while also yielding algorithms for bio-inspired technologies and autonomous systems. It is becoming increasingly clear that many mobile animal groups are composed of heterogeneous individuals with differential levels and types of influence over group behaviors--often considered as "leaders". The ability to infer this differential influence, or leadership, is critical to understanding group functioning in these collective animal systems. Due to the broad interpretation of leadership, many different measures and mathematical tools are used to describe and infer "leadership", e.g., position, causality, influence, information flow. But a key question remains: which, if any, of these concepts actually describes leadership? We argue that instead of asserting a single definition or notion of leadership, the complex interaction rules and dynamics typical of a group implies that leadership itself is not merely a scalar quantity, but rather, a complex combination of many different components. In this manuscript we develop an anatomy of leadership, identify several principle components and provide a general mathematical framework for discussing leadership. With real and synthetic examples we then illustrate how to use this framework. We believe this multifaceted approach to leadership definition will allow for a broader understanding the role of leadership and its inference from data in mobile animal groups and beyond.
  • PDF
    In this paper, we introduce a game-theoretical formulation for a specific form of collaborative industrial relations called "Industrial Symbiotic Relation (ISR) games" and provide a formal framework to model, verify, and support collaboration decisions in this new class of two-person operational games. ISR games are formalized as cooperative cost-allocation games with the aim to allocate the total ISR-related operational cost to involved industrial firms in a fair and stable manner by taking into account their contribution to the total traditional ISR-related cost. We tailor two types of allocation mechanisms using which firms can implement cost allocations that result in a collaboration that satisfies the fairness and stability properties. Moreover, while industries receive a particular ISR proposal, our introduced methodology is applicable as a managerial decision support to systematically verify the quality of the ISR in question. This is achievable by analyzing if the implemented allocation mechanism is a stable/fair allocation.
  • PDF
    The 1st workshop on Architectures, Languages and Paradigms for IoT (ALP4IoT 2017), was held in Turin on September 19th, 2017. ALP4IoT was a satellite event of the 13th International Conference on integrated Formal Methods (iFM 2017). The workshop aimed at critically reviewing the state-of-the-art and the state-of-the-practice of formal techniques and software methods for the IoT, presenting open problems and challenges and triggering a discussion among the participants with different views and backgrounds. The Internet of Things is ushering a dramatic increase in number and variety of interconnected and smart objects. Communication capabilities and computational power are growingly embedded in everyday devices, including personal smart devices, public displays, cars, drones, and electronic tags. This state of the things opens an unprecedented range of research opportunities: the inherent distribution, mobility, situatedness, and heterogeneity of such devices call for proper scientific understanding of the foundations of such systems as well as for novel software methods. The workshop solicited original contributions on architectures, languages, paradigms, and techniques with potential practical and theoretical impact on software systems targeting the IoT, welcoming inter-disciplinary approaches.
  • PDF
    Multiagent systems where the agents interact among themselves and with an stochastic environment can be formalized as stochastic games. We study a subclass, named Markov potential games (MPGs), that appear often in economic and engineering applications when the agents share some common resource. We consider MPGs with continuous state-action variables, coupled constraints and nonconvex rewards. Previous analysis are only valid for very simple cases (convex rewards, invertible dynamics, and no coupled constraints); or considered deterministic dynamics and provided open-loop (OL) analysis, studying strategies that consist in predefined action sequences. We present a closed-loop (CL) analysis for MPGs and consider parametric policies that depend on the current state and where agents adapt to stochastic transitions. We provide verifiable, sufficient and necessary conditions for a stochastic game to be an MPG, even for complex parametric functions (e.g., deep neural networks); and show that a CL Nash equilibrium (NE) can be found (or at least approximated) by solving a related optimal control problem (OCP). This is useful since solving an OCP---a single-objective problem---is usually much simpler than solving the original set of coupled OCPs that form the game---a multiobjective control problem. This is a considerable improvement over previously standard approach. We illustrate the theoretical contributions with an example by applying our approach to a noncooperative communications engineering game. We then solve the game with a deep reinforcement learning algorithm that learns policies that closely approximates an exact variational NE of the game.
  • PDF
    Agent-based modeling has been criticized for its apparent lack of establishing causality of social phenomena. However, we demonstrate that when coupled with evolutionary computation techniques, agent-based models can be used to evolve plausible agent behaviors that are able to recreate patterns observed in real-world data, from which valuable insights into candidate explanations of the macro-phenomenon can be drawn. Existing methodologies have suggested the manual assembly and comparison or automated selection of pre-built models on their ability to fit patterns in data. We discuss the cons of existing manual approaches and how evolutionary model discovery, an evolutionary approach to explore the space of agent behaviors for plausible rule-sets, can overcome these issues. We couple evolutionary model discovery with concepts from the Agent\_Zero framework, ensuring social connectivity, emotional theory components and rational mechanisms. In this study, we revisit the farm-seeking strategy of the Artificial Anasazi model, originally designed to simply select the closest potential farm plot as their next farming location. We use evolutionary model discovery to explore plausible farm seeking strategies, extending our previous study by testing four social connectivity strategies, four emotional theory components and five rational mechanisms for a more complex human-like approach towards farm plot selection. Our results confirm that, plot quality, dryness and community presence were more important in the farm selection process of the Anasazi than distance, and discover farm selection strategies that generate simulations that produce a closer fit to the archaeological data.
  • PDF
    In this work, we investigate the interesting impact of mobility on the problem of efficient wireless power transfer in ad hoc networks. We consider a set of mobile agents (consuming energy to perform certain sensing and communication tasks), and a single static charger (with finite energy) which can recharge the agents when they get in its range. In particular, we focus on the problem of efficiently computing the appropriate range of the charger with the goal of prolonging the network lifetime. We first demonstrate (under the realistic assumption of fixed energy supplies) the limitations of any fixed charging range and, therefore, the need for and power of a dynamic selection of the charging range, by adapting to the behavior of the mobile agents which is revealed in an online manner. We investigate the complexity of optimizing the selection of such an adaptive charging range, by showing that a simplified offline optimization problem (closely related to the online one) is NP-hard. To effectively address the involved performance trade-offs, we finally present a variety of adaptive heuristics, assuming different levels of agent information regarding their mobility and energy.
  • PDF
    In this paper we present a novel crowd simulation method by modeling the generation and contagion of panic emotion under multi-hazard circumstances. Specifically, we first classify hazards into different types (transient and persistent, concurrent and non-concurrent, static and dynamic ) based on their inherent characteristics. Then, we introduce the concept of perilous field for each hazard and further transform the critical level of the field to its invoked-panic emotion. After that, we propose an emotional contagion model to simulate the evolving process of panic emotion caused by multiple hazards in these situations. Finally, we introduce an Emotional Reciprocal Velocity Obstacles (ERVO) model to simulate the crowd behaviors by augmenting the traditional RVO model with emotional contagion, which combines the emotional impact and local avoidance together for the first time. Our experimental results show that this method can soundly generate realistic group behaviors as well as panic emotion dynamics in a crowd in multi-hazard environments.
  • PDF
    Manipulation models for electoral systems are a core research theme in social choice theory; they include bribery (unweighted, weighted, swap, shift, ...), control (by adding or deleting voters or candidates), lobbying in referenda and others. We develop a unifying framework for manipulation models with few types of people, one of the most commonly studied scenarios. A critical insight of our framework is to separate the descriptive complexity of the voting rule R from the number of types of people. This allows us to finally settle the computational complexity of R-Swap Bribery, one of the most fundamental manipulation problems. In particular, we prove that R-Swap Bribery is fixed-parameter tractable when R is Dodgson's rule and Young's rule, when parameterized by the number of candidates. This way, we resolve a long-standing open question from 2007 which was explicitly asked by Faliszewski et al. [JAIR 40, 2011]. Our algorithms reveal that the true hardness of bribery problems often stems from the complexity of the voting rules. On one hand, we give a fixed-parameter algorithm parameterized by number of types of people for complex voting rules. Thus, we reveal that R-Swap Bribery with Dodgson's rule is much harder than with Condorcet's rule, which can be expressed by a conjunction of linear inequalities, while Dodson's rule requires quantifier alternation and a bounded number of disjunctions of linear systems. On the other hand, we give an algorithm for quantifier-free voting rules which is parameterized only by the number of conjunctions of the voting rule and runs in time polynomial in the number of types of people. This way, our framework explains why Shift Bribery is polynomial-time solvable for the plurality voting rule, making explicit that the rule is simple in that it can be expressed with a single linear inequality, and that the number of voter types is polynomial.
  • PDF
    Permission-less blockchains can realise trustless trust, albeit at the cost of limiting the complexity of computation tasks. To explain the implications for scalability, we have implemented a trust model for smart contracts, described as agents in an open multi-agent system. Agent intentions are not necessarily known and autonomous agents have to be able to make decisions under risk. The ramifications of these general conditions for scalability are analysed for Ethereum and then generalised to other current and future platforms.
  • PDF
    The spread of unwanted or malicious content through social media has become a major challenge. Traditional examples of this include social network spam, but an important new concern is the propagation of fake news through social media. A common approach for mitigating this problem is by using standard statistical classification to distinguish malicious (e.g., fake news) instances from benign (e.g., actual news stories). However, such an approach ignores the fact that malicious instances propagate through the network, which is consequential both in quantifying consequences (e.g., fake news diffusing through the network), and capturing detection redundancy (bad content can be detected at different nodes). An additional concern is evasion attacks, whereby the generators of malicious instances modify the nature of these to escape detection. We model this problem as a Stackelberg game between the defender who is choosing parameters of the detection model, and an attacker, who is choosing both the node at which to initiate malicious spread, and the nature of malicious entities. We develop a novel bi-level programming approach for this problem, as well as a novel solution approach based on implicit function gradients, and experimentally demonstrate the advantage of our approach over alternatives which ignore network structure.
  • PDF
    This paper builds on an existing notion of group responsibility and proposes two ways to define the degree of group responsibility: structural and functional degrees of responsibility. These notions measure the potential responsibilities of (agent) groups for avoiding a state of affairs. According to these notions, a degree of responsibility for a state of affairs can be assigned to a group of agents if, and to the extent that, the group has the potential to preclude the state of affairs.
  • PDF
    Unlike most existing studies on off-ramp traffic signal control, this paper focuses on the optimization problem of the signalized intersection connected to freeway on-ramps. Conflicts are often observed between the traffic heading to an on-ramp and the traffic continuing straight which leads to issues such as intersection overflow, increased delay, and concerns about safety. For studying this problem, a real-world signalized intersection in Buffalo, New York was chosen, which has two through lanes and one short shared (through and right-turn) lane. At the downstream of the intersection are two following on-ramps, one to the highway I-290 West and the other to I-290 East. During peak hours, the shared lane often observes a long queue, which furthermore blocks the through traffic on the parallel lane. To solve this problem, a VISSIM agent-based simulation model was built and calibrated based on field observations. Three potential optimization solutions were proposed and tested with the help of VISSIM: (1) increasing the length of the short shared through and right-turn lane; (2) making the short shared through and right-turn lane right-turn only, and (3) adding a new diverge lane for the right-turn vehicles. According to the simulation results, solution (3) performs the best, resulting in the least vehicle delay time.
  • PDF
    For enhancing the privacy protections of databases, where the increasing amount of detailed personal data is stored and processed, multiple mechanisms have been developed, such as audit logging and alert triggers, which notify administrators about suspicious activities; however, the two main limitations in common are: 1) the volume of such alerts is often substantially greater than the capabilities of resource-constrained organizations, and 2) strategic attackers may disguise their actions or carefully choosing which records they touch, making incompetent the statistical detection models. For solving them, we introduce a novel approach to database auditing that explicitly accounts for adversarial behavior by 1) prioritizing the order in which types of alerts are investigated and 2) providing an upper bound on how much resource to allocate for each type. We model the interaction between a database auditor and potential attackers as a Stackelberg game in which the auditor chooses an auditing policy and attackers choose which records to target. A corresponding approach combining linear programming, column generation, and heuristic search is proposed to derive an auditing policy. For testing the policy-searching performance, a publicly available credit card application dataset are adopted, on which it shows that our methods produce high-quality mixed strategies as database audit policies, and our general approach significantly outperforms non-game-theoretic baselines.
  • PDF
    Within the model of social dynamics determined by collective decisions in a stochastic environment (ViSE model), we consider the case of a homogeneous society consisting of classically rational economic agents (or homines economici, or egoists). We present expressions for the optimal majority threshold and the maximum expected capital increment as functions of the parameters of the environment. An estimate of the rate of change of the optimal threshold at zero is given, which is an absolute constant: $(\sqrt{2/\pi}-\sqrt{\pi/2})/2$.
  • PDF
    The Robotic Mobile Fulfillment Systems (RMFS) is a new type of robotized, parts-to-picker material handling system, designed especially for e-commerce warehouses. Robots bring movable shelves, called pods, to workstations where inventory is put on or removed from the pods. This paper simulates both the pick and replenishment process and studies the order assignment, pod selection and pod storage assignment problems by evaluating multiple decision rules per problem. The discrete event simulation uses realistic robot movements and keeps track of every unit of inventory on every pod. We analyze seven performance measures, e.g. throughput capacity and order due time, and find that the unit throughput is strongly correlated with the other performance measures. We vary the number of robots, the number of pick stations, the number of SKUs (stock keeping units), the order size and whether returns need processing or not. The decision rules for pick order assignment have a strong impact on the unit throughput rate. This is not the case for replenishment order assignment, pod selection and pod storage. Furthermore, for warehouses with a large number of SKUs, more robots are needed for a high unit throughput rate, even if the number of pods and the dimensions of the storage area remain the same. Lastly, processing return orders only affects the unit throughput rate for warehouse with a large number of SKUs and large pick orders.
  • PDF
    Mechanism design is concerned with settings where a policy maker (or social planner) faces the problem of aggregating the announced preferences of multiple agents into a collective (or social), system-wide decision. One of the most important ways for aggregation preference used in a multi agent system is using election. In an election, the aim is to select the candidate who reects the common will of the whole society. Despite the importance of this subject, in the real world situations, sometimes under special circumstances, the result of the election is completely an antithesis of the purpose of those who execute it or the election leads to the dissatisfaction of a large amount of people. For analyzing these situations, a notion is discussed in the present paper called social disappointment and then new protocols are proposed to prevent social disappointment. A version of the impossibility theorem is stated and proved regarding social disappointment in elections. In the end, the numerical results obtained by simulating the voting protocols of plurality and Hare system are given, to show that Hare system is a little more seccessful than plurality to prevent social disappointment.
  • PDF
    This paper pertains to the analysis and design of decentralized estimation schemes that make use of limited communication. Briefly, these schemes equip the sensors with scalar states that iteratively merge the measurements and the state of other sensors to be used for state estimation. Contrarily to commonly used distributed estimation schemes, the only information being exchanged are scalars, there is only one common time-scale for communication and estimation, and the retrieval of the state of the system and sensors is achieved in finite-time. We extend previous work to a more general setup and provide necessary and sufficient conditions required for the communication between the sensors that enable the use of limited communication decentralized estimation~schemes. Additionally, we discuss the cases where the sensors are memoryless, and where the sensors might not have the capacity to discern the contributions of other sensors. Based on these conditions and the fact that communication channels incur a cost, we cast the problem of finding the minimum cost communication graph that enables limited communication decentralized estimation schemes as an integer programming problem.
  • PDF
    In diffusion social learning over weakly-connected graphs, it has been shown recently that influential agents end up shaping the beliefs of non-influential agents. This paper analyzes this control mechanism more closely and addresses two main questions. First, the article examines how much freedom influential agents have in controlling the beliefs of the receiving agents. That is, the derivations clarify whether receiving agents can be driven to arbitrary beliefs and whether the network structure limits the scope of control by the influential agents. Second, even if there is a limit to what influential agents can accomplish, this article develops mechanisms by which these agents can lead receiving agents to adopt certain beliefs. These questions raise interesting possibilities about belief control over networked agents. Once addressed, one ends up with design procedures that allow influential agents to drive other agents to endorse particular beliefs regardless of their local observations or convictions. The theoretical findings are illustrated by means of several examples.
  • PDF
    Fractional Frequency Reuse techniques can be employed to address interference in mobile networks, improving throughput for edge users. There is a tradeoff between the coverage and overall throughput achievable, as interference avoidance techniques lead to a loss in a cell's overall throughput, with spectrum efficiency decreasing with the fencing off of orthogonal resources. In this paper we propose MANN, a dynamic multiagent frequency reuse scheme, where individual agents in charge of cells control their configurations based on input from neural networks. The agents' decisions are partially influenced by a coordinator agent, which attempts to maximise a global metric of the network (e.g., cell-edge performance). Each agent uses a neural network to estimate the best action (i.e., cell configuration) for its current environment setup, and attempts to maximise in turn a local metric, subject to the constraint imposed by the coordinator agent. Results show that our solution provides improved performance for edge users, increasing the throughput of the bottom 5% of users by 22%, while retaining 95% of a network's overall throughput from the full frequency reuse case. Furthermore, we show how our method improves on static fractional frequency reuse schemes.
  • PDF
    We prove that the efficiency gap does not satisfy the efficiency principle. We assume no mathematical background, with the intent that a law scholar can read this short note.

Recent comments