Erel Segal-Halevi

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.

Noga Klein Elmalem, Rica Gonen, Erel Segal-Halevi

When an old apartment building is demolished and rebuilt, how can we fairly redistribute the new apartments to minimize envy among residents? We reduce this question to a combinatorial optimization problem called the *Min Max Average Cycle Weight* problem. In that problem we seek to assign objects to agents in a way that minimizes the maximum average weight of directed cycles in an associated envy graph. While this problem reduces to maximum-weight matching when starting from a clean slate (achieving polynomial-time solvability), we show that this is not the case when we account for preexisting conditions, such as residents' satisfaction with their original apartments. Whether the problem is polynomial-time solvable in the general case remains an intriguing open problem.

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.

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.