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
17 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 ...
1
vote
0answers
75 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 ...
2
votes
0answers
45 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
42 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 ...
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
82 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
27 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
54 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
12 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
56 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
41 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
135 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
66 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
56 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
945 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
31 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
45 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 ...
0
votes
1answer
48 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
64 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
72 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
27 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
75 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 ...
1
vote
1answer
34 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
105 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
44 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
27 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
131 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
120 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
97 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
91 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
46 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
89 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
179 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
174 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
187 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
39 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
193 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
144 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
70 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, ...
2
votes
1answer
99 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 ...
6
votes
0answers
256 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$ ...