Výsledky vyhledávání - "Alexandros Hollender"

Consensus-Halving: Does It Ever Get Easier?

Autor: Katerina Sotiraki, Aris Filos-Ratsikas, Manolis Zampetakis, Alexandros Hollender

Publikováno v: Filos-Ratsikas, A, Hollender, A, Sotiraki, K & Zampetakis, M 2023, ' Consensus-Halving: Does It Ever Get Easier? ', SIAM Journal on Computing, vol. 52, no. 2, pp. 563-602 . https://doi.org/10.1137/20M1387493
EC

In the $\varepsilon$-Consensus-Halving problem, a fundamental problem in fair division, there are $n$ agents with valuations over the interval $[0,1]$, and the goal is to divide the interval into pieces and assign a label "$+$" or "$-$" to each piece

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::788596e2d3657f60e7651c0a1e1f286c
https://hdl.handle.net/20.500.11820/01b381fe-29dc-4ec3-b7c8-e7f5ccd10eac

Zobrazit plný text záznamu

The Hairy Ball problem is PPAD-complete

Autor: Alexandros Hollender, Paul Goldberg

Publikováno v: Journal of Computer and System Sciences. 122:34-62

The Hairy Ball Theorem states that every continuous tangent vector field on an even-dimensional sphere must have a zero. We prove that the associated computational problem of (a) computing an approximate zero is PPAD-complete, and (b) computing an ex

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d663ee6b2a747281c894aa8c0ec909ae
https://doi.org/10.1016/j.jcss.2021.05.004

Zobrazit plný text záznamu

Two’s Company, Three’s a Crowd: Consensus-Halving for a Constant Number of Agents

Autor: Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender

Publikováno v: Deligkas, A, Filos-Ratsikas, A & Hollender, A 2022, ' Two’s Company, Three’s a Crowd: Consensus-Halving for a Constant Number of Agents ', Artificial Intelligence Journal, vol. 313, 103784 . https://doi.org/10.1016/j.artint.2022.103784
Proceedings of the 22nd ACM Conference on Economics and Computation
EC

We consider the $\varepsilon$-Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions that all of them simultaneously consider to be of approximately the s

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::025f2a21ddc312436fc12812df124acb
https://hdl.handle.net/20.500.11820/f92c933a-c6bd-4f93-b56f-de38970860e7

Zobrazit plný text záznamu

On the complexity of equilibrium computation in first-price auctions

Autor: Diogo Poças, Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos

Publikováno v: Filos-Ratsikas, A, Giannakopoulos, Y, Hollender, A, Lazos, P & Poças, D 2023, ' On the Complexity of Equilibrium Computation in First-Price Auctions ', SIAM Journal on Computing, vol. 52, no. 1, pp. 80-131 . https://doi.org/10.1137/21M1435823
Proceedings of the 22nd ACM Conference on Economics and Computation
EC

We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distr

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f89cda94478f4e72f080c761da76a10c
https://ora.ox.ac.uk/objects/uuid:4b3b81ce-8cc5-4886-8727-2ae846a1853a

Zobrazit plný text záznamu

Structural results for total search complexity classes with applications to game theory and optimisation

Autor: Alexandros Hollender

Publikováno v: Alexandros Hollender

While the celebrated theory of NP-completeness has been very successful in explaining the intractability of many interesting problems, there still remain many natural and seemingly hard problems that are not known to be NP-hard. Several of these prob

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::d568b91eb63ea0154c4a583e9158d4cf
https://ora.ox.ac.uk/objects/uuid:67e2d80b-76bf-4b49-9b7d-8bbd91633dd7

Zobrazit plný text záznamu

A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting

Autor: Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::f3459af5da2a4fea7e93cc3888d58c14
https://doi.org/10.1137/1.9781611976465.155

Zobrazit plný text záznamu

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Autor: Paul Goldberg, Alexandros Hollender, Warut Suksompong

Publikováno v: Journal of Artificial Intelligence Research
AAAI
Scopus-Elsevier

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this sett

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::50552535d39bb003b0d678e37a77fcdb

Zobrazit plný text záznamu

Consensus Halving for Sets of Items

Autor: Warut Suksompong, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Paul Goldberg

Publikováno v: Web and Internet Economics-16th International Conference, WINE 2020, Beijing, China, December 7–11, 2020, Proceedings
Web and Internet Economics ISBN: 9783030649456
WINE
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Web and Internet Economics

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a consensus halving with at most n cuts always exists

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1541f6153d6616e5451e2f8d7dcf9a57

Zobrazit plný text záznamu

MergeShuffle: A Very Fast, Parallel Random Permutation Algorithm

Autor: Bacher, A., Bodini, O., Alexandros Hollender, Lumbroso, J.

Publikováno v: Scopus-Elsevier

This article introduces an algorithm, MergeShuffle, which is an extremely efficient algorithm to generate random permutations (or to randomly permute an existing array). It is easy to implement, runs in $n\log_2 n + O(1)$ time, is in-place, uses $n\l

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::493aa1dbe2eec2955f81164bb665f58e
http://arxiv.org/abs/1508.03167

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání