SMSimon Mauras

Simon Mauras

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Simon Mauras has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Online Combinatorial Allocation with Interdependent Values

    by Michal Feldman, Simon Mauras, Divyarthi Mohan, Rebecca Reiffenhäuser

    We study online combinatorial allocation problems in the secretary setting, under interdependent values. In the interdependent model, introduced by Milgrom and Weber (1982), each agent possesses a private signal that captures her information about an item for sale, and the value of every agent depends on the signals held by all agents. Mauras, Mohan, and Reiffenhäuser (2024) were the first to study interdependent values in online settings, providing constant-approximation guarantees for secretary settings, where agents arrive online along with their signals and values, and the goal is to select the agent with the highest value. In this work, we extend this framework to {\em combinatorial} secretary problems, where agents have interdependent valuations over {\em bundles} of items, introducing additional challenges due to both combinatorial structure and interdependence. We provide $2e$-competitive algorithms for a broad class of valuation functions, including submodular and XOS functions, matching the approximation guarantees in the single-choice secretary setting. Furthermore, our results cover the same range of valuation classes for which constant-factor algorithms exist in classical (non-interdependent) secretary settings, while incurring only an additional factor of $2$ due to interdependence. Finally, we extend our study to strategic settings, and provide a $4e$-competitive truthful mechanism for online bipartite matching with interdependent valuations, again meeting the frontier of what is known, even without interdependence.

  • 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

    Optimal Stopping with Interdependent Values

    by Simon Mauras, Divyarthi Mohan, Rebecca Reiffenhäuser

    We study online selection problems in both the prophet and secretary settings, when arriving agents have interdependent values. In the interdependent values model, introduced in the seminal work of Milgrom and Weber [1982], each agent has a private signal and the value of an agent is a function of the signals held by all agents. Results in online selection crucially rely on some degree of independence of values, which is conceptually at odds with the interdependent values model. For prophet and secretary models under the standard independent values assumption, prior works provide constant factor approximations to the welfare. On the other hand, when agents have interdependent values, prior works in Economics and Computer Science provide truthful mechanisms that obtain optimal and approximately optimal welfare under certain assumptions on the valuation functions. We bring together these two important lines of work and provide the first constant factor approximations for prophet and secretary problems with interdependent values. We consider both the algorithmic setting, where agents are non-strategic (but have interdependent values), and the mechanism design setting with strategic agents. All our results are constructive and use simple stopping rules.


  • 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.