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
0answers
44 views

Strategy of ball math game

Found math game: http://www.emathhelp.net/math-games-and-logic-puzzles/rgbw/ What is a strategy for it? I can make 15 white balls max. Any thoughts?
1
vote
0answers
115 views

A variation of Nim game

There are two players X and Y . They write N integers on paper ( A_1 , A_2 , A_3 , .... A_N ). They have also p integers (b_1 , b_2 , b_3 , .... b_p ) . Now , Player X always takes turn first . He ...
0
votes
1answer
33 views

Strategy optimisation

This is a question from the Singapore Invitational Mathematics Challenge 2016. The question paper can be found here. (Part C:Question 2) http://www.nushigh.edu.sg/qql/slot/u90/file/simc/...
8
votes
4answers
110 views

Guess the number despite false answer

This is the Guess-The-Number game with a twist! Variant 1 Take any positive integer $n$. The game-master chooses an $n$-bit integer $x$. The player makes queries one by one, each of the ...
0
votes
1answer
20 views

Is the Shapely value of this voting game in the core?

Given a voting game where $v(1),v(2),v(3) = 0, v(1,2)= \frac{1} {3}, v(2,3) = \frac{5} {6}$, $v(1,3)= \frac{1} {6}$ and $v(1,2,3) = 1$ I know the Shapely coefficients for a 3 player game, for $|s|=1,...
1
vote
0answers
32 views

Check an algorithm to win hex as first player guaranteed

This question has more to do with the validity of the alogirthm than help per se. I'm unsure if this works with all board setups or just this one, or if it's valid at all. I'm going to start with a ...
1
vote
0answers
76 views

Finding a Mathematical definition of a Discrete Time Game

Preface: Suppose we have a game world as depicted in the following figure: Where each of the white blocks is passable, And each of the black blocks is a wall and so impassable. Each of the Green ...
3
votes
0answers
54 views

Candy Crush as an integer programming problem

I'm trying to model the basic version of a match-three game, where the player (has a maximum number of swaps) must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match ...
0
votes
1answer
54 views

How to calculate the payoff in Battleship Game Theory

Consider a 3 by 3 board and suppose that Player I hides a destroyer(length 2 squares) vertically or horizontally on this board. Then Player II shoots by calling out squares of the board, one at a time....
2
votes
1answer
118 views

What is the maximum sum of these numbers?

Consider $n$ circles with intersection by any two of them. Any area is all the common part between $m$ circles(a $m$-area): We have $2^n - 1$ areas, $m$ varies between $1$ and $m$. A $1$-area is an ...
1
vote
1answer
89 views

How to find periodicity of a nim sequence?

I am trying to solve a problem which is a simple algorithmic game. Link to the problem - https://community.topcoder.com/stat?c=problem_statement&pm=6856 I have basically figured out that for ...
4
votes
0answers
42 views

Interesting properties of a mathematical number theory game

The game, which is purely recreational, goes as follows: Starting out with 1, you can employ any of two different generation rules: You can multiply by 3 You can divide by two, rounding up (e.g. 3 ...
0
votes
1answer
26 views

Best strategy to detect if 2 words are different while uveiling as little as possible

I though of the following problem; I did not have time to seriously think about and I probably won't, but rather than forgetting it I thought, maybe, someone will like it so I decided to post it here. ...
1
vote
0answers
34 views

Has a simple optimal or provably near optimal strategy been shown for backgammon bearing off?

I aplogize in advance for the somewhat long post. I've tried to split it into manageable paragraphs. So in backgammmon, in the so-called "end-game", both players have their pieces in their respective ...
3
votes
1answer
71 views

Algorithm for assigning users to “buckets” according to users' preferences and ranking

Suppose there is a set of $n$ users which must each be assigned to one, and only one, of $k$ mutually exclusive "buckets". However, the number of users allocated to the $i$-th bucket must be no lower ...
0
votes
0answers
14 views

Information sets in Extensive Form Game with imperfect information

I have constructed an extensive form game with imperfect information given in the attached image. I am however a little uncertain as to whether my information sets are actually admissible if I, for ...
2
votes
1answer
19 views

When does a matrix game and the sign flipped matrix game have the same nash equilibria?

Given a game $G$, we can construct another $G'$, by a positive scaling i.e. $\lambda \in \mathbb{R}_{++}$, s.t. each entry of $A$ is scaled by $\lambda$ Obviously, $G$ and $G'$ have the same nash ...
0
votes
1answer
62 views

Mixed Nash equilibria in $n$-player games

I'm reading up on Game Theory. So far, I feel like I have a pretty good understanding on two-player games and their properties. Consider a two person game where the payoff matrices are $A_{m\times ...
0
votes
0answers
43 views

Combinatorial Allocation Problem

The problem I am trying to solve is that there are $m$ distinct items to sell through a combinatorial auction and bids have been received. But for any pairs of bids $b_i(X)$ and $b_i(Y)$, the subsets $...
1
vote
1answer
160 views

Nash equilibrium indifference principle

In the Hebrew wiki page on Nash equilibrium there is a reference to an indifference principle which means that once we know the other player uses the equilibrium strategy then the first player can use ...
4
votes
1answer
101 views

How to setup the correct transportation tableu for this Caterer Problem?

The problem said: A caterer must supply 110 napkins on Monday, 90 on Tuesday, 130 on Wednesday, and 170 on Thursday. The caterer initially has no napkins on hand. New napkins can be bought for ...
0
votes
0answers
75 views

What is the formula for winning at Pentago?

Pentago is a board game and you can think of it as a highly advanced version of tic-tac-toe. With the aid of supercomputers, it has been strongly solved. Just like tic-tac-toe, it is possible for ...
26
votes
1answer
970 views

What is the optimal strategy in the “Factor Game”?

Edit (Nov 1, 2015): Bounty awarded, but the full question (i.e., what is the optimal strategy) remains open at the time of this update. Consider the Factor Game played as follows: Given a list of ...
2
votes
0answers
32 views

Ideal Card Game

I have invented a very interesting card game. All the cards from 2 to 10 (in four colours) are divided evenly between the two players (the deck is shuffled before dealing the cards, of course). Now ...
0
votes
1answer
24 views

Understanding pure nash strategy for general sum game

Given a general sum game with the cost function $A = \begin{bmatrix} 2000 & 0 & 2000 \\ 1000 & 100 & 1000 \end{bmatrix}$ $B = \begin{bmatrix} 400 & 0 & 0 \\ 1 & 1 & ...
1
vote
1answer
25 views

How does this textbook compute the Nash Equilibrium of the two person zero sum game?

In Tamer Basar Noncooperative Game theory pg $33$ there is a $2 \times 3$ game (zero sum game) $A = \begin{bmatrix} 1 & 3 & 0 \\ 6 & 2 & 7 \end{bmatrix}$ (each element is a cost, ...
1
vote
1answer
51 views

What is the intuition for two player games, mixed strategies are computed with respect to pure strategies instead of mixed strategies?

Let $x$ be the mixed strategy of player $1$ Then the mixed strategy for player $1$ is calculated with respect to $[1, 0], [0, 1]$, the pure strategies of player $2$. i.e. $x^*$ = $\max \min x^TA([1,...
0
votes
1answer
53 views

Using trigonometry to calculate a players angle of movement according to mouse position in a game

This is a question related to programming but it is mostly pure mathematics and that is why I am asking it here. Please don't tell me to move this to the Programming Stack Exchange. It is here for a ...
0
votes
1answer
67 views

Nash equilibrium for n players game

There is a question that I am trying to solve but I am not sure about my approach and is hoping I could get some help. Here is the question: There are $n$ companies sharing a water reservoir, let's ...
0
votes
1answer
43 views

Mechanism design with known utilities (game theory)

I'm trying to prove that in an n-party setting, where each party has a private value, the dominant strategy is always to reveal it. I'm assuming that parties only care about monetary payoffs and ...
1
vote
0answers
37 views

Optimizing generalized ternary search

There are $N$ socks numbered $1$ to $N$, one containing a gift. Dave needs to find the sock with the gift. He can ask some questions in order to find that sock: in each question, Dave chooses $2$ ...
0
votes
0answers
84 views

Find the mixed strategy Nash equilibria in the investment race

This is Exercise 35.2 in Rubinstein's "A Course in Game Theory". This problem is very difficult. The lecturer gave us the answer but it's very hard to understand. I paste the problem here: Two ...
1
vote
1answer
29 views

Question about usage of $\leq$ in definition of Nash equilibrium

Quick definition: Given $g$, a strategy N-tuple $u^* = (u_1^*,...,u^*_N)$ is said to be a Nash equilibrium if: $$J_i(u_i^*, u^*_{-i}) \leq J_i(u_i, u^*_{-i}), i \in N$$ where $J$ is ...
1
vote
1answer
83 views

What is the quickest way to find Nash equilibria in two player bimatrix game?

Suppose the cost/penalty matrix of a game is given as: $$M = \begin{bmatrix} (-5,-5) & (0,0) \\ (0,0) & (-3,-3) \end{bmatrix}$$ Then the game as two equilibria $(u_{11},u_{21})$ and $(u_{12},...
1
vote
1answer
37 views

Can someone please help me understand what a “player set” is in extensive form game

my text defines player set as: In N-player game $g$, each non-terminating node is partitioned into $N+1$ sets $g^0, ... g^N$. These are player sets. However it makes no attempt to identify ...
2
votes
0answers
108 views

A fashion victim puzzle

Consider $n \in \mathbb{N}$ fashion-sensitive kids, each wearing a T-shirt; for simplicity, kid $i \in \{1, \ldots, n\}$ initially wears shirt $i$. Tastes over the shirts are summarized in an $n \...
2
votes
0answers
51 views

Stable Marriage algorithms other than Gale-Shapely?

I've looked around lot and I haven't been able to find any algorithms for to the traditional stable marriage problem (I'm not talking about any of its variants like the roommate problem) besides the ...
0
votes
0answers
30 views

super-additive, sub-additive, and shapely value limitations?

I am working on the coalition formation. Most of the scientist used concept of shapely value for distributing the utility among the members of coalition. Up to my understanding, shapely value is good ...
0
votes
3answers
153 views

Stone, Paper, Scissors Game Winning Probability between two players in 1 match [closed]

I am required to find winning probability and algorithm of winning a game between two players in the above mentioned game. The catch is to find the winning stone, paper, scissor pattern so that ...
1
vote
1answer
129 views

Expected Utility Method and a Repeated Game Solution [closed]

I am trying to replicate Bruce B. de Mesquita's (BDM) results on political game theory for prediction. Based on where actors stand on issues, their capabilities, salience, BDM's method attempts to ...
0
votes
1answer
115 views

Average score for a Quiz based on recent performance

A quiz always has 10 questions. Correct answer results in 1 mark. No negative marking. A user can take the quiz as many times as he likes. I want to show his 'Average Score' based on last 5 quiz ...
1
vote
1answer
97 views

Can a transitive relation be represented by a utility function?

I am currently studying for my Game Theory exam and came across a question that seems pretty basic but somehow can't wrap my head around. So if you could share some insight with me, that would be ...
1
vote
1answer
52 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
90 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
200 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
88 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
197 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
1answer
201 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
40 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
40 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$, ...