Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
- URL: http://arxiv.org/abs/2402.08547v2
- Date: Sun, 18 Feb 2024 22:33:10 GMT
- Title: Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
- Authors: Simina Br\^anzei and MohammadTaghi Hajiaghayi and Reed Phillips and
Suho Shin and Kun Wang
- Abstract summary: We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake.
We consider two versions: sequential, where Bob observes Alice's cut point before choosing left/right, and simultaneous, where he only observes her cut point after making his choice.
- Score: 10.50673995077851
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the setting of repeated fair division between two players,
denoted Alice and Bob, with private valuations over a cake. In each round, a
new cake arrives, which is identical to the ones in previous rounds. Alice cuts
the cake at a point of her choice, while Bob chooses the left piece or the
right piece, leaving the remainder for Alice. We consider two versions:
sequential, where Bob observes Alice's cut point before choosing left/right,
and simultaneous, where he only observes her cut point after making his choice.
The simultaneous version was first considered by Aumann and Maschler (1995).
We observe that if Bob is almost myopic and chooses his favorite piece too
often, then he can be systematically exploited by Alice through a strategy akin
to a binary search. This strategy allows Alice to approximate Bob's preferences
with increasing precision, thereby securing a disproportionate share of the
resource over time.
We analyze the limits of how much a player can exploit the other one and show
that fair utility profiles are in fact achievable. Specifically, the players
can enforce the equitable utility profile of $(1/2, 1/2)$ in the limit on every
trajectory of play, by keeping the other player's utility to approximately
$1/2$ on average while guaranteeing they themselves get at least approximately
$1/2$ on average. We show this theorem using a connection with Blackwell
approachability.
Finally, we analyze a natural dynamic known as fictitious play, where players
best respond to the empirical distribution of the other player. We show that
fictitious play converges to the equitable utility profile of $(1/2, 1/2)$ at a
rate of $O(1/\sqrt{T})$.
Related papers
- Optimal Strategies for Winning Certain Coset-Guessing Quantum Games [8.03451158784716]
In a recently introduced coset guessing game, Alice plays against Bob and Charlie, aiming to meet a joint winning condition.
We show that the probability of Bob's and Charlie's guesses being simultaneously correct goes to zero exponentially as m increases.
We devised an encoding circuit using only CNOT and Hadamard gates, which could be relevant for building efficient CSS-coded systems.
arXiv Detail & Related papers (2024-10-10T17:42:30Z) - Quantum advantage in a unified scenario and secure detection of
resources [55.2480439325792]
We consider a single task to study different approaches of having quantum advantage.
We show that the optimal success probability in the overall process for a qubit communication might be higher than that for a cbit communication.
arXiv Detail & Related papers (2023-09-22T23:06:20Z) - Offline Reinforcement Learning for Human-Guided Human-Machine
Interaction with Private Information [110.42866062614912]
We study human-guided human-machine interaction involving private information.
We focus on offline reinforcement learning (RL) in this game.
We develop a novel identification result and use it to propose a new off-policy evaluation method.
arXiv Detail & Related papers (2022-12-23T06:26:44Z) - Identifying the value of a random variable unambiguously: Quantum versus classical approaches [44.99833362998488]
Quantum resources may provide advantage over their classical counterparts.
We construct such a task based on a game, mediated by Referee and played between Alice and Bob.
We show that if Alice sends limited amount of classical information then the game cannot be won while the quantum analogue of the limited amount of classical information' is sufficient for winning the game.
arXiv Detail & Related papers (2022-11-16T20:28:49Z) - Two quantum algorithms for communication between spacelike separated
locations [0.7614628596146599]
We argue that superluminal communication is possible through state discrimination in a higher-dimensional Hilbert space using ancilla qubits.
We propose two quantum algorithms through state discrimantion for communication between two observers Alice and Bob.
arXiv Detail & Related papers (2022-09-16T06:54:22Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions.
We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario.
Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
arXiv Detail & Related papers (2022-07-25T18:29:16Z) - Experimental test of Tsirelson's bound with a single photonic qubit [8.8709589922781]
In the Clauser-Horne-Shimony-Holt game, two space-like separated players, Alice and Bob are each assigned a classical bit $a$ and $b$ respectively.
In the game, if the players use the classical strategies, the optimal success probability $w(textCHSH)=0.75$.
Popescu and Rohrlich noted that the perfect success probability $1$ can also be achieved in a more general theory without violating the no-signaling assumption.
arXiv Detail & Related papers (2022-01-25T09:06:53Z) - Almost Optimal Algorithms for Two-player Markov Games with Linear
Function Approximation [92.99933928528797]
We study reinforcement learning for two-player zero-sum Markov games with simultaneous moves.
We propose an algorithm Nash-UCRL-VTR based on the principle "Optimism-in-Face-of-Uncertainty"
We show that Nash-UCRL-VTR can provably achieve an $tildeO(dHsqrtT)$ regret, where $d$ is the linear function dimension.
arXiv Detail & Related papers (2021-02-15T09:09:16Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game.
In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game.
We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
arXiv Detail & Related papers (2020-09-21T17:51:57Z) - Arbitrarily many independent observers can share the nonlocality of a
single maximally entangled qubit pair [4.061135251278187]
We show that arbitrarily many independent Bobs can have an expected CHSH violation with the single Alice.
Our work represents a step towards an eventual understanding of the limitations on how much device-independent randomness can be robustly generated from a single pair of qubits.
arXiv Detail & Related papers (2020-03-26T18:38:56Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.