Author name cluster

Alon Eden

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

NeurIPS Conference 2024 Conference Paper

Plant-and-Steal: Truthful Fair Allocations via Predictions

Ilan R. Cohen
Alon Eden
Talya Eden
Arsen Vasilyan

We study truthful mechanisms for approximating the Maximin-Share (MMS) allocation of agents with additive valuations for indivisible goods. Algorithmically, constant factor approximations exist for the problem for any number of agents. When adding incentives to the mix, a jarring result by Amanatidis, Birmpas, Christodoulou, and Markakis [EC 2017] shows that the best possible approximation for two agents and $m$ items is $\lfloor \frac{m}{2} \rfloor$. We adopt a learning-augmented framework to investigate what is possible when some prediction on the input is given. For two agents, we give a truthful mechanism that takes agents' ordering over items as prediction. When the prediction is accurate, we give a $2$-approximation to the MMS (consistency), and when the prediction is off, we still get an $\lceil \frac{m}{2} \rceil$-approximation to the MMS (robustness). We further show that the mechanism's performance degrades gracefully in the number of ``mistakes" in the prediction; i. e. , we interpolate (up to constant factors) between the two extremes: when there are no mistakes, and when there is a maximum number of mistakes. We also show an impossibility result on the obtainable consistency for mechanisms with finite robustness. For the general case of $n\ge 2$ agents, we give a 2-approximation mechanism for accurate predictions, with relaxed fallback guarantees. Finally, we give experimental results which illustrate when different components of our framework, made to insure consistency and robustness, come into play.

PDF Details DOI

FOCS Conference 2023 Conference Paper

Constant Approximation for Private Interdependent Valuations

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}\left(s_{1}, \ldots, s_{n}\right)$. 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\left(\log ^{2} n\right)$-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).

Details

SODA Conference 2022 Conference Paper

Private Interdependent Valuations

Alon Eden
Kira Goldner
Shuran Zheng

We consider the single-item interdependent value setting, where there is a single item sold by a monopolist, n buyers, and each buyer has a private signal si describing a piece of information about the item. Additionally, each bidder i has a valuation function v i ( s 1, …, s n ) mapping the (private) signals of all buyers into a positive real number representing their value for the item. This setting captures scenarios where the item's information is asymmetric or dispersed among agents, such as in competitions for oil drilling rights, or in auctions for art pieces. Due to the increased complexity of this model compared to the standard private values model, it is generally assumed that each bidder's valuation function v i is public knowledge to the seller or all other buyers. But in many situations, the seller may not know the bidders' valuation functions—how a bidder aggregates signals into a valuation is often their private information. In this paper, we design mechanisms that guarantee approximately-optimal social welfare while satisfying ex-post incentive compatibility and individually rationality for the case where the valuation functions are private to the bidders, and thus may be strategically misreported to the seller. When the valuations are public, it is possible for optimal social welfare to be attained by a deterministic mechanism when the valuations satisfy a single-crossing condition. In contrast, when the valuations are the bidders' private information, we show that no finite bound on the social welfare can be achieved by any deterministic mechanism even under single-crossing. Moreover, no randomized mechanism can guarantee better than n -approximation. We thus consider valuation functions that are submodular over signals (SOS), introduced in the context of combinatorial auctions in a recent breakthrough paper by Eden et al. [EC'19]. Our main result is an O (log 2 n )-approximation randomized mechanism for buyers with private signals and valuations under the SOS condition. We also give a tight Θ( k )-approximation mechanism for the case each agent's valuation depends on at most k other signals even for unknown k.

Details

AAAI Conference 2021 Conference Paper

PoA of Simple Auctions with Interdependent Values

Alon Eden
Michal Feldman
Inbal Talgam-Cohen
Ori Zviran

We expand the literature on the price of anarchy (PoA) of simultaneous item auctions by considering settings with correlated values; we do this via the fundamental economic model of interdependent values (IDV). It is well-known that in multi-item settings with private values, correlated values can lead to bad PoA, which can be polynomially large in the number of agents n. In the more general model of IDV, we show that the PoA can be polynomially large even in singleitem settings. On the positive side, we identify a natural condition on information dispersion in the market, which enables good PoA guarantees. Under this condition, we show that for single-item settings, the PoA of standard mechanisms degrades gracefully. For settings with multiple items we show a separation between two domains: If there are more buyers, we devise a new simultaneous item auction with good PoA, under limited information asymmetry. To the best of our knowledge, this is the first positive PoA result for correlated values in multi-item settings. The main technical difficulty in establishing this result is that the standard tool for establishing PoA results — the smoothness framework — is unsuitable for IDV settings, and so we must introduce new techniques to address the unique challenges imposed by such settings. In the domain of more items, we establish impossibility results even for surprisingly simple scenarios.

PDF Details

AAAI Conference 2021 Conference Paper

Reinforcement Learning of Sequential Price Mechanisms

Gianluca Brero
Alon Eden
Matthias Gerstgrasser
David Parkes
Duncan Rheingans-Yoo

We introduce the use of reinforcement learning for indirect mechanisms, working with the existing class of sequential price mechanisms, which generalizes both serial dictatorship and posted price mechanisms and essentially characterizes all strongly obviously strategyproof mechanisms. Learning an optimal mechanism within this class forms a partiallyobservable Markov decision process. We provide rigorous conditions for when this class of mechanisms is more powerful than simpler static mechanisms, for sufficiency or insufficiency of observation statistics for learning, and for the necessity of complex (deep) policies. We show that our approach can learn optimal or near-optimal mechanisms in several experimental settings.

PDF Details

SODA Conference 2015 Conference Paper

Pricing Online Decisions: Beyond Auctions

Ilan Reuven Cohen
Alon Eden
Amos Fiat
Lukasz Jez

We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the same performance as the best online algorithm. This holds in a wide variety of settings. Unlike online algorithms that learn about the event, and then make enforcable decisions, prices are posted without knowing the future events or even the current event, and are thus inherently dominant strategy incentive compatible. In particular we show that one can give efficient posted price mechanisms for metrical task systems, some instances of the k -server problem, and metrical matching problems. We give both deterministic and randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of free parking exponentially.

Details