{
"cells": [
{
"cell_type": "markdown",
"id": "655b08c7",
"metadata": {},
"source": [
"---\n",
"title: \"Scheduling Dashain Tika\"\n",
"subtitle: \"Exact bounds on sitting and standing costs\"\n",
"author:\n",
" - Apoorva Lal\n",
" - Krabbs\n",
"date: 2026-10-21\n",
"jupyter: python3\n",
"keep-ipynb: true\n",
"execute:\n",
" cache: false\n",
" freeze: false\n",
" warning: false\n",
" error: false\n",
"format:\n",
" html:\n",
" theme: cosmo\n",
" toc: true\n",
" number-sections: true\n",
" html-math-method: katex\n",
" self-contained-math: true\n",
" embed-resources: true\n",
" code-fold: false\n",
" output-file: index.html\n",
" include-in-header:\n",
" text: |\n",
" \n",
" typst:\n",
" output-file: tika-scheduling.pdf\n",
" execute:\n",
" echo: false\n",
" papersize: a4\n",
" fontsize: 10.5pt\n",
" margin:\n",
" x: 20mm\n",
" y: 20mm\n",
" number-sections: true\n",
" toc: false\n",
"---\n",
"\n",
"::: {.content-visible when-format=\"html\"}\n",
"[PDF](tika-scheduling.pdf) · [Quarto source](notes.qmd) ·\n",
"[Executed notebook](notes.ipynb) · [Source bundle](tika-scheduling-source.zip) ·\n",
"[Figure files](tika-scheduling-figures.zip)\n",
":::\n",
"\n",
"## The scheduling problem\n",
"\n",
"During Dashain, elders give tika and blessings to younger family members.\n",
"Consider a gathering with the following rule: **every person gives tika to\n",
"everyone younger than them**, one pair at a time. A recipient sits to receive\n",
"tika and eventually stands to leave. Repeating this for each elder can mean\n",
"many sit–stand cycles. The scheduling question is whether changing the order\n",
"can reduce that movement while completing every required tika.\n",
"\n",
"Assume distinct ages and index the $N\\geq2$ people from youngest, $1$, to\n",
"eldest, $N$. Each older person gives exactly once to each younger person, so\n",
"the required directed dyads are\n",
"\n",
"$$\n",
"\\mathcal E=\\{(i,j):1\\leq j\n",
"\n",
"\n"
],
"text/plain": [
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#| label: fig-dyad-comparison\n",
"#| fig-cap: The same six directed dyads in three schedules, read from left to right. Each downward arrow is one tika, from the numbered giver to the numbered recipient. Each continuous band is one seated episode, including its eventual stand-up. The baseline resets the recipient after every tika. Recipient batching is optimal for recipient-only costs; both lower schedules are optimal for equal-cost two-seat service. All costs use e per sit–stand cycle.\n",
"#| fig-alt: Three sequences of six giver-to-recipient dyads. Eldest first has giver episodes 3 and recipient episodes 6, costing 6e for recipients or 9e for both roles. Recipient batching has giver episodes 4 and recipient episodes 3, costing 3e or 7e. Giver blocks with shared handoffs have giver episodes 3 and recipient episodes 4, costing 4e or 7e. Connected bands show retained occupants.\n",
"#| code-fold: true\n",
"#| code-summary: Draw the dyad-by-dyad comparison\n",
"from pathlib import Path\n",
"import matplotlib.pyplot as plt\n",
"from matplotlib.patches import Circle, Rectangle, FancyBboxPatch\n",
"import numpy as np\n",
"\n",
"Path(\"figures\").mkdir(exist_ok=True)\n",
"\n",
"def export_figure(fig, name):\n",
" fig.savefig(f\"figures/{name}.svg\", bbox_inches=\"tight\")\n",
" fig.savefig(f\"figures/{name}.png\", dpi=180, bbox_inches=\"tight\")\n",
" plt.show()\n",
"\n",
"# Fixed four-person examples; checked against the constructors below.\n",
"dyad_examples = [\n",
" (\"Eldest first · recipient resets\", True,\n",
" [(4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1)]),\n",
" (\"Optimal recipient batching\", False,\n",
" [(4, 3), (4, 2), (3, 2), (3, 1), (4, 1), (2, 1)]),\n",
" (\"Optimal two-seat giver blocks\", False,\n",
" [(4, 3), (4, 1), (4, 2), (3, 2), (3, 1), (2, 1)]),\n",
"]\n",
"\n",
"fig, axes = plt.subplots(3, 1, figsize=(7.7, 7.1), constrained_layout=True)\n",
"for ax, (title, reset, order) in zip(axes, dyad_examples):\n",
" counts = []\n",
" for role, y, label, edge, fill in [\n",
" (0, 1, \"Giver\", \"#8e4b16\", \"#fff0df\"),\n",
" (1, 0, \"Recipient\", \"#17627a\", \"#dceff5\"),\n",
" ]:\n",
" bands = []\n",
" for t, pair in enumerate(order):\n",
" if t == 0 or pair[role] != order[t - 1][role] or (reset and role == 1):\n",
" bands.append([t, t, pair[role]])\n",
" else:\n",
" bands[-1][1] = t\n",
" counts.append(len(bands))\n",
" for start, end, person in bands:\n",
" ax.add_patch(FancyBboxPatch(\n",
" (start - .34, y - .25), end - start + .68, .5,\n",
" boxstyle=\"round,pad=0.015,rounding_size=0.12\",\n",
" facecolor=fill, edgecolor=edge, linewidth=1.4))\n",
" for t, pair in enumerate(order):\n",
" ax.text(t, y, str(pair[role]), ha=\"center\", va=\"center\",\n",
" fontsize=16, weight=\"bold\", color=edge)\n",
" ax.text(-.63, y, label, ha=\"right\", va=\"center\", fontsize=11, color=edge)\n",
" for t in range(6):\n",
" ax.text(t, 1.52, f\"{t + 1}\", ha=\"center\", va=\"center\", fontsize=10, color=\"#64748b\")\n",
" ax.annotate(\"\", xy=(t, .29), xytext=(t, .71),\n",
" arrowprops={\"arrowstyle\": \"->\", \"color\": \"#475569\", \"lw\": 1.4})\n",
" g, r = counts\n",
" ax.text(-.63, 1.52, \"Step\", ha=\"right\", va=\"center\", fontsize=10, color=\"#64748b\")\n",
" ax.text(-1.5, -.71, f\"Recipient only: {r}e\", fontsize=12, weight=\"bold\", color=\"#17627a\")\n",
" ax.text(1.35, -.71, f\"Two seats: {g}e + {r}e = {g + r}e\", fontsize=12, weight=\"bold\")\n",
" ax.set_title(title, loc=\"left\", fontsize=13, weight=\"bold\", pad=8)\n",
" ax.set(xlim=(-1.55, 5.55), ylim=(-.86, 1.75))\n",
" ax.axis(\"off\")\n",
"export_figure(fig, \"dyad-comparison\")"
]
},
{
"cell_type": "markdown",
"id": "790efb63",
"metadata": {},
"source": [
"## A setup-cost model\n",
"\n",
"There is an active giver position and an active recipient position. Consecutive\n",
"interactions can reuse an occupant in the **same role**. Changing roles starts\n",
"a new role episode. Under the two-seat interpretation, the chairs have fixed\n",
"roles; the participant gets up to change chairs.\n",
"\n",
"Let $c_G\\geq0$ be the cost of one giver episode and $c_R\\geq0$ the cost of one\n",
"recipient episode. A seated episode includes entry, any number of consecutive\n",
"interactions in that role, and exit. Count episodes by\n",
"\n",
"$$\n",
"G(\\pi)=1+\\sum_{t=1}^{M-1}\\mathbf1\\{g_{t+1}\\ne g_t\\},\\qquad\n",
"R(\\pi)=1+\\sum_{t=1}^{M-1}\\mathbf1\\{r_{t+1}\\ne r_t\\}.\n",
"$$\n",
"\n",
"For any schedule, keep the occupant seated across consecutive uses of the\n",
"same role. Additional stand–sit resets only increase its cost. The objective is\n",
"\n",
"$$\n",
"\\min_\\pi C(\\pi),\\qquad C(\\pi)=c_GG(\\pi)+c_RR(\\pi).\n",
"$$\n",
"\n",
"This model describes two different practical cases. Setting $(c_G,c_R)=(0,e)$\n",
"allows givers to approach a seated recipient, with their movement uncharged.\n",
"Setting $(c_G,c_R)=(e,e)$ charges both people at a two-seat station. Walking,\n",
"waiting, tray transfers, and reaching costs are excluded. They can change\n",
"which arrangement is attractive.\n",
"\n",
"If each tika itself takes time $\\tau$, total duration is\n",
"$\\tau M+C(\\pi)$ when the setup costs are measured in time. The number of\n",
"tikas stays quadratic in $N$, even when movement costs become linear.\n",
"\n",
"## Three lower bounds and an exact optimum\n",
"\n",
"Every person $2,\\ldots,N$ must give, and every person $1,\\ldots,N-1$ must\n",
"receive. Therefore\n",
"\n",
"$$\n",
"G(\\pi)\\geq N-1,\\qquad R(\\pi)\\geq N-1.\n",
"$$\n",
"\n",
"Two consecutive interactions are distinct, so at least one of their giver and\n",
"recipient identities changes. The first interaction starts two episodes;\n",
"the remaining $M-1$ interactions each start at least one. Consequently,\n",
"\n",
"$$\n",
"G(\\pi)+R(\\pi)\\geq M+1.\n",
"$$\n",
"\n",
"These three inequalities establish the lower bound in the introductory box.\n",
"\n",
"*Lower bound.* Suppose $c_R\\geq c_G$. Then\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"C(\\pi)\n",
"&=c_G\\{G(\\pi)+R(\\pi)\\}+(c_R-c_G)R(\\pi)\\\\\n",
"&\\geq c_G(M+1)+(c_R-c_G)(N-1)\\\\\n",
"&=c_R(N-1)+c_G(M-N+2).\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"The case $c_G\\geq c_R$ follows by interchanging the roles. The constructions\n",
"in the next section attain the bound. This proves global optimality over all\n",
"$M!$ schedules. No probabilistic approximation is required.\n",
"\n",
"The rule is to **batch the more expensive role**, keeping its occupant in place\n",
"for all their interactions, and arrange the block boundaries to retain the\n",
"other occupant too.\n",
"\n",
"## Constructing optimal schedules\n",
"\n",
"The following constructors generate the schedules illustrated below."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "0643b167",
"metadata": {},
"outputs": [],
"source": [
"def eldest_first(n):\n",
" return [(i, j) for i in range(n, 1, -1)\n",
" for j in range(i - 1, 0, -1)]\n",
"\n",
"def giver_blocks(n):\n",
" order = []\n",
" for i in range(n, 1, -1):\n",
" recipients = [i - 1] + list(range(i - 3, 0, -1))\n",
" if i >= 3:\n",
" recipients += [i - 2]\n",
" order.extend((i, j) for j in recipients)\n",
" return order\n",
"\n",
"def recipient_blocks(n):\n",
" return [(n + 1 - j, n + 1 - i)\n",
" for i, j in reversed(giver_blocks(n))]\n",
"\n",
"def episodes(order):\n",
" if not order:\n",
" return 0, 0\n",
" g = 1 + sum(a[0] != b[0] for a, b in zip(order, order[1:]))\n",
" r = 1 + sum(a[1] != b[1] for a, b in zip(order, order[1:]))\n",
" return g, r\n",
"\n",
"def optimal_schedule(n, c_g, c_r):\n",
" return giver_blocks(n) if c_g >= c_r else recipient_blocks(n)"
]
},
{
"cell_type": "markdown",
"id": "885936f8",
"metadata": {},
"source": [
"### Recipient batching: the linear-cost case\n",
"\n",
"Seat person $N-1$ and have every older person give them tika. Then seat\n",
"person $N-2$ and repeat, continuing to person $1$. Every recipient sits once:\n",
"\n",
"$$\n",
"R=N-1,\\qquad C=(N-1)e\\quad\\text{when }c_G=0,\\ c_R=e.\n",
"$$\n",
"\n",
"Every recipient must sit at least once, so this already attains the lower\n",
"bound. Compared with $Me$, the saving is\n",
"\n",
"$$\n",
"Me-(N-1)e=\\frac{(N-1)(N-2)}2e,\n",
"\\qquad \\frac{Me}{(N-1)e}=\\frac N2.\n",
"$$\n",
"\n",
"For $N=10$, there are still $45$ tikas, while recipient sit–stand cycles fall\n",
"from $45$ to $9$. Givers must be able to approach the current recipient."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "fig-recipient-batching",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n"
],
"text/plain": [
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#| label: fig-recipient-batching\n",
"#| fig-cap: 'Recipient-only seating costs, illustrated with four people and six tikas. Each blue band is one sit–stand episode: it begins when a person sits and ends when they stand. The upper policy resets the recipient after every tika; the lower policy lets each recipient remain seated through all their elders. Giver movement is uncharged.'\n",
"#| fig-alt: Two recipient seating timelines. The eldest-first reset policy has six separate seated episodes. Grouping by recipient has three episodes, one each for people 3, 2, and 1.\n",
"#| code-fold: true\n",
"#| code-summary: Draw the recipient seating timelines\n",
"fig, axes = plt.subplots(2, 1, figsize=(8, 5.1), constrained_layout=True)\n",
"for ax, order, reset, title in [\n",
" (axes[0], eldest_first(4), True, \"Reset after each tika: 6 recipient episodes\"),\n",
" (axes[1], recipient_blocks(4), False, \"Batch by recipient: 3 recipient episodes\"),\n",
"]:\n",
" bands = []\n",
" for t, (_, r) in enumerate(order):\n",
" if reset or t == 0 or order[t - 1][1] != r:\n",
" bands.append([t, t + 1, r])\n",
" else:\n",
" bands[-1][1] = t + 1\n",
" for start, end, r in bands:\n",
" ax.add_patch(Rectangle((start + .08, r - .23), end - start - .16, .46,\n",
" facecolor=\"#d1e8f0\", edgecolor=\"#17627a\", linewidth=1.6))\n",
" ax.text((start + end) / 2, r, str(r), ha=\"center\", va=\"center\", fontsize=12)\n",
" for t in range(7):\n",
" ax.axvline(t, color=\"#e2e8f0\", lw=.7, zorder=0)\n",
" ax.set(xlim=(0, 6), ylim=(.45, 3.55), yticks=[1, 2, 3],\n",
" yticklabels=[\"Person 1\", \"Person 2\", \"Person 3\"],\n",
" xticks=np.arange(6) + .5,\n",
" xticklabels=[f\"{g} → {r}\" for g, r in order],\n",
" xlabel=\"Tikas in execution order: giver → recipient\")\n",
" ax.set_title(title, loc=\"left\", fontsize=13, weight=\"bold\", pad=9)\n",
" ax.spines[[\"top\", \"right\", \"left\"]].set_visible(False)\n",
" ax.tick_params(axis=\"y\", length=0)\n",
"export_figure(fig, \"recipient-batching\")"
]
},
{
"cell_type": "markdown",
"id": "c6bb3cb2",
"metadata": {},
"source": [
"### Giver blocks with a shared recipient at each boundary\n",
"\n",
"When giver episodes are at least as expensive as recipient episodes, preserve\n",
"the eldest-first giver blocks. In the block for giver $i\\geq3$, use this\n",
"recipient order:\n",
"\n",
"$$\n",
"i-1,\\quad i-3,i-4,\\ldots,1,\\quad i-2.\n",
"$$\n",
"\n",
"The middle list is empty when $i=3$. Giver $2$ visits recipient $1$.\n",
"Thus giver $i$ finishes with recipient $i-2$, who stays seated while giver\n",
"$i-1$ takes over and also starts with $i-2$.\n",
"\n",
"For $N=4$, the schedule is\n",
"\n",
"$$\n",
"\\underbrace{(4,3),(4,1),(4,2)}_{\\text{giver 4}}\n",
"\\ ;\\ \\underbrace{(3,2),(3,1)}_{\\text{giver 3}}\n",
"\\ ;\\ (2,1).\n",
"$$\n",
"\n",
"Each boundary changes the giver alone. Within a block, only the recipient\n",
"changes. There are $N-1$ giver episodes and $M+1$ total episodes:\n",
"\n",
"$$\n",
"G=N-1,\\qquad R=M-N+2.\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "fig-giver-handoff",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n"
],
"text/plain": [
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#| label: fig-giver-handoff\n",
"#| fig-cap: 'A boundary between giver blocks in the four-person schedule: (4,2) is followed by (3,2). Recipient 2 stays seated while giver 4 is replaced by giver 3. The full six-tika schedule uses three giver episodes and four recipient episodes, attaining the two-seat minimum of seven.'\n",
"#| fig-alt: Two chair diagrams before and after a giver handoff. Recipient 2 remains in the recipient chair. Giver 4 stands and giver 3 sits. Exactly one new seated episode begins.\n",
"#| code-fold: true\n",
"#| code-summary: Draw the giver-block handoff\n",
"def seated_person(ax, x, y, person, color):\n",
" ax.add_patch(Circle((x, y), .27, facecolor=\"white\", edgecolor=color, linewidth=2.2))\n",
" ax.text(x, y, str(person), ha=\"center\", va=\"center\", fontsize=16, weight=\"bold\", color=color)\n",
" ax.plot([x - .35, x + .35], [y - .42, y - .42], color=color, lw=2)\n",
" ax.plot([x - .35, x - .35], [y - .25, y - .65], color=color, lw=2)\n",
" ax.plot([x + .35, x + .35], [y - .42, y - .65], color=color, lw=2)\n",
"\n",
"def handoff_figure(before, after):\n",
" fig, ax = plt.subplots(figsize=(7.7, 3.7))\n",
" ax.set(xlim=(-.8, 6.1), ylim=(-1.1, 2.1))\n",
" ax.axis(\"off\")\n",
" labels = [\"Giver\", \"Recipient\"]\n",
" for k, x in enumerate([.8, 3.0]):\n",
" kept = before[k] == after[k]\n",
" color = \"#087f72\" if kept else \"#ad5713\"\n",
" ax.text(x, 1.92, labels[k], ha=\"center\", fontsize=12, weight=\"bold\")\n",
" for y, pair in [(1.35, before), (0, after)]:\n",
" seated_person(ax, x, y, pair[k], color)\n",
" if kept:\n",
" ax.text(x, -.91, \"Stays seated\", ha=\"center\", color=color, fontsize=11, weight=\"bold\")\n",
" for y, label in [(1.35, \"Before\"), (0, \"After\")]:\n",
" ax.text(-.65, y, label, ha=\"left\", va=\"center\", fontsize=11)\n",
" ax.annotate(\"\", xy=(2.58, y), xytext=(1.22, y),\n",
" arrowprops={\"arrowstyle\": \"->\", \"color\": \"#64748b\", \"lw\": 1.5})\n",
" changed = 0 if before[0] != after[0] else 1\n",
" kept = 1 - changed\n",
" ax.text(4.05, 1.30, f\"{labels[kept]} {before[kept]} stays\", color=\"#087f72\", fontsize=12, weight=\"bold\")\n",
" ax.text(4.05, .78, f\"Person {before[changed]} stands.\\nPerson {after[changed]} sits.\", fontsize=11, linespacing=1.6)\n",
" ax.text(4.05, -.12, \"One new episode\", fontsize=12, weight=\"bold\")\n",
" fig.tight_layout()\n",
" return fig\n",
"\n",
"order = giver_blocks(4)\n",
"fig = handoff_figure(order[2], order[3])\n",
"export_figure(fig, \"giver-handoff\")"
]
},
{
"cell_type": "markdown",
"id": "66026ece",
"metadata": {},
"source": [
"### Recipient blocks with a shared giver at each boundary\n",
"\n",
"For $c_R\\geq c_G$, use the symmetric construction. Recipient $N-1$ first\n",
"receives from giver $N$. For each subsequent recipient $j=N-2,\\ldots,1$,\n",
"the giver order is\n",
"\n",
"$$\n",
"j+2,\\quad N,N-1,\\ldots,j+3,\\quad j+1.\n",
"$$\n",
"\n",
"The middle list can be empty. Recipient $j$ ends with giver $j+1$, who also\n",
"starts the block for recipient $j-1$. The same giver stays in place across\n",
"each boundary. The executable construction obtains this schedule by reversing\n",
"the giver-block schedule, age labels, and role labels.\n",
"\n",
"For $N=4$, this gives\n",
"\n",
"$$\n",
"(4,3)\\ ;\\ \\underbrace{(4,2),(3,2)}_{\\text{recipient 2}}\n",
"\\ ;\\ \\underbrace{(3,1),(4,1),(2,1)}_{\\text{recipient 1}}.\n",
"$$\n",
"\n",
"The recipient blocks proceed in descending age order, so each person receives\n",
"from all their elders before giving to anyone younger. The episode counts are\n",
"\n",
"$$\n",
"R=N-1,\\qquad G=M-N+2.\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "fig-recipient-handoff",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n"
],
"text/plain": [
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#| label: fig-recipient-handoff\n",
"#| fig-cap: 'A boundary between recipient blocks: (3,2) is followed by (3,1). Giver 3 stays seated while recipient 2 is replaced by recipient 1. The full four-person schedule uses four giver episodes and three recipient episodes. This construction is optimal when recipient episodes are at least as costly as giver episodes.'\n",
"#| fig-alt: Two chair diagrams before and after a recipient handoff. Giver 3 remains in the giver chair. Recipient 2 stands and recipient 1 sits. Exactly one new seated episode begins.\n",
"#| code-fold: true\n",
"#| code-summary: Draw the recipient-block handoff\n",
"order = recipient_blocks(4)\n",
"fig = handoff_figure(order[2], order[3])\n",
"export_figure(fig, \"recipient-handoff\")"
]
},
{
"cell_type": "markdown",
"id": "15adb93c",
"metadata": {},
"source": [
"The two constructions satisfy the lower bound for their respective cost\n",
"ordering. They each enumerate all $M$ required interactions in $O(M)$ time.\n",
"\n",
"\n",
"\n",
"### What the two-seat restriction permits\n",
"\n",
"With $c_G=c_R=e$, either construction achieves\n",
"\n",
"$$\n",
"C^*=(M+1)e.\n",
"$$\n",
"\n",
"This is also optimal when the two chairs have interchangeable roles. The\n",
"first pair needs two seated people; every distinct subsequent pair needs at\n",
"least one new person to sit. The construction attains that physical lower\n",
"bound while keeping the chair roles fixed.\n",
"\n",
"To compare with the original policy, charge its giver visits too. If every\n",
"recipient stands after each tika, the eldest-first policy costs\n",
"$\\{M+(N-1)\\}e$. Reusing recipient $1$ across its final two giver blocks\n",
"saves one episode for $N\\geq3$, yielding $(M+N-2)e$ for the same interaction\n",
"order. The optimized order costs $(M+1)e$.\n",
"\n",
"For $N=10$, these are **54, 53, and 46** total episodes, respectively.\n",
"The two-seat restriction allows a modest improvement. The reduction to nine\n",
"recipient episodes applies when giver movement has zero charged cost.\n",
"\n",
"### Everyone remains seated\n",
"\n",
"With enough seats and access between every pair, all $N$ people can sit at the\n",
"start and stand at the end. Execute the $M$ tikas sequentially while everyone\n",
"stays in place. This costs $Ne$, which is optimal because each participant\n",
"must be seated for at least one interaction. The arrangement assumes that\n",
"distance and reach impose no extra standing requirements."
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "fig-all-seated",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n"
],
"text/plain": [
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#| label: fig-all-seated\n",
"#| fig-cap: Four people remain seated for all six required interactions. Arrows mark older-to-younger dyads; the highlighted arrow shows a single active tika, 4 to 1. Each person has one seated episode, giving a total cost of 4e. This arrangement requires physical access between every pair.\n",
"#| fig-alt: Four people in four fixed seats, connected by six directed older-to-younger interactions. One interaction, 4 to 1, is highlighted. All four people stay seated throughout.\n",
"#| code-fold: true\n",
"#| code-summary: Draw the fully seated arrangement\n",
"fig, ax = plt.subplots(figsize=(6.4, 4.4))\n",
"positions = {4: (-1.3, 1.05), 3: (1.3, 1.05), 2: (1.3, -1), 1: (-1.3, -1)}\n",
"for g, r in eldest_first(4):\n",
" active = (g, r) == (4, 1)\n",
" ax.annotate(\"\", xy=positions[r], xytext=positions[g],\n",
" arrowprops={\"arrowstyle\": \"->\", \"shrinkA\": 21, \"shrinkB\": 21,\n",
" \"color\": \"#095c68\" if active else \"#bbc9d3\",\n",
" \"lw\": 2.7 if active else 1.25,\n",
" \"linestyle\": \"-\" if active else \"--\"}, zorder=1)\n",
"for person, (x, y) in positions.items():\n",
" seated_person(ax, x, y, person, \"#087f72\")\n",
"ax.text(0, 1.9, \"All four people sit once\", ha=\"center\", fontsize=14, weight=\"bold\")\n",
"ax.text(-2.15, .05, \"4 → 1\\nactive tika\", ha=\"center\", va=\"center\", color=\"#095c68\", fontsize=11)\n",
"ax.text(0, -2.05, \"6 tikas · 4 seated episodes\", ha=\"center\", fontsize=12)\n",
"ax.set(xlim=(-2.85, 2.5), ylim=(-2.3, 2.2))\n",
"ax.axis(\"off\")\n",
"fig.tight_layout()\n",
"export_figure(fig, \"all-seated\")"
]
},