Theoretical question related to Computer Science and Game Theory

learn more… | top users | synonyms (2)

10
votes
0answers
66 views

Computationally bounded version of Nash equilibrium?

I'm wondering if there is a computationally bounded version of the Nash equilibrium concept, something along the following lines. Imagine some kind of two-player perfect information game which is ...
0
votes
0answers
29 views

Game Tree Evaluation [closed]

I was reading the chapter Game-Theoretic Techniques of Randomized Algorithm by Motwani and Raghavan and there is something I do not understand. It says the "...cost of evaluating any instance of ...
0
votes
1answer
77 views

How to prove the existence of a pure Nash equilibrium?

I have a game as given by the table below. I would like to prove that the game has always at least one pure Nash equilibrium (NE). I used a computer program and in fact the game has a pure NE. So, I ...
7
votes
2answers
158 views

Implementation of surreal numbers for games

There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
-3
votes
1answer
81 views

Iterated Prisoner's Dilemma Algorithms

While reading a post on Scott Aaronson's blog about Eigenmorality, I ran across the idea of the iterated prisoner's dilemma tournament. I've studied some TCS on my own, but had never really thought ...
1
vote
1answer
91 views

Generalized Secretary Optimization Problem

In the standard Secretary Problem, the goal is to hire the best secretary from a list of candidates. I've recently witnessed a failed hiring attempt for a needed position and it inspired a similar ...
9
votes
1answer
234 views

Secretary hiring game

This is an extension of the classical secretary problem. In the hiring game you have a set of candidates $\mathcal C=\{c_1,\ldots,c_N\}$, and order on how skilled each worker is. W.l.o.g, we assume ...
22
votes
2answers
529 views

Is this variation of TQBF still PSPACE-complete?

Deciding if a quantified boolean formula such as $\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$ always evaluates to true is a classical PSPACE-complete ...
4
votes
1answer
207 views

Why is computing pure Nash equilibria NP-complete?

In this paper, it is claimed that computing pure-strategy Nash equilibria of games in standard normal form is NP-complete. This confuses me, because I do not understand why it is hard to guess the ...
0
votes
1answer
46 views

How to define the _regret_ in multiagent systems? Any good definition please?

I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent ...
9
votes
2answers
235 views

For which families of graphs is Generalized Geography in $P$?

