16 citations · 190 across the 78 of their papers we have counts for
62 papers · 1 filter
Ex-Post Equilibria: Structure and Computation
Francesco Giordano, Julien Grand-Clément, Christian Kroer
This paper studies ex-post equilibria (EPEs) in simultaneous-move games with parameter uncertainty. We first compare EPEs with existing notions of robust equilibrium and provide a…
Competitive Equilibrium in Labor Economies through the Lens of Goods and Chores Fisher Markets
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +2
In this paper, we study a two-sided labor market that couples the classical Fisher market with goods and the Fisher market with bads into a single unified framework. In our model,…
Online Generalized-Mean Welfare Maximization: Achieving Near-Optimal Regret from Samples
Zongjun Yang, Rachitesh Kumar, Christian Kroer
We study online fair allocation of sequentially arriving items among agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defin…
A Direct Second-Order Method for Solving Two-Player Zero-Sum Games
David Yang, Yuan Gao, Tianyi Lin +1
We introduce, to our knowledge, the first direct second-order method for computing Nash equilibria in two-player zero-sum games. To do so, we construct a Douglas-Rachford-style spl…
Computing Lindahl Equilibrium for Public Goods with and without Funding Caps
Christian Kroer, Dominik Peters
Lindahl equilibrium is a solution concept for allocating a fixed budget across several divisible public goods. It always lies in the weak core, meaning that the equilibrium allocat…
Contested Logistics: A Game-Theoretic Approach
Jakub Cerny, Chun Kai Ling, Darshan Chakrabarti +4
We introduce Contested Logistics Games, a variant of logistics problems that account for the presence of an adversary that can disrupt the movement of goods in selected areas. We m…
Online Fair Allocation with Best-of-Many-Worlds Guarantees
Zongjun Yang, Luofeng Liao, Yuan Gao +1
We investigate the online fair allocation problem with sequentially arriving items under various input models, with the goal of balancing fairness and efficiency. We propose the un…
Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions
Luofeng Liao, Christian Kroer
We initiate the study of statistical inference and A/B testing for two market equilibrium models: linear Fisher market (LFM) equilibrium and first-price pacing equilibrium (FPPE).…
On the Convergence of Tâtonnement for Linear Fisher Markets
Tianlong Nan, Yuan Gao, Christian Kroer
Tâtonnement is a simple, intuitive market process where prices are iteratively adjusted based on the difference between demand and supply. Many variants under different market assu…
Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimi…
Layered Graph Security Games
Jakub Černý, Chun Kai Ling, Christian Kroer +1
Security games model strategic interactions in adversarial real-world applications. Such applications often involve extremely large but highly structured strategy sets (e.g., selec…
Extensive-Form Game Solving via Blackwell Approachability on Treeplexes
Darshan Chakrabarti, Julien Grand-Clément, Christian Kroer
In this paper, we introduce the first algorithmic framework for Blackwell approachability on the sequence-form polytope, the class of convex polytopes capturing the strategies of p…
Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm
Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta +1
We study the computation of competitive equilibrium for Fisher markets with agents and divisible chores. Competitive equilibria for chores are known to correspond to the no…
Automated Design of Affine Maximizer Mechanisms in Dynamic Settings
Michael Curry, Vinzenz Thoma, Darshan Chakrabarti +5
Dynamic mechanism design is a challenging extension to ordinary mechanism design in which the mechanism designer must make a sequence of decisions over time in the face of possibly…
Efficient Learning in Polyhedral Games via Best Response Oracles
Darshan Chakrabarti, Gabriele Farina, Christian Kroer
We study online learning and equilibrium computation in games with polyhedral decision sets, a property shared by both normal-form games and extensive-form games (EFGs), when the l…
Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching (RM). Despite their widespread use for solving rea…
Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees
Zongjun Yang, Luofeng Liao, Christian Kroer
We study an online allocation problem with sequentially arriving items and adversarially chosen agent values, with the goal of balancing fairness and efficiency. Our goal is to stu…
Block-Coordinate Methods and Restarting for Solving Extensive-Form Games
Darshan Chakrabarti, Jelena Diakonikolas, Christian Kroer
Coordinate descent methods are popular in machine learning and optimization for their simple sparse updates and excellent practical performance. In the context of large-scale seque…
Regret Matching+: (In)Stability and Fast Convergence in Games
Gabriele Farina, Julien Grand-Clément, Christian Kroer +2
Regret Matching+ (RM+) and its variants are important algorithms for solving large-scale games. However, a theoretical understanding of their success in practice is still a mystery…
Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates
Tianlong Nan, Yuan Gao, Christian Kroer
We consider the problem of large-scale Fisher market equilibrium computation through scalable first-order optimization methods. It is well-known that market equilibria can be captu…
Fair Notification Optimization: An Auction Approach
Christian Kroer, Deeksha Sinha, Xuan Zhang +2
Notifications are important for the user experience in mobile apps and can influence their engagement. However, too many notifications can be disruptive for users. A typical mobile…
Online Learning under Budget and ROI Constraints via Weak Adaptivity
Matteo Castiglioni, Andrea Celli, Christian Kroer
We study online learning problems in which a decision maker has to make a sequence of costly decisions, with the goal of maximizing their expected reward while adhering to budget a…
Implementing Fairness Constraints in Markets Using Taxes and Subsidies
Alexander Peysakhovich, Christian Kroer, Nicolas Usunier
Fisher markets are those where buyers with budgets compete for scarce items, a natural model for many real world markets including online advertising. A market equilibrium is a set…
Optimal Efficiency-Envy Trade-Off via Optimal Transport
Steven Yin, Christian Kroer
We consider the problem of allocating a distribution of items to recipients where each recipient has to be allocated a fixed, prespecified fraction of all items, while ensuring…