AEAlon Eden

Alon Eden

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Alon Eden has a total of 31 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Bilateral Trade with Interdependent Values: Information vs. Approximation

    by Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, Thodoris Tsilivis


  • Open Access

    Interdependent Bilateral Trade: Information vs Approximation

    by Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, Thodoris Tsilivis

    Welfare maximization in bilateral trade has been extensively studied in recent years. Previous literature obtained incentive-compatible approximation mechanisms only for the private values case. In this paper, we study welfare maximization in bilateral trade with interdependent values. Designing mechanisms for interdependent settings is much more challenging because the values of the players depend on the private information of the others, requiring complex belief updates and strategic inference. We propose to classify information structures by quantifying the influence that a player's private signal has on their own valuation. We then paint a picture of where approximations are possible and impossible based on these information structures. Finally, we also study the possible approximation ratios for a natural family of information structures.

  • Open Access

    Stable Marriage: Loyalty vs. Competition

    by Amit Ronen, Jonah Evan Hess, Yael Belfer, Simon Mauras, Alon Eden

    We consider the stable matching problem (e.g. between doctors and hospitals) in a one-to-one matching setting, where preferences are drawn uniformly at random. It is known that when doctors propose and the number of doctors equals the number of hospitals, then the expected rank of doctors for their match is $Θ(\log n)$, while the expected rank of the hospitals for their match is $Θ(n/\log n)$, where $n$ is the size of each side of the market. However, when adding even a single doctor, [Ashlagi, Kanoria and Leshno, 2017] show that the tables have turned: doctors have expected rank of $Θ(n/\log n)$ while hospitals have expected rank of $Θ(\log n)$. That is, (slight) competition has a much more dramatically harmful effect than the benefit of being on the proposing side. Motivated by settings where agents inflate their value for an item if it is already allocated to them (termed endowment effect), we study the case where hospitals exhibit ``loyalty". We model loyalty as a parameter $k$, where a hospital currently matched to their $\ell$th most preferred doctor accepts proposals from their $\ell-k-1$th most preferred doctors. Hospital loyalty should help doctors mitigate the harmful effect of competition, as many more outcomes are now stable. However, we show that the effect of competition is so dramatic that, even in settings with extremely high loyalty, in unbalanced markets, the expected rank of doctors already becomes $\tildeΘ(\sqrt{n})$ for loyalty $k=n-\sqrt{n}\log n=n(1-o(1))$.

  • Open Access

    Platform Equilibrium: Analyzing Social Welfare in Online Market Places

    by Alon Eden, Gary Qiurui Ma, David C. Parkes

    We introduce the theoretical study of a Platform Equilibrium in a market with unit-demand buyers and unit-supply sellers. Each seller can join a platform and transact with any buyer or remain off-platform and transact with a subset of buyers whom she knows. Given the constraints on trade, prices form a competitive equilibrium and clears the market. The platform charges a transaction fee to all on-platform sellers, in the form of a fraction of on-platform sellers' price. The platform chooses the fraction to maximize revenue. A Platform Equilibrium is a Nash equilibrium of the game where each seller decides whether or not to join the platform, balancing the effect of a larger pool of buyers to trade with, against the imposition of a transaction fee. Our main insights are:(i) In homogeneous-goods markets, pure equilibria always exist and can be found by a polynomial-time algorithm; (ii) When the platform is unregulated, the resulting Platform Equilibrium guarantees a tight Θ(log(min{m, n}))-approximation of the optimal welfare in homogeneous-goods markets, where n and m are the number of buyers and sellers respectively; (iii) Even light regulation helps: when the platform's fee is capped at α ∈ [0, 1), the price of anarchy is (2-α)/(1--α) for general markets. For example, if the platform takes 30% of the seller's revenue, a rather high fee, our analysis implies the welfare in a Platform Equilibrium is still a 0.412-fraction of the optimal welfare. Our main results extend to markets with multiple platforms, beyond unit-demand buyers, as well as to sellers with production costs. A full version of this paper can be found at https://arxiv.org/abs/2309.08781.


  • Open Access

    Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids

    by Alon Eden, Michal Feldman, Simon Mauras, Divyarthi Mohan

    We study auction design within the widely acclaimed model of interdependent values, introduced by Milgrom and Weber [1982]. In this model, every bidder i has a private signal si for the item for sale, and a public valuation function υi (s1, ..., sn) which maps every vector of private signals (of all bidders) into a real value. A recent line of work established the existence of approximately-optimal mechanisms within this framework, even in the more challenging scenario where each bidder's valuation function υi is also private. This body of work has primarily focused on single-item auctions with two natural classes of valuations: those exhibiting submodularity over signals (SOS) and d-critical valuations. In this work we advance the state of the art on interdependent values with private valuation functions, with respect to both SOS and d-critical valuations. For SOS valuations, we devise a new mechanism that gives an improved approximation bound of 5 for single-item auctions. This mechanism employs a novel variant of an "eating mechanism", leveraging LP-duality to achieve feasibility with reduced welfare loss. For d-critical valuations, we broaden the scope of existing results beyond single-item auctions, introducing a mechanism that gives a (d + 1)-approximation for any environment with matroid feasibility constraints on the set of agents that can be simultaneously served. Notably, this approximation bound is tight, even with respect to single-item auctions.


  • Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue

    by Alon Eden, Michal Feldman, Amos Fiat, Kira Goldner, Anna R. Karlin

    We study combinatorial auctions with interdependent valuations, where each agent i has a private signal si that captures her private information and the valuation function of every agent depends on the entire signal profile, [ ]. The literature in economics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple single-parameter settings (mostly single-item auctions or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guarantees for multidimensional combinatorial auctions achieved by universally ex post incentive-compatible, individually rational mechanisms. Our main results are (i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; (ii) four approximation for any combinatorial auction with multidimensional signals and separable-SOS valuations; and (iii) (k + 3) and (2 log(k) + 4) approximation for any combinatorial auction with single-dimensional signals, with k-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, d-approximate SOS, while losing a factor that depends on d. Funding: A. Eden was partially supported by NSF Award IIS-2007887, the European Research Council (ERC) under the European Union's Seventh Framework Programme [FP7/2007-2013]/ERC Grant Agreement 337122, by the Israel Science Foundation [Grant 317/17], and by an Amazon research award. M. Feldman received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program [Grant Agreement 866132], by the Israel Science Foundation [Grant 317/17], by an Amazon research award, and by the NSF-BSF [Grant 2020788]. The work of K. Goldner was supported partially by NSF awards DMS-1903037 and CNS-2228610 and a Shibulal Family Career Development Professorship. A. R. Karlin was supported by the NSF-CCF [Grant 1813135].


  • Open Access

    Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids

    by Alon Eden, Michal Feldman, Simon Mauras, Divyarthi Mohan

    We study auction design within the widely acclaimed model of interdependent values, introduced by Milgrom and Weber [1982]. In this model, every bidder $i$ has a private signal $s_i$ for the item for sale, and a public valuation function $v_i(s_1,\ldots,s_n)$ which maps every vector of private signals (of all bidders) into a real value. A recent line of work established the existence of approximately-optimal mechanisms within this framework, even in the more challenging scenario where each bidder's valuation function $v_i$ is also private. This body of work has primarily focused on single-item auctions with two natural classes of valuations: those exhibiting submodularity over signals (SOS) and $d$-critical valuations. In this work we advance the state of the art on interdependent values with private valuation functions, with respect to both SOS and $d$-critical valuations. For SOS valuations, we devise a new mechanism that gives an improved approximation bound of $5$ for single-item auctions. This mechanism employs a novel variant of an "eating mechanism", leveraging LP-duality to achieve feasibility with reduced welfare loss. For $d$-critical valuations, we broaden the scope of existing results beyond single-item auctions, introducing a mechanism that gives a $(d+1)$-approximation for any environment with matroid feasibility constraints on the set of agents that can be simultaneously served. Notably, this approximation bound is tight, even with respect to single-item auctions.


  • Open Access

    Stackelberg POMDP: A Reinforcement Learning Approach for Economic Design

    by Gianluca Brero, Alon Eden, Darshan Chakrabarti, Matthias Gerstgrasser, Amy Greenwald, Vincent Li, David C. Parkes

    We introduce a reinforcement learning framework for economic design where the interaction between the environment designer and the participants is modeled as a Stackelberg game. In this game, the designer (leader) sets up the rules of the economic system, while the participants (followers) respond strategically. We integrate algorithms for determining followers' response strategies into the leader's learning environment, providing a formulation of the leader's learning problem as a POMDP that we call the Stackelberg POMDP. We prove that the optimal leader's strategy in the Stackelberg game is the optimal policy in our Stackelberg POMDP under a limited set of possible policies, establishing a connection between solving POMDPs and Stackelberg games. We solve our POMDP under a limited set of policy options via the centralized training with decentralized execution framework. For the specific case of followers that are modeled as no-regret learners, we solve an array of increasingly complex settings, including problems of indirect mechanism design where there is turn-taking and limited communication by agents. We demonstrate the effectiveness of our training framework through ablation studies. We also give convergence results for no-regret learners to a Bayesian version of a coarse-correlated equilibrium, extending known results to the case of correlated types.


  • Open Access

    Constant Approximation for Private Interdependent Valuations

    by Alon Eden, Michal Feldman, Kira Goldner, Simon Mauras, Divyarthi Mohan

    The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $s_1, \ldots, s_n$ of the $n$ bidders and public valuation functions $v_i(s_1, \ldots, s_n)$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and private valuations, and established $O(\log^2 n)$-approximation for SOS valuations. In this paper we show that this setting admits a constant factor approximation, settling the open question raised by Eden et al. (2022).

  • Open Access

    Platform Behavior under Market Shocks: A Simulation Framework and Reinforcement-Learning Based Study

    by Xintong Wang, Gary Qiurui Ma, Alon Eden, Clara Li, Alexander Trott, Stephan Zheng, David Parkes

    We study the behavior of an economic platform (e.g., Amazon, Uber Eats, Instacart) under shocks, such as COVID-19 lockdowns, and the effect of different regulation considerations. To this end, we develop a multi-agent simulation environment of a platform economy in a multi-period setting where shocks may occur and disrupt the economy. Buyers and sellers are heterogeneous and modeled as economically-motivated agents, choosing whether or not to pay fees to access the platform. We use deep reinforcement learning to model the fee-setting and matching behavior of the platform, and consider two major types of regulation frameworks: (1) taxation policies and (2) platform fee restrictions. We offer a number of simulated experiments that cover different market settings and shed light on regulatory tradeoffs. Our results show that while many interventions are ineffective with a sophisticated platform actor, we identify a particular kind of regulation—fixing fees to the optimal, no-shock fees while still allowing a platform to choose how to match buyers and sellers—as holding promise for promoting the efficiency and resilience of the economic system.