Analysis of the gift exchange problem

zbMATH Open1430.05003arXiv1701.08394MaRDI QIDQ2363700FDOQ2363700

Doron Zeilberger, N. J. A. Sloane, David Applegate, Moa Apagodu

Publication date: 26 July 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In the gift exchange game there are n players and n wrapped gifts. When a player's number is called, that person can either choose one of the remaining wrapped gifts, or can "steal" a gift from someone who has already unwrapped it, subject to the restriction that no gift can be stolen more than a total of sigma times. The problem is to determine the number of ways that the game can be played out, for given values of sigma and n. Formulas and asymptotic expansions are given for these numbers. This work was inspired in part by a 2005 remark by Robert A. Proctor in the On-Line Encyclopedia of Integer Sequences.

Full work available at URL: https://arxiv.org/abs/1701.08394

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Optimal incentives under gift exchange
• The swapping problem
• The Secret Santa Problem
• On the generalized shuffle-exchange problem
• scientific article; zbMATH DE number 1353830
• scientific article; zbMATH DE number 1816801
• Gift equilibria and Pareto optimality reconsidered
• On the complexity of exchanging

zbMATH Keywords

hypergeometric functionsrestricted Stirling numbersset partitionsBessel polynomialsAlmkvist-Zeilberger algorithmgift swappingWilf-Zeilberger summation

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of partitions of integers (05A17) Recurrences (11B37) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Probabilistic games; gambling (91A60)

Cites Work

• Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Applications of Basic Hypergeometric Functions
• The J.C.P. miller recurrence for exponentiating a polynomial, and its q- analog
• A New Class of Orthogonal Polynomials: The Bessel Polynomials
• On Solutions of x^d = 1 In Symmetric Groups
• Title not available (Why is that?)
• Resurrecting the asymptotics of linear recurrences
• Bessel polynomials
• The method of differentiating under the integral sign
• An algorithmic proof theory for hypergeometric (ordinary and ``\(q\)) multisum/integral identities
• Reciprocity for multirestricted Stirling numbers
• Restricted Partitions of Finite Sets
• Analysis of the gift exchange problem
• Title not available (Why is that?)

Cited In (3)

• On the Stirling numbers associated with the meromorphic Weyl algebra
• Analysis of the gift exchange problem
• The Secret Santa Problem

Uses Software

• OEIS
• MultiZeilberger
• DEtools

This page was built for publication: Analysis of the gift exchange problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363700)