Theoretical question related to Computer Science and Game Theory

learn more… | top users | synonyms (2)

-1
votes
0answers
60 views

“Simple” algorithm for 1x1 sliding blocks

I'm working on a problem involving a type of sliding block game, and stumbled upon apaper of Hearne and Demaine where they introduced the "Nondeterministic Constraint Logic" machine as a framework for ...
4
votes
1answer
188 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
45 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 ...
8
votes
2answers
205 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
165 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
53 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
159 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
115 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
281 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
103 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
46 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
91 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
312 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
220 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
128 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
76 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
60 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
220 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
157 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
298 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
177 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 ...
2
votes
2answers
190 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
470 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
268 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
991 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
175 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
259 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
414 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 ...
2
votes
2answers
676 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
288 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
273 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
255 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
719 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
148 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
228 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
310 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
188 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
141 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
645 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 ...
2
votes
2answers
1k views

Solving a Min/Max equation set

In solving a certain game, I've ended up with a set of equalities like these: ...
0
votes
2answers
217 views

What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD

I have been thinking about Pspace in conjunction with searching for a Natural Notion of Stablilty for Complex Dynamical Systems. A natural question in this direction is the Nash equilibrium. ...
3
votes
1answer
179 views

Do buyers bidding for sellers and sellers bidding for buyers produce equivalent outcomes?

Google adwords is a well known application of algorithmic game theory. It has a system wherein buyers of ad placements bid to put their ads up on various sellers websites, then pay the second bid ...
8
votes
1answer
264 views

What is the Complexity Classification of Portfolio Theory in Financial Economics?

As you will all know, there is ongoing fall out from the Financial Crisis of 2008. I was thinking about how complexity theory fitted into all this, when I realised I did not know the basic complexity ...
3
votes
3answers
686 views

What games best represent well-known computer science problems?

I heard that Clue is a board game that is related to the NP-complete traveling salesman problem. What are other games that relate to important computational problems?
7
votes
1answer
550 views

The Optimum Strategy to Find the Best Parking Slot Along a Busy Road

Imagine that you are going to a shop. In front of the shop there are $N$ number of parking slots. That shop is located at the $k^{th}$ slot. As you drive along the parking slots, you notice that for ...
9
votes
2answers
414 views

Forcing an honest behavior

How can you force a party to be honest (obey protocol rules)? I have seen some mechanisms such as commitments, proofs and etc., but they simply do not seem to solve the whole problem. It seems ...