An improved cutting plane method for convex optimization, convex-concave games, and its applications

H Jiang, YT Lee, Z Song, SC Wong - … of the 52nd Annual ACM SIGACT …, 2020 - dl.acm.org
Given a separation oracle for a convex set K⊂ ℝ n that is contained in a box of radius R, the
goal is to either compute a point in K or prove that K does not contain a ball of radius є. We …

Fairness-efficiency tradeoffs in dynamic fair division

D Zeng, A Psomas - Proceedings of the 21st ACM Conference on …, 2020 - dl.acm.org
A set of T indivisible goods has to be allocated to a set of n agents with additive utilities, in a
way that is fair and efficient. A standard fairness concept is envy-freeness, which requires …

A strongly polynomial algorithm for approximate forster transforms and its application to halfspace learning

I Diakonikolas, C Tzamos, DM Kane - Proceedings of the 55th Annual …, 2023 - dl.acm.org
The Forster transform is a method of regularizing a dataset by placing it in radial isotropic
position while maintaining some of its essential properties. Forster transforms have played a …

Fair and efficient online allocations

G Benadè, AM Kazachkov, AD Procaccia… - Operations …, 2024 - pubsonline.informs.org
We study trade-offs between fairness and efficiency when allocating indivisible items online.
We attempt to minimize envy, the extent to which any agent prefers another's allocation to …

Minimizing convex functions with integral minimizers

H Jiang - Proceedings of the 2021 ACM-SIAM Symposium on …, 2021 - SIAM
Given a separation oracle SO for a convex function f that has an integral minimizer inside a
box with radius R, we show how to efficiently find a minimizer of f using at most O (n (n+ log …

Algorithms for competitive division of chores

S Brânzei, F Sandomirskiy - Mathematics of Operations …, 2024 - pubsonline.informs.org
We study the problem of allocating divisible bads (chores) among multiple agents with
additive utilities when monetary transfers are not allowed. The competitive rule is known for …

Competitive allocation of a mixed manna

BR Chaudhury, J Garg, P McGlaughlin, R Mehta - Proceedings of the 2021 …, 2021 - SIAM
We study the fair division problem of allocating a mixed manna under additively separable
piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone …

Constant inapproximability for Fisher markets

A Deligkas, J Fearnley, A Hollender… - Proceedings of the 25th …, 2024 - dl.acm.org
We study the problem of computing approximate market equilibria in Fisher markets with
separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was …

Fixp-membership via convex optimization: Games, cakes, and markets

A Filos-Ratsikas, KA Hansen, K Høgh… - SIAM Journal on …, 2023 - SIAM
We introduce a new technique for proving membership of problems in FIXP: the class
capturing the complexity of computing a fixed point of an algebraic circuit. Our technique …

Computational Hardness of the Hylland-Zeckhauser Scheme∗

T Chen, X Chen, B Peng, M Yannakakis - … of the 2022 Annual ACM-SIAM …, 2022 - SIAM
We study the complexity of the classic Hylland-Zeckhauser scheme [21] for one-sided
matching markets. We show that the problem of finding an∊-approximate equilibrium in the …