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

1
vote
1answer
22 views

Relevance scoring mechanism for multiple parameters

I have a program which build few attributes those decide relevance between two objects. attributes are $a_1, a_2, a_3$ Now what are different weighing or scoring mechanism to accumulate all three ...
3
votes
2answers
77 views

Strategy for selecting the optimal time to check a cooldown timer

This is a hard problem for me to word in the title, so I'll try to do better now. Consider the following "game": You are sitting in a room beside a table. In the middle of the table there exists a ...
1
vote
2answers
86 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
72 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
60 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
22 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
94 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
103 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
112 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
57 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
156 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
50 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
184 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
173 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
209 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
150 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
112 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 ...
1
vote
1answer
302 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
121 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
219 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
152 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
213 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
302 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
250 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
75 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
90 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
115 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
295 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
59 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
132 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
139 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
28 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
915 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
147 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
132 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
185 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
909 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
496 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
78 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
273 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
3k 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
317 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
180 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 ...
5
votes
0answers
136 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 ...