As @Marzio mentioned, the following game is known as Generalized Geography. Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows: At each turn (two players ...
1
vote
0answers
175 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
3
votes
0answers
60 views

Social choice theory, preference aggregation data sets

I do computational research on preference aggregation. I am quite interested in Kemeny Optimal Aggregation. However I do not find much useful data for preference aggregation in context of social ...
0
votes
0answers
161 views

Message-based games with ambiguous communication

Consider the following game. We are given two sets of sentences $S_1,S_2$ where $S_1$ is the set of "ambiguous sentences" and $S_2$ is the set of "explicit sentences". Each ambiguous sentence $s \in ...
3
votes
1answer
128 views

How do you compute the fixed point of a best-response function efficiently?

I have a polynomial time best-response function that has the same properties as a game-theory game (convexity, compactness, set-valued). I don't know that much topology, but my understanding is that ...
3
votes
2answers
295 views

Polynomial algorithm for correlated equilibrium

I searched through the web for a polynomial algorithm for correlated equilibrium. I found a lot of papers by C.H. Papadimitriou that proposes a solution using the ellipsoid algorithm. Is there a ...
1
vote
1answer
106 views

Some problems about arrow's theorem and social choice [closed]

I'm just started lecture myself about arrow's theorem. There are some problems which make me confused. ARROW'S THEOREM: Any constitution that respects transitivity, independence of irrelevant ...
3
votes
0answers
49 views

Lower Bound on Zero-order Regret

Here is a brief summary of the experts framework: Given $n$ experts who either give correct or wrong advice for each round $t\in [T]$, an algorithm is required to give a best prediction for each round ...
4
votes
0answers
93 views

Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?

A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to ...
1
vote
0answers
458 views

From CHSH inequality to CHSH game

I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
10
votes
2answers
225 views

How hard is it to count the number of local optima for a problem in PLS?

For a polynomial local search problem, we know that at least one solution (local optimum) must exist. However, many more solutions could exist, how hard is it to count the number of solutions for a ...
4
votes
3answers
135 views

Existence of equilibria in infinite two players zero sum extensive form games with perfect information

I am looking for a study that has examined whether and under which conditions (if any), an infinite and of possibly infinite horizon two person zero sum extensive form game with perfect information ...
1
vote
0answers
95 views

Relation between static Nash equlibria and dynamic equlibria

I am working on Normal form continuous games. I am not very familiar with dynamic game theory. I would like to know if there is any relation between static Nash equilibria and dynamic equilibria. If ...
1
vote
1answer
61 views

Terminology for games with incomplete information and no prior beliefs

Can anyone please tell me what is the term used for games with incomplete information and there are no prior beliefs about other players' private information. For example, let $ v_i(a_i,\theta_i) $ ...
8
votes
4answers
231 views

Examples of Computer-Found Optimal Strategies in Games

I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.
7
votes
1answer
170 views

When do $\epsilon$-Nash equilibrium strategies converge to Nash Equilibrium strategies?

Nash Equilibria are uncomputable in general. An $\epsilon$-Nash equilibrium is a set of strategies where, given the opponents' strategies, each player obtains within $\epsilon$ of the maximum possible ...
11
votes
1answer
300 views

Complexity of finite-state partial information games

Given a deterministic partial-information zero-sum game with only finitely many states, whose possible outcomes are [lose,draw,win] with values [-1,0,+1] respectively, what is the ...
1
vote
1answer
71 views

Multiunit Auction

Consider multiunit auction (as it is defined in Introduction to Mechanism Design by Noam Nisan) , where $k$ identical units of some good are sold in an auction (where $k < n$). In the simple case ...
6
votes
1answer
187 views

External Regret and Nash Equilibrium

There is a well known fact that we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games. The proof can be found in the survey ...
3
votes
2answers
195 views

AI strategies for losing positions

I have a card game that I am analyzing with Maple. Actually, it's a series of card games, one for every parameter k, where k is a natural number (representing the number of ranks of cards used in the ...
12
votes
2answers
484 views

A game of positioning overlapping circles to maximize travel time between them

I encountered the following game. I'll migrate this as requested. A bug is visiting circles, and an adversary wishes to maximize his travel time. The adversary places a circle on every turn. The ...
1
vote
0answers
275 views

How can I find all numbers for which the XOR-sum is 0?

Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied: $x_1 \oplus x_2 \oplus ...
2
votes
4answers
2k views

Applications of Game theory in computer science?

As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided ...
-5
votes
1answer
1k views

Developing A Perfect Tic-Tac-Toe Player - AI [closed]

I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that ...
7
votes
0answers
189 views

mixed vs behavior strategies for zero-sum game with infinite extensive form

This is a crosspost of this post on math.stackexchange, which didn't get any responses. For two-player games given in extensive ("game tree") form, there are several natural ways to define randomized ...
3
votes
1answer
273 views

How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

The following question was first presented in MATHEMATICS of StackExchange. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such ...
14
votes
2answers
630 views

White elephant gift exchanges: mechanisms for fair division

A popular game at holiday parties in North America is the white elephant gift exchange. In brief (ignoring variations) it works as follows: There are $n$ people and $n$ wrapped gifts. Players are ...
3
votes
2answers
850 views

Compute Nash Equilibrium for 2-player games

I want to compute a mixed strategy that will be the Nash Equilibrium of the game. I have used my knowledge in order to create the system for the mixed strategy. I concluded on a system with 3 ...
2
votes
2answers
306 views

What does mechanism design constitute? (Game Theory)

I've been reading about mechanism design and the field seems a little abstract, in that I cannot ascertain whether a certain approach towards solving games falls under mechanism design. Let me ...
9
votes
2answers
275 views

Understanding a Mechanism Design Proof

I have been struggling with the technical details of a proof concerning auction theory in this paper: http://users.eecs.northwestern.edu/~hartline/omd.pdf Specifically, Theorem 2.5: The necessary ...
9
votes
1answer
258 views

A simplified version of card game Winner

I've asked this problem in MathOverflow, without any satisfactory answer. Consider the following two-player game, which is a simplification of the card game called Winner. (The following formulation ...
15
votes
2answers
774 views

How hard is Mafia?

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29. Basically, it works as follows: At the beginning, ...
6
votes
2answers
150 views

Can a non-competitive deterministic algorithm be k-competitive if randomized?

Let's say there is a problem in which all possible deterministic online algorithms tha solve this problem are not-competitive. Does this mean that a randomized online algorithm for the same problem ...
3
votes
0answers
235 views

Graph connectivity related game [closed]

I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
20
votes
4answers
2k views

Permutation game redux

This is a restatement of an earlier question. Consider the following impartial perfect information game between two players, Alice and Bob. The players are given a permutation of the integers 1 ...
0
votes
0answers
332 views

Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

This one's hard, so all help really appreciated! I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it ...
1
vote
0answers
189 views

Can Canetti's composition theorem be used to prove composition of Nash equilibrium?

This might be a very simple doubt, but I am not able to prove or disprove it rigorously. Canetti's work on "Security and Composition of Multiparty Cryptographic Protocols: JoC 2000" allows us to ...
4
votes
1answer
233 views

A protocol for honest compromise

This question did not originate in my research, but I think it's interesting. It is somewhat underspecified. I'd be interested in an example in any particular case. We have $n$ parties that between ...
10
votes
3answers
148 views

Refinements of pair approximation for network analysis

When considering interactions on networks, it is usually very hard to calculate the dynamics analytically, and approximations are employed. Mean-field approximations usually end up ignoring the ...
13
votes
3answers
674 views

Sources for Algorithmic Evolutionary Game Theory

I use the title term in a very loose sense. There is a significant amount of work on evolutionary game theory, including its mathematical foundations. I was recommended "Evolutionary Games and ...