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

3
votes
0answers
30 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
24 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
17 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
32 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
11 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
18 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
37 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
32 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
39 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
40 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
41 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 ...
25
votes
1answer
899 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
27 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
23 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
24 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
30 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
35 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
55 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
40 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
36 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
38 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
26 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
60 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
33 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
99 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
37 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
23 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
111 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
90 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
73 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
86 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
41 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
88 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
162 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
87 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
157 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
41 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
165 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
38 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
168 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
142 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
66 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
97 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
236 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
5answers
295 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
229 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
81 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
229 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 ...
2
votes
2answers
248 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 ...