Erel Segal-Halevi

Ayelet Amster, Lioz Akirav, Rica Gonen et al.

Budget aggregation is a process in which citizens vote by declaring their individual ideal budget allocation, and a pre-determined rule aggregates all votes into a single outcome. Recent theoretical work has proposed various aggregation rules, along with impossibility results for satisfying desirable axioms simultaneously. These analyses rely on assumptions about how voters evaluate non-ideal allocations, yet such assumptions have not been empirically validated on human subjects. We present a framework for empirically testing hypotheses about human utility functions using simple pairwise comparisons. We introduce a modular, open-source polling system that, after eliciting a subject's ideal allocation, presents carefully generated pairs of non-ideal alternatives. Different pair-generation algorithms allow testing various properties of utility functions. Using this framework, we conduct polls with hundreds of participants. The results show that standard utility models, including $\ell_1$, $\ell_2$, and Leontief, fail to capture human preferences, as very few participants behave consistently with any single model. In contrast, we find strong empirical support for more general properties, such as star-shaped, multi-dimensional single-peaked, and peak-linear preferences. We also find that most participants exhibit asymmetries both with respect to sign (gains vs. losses) and issue, contradicting any utility model based on an $\ell_p$ metric. These findings suggest that developing practical budget-aggregation mechanisms requires more flexible models of human utility functions.

Ido Kahana, Erel Segal-Halevi, Noam Hazon

Many decision processes run for a long and unknown duration: in each round new requests arrive, an irrevocable choice must be made immediately, and the system is judged by ongoing fairness requirements. Examples include food banks allocating donated items as they arrive, computing systems repeatedly scheduling scarce resources across users, and institutions making repeated public decisions (e.g., which proposals or cases to prioritize) while remaining fair over time. A key challenge in such settings is that fairness requirements are often naturally \emph{scale-dependent}. For example, in fair item allocation, it is common to require that the unfairness is bounded by the highest values of items seen so far. Thus, the scale of fairness changes over time. We propose a general approach to online fairness based on \emph{deficits}, which measure each requirement's current shortfall relative to a time-varying benchmark. Within this framework, we analyze a simple fully online rule that, in each round, chooses the action that best improves the next-round deficit profile. We prove anytime (prefix-wise) guarantees: after every round, all tracked requirements remain satisfied up to a slack that grows only on the order of $\sqrt{t}$ (up to logarithmic factors), and we show this growth is unavoidable in general. We instantiate the framework for online allocation of indivisible goods (yielding natural relaxations of proportionality and envy-freeness) and for online public decision-making. In contrast to previous works on online fair allocation, our rule does not need to know the horizon (the total number of rounds), nor any other information on the future (e.g. the maximum item value). Moreover, our guarantees hold perpetually, at each individual time step.

Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into the minimum number of bins such that the sum of the item sizes in each bin does not exceed the capacity. We define a new variant, k-times bin-packing (kBP), in which the goal is to pack the items so that each item appears exactly k times in k different bins. We generalize existing approximation algorithms for bin-packing to solve kBP and analyze their performance ratios. The fair electricity division problem motivates the study of kBP. The goal is to allocate the available supply among households using some fairness criteria, such as the egalitarian principle. We prove that every electricity division problem can be solved by k-times bin-packing for some finite k, which depends only on the number of households. We implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve kBP and apply them to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem in terms of the egalitarian allocation of connection time. We study another variant of the egalitarian allocation problem, in which the goal is to maximize the minimum number of watts allocated to a household. For this variant, we prove an impossibility result: there does not exist such a k that depends only on the number of agents. This impossibility result motivates us to develop four different heuristic algorithms to solve the egalitarian allocation of watts problem. We evaluate the heuristics by summing the minimum watts allocated to any household in each hour, yielding a fairness metric that reflects the lowest watt allocation across all hours. A higher total minimum of watts indicates a more equitable distribution. Thus, we establish new benchmarks for fair allocation of watts.

Samuel Bismuth, Erel Segal-Halevi

We present an approximation notion for NP-hard optimization problems represented by binary functions. We prove that (assuming P != NP) the new notion is strictly stronger than FPTAS, but strictly weaker than having a polynomial-time algorithm.

Simina Brânzei, Erel Segal-Halevi, Aviv Zohar

Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies. However, the economic effect of transaction channels on the system has not been explored much until now. We study the economics of Bitcoin transaction channels, and present a framework for an economic analysis of the lightning network and its effect on transaction fees on the blockchain. Our framework allows us to reason about different patterns of demand for transactions and different topologies of the lightning network, and to derive the resulting fees for transacting both on and off the blockchain. Our initial results indicate that while the lightning network does allow for a substantially higher number of transactions to pass through the system, it does not necessarily provide higher fees to miners, and as a result may in fact lead to lower participation in mining within the system.