Game-Theoretically Allocating Resources to Catch Evaders and Payments to Stabilize Teams

Allocating resources optimally is a nontrivial task, especially when multiple

self-interested agents with conflicting goals are involved. This dissertation

uses techniques from game theory to study two classes of such problems:

allocating resources to catch agents that attempt to evade them, and allocating

payments to agents in a team in order to stabilize it. Besides discussing what

allocations are optimal from various game-theoretic perspectives, we also study

how to efficiently compute them, and if no such algorithms are found, what

computational hardness results can be proved.

The first class of problems is inspired by real-world applications such as the

TOEFL iBT test, course final exams, driver's license tests, and airport security

patrols. We call them test games and security games. This dissertation first

studies test games separately, and then proposes a framework of Catcher-Evader

games (CE games) that generalizes both test games and security games. We show

that the optimal test strategy can be efficiently computed for scored test

games, but it is hard to compute for many binary test games. Optimal Stackelberg

strategies are hard to compute for CE games, but we give an empirically

efficient algorithm for computing their Nash equilibria. We also prove that the

Nash equilibria of a CE game are interchangeable.

The second class of problems involves how to split a reward that is collectively

obtained by a team. For example, how should a startup distribute its shares, and

what salary should an enterprise pay to its employees. Several stability-based

solution concepts in cooperative game theory, such as the core, the least core,

and the nucleolus, are well suited to this purpose when the goal is to avoid

coalitions of agents breaking off. We show that some of these solution concepts

can be justified as the most stable payments under noise. Moreover, by adjusting

the noise models (to be arguably more realistic), we obtain new solution

concepts including the partial nucleolus, the multiplicative least core, and the

multiplicative nucleolus. We then study the computational complexity of those

solution concepts under the constraint of superadditivity. Our result is based

on what we call Small-Issues-Large-Team games and it applies to popular

representation schemes such as MC-nets.

GTES: An optimized game-theoretic demand-side management scheme for smart grid

Demand-side management in smart grids has emerged as a hot topic for optimizing energy consumption. In conventional research works, energy consumption is optimized from the perspective of either the users or the power company. In this paper, we investigate how energy consumption may be optimized by taking into consideration the interaction between both parties. We propose a new energy price model as a function of total energy consumption. Also, we propose a new objective function, which optimizes the difference between the value and cost of energy. The power supplier pulls consumers in a round-robin fashion and provides them with energy price parameter and current consumption summary vector. Each user then optimizes his own schedule and reports it to the supplier, which, in turn, updates its energy price parameter before pulling the next consumers. This interaction between the power company and its consumers is modeled through a two-step centralized game, based on which we propose our game-theoretic energy schedule (GTES) method. The objective of our GTES method is to reduce the peak-to-average power ratio by optimizing the users' energy schedules. The performance of the GTES approach is evaluated through computer-based simulations. © 2014 IEEE.

Developing real option game models

By mixing concepts from both game theoretic analysis and real options theory, an investment decision in a competitive market can be seen as a ‘‘game’’ between firms, as firms implicitly take into account other firms’ reactions to their own investment actions. We review two decades of real option game models, suggesting which critical problems have been ‘‘solved’’ by considering game theory, and which significant problems have not been yet adequately addressed. We provide some insights on the plausible empirical applications, or shortfalls in applications to date, and suggest some promising avenues for future research.

Flight testing of an augmented separation management system providing separation protection during failure of the central communication network

Future air traffic management concepts often involve the proposal of automated separation management algorithms that replaces human air traffic controllers. This paper proposes a new type of automated separation management algorithm (based on the satisficing approach) that utilizes inter-aircraft communication and a track file manager (or bank of Kalman filters) that is capable of resolving conflicts during periods of communication failure. The proposed separation management algorithm is tested in a range of flight scenarios involving during periods of communication failure, in both simulation and flight test (flight tests were conducted as part of the Smart Skies project). The intention of the conducted flight tests was to investigate the benefits of using inter-aircraft communication to provide an extra layer of safety protection in support air traffic management during periods of failure of the communication network. These benefits were confirmed.

Access control : allocating resources to selfish agents

The ultimate goal of an authorisation system is to allocate each user the level of access they need to complete their job - no more and no less. This proves to be challenging in an organisational setting because on one hand employees need enough access to perform their tasks, while on the other hand more access will bring about an increasing risk of misuse - either intentionally, where an employee uses the access for personal benefit, or unintentionally through carelessness, losing the information or being socially engineered to give access to an adversary. With the goal of developing a more dynamic authorisation model, we have adopted a game theoretic framework to reason about the factors that may affect users’ likelihood to misuse a permission at the time of an access decision. Game theory provides a useful but previously ignored perspective in authorisation theory: the notion of the user as a self-interested player who selects among a range of possible actions depending on their pay-offs.

Approaches to access control under uncertainty

The ultimate goal of an access control system is to allocate each user the precise level of access they need to complete their job - no more and no less. This proves to be challenging in an organisational setting. On one hand employees need enough access to the organisation’s resources in order to perform their jobs and on the other hand more access will bring about an increasing risk of misuse - either intentionally, where an employee uses the access for personal benefit, or unintentionally, through carelessness or being socially engineered to give access to an adversary. This thesis investigates issues of existing approaches to access control in allocating optimal level of access to users and proposes solutions in the form of new access control models. These issues are most evident when uncertainty surrounding users’ access needs, incentive to misuse and accountability are considered, hence the title of the thesis. We first analyse access control in environments where the administrator is unable to identify the users who may need access to resources. To resolve this uncertainty an administrative model with delegation support is proposed. Further, a detailed technical enforcement mechanism is introduced to ensure delegated resources cannot be misused. Then we explicitly consider that users are self-interested and capable of misusing resources if they choose to. We propose a novel game theoretic access control model to reason about and influence the factors that may affect users’ incentive to misuse. Next we study access control in environments where neither users’ access needs can be predicted nor they can be held accountable for misuse. It is shown that by allocating budget to users, a virtual currency through which they can pay for the resources they deem necessary, the need for a precise pre-allocation of permissions can be relaxed. The budget also imposes an upper-bound on users’ ability to misuse. A generalised budget allocation function is proposed and it is shown that given the context information the optimal level of budget for users can always be numerically determined. Finally, Role Based Access Control (RBAC) model is analysed under the explicit assumption of administrators’ uncertainty about self-interested users’ access needs and their incentives to misuse. A novel Budget-oriented Role Based Access Control (B-RBAC) model is proposed. The new model introduces the notion of users’ behaviour into RBAC and provides means to influence users’ incentives. It is shown how RBAC policy can be used to individualise the cost of access to resources and also to determine users’ budget. The implementation overheads of B-RBAC is examined and several low-cost sub-models are proposed.

Abandoning the Magic Circle

As a concept, the magic circle is in reality just 4 years old. Whilst often accredited to Johan Huizinga (1955), the modern usage of term in truth belongs to Katie Salen and Eric Zimmerman. It became in academia following the publication of “Rules of Play” in 2003. Because of the terminologyused, it carries with it unhelpful preconceptions that the game world, or play-space, excludes reality. In this paper, I argue that Salen and Zimmerman (2003) have taken a term used as an example, and applied a meaning to it that was never intended, based primarily upon definitions given by other authors, namely Apter (1991) and Sniderman (n.d.). I further argue that the definition itself contains a logical fallacy, which has prevented the full understanding of the definition in later work. Through a study of the literature in Game Theory, and examples of possible issues which could arise in contemporary games, I suggest that the emotions of the play experience continue beyond the play space, and that emotions from the “real world” enter it with the participants. I consider a reprise of the Stanley Milgram Obedience Experiment (2006), and what that tells us about human emotions and the effect that events taking place in a virtual environment can have upon them. I evaluate the opinion espoused by some authors of there being different magic circles for different players, and assert that this is not a useful approach to take when studying games, because it prevents the analysis of a game as a single entity. Furthermore I consider the reasons given by other authors for the existence of the Magic Circle, and I assert that the term “Magic Circle” should be discarded, that it has no relevance to contemporary games, and indeed it acts as a hindrance to the design and study of games. I conclude that the play space which it claims to protect from the courts and other governmental authorities would be better served by the existing concepts of intent, consent, and commonly accepted principles associated with international travel.

Resolving the conflicts of sustainable world heritage landscapes in cities : fully open or limited access for visitors?

World Heritage Landscapes (WHLs) are receiving increased attention from researchers, urban planners, managers, and policy makers and many heritage values and resources are becoming irreversibly lost. This phenomenon is especially prominent for WHLs located in cities, where greater development opportunities are involved. Decision making for sustainable urban landscape planning, conservation and management of WHLs often takes place from an economic perspective, especially in developing countries. This, together with the uncertain source of funding to cover WHL operating and maintenance costs, has resulted in many urban managers seeking private sector funding either in the form of visitor access fees or leasing part of the site for high-rental facilities such as five star hotels, clubs and expensive restaurants. For the former, this can result in low-income urban citizens being unable to afford the access fees and hence contradicting the principle of equal access for all; while, for the latter, the principle of open access for all is equally violated. To resolve this conflict, a game model is developed to determine how urban managers should allocate WHL spaces to maximize the combination of economic, social and ecological benefits and cultural values. A case study is provided of the Hangzhou's West Lake Scenic Area, a WHL located at the centre of Hangzhou city, in which several high-rental facilities have recently been closed down by the local authorities due to charges of elitism and misuse of public funds by government officials. The result shows that the best solution is to lease a small space with high rents and leave the remainder of the site to the public. This solution is likely to be applicable only in cities with a strong economy.

An Uber for apartments could solve some common housing problems

Speculative property developers, criticised for building dog boxes and the slums of tomorrow, are generally hated by urban planners and the public alike. But the doors of state governments are seemingly always open to developers and their lobbyists. Politicians find it hard to say no to the demands of the development industry for concessions because of the contribution housing construction makes to the economic bottom line and because there is a need for well located housing. New supply is also seen as a solution to declining housing affordability. Classical economic theory however is too simplistic for housing supply. Instead, an offshoot of Game Theory - Market Design – not only offers greater insight into apartment supply but also can simultaneously address price, design and quality issues. New research reveals the most significant risk in residential development is settlement risk – when buyers fail to proceed with their purchase despite there being a pre-sale contract. At the point of settlement, the developer has expended all the project funds only to see forecast revenue evaporate. While new buyers may be found, this process is likely to strip the profitability out of the project. As the global financial crisis exposed, buyers are inclined to walk if property values slide. This settlement problem reflects a poor legal mechanism (the pre-sale contract), and a lack of incentive for truthfulness. A second problem is the search costs of finding buyers. At around 10% of project costs, pre-sales are more expensive to developers than finance. This is where Market Design comes in.

Study of robust H(infinity) filtering application in loosely coupled INS/GPS system

Since a celebrate linear minimum mean square (MMS) Kalman filter in integration GPS/INS system cannot guarantee the robustness performance, a H(infinity) filtering with respect to polytopic uncertainty is designed. The purpose of this paper is to give an illustration of this application and a contrast with traditional Kalman filter. A game theory H(infinity) filter is first reviewed; next we utilize linear matrix inequalities (LMI) approach to design the robust H(infinity) filter. For the special INS/GPS model, unstable model case is considered. We give an explanation for Kalman filter divergence under uncertain dynamic system and simultaneously investigate the relationship between H(infinity) filter and Kalman filter. A loosely coupled INS/GPS simulation system is given here to verify this application. Result shows that the robust H(infinity) filter has a better performance when system suffers uncertainty; also it is more robust compared to the conventional Kalman filter.

Identifying the financial barriers to deliberative, affordable apartment development in Australia

