34 citations · 429 across the 66 of their papers we have counts for
75 papers
Individual Fairness in Budget Aggregation
Xiaohui Bei, Felix Brandt, Matthias Greger +3
We consider the problem of aggregating individual distributions over alternatives into a collective distribution, also known as budget aggregation. Existing fairness notion…
Time and Supply Fairness in Electricity Distribution using -times bin packing
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…
Perpetual Fully-Online Approximate Fairness
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…
An approximation notion between P and FPTAS
Samuel Bismuth, Erel Segal-Halevi
We present an approximation notion for NP-hard optimization problems. The notion is based on an amortized relaxation: the relaxed optimum of an input is the largest per-copy value…
Perpetually Fair Assignments Via Balanced Sequences of Permutations
Terrence Adams, Erel Segal-Halevi
There is a set of indivisible items (goods or chores), and a set of players. Each day, a single item should be assigned to each player. Assignments based on latin squares g…
How Do People Evaluate Non-Ideal Budgets? Evidence from Pairwise Comparisons
Ayelet Amster, Lioz Akirav, Rica Gonen +1
Budget aggregation allows citizens to express their ideal budget allocations, which a predetermined rule combines into a collective allocation. Existing theoretical work on budget-…
Efficiently Computing Equilibria in Budget-Aggregation Games
Patrick Becker, Alexander Fries, Matthias Greger +1
Budget aggregation deals with the social choice problem of distributing an exogenously given budget among a set of public projects, given agents' preferences. Taking a game-theoret…
The Min Max Average Cycle Weight Problem
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 combinato…
Fair Allocation with Money: What is Your Objective?
Noga Klein Elmalem, Rica Gonen, Erel Segal-Halevi
When allocating indivisible items, there are various ways to use monetary transfers for eliminating envy. Particularly, one can apply a balanced vector of transfer payments, or cha…
Fairly Wired: Towards Leximin-Optimal Division of Electricity
Eden Hartman, Dinesh Kumar Baghel, Erel Segal-Halevi
In many parts of the world - particularly in developing countries - the demand for electricity exceeds the available supply. In such cases, it is impossible to provide electricity…
Fair Allocation of Improvements: When Old Endowments Shape New Assignments
Noga Klein Elmalem, Rica Gonen, Erel Segal-Halevi
This work is motivated by a common urban renewal process called Reconstruct and Divide. It involves the demolition of old buildings and the construction of new ones. Original homeo…
Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy
Noga Klein Elmalem, Haris Aziz, Rica Gonen +7
We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where…
It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents
Eden Hartman, Erel Segal-Halevi, Biaoshuai Tao
The classic notion of \emph{truthfulness} requires that no agent has a profitable manipulation -- an untruthful report that, for \emph{some} combination of reports of the other age…
Improved Maximin Share Approximations for Chores by Bin Packing
Jugal Garg, Xin Huang, Erel Segal-Halevi
We study fair division of indivisible chores among agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not al…
Weighted Envy Freeness With Bounded Subsidies
Noga Klein Elmalem, Rica Gonen, Erel Segal-Halevi
We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where…
Reducing Leximin Fairness to Utilitarian Optimization
Eden Hartman, Yonatan Aumann, Avinatan Hassidim +1
Two prominent objectives in social choice are utilitarian - maximizing the sum of agents' utilities, and leximin - maximizing the smallest agent's utility, then the second-smallest…
Optimal Budget Aggregation with Star-Shaped Preference Domains
Felix Brandt, Matthias Greger, Erel Segal-Halevi +1
We study the problem of aggregating distributions, such as budget proposals, into a collective distribution. An ideal aggregation mechanism would be Pareto efficient, strategyproof…
On Connected Strongly-Proportional Cake-Cutting
Zsuzsanna Jankó, Attila Joó, Erel Segal-Halevi +1
We investigate the problem of fairly dividing a divisible heterogeneous resource, also known as a cake, among a set of agents who may have different entitlements. We characterize t…
-times bin packing and its application to fair electricity distribution
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 a minimum number of bins such that the sum of item sizes in a bin does…
Computing approximate roots of monotone functions
Alexandros Hollender, Chester Lawrence, Erel Segal-Halevi
Given a function f: [a,b] -> R, if f(a) < 0 and f(b)> 0 and f is continuous, the Intermediate Value Theorem implies that f has a root in [a,b]. Moreover, given a value-oracle for f…
Efficient Almost-Egalitarian Allocation of Goods and Bads
Israel Jacobovich, Erel Segal-Halevi
We consider the allocation of indivisible objects among agents with different valuations, which can be positive or negative. An egalitarian allocation is an allocation that maximiz…
Coordinating Charitable Donations with Leontief Preferences
Felix Brandt, Matthias Greger, Erel Segal-Halevi +1
We consider the problem of funding public goods that are complementary in nature. Examples include charities handling different needs (e.g., protecting animals vs. providing health…
On Maximum Bipartite Matching with Separation
Pasin Manurangsi, Erel Segal-Halevi, Warut Suksompong
Maximum bipartite matching is a fundamental algorithmic problem which can be solved in polynomial time. We consider a natural variant in which there is a separation constraint: the…
Leximin Approximation: From Single-Objective to Multi-Objective
Eden Hartman, Avinatan Hassidim, Yonatan Aumann +1
Leximin is a common approach to multi-objective optimization, frequently employed in fair division applications. In leximin optimization, one first aims to maximize the smallest ob…