
{
"cell_type": "markdown",
"id": "e06864ec",
"metadata": {},
"source": [
"## A worked schedule\n",
"\n",
"The cells below represent the same $15$ interactions for six people. Numbers\n",
"give their execution order. Giver blocks run along rows; recipient blocks run\n",
"along columns. The altered order at block boundaries permits an occupant to\n",
"remain seated."
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "fig-orders",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n"
],
"text/plain": [
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#| label: fig-orders\n",
"#| fig-cap: Interaction order for six people. G and R count giver and recipient episodes with consecutive reuse. The specified reset-after-each-tika baseline would add one recipient episode to the first panel.\n",
"#| code-fold: true\n",
"#| code-summary: Draw the schedules\n",
"fig, axes = plt.subplots(1, 3, figsize=(10.5, 3.5), constrained_layout=True)\n",
"for ax, name, fn in zip(axes, [\"Eldest-first order\", \"Giver blocks\", \"Recipient blocks\"],\n",
" [eldest_first, giver_blocks, recipient_blocks]):\n",
" order = fn(6)\n",
" matrix = np.full((6, 6), np.nan)\n",
" for t, (g, r) in enumerate(order, 1):\n",
" matrix[g - 1, r - 1] = t\n",
" ax.imshow(matrix, cmap=\"Blues\", vmin=0, vmax=30, origin=\"lower\")\n",
" for t, (g, r) in enumerate(order, 1):\n",
" ax.text(r - 1, g - 1, str(t), ha=\"center\", va=\"center\", fontsize=10)\n",
" g, r = episodes(order)\n",
" ax.set(title=f\"{name}\\nG = {g}, R = {r}\", xlabel=\"Recipient\", ylabel=\"Giver\",\n",
" xticks=range(6), yticks=range(6), xticklabels=range(1, 7), yticklabels=range(1, 7))\n",
" ax.spines[[\"top\", \"right\"]].set_visible(False)\n",
"export_figure(fig, \"interaction-orders\")"
]
},
{
"cell_type": "markdown",
"id": "20464743",
"metadata": {},
"source": [
"::: {.content-visible when-format=\"html\"}\n",
"### Inspect a schedule\n",
"\n",
"The explorer charges every episode according to the selected cost model.\n",
"The baseline includes its prescribed recipient reset after every tika.\n",
"\n",
"```{=html}\n",
"\n",
"
\n",
" \n",
"\n",
"\n",
"```\n",
":::\n",
"\n",
"## Verification and scope\n",
"\n",
"The optimization is a sequence-dependent setup problem. One can represent\n",
"each required interaction as a vertex, connecting two vertices when their\n",
"interactions share the giver or share the recipient. The block constructions\n",
"give a Hamilton path in this graph, so every transition changes just one\n",
"role. Age gives a triangular set of allowed giver–recipient pairs, which\n",
"makes the path construction particularly simple.\n",
"\n",
"The following exact subset dynamic program independently checks the optimum\n",
"for small $N$. Its state is a set of completed interactions and the final\n",
"interaction; it considers every possible next interaction. The general proof\n",
"above applies to every $N\\geq2$."
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "3f75b3d5",
"metadata": {},
"outputs": [
{
"data": {
"text/markdown": [
"**20 exact optimization checks pass** for N = 2–5; both constructions also pass coverage, cost, and age-precedence checks for N = 2–30."
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#| code-fold: true\n",
"#| code-summary: \"Exact small-instance verification\"\n",
"from functools import lru_cache\n",
"from IPython.display import Markdown, display\n",
"\n",
"for (_, _, illustrated), constructor in zip(\n",
" dyad_examples, [eldest_first, recipient_blocks, giver_blocks]):\n",
" assert illustrated == constructor(4)\n",
"\n",
"def exact_cost(n, c_g, c_r):\n",
" edges = eldest_first(n)\n",
" full = (1 << len(edges)) - 1\n",
"\n",
" @lru_cache(None)\n",
" def finish(mask, last):\n",
" if mask == full:\n",
" return 0\n",
" g, r = edges[last]\n",
" return min(c_g * (h != g) + c_r * (s != r)\n",
" + finish(mask | (1 << k), k)\n",
" for k, (h, s) in enumerate(edges) if not mask & (1 << k))\n",
"\n",
" return c_g + c_r + min(finish(1 << k, k) for k in range(len(edges)))\n",
"\n",
"for n in range(2, 31):\n",
" m = n * (n - 1) // 2\n",
" for fn, counts in [(giver_blocks, (n - 1, m - n + 2)),\n",
" (recipient_blocks, (m - n + 2, n - 1))]:\n",
" order = fn(n)\n",
" assert len(order) == m and set(order) == set(eldest_first(n))\n",
" assert episodes(order) == counts\n",
" assert all(a[0] == b[0] or a[1] == b[1]\n",
" for a, b in zip(order, order[1:]))\n",
" # Every person receives from all elders before giving to anyone younger.\n",
" for person in range(2, n):\n",
" assert max(t for t, (_, r) in enumerate(order) if r == person) < min(\n",
" t for t, (g, _) in enumerate(order) if g == person)\n",
"\n",
"checks = 0\n",
"for n in range(2, 6):\n",
" m = n * (n - 1) // 2\n",
" for c_g, c_r in [(0, 1), (1, 0), (1, 1), (4, 1), (1, 4)]:\n",
" bound = (n - 1) * max(c_g, c_r) + (m - n + 2) * min(c_g, c_r)\n",
" g, r = episodes(optimal_schedule(n, c_g, c_r))\n",
" assert exact_cost(n, c_g, c_r) == c_g * g + c_r * r == bound\n",
" checks += 1\n",
"display(Markdown(f\"**{checks} exact optimization checks pass** for N = 2–5; \"\n",
" \"both constructions also pass coverage, cost, and age-precedence checks for N = 2–30.\"))"
]
},
{
"cell_type": "markdown",
"id": "4a2d0823",
"metadata": {},
"source": [
"Several extensions change the optimization problem:\n",
"\n",
"- **Participant-specific discomfort.** In the recipient-only model, costs\n",
" $e_j$ give optimum $\\sum_{j=1}^{N-1}e_j$: seat every recipient once. With\n",
" costs on both sides, minimizing the number of episodes alone can miss an\n",
" important distributional objective.\n",
"- **Fixed giver priority.** Eldest-first giver blocks are preserved by the\n",
" giver construction. Recipient batching allows younger givers to act before\n",
" the eldest has finished all their tikas. Both implemented schedules ensure\n",
" that each person receives from every elder before starting to give.\n",
"- **Space and movement.** A single recipient seat, a two-seat station, and a\n",
" fully seated group have different feasible schedules. Reaching and walking\n",
" costs need to be included when those actions are consequential.\n",
"- **Parallel service or omitted dyads.** Multiple simultaneous tikas introduce\n",
" resource conflicts; incomplete family interaction graphs can eliminate the\n",
" simple triangular construction. Those are different scheduling problems.\n",
"\n",
"For the complete sequential ceremony, the cost model has an exact solution:\n",
"batch the expensive role and retain one participant across each block boundary.\n",
"The required social interactions are unchanged."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3",
"path": "/Users/alal/tmp/krabbs_the_koder/.venv/share/jupyter/kernels/python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.13.2"
}
},
"nbformat": 4,
"nbformat_minor": 5
}