Logarithmic algorithms for fair division problems

We study the algorithmic complexity of fair division problems with a focus on minimizing the number of queries needed to find an approximate solution with desired accuracy. We show for several classes of fair division problems that under certain natural conditions on sets of preferences, a logarithm...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-11
Main Authors: Grebennikov, Alexandr, Isaeva, Xenia, Malyutin, Andrei V, Mikhailov, Mikhail, Musin, Oleg R
Format: Article
Language:English
Subjects:
Algorithms
Queries
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the algorithmic complexity of fair division problems with a focus on minimizing the number of queries needed to find an approximate solution with desired accuracy. We show for several classes of fair division problems that under certain natural conditions on sets of preferences, a logarithmic number of queries with respect to accuracy is sufficient.
ISSN:2331-8422