Skip to main content
8 votes
Accepted

Among an infinite variety of n x n board games, why are some interesting?

I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game ...
Marzio De Biasi's user avatar
6 votes

Can generalized twenty questions be solved by a greedy algorithm?

Your question is not very different from set cover (it would be exactly set cover if you stopped as soon as you found a set containing $x$ rather than keeping going until you have determined $x$) and ...
David Eppstein's user avatar
6 votes
Accepted

Can generalized twenty questions be solved by a greedy algorithm?

No. There's a huge literature on the topic, called combinatorial search theory, you can read more about these types of questions there. The simplest example that I could think of is the following. ...
domotorp's user avatar
  • 14k
4 votes

How much information does it take to specify, not each member of a group, but any one member?

This answer continues Peter's. It assumes Peter's interpretation of the problem and verifies that with that interpretation the function $f(S)=\min S$ is optimal, as Peter suggested. Here's the ...
Neal Young's user avatar
  • 10.8k
3 votes
Accepted

Winning strategy in the game of triplets

This isn't a complete proof, but here's some justification for why known conjectures imply that the game may be computationally hard to solve. Namely, I'm going to argue that finding the correct first ...
Yonatan N's user avatar
  • 1,642
3 votes

How hard is Hex from a symmetric position?

Finding a winning move in symmetric positions in Hex is PSPACE-complete First, let's define our problem, and call it SYMHEXMOVE: Take as an input: a symmetric Hex position Output: any move which is ...
Kevin Wang's user avatar
2 votes

The logic in derivation of virtual welfare

I think I've gotten part of the answer. The above statement actually says that for any truthful mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for ...
xyguo's user avatar
  • 191
2 votes

Implementation of surreal numbers for games

Here is an implementation of Surreal Numbers in a relatively new language, Julia. https://github.com/mroughan/SurrealNumbers.jl Described at https://www.sciencedirect.com/science/article/pii/...
Matt's user avatar
  • 21
2 votes

Is there a natural problem on the naturals that is NP-complete?

Our FOCS'17 paper on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number $C$ of integers in the input, say $C< 220$. It is different from ...
Igor Pak's user avatar
  • 812
2 votes

How much information does it take to specify, not each member of a group, but any one member?

This is a request for clarification and a partial answer, but I'm posting it as an answer because there is no way for it to fit in a comment. Is the OP asking for how much information you need to send,...
Peter Shor 's user avatar
1 vote
Accepted

Auction theory - Selling Multiple Items via Social Networks

the calculation of $\mathcal{SW}_{-D_i}$ and $\mathcal{SW}_{-C_i^\mathcal{K}}$ is incorrect. There are still $\mathcal{K}$ items to be allocated in both allocations, so for node $D$, the first is 20+...
Dengji Zhao's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible