Theoretical question related to Computer Science and Game Theory
0
votes
0answers
12 views
Ratio of the External and Swap Regret is Unbounded
Sorry if it's not an appropriate place for my question, however in my opinion the question touch upon advanced topic of game theory and have significant meaning in defining the ratio between different ...
0
votes
0answers
23 views
Finding the potential function for a finite game
Suppose that there is a strategic game $G=(N,A,u)$. The agent set $N$ and all actions sets $A_i$, $i = 1, 2,\dotsc, |N|$, are all finite. The utility functions $u = (u_1, u_2, \dotsc, u_{|N|})$ are ...
1
vote
0answers
28 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
38 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) $ ...
2
votes
2answers
89 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 more optimal strategies.
-1
votes
0answers
56 views
Finding a winning strategy for toads and frogs [closed]
Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm ...
5
votes
0answers
44 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 ...
5
votes
1answer
184 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
45 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
114 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
1answer
117 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
401 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
233 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
479 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
278 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
133 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
193 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 ...
12
votes
2answers
229 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 ...
0
votes
0answers
96 views
Nash Equilibrium in extensive form games
I want to find Nash Equilibrium in a game of Inperfect Information.I know the backward algorithm which is uses Perfect information games but I have a very small game of Inperfect Information and I ...
0
votes
0answers
336 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
230 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
266 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 ...
8
votes
1answer
243 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
631 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
138 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
190 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 ...
19
votes
4answers
1k 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
233 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
179 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
230 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
95 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 ...
10
votes
1answer
361 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
687 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
188 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
234 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 ...
4
votes
3answers
610 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?
0
votes
1answer
229 views
Puzzle on Wythoff's game [closed]
There is an $(n+1)\times(n+1)$ chessboard. A queen is placed on a cell $(x,y)$. Each player takes turn moving the queen. A queen’s move is considered valid if the queen moves to the left, or bottom or ...
7
votes
1answer
491 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
398 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 ...
9
votes
1answer
155 views
What's the complexity of this estate-division game?
Alice and Bob are splitting their deceased uncle Charlie's estate (a finite collection $X$ of discrete items) according to his wishes. First A picks an item, then B, then A, and so on.
Alice and Bob ...
9
votes
3answers
265 views
Keyword selection problem in search engine marketing auction
First of all, I am still not sure whether cstheory is well adapted for this question, so I won't be offended if the crowd thinks it is not the case...
In search engine marketing, several problems are ...
16
votes
1answer
1k views
Choosing a research topic using game theory
This recent game theory question got me thinking (this is a tangent, of course): Is it possible to efficiently optimize a personal strategy for choosing research questions to work on using game ...
5
votes
4answers
698 views
Is this game solvable?
Suppose we have two stacks of cards on a table. On each turn, each of two players draws a card from the top of one of the stacks. The game ends when there are no cards left in either stack. The person ...
20
votes
4answers
872 views
Social choice, arrow's theorem and open problems ?
Last few months I started to lecture myself on social choice, arrow's theorem and related results.
After reading about the seminal results, I asked myself about what happens with partial order ...
2
votes
2answers
309 views
Generate a sequence of numbers
I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$.
Another agent $B$ ...
30
votes
1answer
1k views
Refereed games with uncorrelated semi-private coins
I was (and still am) really interested in the answer to this question, because this is an interesting variation on the complexity of games which hasn't been resolved, so I offered a bounty. I thought ...
16
votes
1answer
510 views
Separation between coarse correlated equilibria and correlated equilibria
I am looking for examples of techniques for proving price of anarchy bounds that have the power to separate the price of anarchy over coarse correlated equilibria (the limiting set of ...
10
votes
3answers
448 views
Algorithms for Nash equilibrium computation.
I searched the forum to see if this has been asked before, and while algorithmic game theory is discussed, I couldn't find this particular issue addressed. I am trying to figure out what the best ...
10
votes
5answers
438 views
Algorithmic game theory - nonstandard equilibrium concepts?
I'm beginning my studies of algorithmic game theory, and it seems that the equilibrium concept usually taken is that of a fixed point in a graph. However, have people looked at alternative equilibrium ...
