Search results for " Game theory"
showing 10 items of 120 documents
On the Complexity of Solving Subtraction Games
2018
We study algorithms for solving Subtraction games, which sometimes are referred to as one-heap Nim games. We describe a quantum algorithm which is applicable to any game on DAG, and show that its query compexity for solving an arbitrary Subtraction game of $n$ stones is $O(n^{3/2}\log n)$. The best known deterministic algorithms for solving such games are based on the dynamic programming approach. We show that this approach is asymptotically optimal and that classical query complexity for solving a Subtraction game is generally $\Theta(n^2)$. This paper perhaps is the first explicit "quantum" contribution to algorithmic game theory.
Nash codes for noisy channels
2012
This paper studies the stability of communication protocols that deal with transmission errors. We consider a coordination game between an informed sender and an uninformed decision maker, the receiver, who communicate over a noisy channel. The sender's strategy, called a code, maps states of nature to signals. The receiver's best response is to decode the received channel output as the state with highest expected receiver payoff. Given this decoding, an equilibrium or "Nash code" results if the sender encodes every state as prescribed. We show two theorems that give sufficient conditions for Nash codes. First, a receiver-optimal code defines a Nash code. A second, more surprising observati…
Shared value economics: an axiomatic approach
2020
[EN]The concept of shared value was introduced by Porter and Kramer as a new conception of capitalism. Shared value describes the strategy of organizations that simultaneously enhance their competitiveness and the social conditions of related stakeholders such as employees, suppliers and the natural environment. The idea has generated strong interest, but also some controversy due to a lack of a precise definition, measurement techniques and difficulties to connect theory to practice. We overcome these drawbacks by proposing an economic framework based on three key aspects: coalition formation, sustainability and consistency, meaning that conclusions can be tested by means of logical deduct…
Quantum-over-classical Advantage in Solving Multiplayer Games
2020
We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum combinatorial games with provable separation between quantum and classical complexity of solving them. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms for finding solutions with probability $1$. Typically, both Nim and Subtraction games are defined for only two players. We extend some known results to games for t…
Quantum strategies are better than classical in almost any XOR game
2011
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.
MAC Design for WiFi Infrastructure Networks: A Game-Theoretic Approach
2011
In WiFi networks, mobile nodes compete for accessing a shared channel by means of a random access protocol called Distributed Coordination Function (DCF). Although this protocol is in principle fair, since all the stations have the same probability to transmit on the channel, it has been shown that unfair behaviors may emerge in actual networking scenarios because of non-standard configurations of the nodes. Due to the proliferation of open source drivers and programmable cards, enabling an easy customization of the channel access policies, we propose a game-theoretic analysis of random access schemes. Assuming that each node is rational and implements a best response strategy, we show that…
On Applying Adaptive Data Structures to Multi-Player Game Playing
2013
In the field of game playing, the focus has been on two-player games, such as Chess and Go, rather than on multi-player games, with dominant multi-player techniques largely being an extension of two-player techniques to an \(N\)-player environment. To address the problem of multiple opponents, we propose the merging of two previously unrelated fields, namely those of multi-player game playing and Adaptive Data Structures (ADS). We present here a novel move-ordering heuristic for a dominant multi-player game playing algorithm, namely the Best-Reply Search (BRS). Our enhancement uses an ADS to rank the opponents in terms of their respective threat levels to the player modeled by the AI algori…
From Global Games to Re-contextualized Games: The Design Process of TekMyst
2011
Designing, developing and testing a game for a specific learning context and then achieving positive results, encourages one to deploy it in other environments. We know however that it is not always possible to successfully transfer artifacts from one learning context to the next. In this chapter we explore the principles to be considered when re-contextualizing a game. We base our analysis on the transfer of a Hypercontextualized Game SciMyst (which was designed and developed for the Joensuu Science Festival) into its re-contextualized version TekMyst (for the Helsinki Museum of Technology). Employing a qualitative approach we review the requirements and design decisions at the hand of fou…
Novel threat-based AI strategies that incorporate adaptive data structures for multi-player board games
2016
This paper considers the problem of designing novel techniques for multi-player game playing, in a range of board games and configurations. Compared to the well-known case of two-player game playing, multi-player game playing is a more complex problem with unique requirements. To address the unique challenges of this domain, we examine the potential of employing techniques inspired by Adaptive Data Structures (ADSs) to rank opponents based on their relative threats, and using this information to achieve gains in move ordering and tree pruning. We name our new technique the Threat-ADS heuristic. We examine the Threat-ADS’ performance within a range of game models, employing a number of diffe…
Models, information and meaning
2018
Abstract There has recently been an explosion of formal models of signaling, which have been developed in order to learn about different aspects of meaning. This paper discusses whether that success can also be used to provide an original naturalistic theory of meaning in terms of information or some related notion. In particular, it argues that, although these models can teach us a lot about different aspects of content, at the moment they fail to support the idea that meaning just is some kind of information. As an alternative, I suggest a more modest approach to the relationship between the informational notions used in models and semantic properties in the natural world.