Theoretical question related to Computer Science and Game Theory

learn more… | top users | synonyms (2)

3
votes
0answers
34 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
120 views

What is the Unique Game Conjecture? [closed]

What is the unique game conjecture in relatively simple words? What are the consequences of proving it or disproving it? Does it has any relation to Game Theory? Why there is "game" in the name?
0
votes
0answers
147 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
93 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
275 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
102 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
44 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
90 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
207 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
215 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
124 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 ...
0
votes
0answers
61 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
71 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
212 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
145 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
69 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
170 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
187 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
461 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
260 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
878 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
986 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
172 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
247 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
388 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
540 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
282 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
272 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
692 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
224 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
302 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
187 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
232 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
137 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
616 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
207 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
255 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
660 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
539 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
413 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
156 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
270 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 ...