Exact bill splitting and minimum-transfer debt settlement: an integer model and a prediction-robust block decomposition

Preprint. Submitted to the Open Journal of Mathematical Optimization (November 2026). Code and seeded benchmarks: https://github.com/Gautam5514/exact-bill-splitting Shared-expense ledgers must divide each bill in indivisible currency units and settle the resulting net balances with few transfers. We give one integer model for both problems. Every split rule is reduced to exact rational quotas followed by a single largest-remainder rounding, which is exact in sum, within one unit of every quota, and minimises every separable convex measure of rounding error. For settlement we restate the classical facts with complete proofs: the minimum number of transfers is n − Z, exact opposite pairs can be removed without loss, and a subset dynamic program solves m members in O(m·2^m) time. For large groups we analyse zero-sum-safe block decompositions: whatever a predictor proposes, the plan conserves all balances, moves the least possible amount, and uses at most min(OPT + η, (3/2)·OPT) transfers, where η counts the optimal zero-sum parts cut by the blocks. On seeded synthetic clustered groups of 30 to 200 members a learned instance used 3.0–25.0% fewer transfers than greedy. Learned edge weights improved on Louvain blocks of the co-spend-weighted co-participation graph by only 0.8% on average (at most 2.0%), and the mean gap to a certified lower bound was 12.8–43.1%.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-21
DOI
https://doi.org/10.5281/zenodo.24421985
Primary Topic
Game Theory and Voting Systems
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact bill splitting and minimum-transfer debt settlement: an integer model and a prediction-robust block decomposition

Gautam Pandit
Zenodo (CERN European Organization for Nuclear Research)
Game Theory and Voting Systems
preprint

Exact bill splitting and minimum-transfer debt settlement: an integer model and a prediction-robust block decomposition

Gautam Pandit
preprint en

Abstract

Preprint. Submitted to the Open Journal of Mathematical Optimization (November 2026). Code and seeded benchmarks: https://github.com/Gautam5514/exact-bill-splitting Shared-expense ledgers must divide each bill in indivisible currency units and settle the resulting net balances with few transfers. We give one integer model for both problems. Every split rule is reduced to exact rational quotas followed by a single largest-remainder rounding, which is exact in sum, within one unit of every quota, and minimises every separable convex measure of rounding error. For settlement we restate the classical facts with complete proofs: the minimum number of transfers is n − Z, exact opposite pairs can be removed without loss, and a subset dynamic program solves m members in O(m·2^m) time. For large groups we analyse zero-sum-safe block decompositions: whatever a predictor proposes, the plan conserves all balances, moves the least possible amount, and uses at most min(OPT + η, (3/2)·OPT) transfers, where η counts the optimal zero-sum parts cut by the blocks. On seeded synthetic clustered groups of 30 to 200 members a learned instance used 3.0–25.0% fewer transfers than greedy. Learned edge weights improved on Louvain blocks of the co-spend-weighted co-participation graph by only 0.8% on average (at most 2.0%), and the mean gap to a certified lower bound was 12.8–43.1%.

Zenodo (CERN European Organization for Nuclear Research)
Game Theory and Voting Systems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon