Cover Image

Complexity of Auctions with Interdependence

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Loiseau, Patrick, Mauras, Simon, Xu, Minrui
Format:	Preprint
Published:	2026
Subjects:	Computer Science and Game Theory Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
by: Eden, Alon, et al.
Published: (2024)

Optimal Stopping with Interdependent Values
by: Mauras, Simon, et al.
Published: (2024)

Online Combinatorial Allocation with Interdependent Values
by: Feldman, Michal, et al.
Published: (2025)

Unravelling Expressive Delegations: Complexity and Normative Analysis
by: Tyrovolas, Giannis, et al.
Published: (2023)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
by: Koenemann, Jochen, et al.
Published: (2021)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
by: Kawase, Sota, et al.
Published: (2024)

Nemesis, an Escape Game in Graphs
by: Bergé, Pierre, et al.
Published: (2026)

Hedonic Seat Arrangement Problems
by: Bodlaender, Hans L., et al.
Published: (2020)

Core Stability in Additively Separable Hedonic Games of Low Treewidth
by: Hanaka, Tesshu, et al.
Published: (2024)

The Price of Justified Representation
by: Elkind, Edith, et al.
Published: (2021)

A Smoothed FPTAS for Equilibria in Congestion Games
by: Giannakopoulos, Yiannis
Published: (2023)

Satisfactory Budget Division
by: Gourvès, Laurent, et al.
Published: (2025)

A Quadratic Lower Bound for Stable Roommates Solvability
by: Rosenbaum, Will
Published: (2025)

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
by: Benedek, Márton, et al.
Published: (2023)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
by: Chen, Xi, et al.
Published: (2024)

EF1 and EFX Orientations
by: Deligkas, Argyrios, et al.
Published: (2024)

Truthful Matching with Online Items and Offline Agents
by: Feldman, Michal, et al.
Published: (2022)

Partitioned Matching Games for International Kidney Exchange
by: Benedek, Márton, et al.
Published: (2023)

A Strongly Polynomial Algorithm for Arctic Auctions
by: Garg, Jugal, et al.
Published: (2026)

Prophet Upper Bounds for Online Matching and Auctions
by: Soto, José, et al.
Published: (2024)

Dynamic Debt Swapping in Financial Networks
by: Froese, Henri, et al.
Published: (2023)

Repeated Descent: A Framework for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2026)

Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments
by: Ganesh, Aadityan, et al.
Published: (2025)

A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions
by: Charalampopoulos, Andreas, et al.
Published: (2025)

Prophet Inequalities: Competing with the Top $\ell$ Items is Easy
by: Molina, Mathieu, et al.
Published: (2024)

On Binary Networked Public Goods Game with Altruism
by: Maiti, Arnab, et al.
Published: (2022)

Online Combinatorial Allocations and Auctions with Few Samples
by: Dütting, Paul, et al.
Published: (2024)

On the Complexity of the Two-Stage Majoritarian Rule
by: Yang, Yongjie
Published: (2023)

Min-Max Optimization Requires Exponentially Many Queries
by: Bernasconi, Martino, et al.
Published: (2026)

On the Parameterized Complexity of Controlling Amendment and Successive Winners
by: Yang, Yongjie
Published: (2025)

Sample Complexity of Posted Pricing for a Single Item
by: Jin, Billy, et al.
Published: (2024)

Strategizing against No-Regret Learners in First-Price Auctions
by: Rubinstein, Aviad, et al.
Published: (2024)

Procurement Auctions via Approximately Optimal Submodular Optimization
by: Deng, Yuan, et al.
Published: (2024)

Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs
by: Vazirani, Vijay V.
Published: (2025)

Combinatorial Pen Testing (or Consumer Surplus of Deferred-Acceptance Auctions)
by: Ganesh, Aadityan, et al.
Published: (2023)

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
by: Cesa-Bianchi, Nicolò, et al.
Published: (2023)

Bipartiteness in Progressive Second-Price Multi-Auction Networks with Perfect Substitute
by: Blazek, Jordana, et al.
Published: (2025)

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
by: Golrezaei, Negin, et al.
Published: (2024)

Attractors Is All You Need: Parity Games In Polynomial Time
by: van der Heijden, Rick
Published: (2025)