Questions tagged [game-theory]
Theory of dynamic processes with several competing actors that try to achieve some goal in a strategic way.
153 questions
-3 votes
0 answers
30 views
Can We Design Incentive-Compatible LLM Judge Certification Beyond Shared Information Invariants? [closed]
The TVD-MI (Total Variation Distance–Mutual Information) framework provides a reference-free method for certifying LLM judges—models that evaluate outputs like code correctness or theorem proofs ...
- 3,124
1 vote
1 answer
145 views
How to model adversarial moves (e.g. chess) with Boolean Satisfiability?
I'm trying to solve the game of chess with a Boolean Satisfiability Sovler. For that, I implement a C/C++ program with some non-deterministic values, convert this program to a Boolean Formula (CNF) ...
- 165
1 vote
0 answers
47 views
Can stochastic optimization algorithms achieve convergence in $\Theta(N^{m^{1/s}} / \log^k N)$ with $m > 1, s > 1, k \gg m$? [closed]
This specific convergence rate with dominant logarithmic factors is indeed highly desirable for large-scale systems. While there's a rich body of work on stochastic approximation and equilibrium ...
3 votes
2 answers
240 views
Show that in every pure SPNE, the first agent weakly prefers their own bundle to any other
Suppose we have a set $N$ of $n$ players and a set $M$ of $m$ items. We are given a matrix $P_{n \times m}$ whose element $p_{ij} \geq 0$ $(i \in N, m \in M)$ denotes the valuation of good $j$ by ...
- 108
3 votes
1 answer
119 views
Show that both the standard and bottom-up greedy strategies give the same outcomes
Suppose there are $n$ players $N = \{p_1, \cdots, p_n\}$ and a set $M$ of $m \geq n$ items that are to be claimed. Suppose further that players have strict, additive, ordinal rankings $\succ_{p_j}$ ...
- 108
0 votes
0 answers
60 views
need board evaluation heuristics for ultimate tic tac toe
I am trying to code a bot that can play ultimate tic tac toe and beat other bots https://en.wikipedia.org/wiki/Ultimate_tic-tac-toe. I am doing so using minimax with alpha-beta pruning to limited ...
- 1
2 votes
2 answers
267 views
Why does it make sense to minimize regret?
In fields such as game theory and reinforcement learning, it is standard to consider the regret-minimization strategy. I don't get the motivation for the definition. Yes, doing your best under worst-...
- 171
1 vote
1 answer
76 views
In multi-agent RL stochastic games (multi-agent version of an MDP), why does the Nash equilibrium policy only depend on the state, not history?
I am studying from the MARL textbook by Albrecht, Christianos and Schäfer. They define a stochastic game in Sec 3.3 as the multi-agent version of an MDP. In Fig 3.3 (pg 50) they give an intuition for ...
1 vote
1 answer
321 views
Nash equilibrium details for Leduc Hold'em
Can anyone point me to the details of a verified Nash equilibrium for Leduc Hold'em? I have an implementation of Counterfactual Regret Minimization (CFR) that I am testing with Leduc, and would like ...
- 111
1 vote
0 answers
40 views
Multiplayer one-round one-move voronoi game on graphs
I'm trying to solve a variant of Voronoi Game. Given a Graph $G=(V, E)$, with uniform distance $d(E)=1$, a subset of the vertices $\hat{V} \subseteq V$ are vertices of interests. $k$ players take ...
- 111
1 vote
0 answers
35 views
Examples of challenging general-sum matrix games
Solving $N$-player general sum matrix games is known to be PPAD-complete, and even for two players algorithms such as Lemke-Howson can take exponential time in the worst case. On the other hand, ...
- 111
1 vote
0 answers
38 views
Stable Flow Problem with one sided preferences
I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
- 11
4 votes
0 answers
244 views
Game of permutations as a minimization problem
Consider the following "game". There is an ant on a strip of length N. The ant can perform the following actions: move left, move right, and paint the cell he is on with white or black. The ...
- 41
1 vote
0 answers
69 views
Which good should I split?
One classic fair division allocation problem is to allocate indivisible goods among agents with respect to envy freeness (no agent envies another agent). In my settings, all the goods are divisible (...
- 269
0 votes
1 answer
292 views
BFS on a graph and BFS on a tree
I found the following question in my book and I have no clue on what the answer should be: What is the condition on search graph so that BFS Algorithm for graph and BFS Algorithm for tree generate ...
- 1