BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Michal Feldman

Michal Feldman contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game Theoryecon.THComputational ComplexityData Structures and AlgorithmsMultiagent Systemsphysics.soc-phPopulations and Evolution

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

Are Gross Substitutes a Substitute for Submodular Valuations?

The class of gross substitutes (GS) set functions plays a central role in Economics and Computer Science. GS belongs to the hierarchy of {\em complement free} valuations introduced by Lehmann, Lehmann and Nisan, along with other prominent classes: $GS \subsetneq Submodular \subsetneq XOS \subsetneq Subadditive$. The GS class has always been more enigmatic than its counterpart classes, both in its definition and in its relation to the other classes. For example, while it is well understood how closely the Submodular, XOS and Subadditive classes (point-wise) approximate one another, approximability of these classes by GS remained wide open. Our main result is the existence of a submodular valuation (one that is also budget additive) that cannot be approximated by GS within a ratio better than $Ω(\frac{\log m}{\log\log m})$, where $m$ is the number of items. En route, we uncover a new symmetrization operation that preserves GS, which may be of independent interest. We show that our main result is tight with respect to budget additive valuations. Additionally, for a class of submodular functions that we refer to as {\em concave of Rado} valuations (this class greatly extends budget additive valuations), we show approximability by GS within an $O(\log^2m)$ factor.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Bayesian and Randomized Clock Auctions

In a single-parameter mechanism design problem, a provider is looking to sell a service to a group of potential buyers. Each buyer $i$ has a private value $v_i$ for receiving the service and a feasibility constraint restricts which sets of buyers can be served simultaneously. Recent work in economics introduced clock auctions as a superior class of auctions for this problem, due to their transparency, simplicity, and strong incentive guarantees. Subsequent work focused on evaluating the social welfare approximation guarantees of these auctions, leading to strong impossibility results: in the absence of prior information regarding the buyers' values, no deterministic clock auction can achieve a bounded approximation, even for simple feasibility constraints with only two maximal feasible sets. We show that these negative results can be circumvented by using prior information or by leveraging randomization. We provide clock auctions that give a $O(\log\log k)$ approximation for general downward-closed feasibility constraints with $k$ maximal feasible sets for three different information models, ranging from full access to the value distributions to complete absence of information. The more information the seller has, the simpler these auctions are. Under full access, we use a particularly simple deterministic clock auction, called a single-price clock auction, which is only slightly more complex than posted price mechanisms. In this auction, each buyer is offered a single price and a feasible set is selected among those who accept their offers. In the other extreme, where no prior information is available, this approximation guarantee is obtained using a complex randomized clock auction. In addition to our main results, we propose a parameterization that interpolates between single-price clock auctions and general clock auctions, paving the way for an exciting line of future research.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Fair Division under Heterogeneous Matroid Constraints

We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors, and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints, or allow free disposal of items. An open problem is the existence of EF1 complete allocations among heterogeneous agents, where the heterogeneity is both in the agents' feasibility constraints and in their valuations. In this work, we make progress on this problem by providing positive and negative results for different matroid and valuation types. Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) $n$ agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous additive valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable matroid constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

(Almost Full) EFX Exists for Four Agents (and Beyond)

The existence of EFX allocations is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and EFX is known to exist for ($i$) agents with identical valuations, ($ii$) 2 agents, ($iii$) 3 agents with additive valuations, ($iv$) agents with one of two additive valuations and ($v$) agents with two-valued instances. It is also known that EFX exists if one can leave $n-1$ items unallocated, where $n$ is the number of agents. We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and, arguably, to simplify proofs of earlier results. Our main results are ($i$) every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated, ($ii$) every setting with $n$ additive valuations has an EFX allocation with at most $n-2$ unallocated items. Moreover, all of our results extend beyond additive valuations to all nice cancelable valuations (a new class, including additive, unit-demand, budget-additive and multiplicative valuations, among others). Furthermore, using our new techniques, we show that previous results for additive valuations extend to nice cancelable valuations.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Price of Anarchy of Simple Auctions with Interdependent Values

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 single-item settings. On the positive side, we identify a natural condition on information dispersion in the market, termed $γ$-heterogeneity, which enables good PoA guarantees. Under this condition, we show that for single-item settings, the PoA of standard mechanisms degrades gracefully with $γ$. For settings with $m>1$ items we show a separation between two domains: If $n \geq m$, we devise a new simultaneous item auction with good PoA (with respect to $γ$), 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 $n \ll m$, we establish impossibility results even for surprisingly simple scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer

We consider a robust version of the revenue maximization problem, where a single seller wishes to sell $n$ items to a single unit-demand buyer. In this robust version, the seller knows the buyer's marginal value distribution for each item separately, but not the joint distribution, and prices the items to maximize revenue in the worst case over all compatible correlation structures. We devise a computationally efficient (polynomial in the support size of the marginals) algorithm that computes the worst-case joint distribution for any choice of item prices. And yet, in sharp contrast to the additive buyer case (Carroll, 2017), we show that it is NP-hard to approximate the optimal choice of prices to within any factor better than $n^{1/2-ε}$. For the special case of marginal distributions that satisfy the monotone hazard rate property, we show how to guarantee a constant fraction of the optimal worst-case revenue using item pricing; this pricing equates revenue across all possible correlations and can be computed efficiently.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Long-Term Care Facilities as a Risk Factor for Death Due to COVID-19

A large percentage of the deaths from COVID-19 occur among residents of long-term care facilities. There are two possible reasons for this phenomenon. First, the structural features of such settings may lead to death. Alternatively, it is possible that individuals in these facilities are in poorer health than those living elsewhere, and that these individuals would have died even if they had not been in these facilities. Our findings show that, controlling for the population density and the percentage of older adults in the population, there is a significant positive association between the number of long-term care beds per capita and COVID-19 mortality rates. This finding provides support for the claim that long-term care living arrangements (of older people) are a significant risk factor for dying from COVID-19.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On a Competitive Secretary Problem with Deferred Selections

We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models

We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Efficiency of Best-Response Dynamics

Best response (BR) dynamics is a natural method by which players proceed toward a pure Nash equilibrium via a local search method. The quality of the equilibrium reached may depend heavily on the order by which players are chosen to perform their best response moves. A {\em deviator rule} $S$ is a method for selecting the next deviating player. We provide a measure for quantifying the performance of different deviator rules. The {\em inefficiency} of a deviator rule $S$ is the maximum ratio, over all initial profiles $p$, between the social cost of the worst equilibrium reachable by $S$ from $p$ and the social cost of the best equilibrium reachable from $p$. This inefficiency always lies between $1$ and the {\em price of anarchy}. We study the inefficiency of various deviator rules in network formation games and job scheduling games (both are congestion games, where BR dynamics always converges to a pure NE). For some classes of games, we compute optimal deviator rules. Furthermore, we define and study a new class of deviator rules, called {\em local} deviator rules. Such rules choose the next deviator as a function of a restricted set of parameters, and satisfy a natural condition called {\em independence of irrelevant players}. We present upper bounds on the inefficiency of some local deviator rules, and also show that for some classes of games, no local deviator rule can guarantee inefficiency lower than the price of anarchy.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Pricing Multi-Unit Markets

We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted prices, under a range of assumptions about the designer's information and agents' valuations. Our results provide insights about the relative power of uniform and non-uniform prices, the relative difficulty of different valuation classes, and the implications of different informational assumptions. Among other results, we prove constant-factor guarantees for agents with (symmetric) subadditive valuations, even in an incomplete-information setting and with uniform prices.

0 citations0 reviewsNo code linkedOpen access