Ron Lavi

AAAI Conference 2023 Conference Paper

From Monopoly to Competition: Optimal Contests Prevail

• Xiaotie Deng
• Yotam Gafni
• Ron Lavi
• Tao Lin
• Hongyi Ling

We study competition among contests in a general model that allows for an arbitrary and heterogeneous space of contest design and symmetric contestants. The goal of the contest designers is to maximize the contestants' sum of efforts. Our main result shows that optimal contests in the monopolistic setting (i.e., those that maximize the sum of efforts in a model with a single contest) form an equilibrium in the model with competition among contests. Under a very natural assumption these contests are in fact dominant, and the equilibria that they form are unique. Moreover, equilibria with the optimal contests are Pareto-optimal even in cases where other equilibria emerge. In many natural cases, they also maximize the social welfare.

JAIR Journal 2021 Journal Article

Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with an Application to False-name Manipulation

• Yotam Gafni
• Ron Lavi
• Moshe Tennenholtz

Weighted voting games apply to a wide variety of multi-agent settings. They enable the formalization of power indices which quantify the coalitional power of players. We take a novel approach to the study of the power of big vs. small players in these games. We model small (big) players as having single (multiple) votes. The aggregate relative power of big players is measured w.r.t. their votes proportion. For this ratio, we show small constant worst-case bounds for the Shapley-Shubik and the Deegan-Packel indices. In sharp contrast, this ratio is unbounded for the Banzhaf index. As an application, we define a false-name strategic normal form game where each big player may split its votes between false identities, and study its various properties. Together, our results provide foundations for the implications of players’ size, modeled as their ability to split, on their relative power.

IJCAI Conference 2021 Conference Paper

Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with Application to False-name Manipulation

• Yotam Gafni
• Ron Lavi
• Moshe Tennenholtz

Weighted voting games are applicable to a wide variety of multi-agent settings. They enable the formalization of power indices which quantify the coalitional power of players. We take a novel approach to the study of the power of big vs. ~small players in these games. We model small (big) players as having single (multiple) votes. The aggregate relative power of big players is measured w. r. t. ~their votes proportion. For this ratio, we show small constant worst-case bounds for the Shapley-Shubik and the Deegan-Packel indices. In sharp contrast, this ratio is unbounded for the Banzhaf index. As an application, we define a false-name strategic normal form game where each big player may split its votes between false identities, and study its various properties. Together our results provide foundations for the implications of players' size, modeled as their ability to split, on their relative power.

NeurIPS Conference 2020 Conference Paper

A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling

• Xiaotie Deng
• Ron Lavi
• Tao Lin
• Qi Qi
• Wenwei WANG
• Xiang Yan

The Empirical Revenue Maximization (ERM) is one of the most important price learning algorithms in auction design: as the literature shows it can learn approximately optimal reserve prices for revenue-maximizing auctioneers in both repeated auctions and uniform-price auctions. However, in these applications the agents who provide inputs to ERM have incentives to manipulate the inputs to lower the outputted price. We generalize the definition of an incentive-awareness measure proposed by Lavi et al (2019), to quantify the reduction of ERM's outputted price due to a change of m>=1 out of N input samples, and provide specific convergence rates of this measure to zero as N goes to infinity for different types of input distributions. By adopting this measure, we construct an efficient, approximately incentive-compatible, and revenue-optimal learning algorithm using ERM in repeated auctions against non-myopic bidders, and show approximate group incentive-compatibility in uniform-price auctions.

TCS Journal 2020 Journal Article

Bayesian generalized network design

• Yuval Emek
• Shay Kutten
• Ron Lavi
• Yangguang Shi

We study network coordination problems, as captured by the setting of generalized network design (Emek et al. , STOC 2018 [18]), in the face of uncertainty resulting from partial information that the network users hold regarding the actions of their peers. This uncertainty is formalized using Alon et al. 's Bayesian ignorance framework (TCS 2012 [1]). While the approach of Alon et al. is purely combinatorial, the current paper takes into account computational considerations: Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty.

IJCAI Conference 2020 Conference Paper

Competition Among Contests: a Safety Level Analysis

• Ron Lavi
• Omer Shiran-Shvarzbard

We study a competition among two contests, where each contest designer aims to attract as much effort as possible. Such a competition exists in reality, e. g. , in crowd-sourcing websites. Our results are phrased in terms of the ``relative prize power'' of a contest, which is the ratio of the total prize offered by this contest designer relative to the sum of total prizes of the two contests. When contestants have a quasi-linear utility function that captures both a risk-aversion effect and a cost of effort, we show that a simple contest attracts a total effort which approaches the relative prize power of the contest designer assuming a large number of contestants. This holds regardless of the contest policy of the opponent, hence providing a ``safety level'' which is a robust notion similar in spirit to the max-min solution concept.

NeurIPS Conference 2020 Conference Paper

Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes

• Yuval Emek
• Ron Lavi
• Rad Niazadeh
• Yangguang Shi

In this paper, a rather general online problem called \emph{dynamic resource allocation with capacity constraints (DRACC)} is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. As the existing online learning techniques do not yield vanishing-regret mechanisms for this problem, we develop a novel online learning framework defined over deterministic Markov decision processes with \emph{dynamic} state transition and reward functions. We then prove that if the Markov decision process is guaranteed to admit an oracle that can simulate any given policy from any initial state with bounded loss --- a condition that is satisfied in the DRACC problem --- then the online learning problem can be solved with vanishing regret. Our proof technique is based on a reduction to online learning with \emph{switching cost}, in which an online decision maker incurs an extra cost every time she switches from one arm to another. We formally demonstrate this connection and further show how DRACC can be used in our proposed applications of stateful pricing.

AAAI Conference 2020 Conference Paper

VCG under Sybil (False-Name) Attacks – A Bayesian Analysis

• Yotam Gafni
• Ron Lavi
• Moshe Tennenholtz

VCG is a classical combinatorial auction that maximizes social welfare. However, while the standard single-item Vickrey auction is false-name-proof, a major failure of multi-item VCG is its vulnerability to false-name attacks. This occurs already in the natural bare minimum model in which there are two identical items and bidders are single-minded. Previous solutions to this challenge focused on developing alternative mechanisms that compromise social welfare. We re-visit the VCG auction vulnerability and consider the bidder behavior in Bayesian settings. In service of that we introduce a novel notion, termed the granularity threshold, that characterizes VCG Bayesian resilience to false-name attacks as a function of the bidder type distribution. Using this notion we show a large class of cases in which VCG indeed obtains Bayesian resilience for the two-item single-minded setting.

STOC Conference 2018 Conference Paper

Approximating generalized network design under (dis)economies of scale with applications to energy efficiency

• Yuval Emek
• Shay Kutten
• Ron Lavi
• Yangguang Shi

In a generalized network design (GND) problem, a set of resources are assigned (non-exclusively) to multiple requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource specific cost function. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS), namely, cost functions that appear subadditive for small loads and superadditive for larger loads.

IJCAI Conference 2018 Conference Paper

Traffic Light Scheduling, Value of Time, and Incentives

• Argyrios Deligkas
• Erez Karpas
• Ron Lavi
• Rann Smorodinsky

We study the intersection signalling control problem for cars with heterogeneous valuations of time (VoT). We are interested in a control algorithm that has some desirable properties: (1) it induces cars to report their VoT truthfully, (2) it minimizes the value of time lost for cars waiting at the intersection, and (3) it is computationally efficient. We obtain three main results: (1) We describe a computationally efficient heuristic forward search approach to solve the static problem. Simulation results show that this method is significantly faster than the dynamic-programming approach to solve the static problem (which is by itself polynomial time). We therefore believe that our algorithm can be commercially implemented. (2) We extend the solution of the static problem to the dynamic case. We couple our algorithm with a carefully designed payment scheme which yields an incentive compatible mechanism. In other words, it is the best interest of each car to truthfully report its VoT. (3) We describe simulation results that compare the social welfare obtained by our scheduling algorithm, as measured by the total value of waiting time, to the social welfare obtained by other intersection signalling control methods.

AAAI Conference 2013 Conference Paper

Composition Games for Distributed Systems: The EU Grant Games

• Shay Kutten
• Ron Lavi
• Amitabh Trehan