Purpose The purpose of this paper is to identify the financial barriers to the supply of affordable apartments in Australia and examine whether demand aggregation and ‘deliberative development’ (self-build) can form a new affordable housing ‘structure of provision’. Design/methodology/approach Market design, an offshoot of game theory, is used to analyse the existing apartment development model, with ‘deliberative development’ proposed as an innovative alternative. Semi-structured interviews with residential development financiers are used to evaluate whether deliberative development could obtain the requisite development finance. Findings Our investigation into the financial barriers of a deliberative development model suggest that while there are hurdles, these can be addressed if key risks in the exchange process can be mitigated. Hence, affordability can be enhanced by ‘deliberative development’ replacing the existing speculative development model. Research implications Market design is a new innovative theoretical approach to understanding the supply of housing, offering practical solutions to affordable apartment supply in Australia. Originality/value This research identifies financial barriers to the supply of affordable apartments; introduces theoretical understandings gained from market design as an innovative solution; provides evidence that a new structure of building provision based on ‘deliberative development’ could become a key means of achieving more affordable and better designed apartments.

Deriving optimal competition in infrastructure procurement

Typically only a limited number of consortiums are able to competitively bid for Public Private Partnership (PPP) projects. Consequently, this may lead to oligopoly pricing constraints and ineffective competition, thus engendering ex ante market failure. In addressing this issue, this paper aims to determine the optimal number of bidders required to ensure a healthy level of competition is available to procure major infrastructure projects. The theories of Structure-Conduct-Performance (SCP) paradigm; Game Theory and Auction Theory and Transaction Cost Economics are reviewed and discussed and used to produce an optimal level of competition for major infrastructure procurement, that prevents market failure ex ante (lack of competition) and market failure ex post (due to asymmetric lock-in).

Essays on the Bioeconomics of the Northern Baltic Fisheries

World marine fisheries suffer from economic and biological overfishing: too many vessels are harvesting too few fish stocks. Fisheries economics has explained the causes of overfishing and provided a theoretical background for management systems capable of solving the problem. Yet only a few examples of fisheries managed by the principles of the bioeconomic theory exist. With the aim of bridging the gap between the actual fish stock assessment models used to provide management advice and economic optimisation models, the thesis explores economically sound harvesting from national and international perspectives. Using data calibrated for the Baltic salmon and herring stocks, optimal harvesting policies are outlined using numerical methods. First, the thesis focuses on the socially optimal harvest of a single salmon stock by commercial and recreational fisheries. The results obtained using dynamic programming show that the optimal fishery configuration would be to close down three out of the five studied fisheries. The result is robust to stock size fluctuations. Compared to a base case situation, the optimal fleet structure would yield a slight decrease in the commercial catch, but a recreational catch that is nearly seven times higher. As a result, the expected economic net benefits from the fishery would increase nearly 60%, and the expected number of juvenile salmon (smolt) would increase by 30%. Second, the thesis explores the management of multiple salmon stocks in an international framework. Non-cooperative and cooperative game theory are used to demonstrate different "what if" scenarios. The results of the four player game suggest that, despite the commonly agreed fishing quota, the behaviour of the countries has been closer to non-cooperation than cooperation. Cooperation would more than double the net benefits from the fishery compared to a past fisheries policy. Side payments, however, are a prerequisite for a cooperative solution. Third, the thesis applies coalitional games in the partition function form to study whether the cooperative solution would be stable despite the potential presence of positive externalities. The results show that the cooperation of two out of four studied countries can be stable. Compared to a past fisheries policy, a stable coalition structure would provide substantial economic benefits. Nevertheless, the status of the salmon stocks would not improve significantly. Fourth, the thesis studies the prerequisites for and potential consequences of the implementation of an individual transferable quota (ITQ) system in the Finnish herring fishery. Simulation results suggest that ITQs would result in a decrease in the number of fishing vessels, but enables positive profits to overlap with a higher stock size. The empirical findings of the thesis affirm that the profitability of the studied fisheries could be improved. The evidence, however, indicates that incentives for free riding exist, and thus the most preferable outcome both in economic and biological terms is elusive.