BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jason Hartline

Jason Hartline appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryData Structures and Algorithmsecon.THMachine Learning

Catalog footprint

What is connected

13works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

13 published item(s)

preprint2022arXiv

Bias-Variance Games

Firms engaged in electronic commerce increasingly rely on predictive analytics via machine-learning algorithms to drive a wide array of managerial decisions. The tuning of many standard machine learning algorithms can be understood as trading off bias (i.e., accuracy) with variance (i.e., precision) in the algorithm's predictions. The goal of this paper is to understand how competition between firms affects their strategic choice of such algorithms. To this end, we model the interaction of two firms choosing learning algorithms as a game and analyze its equilibria. Absent competition, players care only about the magnitude of predictive error and not its source. In contrast, our main result is that with competition, players prefer to incur error due to variance rather than due to bias, even at the cost of higher total error. In addition, we show that competition can have counterintuitive implications -- for example, reducing the error incurred by a firm's algorithm can be harmful to that firm -- but we provide conditions under which such phenomena do not occur. In addition to our theoretical analysis, we also validate our insights by applying our metrics to several publicly available datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Benchmark Design and Prior-independent Optimization

This paper compares two leading approaches for robust optimization in the models of online algorithms and mechanism design. Competitive analysis compares the performance of an online algorithm to an offline benchmark in worst-case over inputs, and prior-independent mechanism design compares the expected performance of a mechanism on an unknown distribution (of inputs, i.e., agent values) to the optimal mechanism for the distribution in worst case over distributions. For competitive analysis, a critical concern is the choice of benchmark. This paper gives a method for selecting a good benchmark. We show that optimal algorithm/mechanism for the optimal benchmark are equal to the prior-independent optimal algorithm/mechanism. We solve a central open question in prior-independent mechanism design, namely we identify the prior-independent revenue-optimal mechanism for selling a single item to two agents with i.i.d. and regularly distributed values. Via this solution and the above equivalence of prior-independent mechanism design and competitive analysis (a.k.a. prior-free mechanism design) we show that the standard method for lower bounds of prior-free mechanisms is not generally tight for the benchmark design program.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Inference from Auction Prices

Econometric inference allows an analyst to back out the values of agents in a mechanism from the rules of the mechanism and bids of the agents. This paper gives an algorithm to solve the problem of inferring the values of agents in a dominant-strategy mechanism from the social choice function implemented by the mechanism and the per-unit prices paid by the agents (the agent bids are not observed). For single-dimensional agents, this inference problem is a multi-dimensional inversion of the payment identity and is feasible only if the payment identity is uniquely invertible. The inversion is unique for single-unit proportional weights social choice functions (common, for example, in bandwidth allocation); and its inverse can be found efficiently. This inversion is not unique for social choice functions that exhibit complementarities. Of independent interest, we extend a result of Rosen (1965), that the Nash equilbria of "concave games" are unique and pure, to an alternative notion of concavity based on Gale and Nikaido (1965).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Mechanisms for a No-Regret Agent: Beyond the Common Prior

A rich class of mechanism design problems can be understood as incomplete-information games between a principal who commits to a policy and an agent who responds, with payoffs determined by an unknown state of the world. Traditionally, these models require strong and often-impractical assumptions about beliefs (a common prior over the state). In this paper, we dispense with the common prior. Instead, we consider a repeated interaction where both the principal and the agent may learn over time from the state history. We reformulate mechanism design as a reinforcement learning problem and develop mechanisms that attain natural benchmarks without any assumptions on the state-generating process. Our results make use of novel behavioral assumptions for the agent -- centered around counterfactual internal regret -- that capture the spirit of rationality without relying on beliefs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multi-dimensional Virtual Values and Second-degree Price Discrimination

We consider a multi-dimensional screening problem of selling a product with multiple quality levels and design virtual value functions to derive conditions that imply optimality of only selling highest quality. A challenge of designing virtual values for multi-dimensional agents is that a mechanism that pointwise optimizes virtual values resulting from a general application of integration by parts is not incentive compatible, and no general methodology is known for selecting the right paths for integration by parts. We resolve this issue by first uniquely solving for paths that satisfy certain necessary conditions that the pointwise optimality of the mechanism imposes on virtual values, and then identifying distributions that ensure the resulting virtual surplus is indeed pointwise optimized by the mechanism. Our method of solving for virtual values is general, and as a second application we use it to derive conditions of optimality for selling only the grand bundle of items to an agent with additive preferences.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

No-Regret Learning in Bayesian Games

Recent price-of-anarchy analyses of games of complete information suggest that coarse correlated equilibria, which characterize outcomes resulting from no-regret learning dynamics, have near-optimal welfare. This work provides two main technical results that lift this conclusion to games of incomplete information, a.k.a., Bayesian games. First, near-optimal welfare in Bayesian games follows directly from the smoothness-based proof of near-optimal welfare in the same game when the private information is public. Second, no-regret learning dynamics converge to Bayesian coarse correlated equilibrium in these incomplete information games. These results are enabled by interpretation of a Bayesian game as a stochastic game of complete information.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Auctions vs. Anonymous Pricing

For selling a single item to agents with independent but non-identically distributed values, the revenue optimal auction is complex. With respect to it, Hartline and Roughgarden (2009) showed that the approximation factor of the second-price auction with an anonymous reserve is between two and four. We consider the more demanding problem of approximating the revenue of the ex ante relaxation of the auction problem by posting an anonymous price (while supplies last) and prove that their worst-case ratio is e. As a corollary, the upper-bound of anonymous pricing or anonymous reserves versus the optimal auction improves from four to $e$. We conclude that, up to an $e$ factor, discrimination and simultaneity are unimportant for driving revenue in single-item auctions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Mechanism Design for Data Science

Good economic mechanisms depend on the preferences of participants in the mechanism. For example, the revenue-optimal auction for selling an item is parameterized by a reserve price, and the appropriate reserve price depends on how much the bidders are willing to pay. A mechanism designer can potentially learn about the participants' preferences by observing historical data from the mechanism; the designer could then update the mechanism in response to learned preferences to improve its performance. The challenge of such an approach is that the data corresponds to the actions of the participants and not their preferences. Preferences can potentially be inferred from actions but the degree of inference possible depends on the mechanism. In the optimal auction example, it is impossible to learn anything about preferences of bidders who are not willing to pay the reserve price. These bidders will not cast bids in the auction and, from historical bid data, the auctioneer could never learn that lowering the reserve price would give a higher revenue (even if it would). To address this impossibility, the auctioneer could sacrifice revenue optimality in the initial auction to obtain better inference properties so that the auction's parameters can be adapted to changing preferences in the future. This paper develops the theory for optimal mechanism design subject to good inferability.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Optimal Auctions for Correlated Buyers with Sampling

Crémer and McLean [1985] showed that, when buyers' valuations are drawn from a correlated distribution, an auction with full knowledge on the distribution can extract the full social surplus. We study whether this phenomenon persists when the auctioneer has only incomplete knowledge of the distribution, represented by a finite family of candidate distributions, and has sample access to the real distribution. We show that the naive approach which uses samples to distinguish candidate distributions may fail, whereas an extended version of the Crémer-McLean auction simultaneously extracts full social surplus under each candidate distribution. With an algebraic argument, we give a tight bound on the number of samples needed by this auction, which is the difference between the number of candidate distributions and the dimension of the linear space they span.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Simple Economics of Approximately Optimal Auctions

The intuition that profit is optimized by maximizing marginal revenue is a guiding principle in microeconomics. In the classical auction theory for agents with linear utility and single-dimensional preferences, Bulow and Roberts (1989) show that the optimal auction of Myerson (1981) is in fact optimizing marginal revenue. In particular Myerson's virtual values are exactly the derivative of an appropriate revenue curve. This paper considers mechanism design in environments where the agents have multi-dimensional and non-linear preferences. Understanding good auctions for these environments is considered to be the main challenge in Bayesian optimal mechanism design. In these environments maximizing marginal revenue may not be optimal and there is sometimes no direct way to implement the marginal revenue maximization. Our contributions are three fold: we characterize the settings for which marginal revenue maximization is optimal (by identifying an important condition that we call revenue linearity), we give simple procedures for implementing marginal revenue maximization in general, and we show that marginal revenue maximization is approximately optimal. Our approximation factor smoothly degrades in a term that quantifies how far the environment is from ideal (where marginal revenue maximization is optimal). Because the marginal revenue mechanism is optimal for single-dimensional agents, our generalization immediately approximately extends many results for single-dimensional agents. One of the biggest open questions in Bayesian algorithmic mechanism design is developing methodologies that are not brute-force in the size of the agent type space. Our methods identify a subproblem that, e.g., for unit-demand agents with values drawn from product distributions, enables approximation mechanisms that are polynomial in the dimension.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Prior-independent Auctions for Risk-averse Agents

We study simple and approximately optimal auctions for agents with a particular form of risk-averse preferences. We show that, for symmetric agents, the optimal revenue (given a prior distribution over the agent preferences) can be approximated by the first-price auction (which is prior independent), and, for asymmetric agents, the optimal revenue can be approximated by an auction with simple form. These results are based on two technical methods. The first is for upper-bounding the revenue from a risk-averse agent. The second gives a payment identity for mechanisms with pay-your-bid semantics.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bayesian Optimal Auctions via Multi- to Single-agent Reduction

We study an abstract optimal auction problem for a single good or service. This problem includes environments where agents have budgets, risk preferences, or multi-dimensional preferences over several possible configurations of the good (furthermore, it allows an agent's budget and risk preference to be known only privately to the agent). These are the main challenge areas for auction theory. A single-agent problem is to optimize a given objective subject to a constraint on the maximum probability with which each type is allocated, a.k.a., an allocation rule. Our approach is a reduction from multi-agent mechanism design problem to collection of single-agent problems. We focus on maximizing revenue, but our results can be applied to other objectives (e.g., welfare). An optimal multi-agent mechanism can be computed by a linear/convex program on interim allocation rules by simultaneously optimizing several single-agent mechanisms subject to joint feasibility of the allocation rules. For single-unit auctions, Border \citeyearpar{B91} showed that the space of all jointly feasible interim allocation rules for $n$ agents is a $\NumTypes$-dimensional convex polytope which can be specified by $2^\NumTypes$ linear constraints, where $\NumTypes$ is the total number of all agents' types. Consequently, efficiently solving the mechanism design problem requires a separation oracle for the feasibility conditions and also an algorithm for ex-post implementation of the interim allocation rules. We show that the polytope of jointly feasible interim allocation rules is the projection of a higher dimensional polytope which can be specified by only $O(\NumTypes^2)$ linear constraints. Furthermore, our proof shows that finding a preimage of the interim allocation rules in the higher dimensional polytope immediately gives an ex-post implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Sequential Posted Pricing and Multi-parameter Mechanism Design

We consider the classical mathematical economics problem of {\em Bayesian optimal mechanism design} where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single-parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [Myerson '81]. Unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [Ausubel and Milgrom '06], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [Manelli and Vincent '07]. In contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. These mechanisms are approximately optimal in single-dimensional settings, and avoid many of the properties that make optimal mechanisms impractical. Furthermore, these mechanisms generalize naturally to give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. In particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 1.5 to 8. For all but one case, our posted price sequences can be computed in polynomial time.

0 citations0 reviewsNo code linkedOpen access