We analyze ways by which people decompose into groups in distributed systems. We are interested in systems in which an agent can increase its utility by connecting to other agents, but must also pay a cost that increases with the size of the system. The right balance is achieved by the right size group of agents. We formulate and analyze three intuitive and realistic games and show how simple changes in the protocol can drastically improve the price of anarchy of these games. In particular, we identify two important properties for a low price of anarchy: agreement in joining the system, and the possibility of appealing a rejection from a system. We show that the latter property is especially important if there are some preexisting constraints regarding who may collaborate (or communicate) with whom.

FOCS Conference 2008 Conference Paper

Multi-unit Auctions with Budget Limits

• Shahar Dobzinski
• Ron Lavi
• Noam Nisan

We study multi-unit auctions where the bidders have a budget constraint, a situation very common in practice that has received very little attention in the auction theory literature. Our main result is an impossibility: there are no incentive-compatible auctions that always produce a Pareto-optimal allocation. We also obtain some surprising positive results for certain special cases.

SODA Conference 2006 Conference Paper

Single-value combinatorial auctions and implementation in undominated strategies

• Moshe Babaioff
• Ron Lavi
• Elan Pavlov

SODA Conference 2005 Conference Paper

Online ascending auctions for gradually expiring items

• Ron Lavi
• Noam Nisan

FOCS Conference 2005 Conference Paper

Truthful and Near-Optimal Mechanism Design via Linear Programming

• Ron Lavi
• Chaitanya Swamy

We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for packing domains, any /spl alpha/-approximation algorithm that also bounds the integrality gap of the IF relaxation of the problem by a can be used to construct an /spl alpha/-approximation mechanism that is truthful in expectation. This immediately yields a variety of new and significantly improved results for various problem domains and furthermore, yields truthful (in expectation) mechanisms with guarantees that match the best known approximation guarantees when truthfulness is not required. In particular, we obtain the first truthful mechanisms with approximation guarantees for a variety of multi-parameter domains. We obtain truthful (in expectation) mechanisms achieving approximation guarantees of O(/spl radic/m) for combinatorial auctions (CAs), (1 + /spl epsi/ ) for multiunit CAs with B = /spl Omega/(log m) copies of each item, and 2 for multiparameter knapsack problems (multiunit auctions). Our construction is based on considering an LP relaxation of the problem and using the classic VCG mechanism by W. Vickrey (1961), E. Clarke (1971) and T. Groves (1973) to obtain a truthful mechanism in this fractional domain. We argue that the (fractional) optimal solution scaled down by a, where a is the integrality gap of the problem, can be represented as a convex combination of integer solutions, and by viewing this convex combination as specifying a probability distribution over integer solutions, we get a randomized, truthful in expectation mechanism. Our construction can be seen as a way of exploiting VCG in a computational tractable way even when the underlying social-welfare maximization problem is NP-hard.

TCS Journal 2004 Journal Article

Competitive analysis of incentive compatible on-line auctions

• Ron Lavi
• Noam Nisan

This paper studies auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such auctions, on-line auctions. We first characterize exactly on-line auctions that are incentive compatible, i. e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible on-line auctions. We obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. This auction has an optimal competitive ratio, both in terms of seller's revenue and in terms of the total social efficiency obtained.

FOCS Conference 2003 Conference Paper

Towards a Characterization of Truthful Combinatorial Auctions

• Ron Lavi
• Ahuva Mu'alem
• Noam Nisan

This paper analyzes incentive compatible (truthful) mechanisms over restricted domains of preferences, the leading example being combinatorial auctions. Our work generalizes the characterization of Roberts (1979) who showed that truthful mechanisms over unrestricted domains with at least 3 possible outcomes must be "affine maximizers". We show that truthful mechanisms for combinatorial auctions (and related restricted domains) must be "almost affine maximizers" if they also satisfy an additional requirement of "independence of irrelevant alternatives". This requirement is without loss of generality for unrestricted domains as well as for auctions between two players where all goods must be allocated. This implies unconditional results for these cases, including a new proof of Roberts' theorem. The computational implications of this characterization are severe, as reasonable "almost affine maximizers" are shown to be as computationally hard as exact optimization. This implies the near-helplessness of such truthful polynomial-time auctions in all cases where exact optimization is computationally intractable.