The paper develops constant-factor approximation algorithms for one-sided and two-sided Nash social welfare under submodular and subadditive valuations, respectively, and capacity constraints.

How to assign a set of numbers to the vertices of a graph to minimize the sum of absolute differences along the edges?

Using Sperner's lemma to show the existence of a connected and equitable division of a cake.

How an online algorithm, that buys or sells stocks based only on current prices, can compete with an offline prophet that knows all prices beforehand.

Fairly allocating homogeneous divisible resources among agents with different consumption rates and arrival and departure times.

How to fairly allocate resources under conflict constraints?

When some resources are pre-assigned, how should the remaining resources be distributed to make the final allocation fair and efficient?

In the many-to-one stable matching problem, how can the capacities on the "many" side be modified to achieve desirable outcomes as stable solutions of the modified problem?

Finding a many-to-one matching that maximizes Nash social welfare.

Approximation algorithms for the graphical house allocation studied in the AAMAS 2023 paper. Also, Ramanujan graphs and a cool connection between graph cuts and bitstrings.

How much welfare loss does fairness impose? The paper looks at a worst-case quantification called price of fairness for the class of generalized mean welfare measures and provides fine-grained bounds in terms of the number of agent types.

Do real-world users consider approximately envy-free allocations fair?

The paper studies the best-of-both-worlds framework for fair allocations of indivisible goods, and constructs randomized allocations that are ex-ante approximately proportional and simultaneously satisfy envy-based and fair share-based ex-post guarantees.

Fair division under two-sided cardinality constraints.

How to assign a set of numbers to the vertices of a graph to minimize the sum of absolute differences along the edges?

When agents have lexicographic preferences over mixtures of indivisible goods and chores, an EFX allocation could fail to exist.

The paper applies voting theory to the study of matchings-under-preferences, and proposes a relaxation of popularity called weak Copeland matching that is guaranteed to exist in general roommates instances with weak preferences and admits an FPRAS.

A polynomial-time algorithm for finding a distribution over EF1 allocations that is envy-free in expectation.

The paper gives a polynomial-time algorithm for computing the optimal joint strategy for a man-woman pair who want to help the woman under the deferred acceptance algorithm.

This paper gives an algorithm that, given an arrangement of indivisible items on a path and any ordering of agents, computes an EQ1 allocation consistent with the given ordering in which agents receive connected bundles and with the highest egalitarian welfare.

How to make group decisions when agents' preferences are specified not as rankings or numerical utilities but in natural language.

Resolving arbitrary envy cycles could fail to achieve EF1 even for additive chores. The paper proposes the top-trading envy cycle algorithm that guarantees EF1 for monotone chores.

Under the deferred acceptance algorithm, an agent on the proposed-to side is typically better off asking a proposer (a.k.a., an accomplice) to manipulate on her behalf rather than manipulating on her own.

Characterizing allocations that are envy-free up to any good (EFX) and Pareto optimal (PO) under lexicographic preferences.

Computing proxy arrangements that fairly represent a continuum of voters in a one-dimensional setting.

A polynomial-time algorithm for finding a distribution over EF1 allocations that is envy-free in expectation.

What is the smallest number of goods that need to be concealed in order to achieve envy-freeness?

A pseudopolynomial-time algorithm for finding an allocation that is equitable up to one chore (EQ1) and Pareto optimal (PO).

The paper studies computational aspects of the stable matching problem when agents have cardinal preferences and one seeks a fractional solution with high social welfare.

This paper studies approximately equitable and economically efficient allocations of indivisible goods.

The paper develops a framework for optimizing the time it takes a user to transform a given ranking into a desired ranking via drag-and-drop operations.

A polynomial-time algorithm for maximizing Nash social welfare under binary valuations.

An algorithmic framework for finding an allocation that is envy-free up to one good (EF1) and Pareto optimal (PO), and a 1.45-approximation algorithm for Nash social welfare.

The paper studies a semi-random model for kidney exchange with a worst-case compatibility graph and a uniformly random assignment of patient-donor pairs to hospitals.

Under the deferred acceptance algorithm, optimal manipulation by an agent on the proposed-to side is inconspicuous and stability-preserving.

Analyzing the Thomson sampling algorithm for stochastic multiarmed bandits when not all arms are available in each round.

In elections where each voter's preferences are given by a set of pairwise comparisons, no "reasonable" voting rule can prevent tactical voting, but NP-hardness comes to the rescue.

This paper undertakes a parameterized complexity analysis of the manipulation problem studied in our AAMAS 2016 paper.

The paper shows that plug-in algorithms are statistically consistent for non-decomposable performance measures (e.g., F-measure).