The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
104 views

A bound on the number of bilinear functions needed in order to obtain the minmax

For $n\in\mathbb N$, let $\Delta(n)=\{x\in\mathbb R^n:x_i\geq 0, \sum_ix_i=1\}$ be the set of probability vectors in $\mathbb R^n$. Is there a function $m:\mathbb N\to\mathbb N$ such that for any ...
-1
votes
1answer
167 views

To what equal constant in the Gibbs lemma

The Gibbs lemma is broadly used in games theory and in mathematical economics (optimal distributions of resourses, Cournot competition e.t.c.). Here it is: Lemma (Gibbs). $f_1,f_2,\ldots,f_n$ be ...
14
votes
0answers
456 views

The multiplication game on the free group

Fix $W\subseteq\mathbb F_2$ and consider the following two-person game: Player 1 and Player 2 simultaneously choose $x$ and $y$ in $\mathbb F_2$. The first player wins, say one dollar, iff $xy\in W$. ...
12
votes
0answers
193 views

Is the game Hanabi NEXPTIME-complete?

The game Hanabi is a cooperative, hidden-information game. You can read the rules elsewhere, but broadly speaking the players are attempting to cooperatively build a fireworks display by playing cards ...
8
votes
0answers
2k views

Group Theory, Game Theory, a bit of Philosophy and a post in Tao's blog

I've decided to write this post after reading the incredibly beautiful and highly recomended post by Terence Tao http://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-...
6
votes
0answers
261 views

Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...
6
votes
0answers
254 views

Identification of a curious function

The following question was asked on math.stackexchange, but there were no replies. During computation of some Shapley values (details below), I encountered the following function: $$ f\left(\sum_{k \...
5
votes
0answers
211 views

When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods. We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...
5
votes
0answers
621 views

Coin Toss Probabilities like Penney's Game

Generate a binary number, using coin toss. Until you receive a predefined terminating sequence. What is the probability that the number is a multiple of some $k$. For example, the terminating ...
4
votes
0answers
86 views

Combinatorial fairness property in division of goods

Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
4
votes
0answers
147 views

Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...
4
votes
0answers
166 views

Examples of functions from matrices to real numbers with certain properties

Let $M(\mathbb{R})$ be the set of all matrices (of any size) over $\mathbb{R}$. Let $v : M(\mathbb{R}) \rightarrow \mathbb{R}$ be a function which satisfies the following 5 properties: If $\mathbf{...
4
votes
0answers
247 views

References for this game

I would like to know how the following game is known in the literature and, possibly, to have references for related papers. Description of the game: Fix a space $X$ and two Borel probability ...
3
votes
0answers
170 views

What mathematical models can analyze and optimize systems based on gossip?

I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as people gossiping about stuff. System description: We have a ...
2
votes
0answers
33 views

How to model how players affect each others in a cooperative game?

The Shapley value is a very useful concept to evaluate the importance/contribution of a player based on how he affects different possible coalitions. Now based on this information, is it possible to ...
2
votes
0answers
88 views

On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$. Denote concatenated pair $[uv]$. Denote $$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$ collection of pairs with Hamming distance $1$ from $[uv]$ string ...
1
vote
0answers
45 views

Projecting on a convex compact polytope with special form

Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
1
vote
0answers
129 views

Convergence proof for fictitious play!

In "Fictitious play property for games with identical interests" by D. Monderer and L.S. Shapley, the convergence of fictitious play to a Nash equilibrium is proved for a potential game with players ...
1
vote
0answers
107 views

optimal strategies for 2-player zero-sum games of perfect information

I asked essentially this on math.SE slightly more than 3 days ago, and it hasn't received any answer there. Do finite-state 2-player zero-sum games of perfect information with only win-draw-loss ...
1
vote
0answers
290 views

What is known about multiplayer poker with flop?

I am interested in the following simplified version of poker. Each player gets a card (for example, either A or B). Then they bet knowing their own cards (for example, the pot initially has 1 euro, ...
1
vote
0answers
312 views

Allocation game optimal strategy

There are two players, Alice and Bob. There is an initial pool of 100 dollars. Alice proposes an allocation of the dollars (real numbers, not necessarily integers), and Bob can either accept or reject....
0
votes
0answers
46 views

Factorization (separation?) of n-player game into p-player game and (n-p)-player game

When is an n-player game factorizable (separable?) into a p-player game and an (n-p)-player game? Apologies if this is known among game theorists already - but it leads to further questions, ...
0
votes
0answers
388 views

On the Theory of Infinite Step Processes of Sequential Decision Making

On the border of Set Theory and Game Theory there is a broad class of Infinite Step Processes of Sequential Decision Making that can be characterized by the main following property: a Future ...
0
votes
0answers
128 views

Maximizing Expected Utility

I am currently trying to solve a maximization problem given by $\max_{f(x)} \int_0^1 \int_\mathbb{R} (c-y\cdot f(x)-d\cdot (x+f(x)-b)^2) \ h(x) \ dx \ dy$. Or in other words, I have a utility ...
0
votes
0answers
211 views

Game Theory - need references on analysis of particular game

My hobby AI research have led me to a thorethical game of particular design. As design is pretty simple, I was sure that such game has well-known name. But my question on math.stackexchange, where I ...
0
votes
0answers
761 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
0
votes
0answers
72 views

Computing maximum point for minimal function of a family of linear functions

Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such that:...
0
votes
0answers
432 views

Proof of Upper bound of price of anarchy in local connection game

I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic ...