Buchumschlag

A new lower bound for multi-color discrepancy with applications to fair division

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Caragiannis, Ioannis, Larsen, Kasper Green, Shyam, Sudarshan
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computer Science and Game Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Existence and Computation of Fair Allocations under Constraints
von: Barman, Siddharth, et al.
Veröffentlicht: (2026)

Low-Distortion Clustering with Ordinal and Limited Cardinal Information
von: Burkhardt, Jakob, et al.
Veröffentlicht: (2024)

Bounds on the revenue gap of linear posted pricing for selling a divisible item
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2020)

Selling an Item Among a Strategic Bidder and a Profiled Agent
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2025)

Randomized learning-augmented auctions with revenue guarantees
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2024)

Estimating the Expected Social Welfare and Cost of Random Serial Dictatorship
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2024)

An impossibility result for strongly group-strategyproof multi-winner approval-based voting
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2024)

Rethinking Pricing in Energy Markets: Pay-as-Bid vs Pay-as-Clear
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2025)

Quantile agent utility and implications to randomized social choice
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2025)

Can a Few Decide for Many? The Metric Distortion of Sortition
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2024)

Revenue Guarantees in Autobidding Platforms
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2026)

Beyond the worst case: Distortion in impartial culture electorates
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2023)

FAIRFORMER: A transformer architecture for discrete fair division
von: Mascioli, Chris, et al.
Veröffentlicht: (2026)

New Fairness Concepts for Allocating Indivisible Items
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2022)

The Distortion of Prior-Independent b-Matching Mechanisms
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2026)

On Interim Envy-Free Allocation Lotteries
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2021)

Proportional Fairness in Non-Centroid Clustering
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2024)

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
von: Andersen, Martin Jupakkal, et al.
Veröffentlicht: (2025)

Group fairness in dynamic refugee assignment
von: Freund, Daniel, et al.
Veröffentlicht: (2023)

Concentration and maximin fair allocations for subadditive valuations
von: Feige, Uriel, et al.
Veröffentlicht: (2025)

Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2024)

Improved lower bounds for the maximum size of Condorcet domains
von: Karpov, Alexander, et al.
Veröffentlicht: (2026)

Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods
von: Nishimura, Koichi, et al.
Veröffentlicht: (2023)

(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2026)

Convergence of $\text{log}(1/ε)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2024)

On the Interplay between Social Welfare and Tractability of Equilibria
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2023)

On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX
von: Mortazavi, Ali, et al.
Veröffentlicht: (2024)

Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem
von: Kalogiannis, Fivos, et al.
Veröffentlicht: (2024)

Evolution of fairness in hybrid populations with specialised AI agents
von: Song, Zhao, et al.
Veröffentlicht: (2026)

Connectedness in weighted consensus division of graphical cakes between two agents
von: Hanke, Josef, et al.
Veröffentlicht: (2023)

Mechanism design augmented with output advice
von: Christodoulou, George, et al.
Veröffentlicht: (2024)

When agents choose bundles autonomously: guarantees beyond discrepancy
von: Gupta, Sushmita, et al.
Veröffentlicht: (2026)

A potentialization algorithm for games with applications to multi-agent learning in repeated games
von: Lakheshar, Philipp, et al.
Veröffentlicht: (2026)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2025)

An improved bound for the price of anarchy for related machine scheduling
von: Berger, Andre, et al.
Veröffentlicht: (2024)

Improving the Price of Anarchy via Predictions in Parallel-Link Networks
von: Christodoulou, George, et al.
Veröffentlicht: (2025)

Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2026)

Chaos in Autobidding Auctions
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2026)

Efficient $Φ$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2024)

From multi-allocations to allocations, with subadditive valuations
von: Feige, Uriel
Veröffentlicht: (2025)