9,150 research outputs found
Synthesis of Reward Machines for Multi-Agent Equilibrium Design
No full textMechanism design is a well-established game-theoretic paradigm for designing games to achieve desired outcomes. This paper addresses a closely related but distinct concept, equilibrium design. Unlike mechanism design, the designer’s authority in equilibrium design is more constrained; she can only modify the incentive structures in a given game to achieve certain outcomes without the ability to create the game from scratch. We study the problem of equilibrium design using dynamic incentive structures, known as reward machines. We use weighted concurrent game structures for the game model, with goals (for the players and the designer) defined as mean-payoff objectives. We show how reward machines can be used to represent dynamic incentives that allocate rewards in a manner that optimises the designer’s goal. We also introduce the main decision problem within our framework, the payoff improvement problem. This problem essentially asks whether there exists a dynamic incentive (represented by some reward machine) that can improve the designer’s payoff by more than a given threshold value. We present two variants of the problem: strong and weak. We demonstrate that both can be solved in polynomial time using a Turing machine equipped with an NP oracle. Furthermore, we also establish that these variants are either NP-hard or coNP-hard. Finally, we show how to synthesise the corresponding reward machine if it exists
Pioneers of Library Movement in Pakistan
Full text linkThe paper aims to describe in brief the contribution of seven leaders of Pakistan librarianship, viz. K.B. Khalifa M. Asadullah, Prof. Dr. Abdul Moid, Dr. Abdus Subuh Qasimi, Muhammad Shafi, Fazal Elahi, Khawaja Nur Elahi and S. V. Hussain. The early library developments are given for better understanding of the role of these leaders
Blueprint : Prism Spectacle / Muhammad Najib Mohd Fadzli
Full text linkNowadays, human life getting better and easier because of the technology and this technology is developing year by year with a new innovation created by humans that will reach all aspects either in food, machine, vehicle and more. As we know, over the years technology has been growing fast. Knowing human used communication by texting, calling and social media like Instagram, twitter, Facebook and many others. Technology is often changing our lives to make things easier and better for them. Facebook chanting is something new to them and it’s an obsession to them. They use it to chart to each other’s. My company has developed an idea of spectacles known as prism spectacles. This spectacles is special and unique because it combine of prism glasses and spectacles frame.
The function of prism glasses is to reflect the eyesight by 90 degree. This spectacle is very useful for community nowadays who are obsessed with their phone. Not all of them believe their neck pain began with staring at their phones. This is result of staring down or staying hunched over an activity for too long. This posture isn’t exactly new; people have done this for centuries with books, drawings, sewing, and many other activitie
Automated temporal equilibrium analysis: Verification and synthesis of multi-player games
Full text linkIn the context of multi-agent systems, the rational verification problem is concerned with checking which temporal logic properties will hold in a system when its constituent agents are assumed to behave rationally and strategically in pursuit of individual objectives. Typically, those objectives are expressed as temporal logic formulae which the relevant agent desires to see satisfied. Unfortunately, rational verification is computationally complex, and requires specialised techniques in order to obtain practically useable implementations. In this paper, we present such a technique. This technique relies on a reduction of the rational verification problem to the solution of a collection of parity games. Our approach has been implemented in the Equilibrium Verification Environment (EVE) system. The EVE system takes as input a model of a concurrent/multi-agent system represented using the Simple Reactive Modules Language (SRML), where agent goals are represented as Linear Temporal Logic (LTL) formulae, together with a claim about the equilibrium behaviour of the system, also expressed as an LTL formula. EVE can then check whether the LTL claim holds on some (or every) computation of the system that could arise through agents choosing Nash equilibrium strategies; it can also check whether a system has a Nash equilibrium, and synthesise individual strategies for players in the multi-player game. After presenting our basic framework, we describe our new technique and prove its correctness. We then describe our implementation in the EVE system, and present experimental results which show that EVE performs favourably in comparison to other existing tools that support rational verification
Designing Equilibria in Concurrent Games with Social Welfare and Temporal Logic Constraints
Full text linkIn game theory, mechanism design is concerned with the design of incentives so that a desired outcome of the game can be achieved. In this paper, we explore the concept of equilibrium design, where incentives are designed to obtain a desirable equilibrium that satisfies a specific temporal logic property. Our study is based on a framework where system specifications are represented as temporal logic formulae, games as quantitative concurrent game structures, and players\u27 goals as mean-payoff objectives. We consider system specifications given by LTL and GR(1) formulae, and show that designing incentives to ensure that a given temporal logic property is satisfied on some/every Nash equilibrium of the game can be achieved in PSPACE for LTL properties and in NP/ΣP 2 for GR(1) specifications. We also examine the complexity of related decision and optimisation problems, such as optimality and uniqueness of solutions, as well as considering social welfare, and show that the complexities of these problems lie within the polynomial hierarchy. Equilibrium design can be used as an alternative solution to rational synthesis and verification problems for concurrent games with mean-payoff objectives when no solution exists or as a technique to repair concurrent games with undesirable Nash equilibria in an optimal way.arXiv admin note: substantial text overlap with arXiv:2106.1019
On the complexity of rational verification
Full text linkRational verification refers to the problem of checking which temporal logic properties hold of a concurrent/multiagent system, under the assumption that agents in the system choose strategies that form a game theoretic equilibrium. Rational verification can be understood as a counterpart to model checking for multiagent systems, but while classical model checking can be done in polynomial time for some temporal logic specification languages such as CTL, and polynomial space with LTL specifications, rational verification is much harder: the key decision problems for rational verification are 2EXPTIME-complete with LTL specifications, even when using explicit-state system representations. Against this background, our contributions in this paper are threefold. First, we show that the complexity of rational verification can be greatly reduced by restricting specifications to GR(1), a fragment of LTL that can represent a broad and practically useful class of response properties of reactive systems. In particular, we show that for a number of relevant settings, rational verification can be done in polynomial space and even in polynomial time. Second, we provide improved complexity results for rational verification when considering players’ goals given by mean-payoff utility functions—arguably the most widely used approach for quantitative objectives in concurrent and multiagent systems. Finally, we consider the problem of computing outcomes that satisfy social welfare constraints. To this end, we consider both utilitarian and egalitarian social welfare and show that computing such outcomes is either PSPACE-complete or NP-complete
Case Study : Eco-Shop / Muhammad Najib Mohd Fadzli
Full text linkEco-Shop Sdn Bhd is one of the leading Retail Chain Store and has 82 branches throughout Malaysia.
Eco-Shop was established on 1 June 2003, the head office and warehouse is located in Jementah, Johor. The main business is selling convenience goods including food, daily products, household products, cosmetics, toys, stationary, hardware and so on. The price for each item is RM2.12 only.
In addition, they have used the fully computerized system to organize and facilitate the logistic of warehouse management with branches and sales management in the branch. The company promised to provides quality service based on customer request, supplying of goods is not only convenient but well worth to satisfy the needs of each customer. For example, supply of the latest products and goods collocation more than 8,000 types of products. The slogan for their company is “Beli Sekali, Pasti Kembali.” Their company type is Small-Medium Enterprise
- …
