Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. (Def: http://en.m.wikipedia.org/wiki/Algorithmic_game_theory)

learn more… | top users | synonyms

0
votes
1answer
37 views

How many ways to win this ternary row-game?

Sorry for the vague title. Please edit or comment if you know of a better one. Game description is below. I have a solution that works but coding it would be O($N!$) time complexity. I know there's a ...
1
vote
2answers
70 views

Sierpinski triangle game for 3 players

The players are red, green and blue. The game is played on a n-deep Sierpinski triangle. Each player colors a (black) triangle, starting at one of the main vertices. They then take turns to color an ...
0
votes
1answer
39 views

How to find rotation quaternion for a model so that it is perpendicular to a line in 3D space?

How to find the target rotation quaternion for a model when one of its faces need to be aligned perpendicular to a line in 3D space. For example, if the model is a cube and if two 3D points connecting ...
0
votes
0answers
20 views

Piecewise continuous potential function?

This question arises from a game theoretic problem. I'm posing it in 2-D to simplify the exposition. Given two functions $f(x,y)$ and $g(x,y)$, the problem is to find a potential function $P(x,y)$ ...
0
votes
1answer
84 views

Fan speed algorithm

I'm a programmer an I think my problem related to mathematics! I want when CPU have a static percentage of load (for example $10\%$) fan also have static rpm (Rotations per minute). But for now I have ...
0
votes
1answer
38 views

Reducing an I-optimal problem to a Pareto-optimal problem

Given a set $\textbf y\subset\mathbb R^2$, let $y = (y_1,y_2), y'=(y'_1,y'_2)\in\textbf y$ be elements of that set, let $\alpha_{min}\in\mathbb R$, $\alpha_{min}<1$, $\alpha_{max}\in\mathbb R$, ...
0
votes
1answer
31 views

Biobjective optimisation, pareto non-domination

Ok, so, I have a function $f_I(y_1, y_2) = \max\{\alpha y_1 + (1-\alpha)y_2:\alpha\in[\alpha_{min},\alpha_{max}]\}$ that I'm trying to minimise, and I'm asked to find, amongst a set of vectors $y$, ...
0
votes
2answers
87 views

Math theories in Game Theory

What are all the mathematical theories in Game Theory? I have taken Mathematical Modelling, including: application of linear systems, matrix operations, inverse of matrix, leontif input-output model, ...
0
votes
1answer
110 views

Nim Sum Game Variant

Suppose there are black and white balls in a box. The initial number of white balls is m and the initial number of black balls is n. This is a two player game. Each player can do the following taking ...
2
votes
2answers
55 views

Another question on a 2-player game strategy

This is a 2-player game. The game begins with a binary string (leading zeros not ignored). Each turn, a player can remove a sequence of consecutive and identical digits from the left. For example, ...
3
votes
1answer
90 views

Resources for understanding game trees?

I am trying to make an AI to solve the popular game $2048$, and I think that the theory of game trees would help me quite a bit in this endeavor. The only issue is that most of the results I've found ...
5
votes
0answers
143 views

Optimal Strategy for “I'm Thinking of a Number” Game

This question is inspired by one of the classic ways of breaking ties: the "I'm thinking of a number" game. In this game, one person thinks of a number in some range, say from $0$ to $100$ ...
0
votes
0answers
41 views

Multi-armed bandit optimization

I've got a variation of multi-armed bandit problem, where I need not to minimize the regret, but to find a bandit with a maximum reward. Could you please tell how this problem is called or suggest ...
0
votes
5answers
170 views

Some examples of applications of Game Theory

I'm approaching my junior year of HS now, and I'm looking for a good science fair project to do. I love mathematics, so I decided to a category of mathematics that can help base logical conclusions to ...
2
votes
1answer
162 views

Game theory: Mixed Strategies and Nash Equilibrium

So I've recently become interested in game theory, and I've visited this site to help me understand what exactly game theory is and the applications of it. In the lesson, they use an example of ...
2
votes
1answer
77 views

A game with numbers from MEMO $2013$

The expression $$\displaystyle \pm \Box \pm \Box \pm \Box \pm \Box \pm \Box \pm \Box $$ is written on the blackboard. Tow players, $ A $ and $ B $, play a game, taking turns. Player $ A $ takes the ...
12
votes
4answers
205 views

How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
1
vote
2answers
137 views

Hex game winning strategy

I was teaching myself how to play a hex board game by reading some books a couple days ago. I learned how to do $2$ x $2$ and $3$ x $3$ hex games by starting at the principal diagonal. I wanted to ...
0
votes
1answer
97 views

The potential function of Prisoner's Dilemma

As in the famous example of "Prisoner's Dilemma" like this If the potential function is defined as: (V(q,q), V(q,c), V(c,q), V(c,c)) q = quiet, c = confess, V is the potential. So should the order ...
0
votes
0answers
27 views

de Bono's L-game modification

I am trying to find out if a simple modification od de Bono's L-game is still infinite if two players are perfect. Modified rule is that there no neutral pieces but, there is one piece for each player ...
1
vote
1answer
263 views

Optimal strategy for dominoes game

Here is the basic principle of the game I'm trying to find an optimal strategy for: Two players (say P and Q) are given a 2x3 grid and a domino. Then P chooses one way of positioning the domino on ...
4
votes
1answer
116 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
0
votes
1answer
186 views

Game Theory - trying to find game name by description

My hobby AI research have led me to a thorethical game of particular design. As design is pretty simple, I'm almost sure that such game has well-known name and tons of research already done around it. ...
1
vote
1answer
149 views

Game Theory - Nash equilibrium question

Consider a game in which 2 players transmit packets in a network with a selected power $x ∈ [1, A]$ and $y∈ [1, A]$, respectively. The utility of the players can be expressed as: $$u_{i} (x,y) = ...
13
votes
4answers
210 views

perfect play in 1-dimensional Minesweeper

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly), is there a known somewhat-simple strategy for perfect play? When there are n cells and [0 or n-1 ...
4
votes
1answer
284 views

A game of Chess - Ideal Solution

I am a student of physics. I have learnt some basic group theory, and I am wondering if there is any ideal solution for a given Chess game (like solving Rubik's cube). I know the no. of permutations ...
1
vote
1answer
243 views

Largest white rectangle on board

Given a string rectangular board which is divided into unit cells. Each cell is initially painted black or white. The character board[i][j] represents the cell with coordinates (i, j). Each of those ...
2
votes
1answer
73 views

What's the most efficient algorithm to determine the relative ordering of an unknown set of values?

This comes from a question on Arqade. The background is, there's a mall level. Vlad the organized crime boss wants $50,000 worth of mall property destroyed. Your task is to shoot and blow ...
4
votes
1answer
87 views

How to design a cost sharing auction format for collective bidding?

Problem goes like this: There's one resource which can only be utilized by a single set of agents $A_i$ (at any one time) out of $n$ predefined (disjoint) sets of agents. Each agent wants to use the ...
2
votes
1answer
112 views

the proof of Arrow's Theorem

I read Philip J. Reny's paper (Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach) What I cannot understand is step 5 of the proof of arrow's theorem. I think figure 4 is a ...
7
votes
2answers
293 views

A Nim-like game with conditions and strategies

The game: Given $S = \{ a_1,..., a_n \}$ of positive integers ($n \ge 2$). The game is played by two people. At each of their turns, the player chooses two different non-zero numbers and subtracts ...
1
vote
2answers
60 views

extensive and strategic game

definitions of extensive and strategic (normal) games are very different. Here is the question, what would you call a game which is extensive but in each step strategic. For instance at each step ...
1
vote
1answer
56 views

Segment crossing algorithm

I need an ideea of an algorithm to solve a puzzle 'game'. The game is : is given N number of line segments by coordinates [(X1n,Y1n),(X2n,Y2n)] some of segments have the same ends We've got ...
4
votes
1answer
124 views

Flip all to zero

I have a square grid of size $N$, with rows numbered from $0$ to $N - 1$ starting from the top and columns numbered from $0$ to $N - 1$ starting from the left. A cell $(u, v)$ refers to the cell that ...
0
votes
1answer
122 views

Prize distribution system based on quantity/priority per day

I'm trying to figure out a way to "fairly" distribute a pool of prizes on a daily basis depending on the time the contest will run, the priority and max items per day/week. For a better explanation, ...
1
vote
0answers
26 views

Are there any good resources to learn mathematical analysis of single player games and puzzles?

What are the best resources to understand the mathematical analysis of single player games like Solitaire, Free Cell, Sudoku, Rubik's Cube, etc.? Most game theory books I browsed in the local book ...
2
votes
1answer
869 views

questions on information set definition

The definition of "information set" is An information set is a set of decision nodes, all belonging to the same player, over which that player cannot distinguish. ...
1
vote
2answers
144 views

How do I grade the complexity of the below math puzzle game?

The game (I built it, and it is currently live on mobile) involves solving a pascal's triangle like grid of numbers with operators between the numbers - an example with 3 rows is: ...
0
votes
1answer
123 views

Partisan/Partial Game Theory

There are enough resources available on the internet regarding "impartial" game theory. But I cannot seem to find much information regarding "partial" game theory. Can someone name some such resources ...
2
votes
1answer
170 views

Sort objects into groups based on group size preference

I have a research question that involves human subjects being sorted into groups before playing a social game. Before sorting, each person decides on their preferred group size, from 1 to n; where n ...
2
votes
1answer
861 views

Finding Pareto optimal solution set in $O(n \log n)$ time

http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says: For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a ...
3
votes
5answers
481 views

Provide an algorithm $O (n ^ 3 \log n)$, any example?

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations. Any idea of how to approach this problem?...I am studying for the computer science ...
0
votes
1answer
73 views

Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists. Can someone please tell me how do I ...
1
vote
1answer
256 views

Require help in writing the algorithm for my cricket simulation game

I am trying to write the algorithm for a cricket simulation game which generates runs on each ball between 0 to 6. The run rate or runs generated changes when these factors come into play like Skill ...
46
votes
3answers
2k views

A non-losing strategy for tic-tac-toe $\times$ tic-tac-toe

Consider a 9 by 9 matrix that consists of 9 block matrices of 3 by 3. Let each 3 by 3 block be a game of tic-tac-toe. For each game, label the 9 cells of the game from 1-9 with order from left to ...
1
vote
1answer
109 views

Two Player Game Useless Strategy

Let's consider the variant of dominated strategy which is the pure strategy that is not a best response to any mixed strategy of the opponent (two player game). Intuitively it sounds like more ...
2
votes
0answers
312 views

Is quantum game theory reducible to classical game theory? [closed]

Modnote: This question was manually migrated (closed and crossposted) to MathOverflow by request of the OP. Quantum game theory is an extension of classical game theory to the quantum domain. It ...
1
vote
0answers
172 views

Stable Matching Optimal Strategy Existence

There is a famous stable marriage problem. It's well known that the standard algorithm for stable marriage problem proposed by Shapley and Gale is man-optimal, men get a best according to their ...
4
votes
0answers
132 views

Unexpected hanging paradox maxmin strategies

I have a question about strategies of the players of Unexpected hanging paradox (I am very sorry for a long topic, topic exist already for a while, during this time I try to develop idea how to solve ...
3
votes
1answer
533 views

Converting a game in extensive form to normal form

I have some difficulties in representing the following game in the standard form. Game: two players game is represented as a game tree (in extensive form), a game tree is a full binary tree, both ...