ACM DL

ACM Transactions on

Economics and Computation (TEAC)

Menu
Latest Articles

Valuation Compressions in VCG-Based Combinatorial Auctions

The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful... (more)

Causal Strategic Inference in a Game—Theoretic Model of Multiplayer Networked Microfinance Markets

Performing interventions is a major challenge in economic policy-making. We present causal strategic... (more)

Cardinal Contests

We model and analyze cardinal contests, where a principal running a rank-order tournament has access to an absolute measure of the quality of agents’ submissions in addition to their relative rankings. We show that a mechanism that compares each agent’s output quality against a threshold to decide whether to award her the prize... (more)

The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms, and Fundamental Limits

We study the value of data privacy in a game-theoretic model of trading private data, where a data collector purchases private data from strategic data subjects (individuals) through an incentive mechanism. One primary goal of the data collector is to learn some desired information from the elicited data. Specifically, this information is modeled... (more)

NEWS

New Editors-In-Chief

David Pennock and Ilya Segal took over as co-Editors-in-Chief in March 2017.


About TEAC

ACM Transactions on Economics and Computation (TEAC) is a journal focusing on the intersection of computer science and economics. Of interest to the journal is any topic relevant to both economists and computer scientists, including but not limited to the following: read more

Forthcoming Articles
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

We study the revenue maximization problem of a seller with $n$ heterogeneous
items for sale to a single buyer whose valuation function for sets
of items is unknown and drawn from some distribution $D$. We show
that if $D$ is a distribution over subadditive valuations with independent
items, then the better of pricing each item separately or pricing
only the grand bundle achieves a constant-factor approximation to
the revenue of the optimal mechanism. This includes buyers who are
$k$-demand, additive up to a matroid constraint, or additive up to
constraints of any downwards-closed set system (and whose values for
the individual items are sampled independently), as well as buyers
who are fractionally subadditive with item multipliers drawn independently.
Our proof makes use of the core-tail decomposition framework developed
in prior work showing similar results for the significantly simpler
class of additive buyers~\cite{LiY13, BabaioffILW14}.

In the second part of the paper, we develop a connection between approximately
optimal simple mechanisms and approximate revenue monotonicity with
respect to buyers' valuations. Revenue non-monotonicity is the phenomenon
that sometimes strictly \emph{increasing} buyers' values for every
set can strictly \emph{decrease} the revenue of the optimal mechanism~\cite{HartR12}.
Using our main result, we derive a bound on how bad this degradation
can be (and dub such a bound a proof of \emph{approximate} revenue
monotonicity); we further show that better bounds on approximate monotonicity
imply a better analysis of our simple mechanisms.

Equitable rent division

Introduction to the Special Issue on EC?15

Redesigning the Israeli Medical Internship Match

The final step in getting an Israeli M.D. is performing a year-long internship in one of the hospitals in Israel. Internships are decided upon by a lottery, which is known as ``The Internship Lottery''. In 2014 we redesigned the lottery, replacing it with a more efficient one. This paper presents the market, the redesign process and the new mechanism which is now in use. There are two main lessons that we have learned from this market. The first is the ``Do No Harm'' principle, which states that (almost) all participants should prefer the new mechanism to the old one. The second is that new approaches need to be used when dealing with two-body problems in object assignment. We focus on the second lesson, and study two-body problems in the context of the assignment problem. We show that decomposing stochastic assignment matrices to deterministic allocations is NP-hard in the presence of couples, and present a polynomial time algorithm with the optimal worst case guarantee. We also study the performance of our algorithm on real-world and on simulated data.

Leximin Allocations in the Real World

As part of a collaboration with a major California school district, we study the problem of fairly allocating unused classrooms in public schools to charter schools. Our approach revolves around the randomized leximin mechanism. We extend previous work to the classroom allocation setting, showing that the leximin mechanism is proportional, envy-free, efficient, and group strategyproof. We also prove that the leximin mechanism provides a (worst-case) 4-approximation to the maximum number of classrooms that can possibly be allocated. Our experiments, which are based on real data, show that a nontrivial implementation of the leximin mechanism scales gracefully in terms of running time (even though the problem is intractable in theory), and performs extremely well with respect to a number of efficiency objectives. We take great pains to establish the practicability of our approach, and discuss issues related to its deployment.

Learning What's Going on: Reconstructing Preferences and Priorities from Opaque Transactions

We consider a setting where n buyers, with combinatorial preferences over m items, and a seller, running a priority-based allocation mechanism, repeatedly interact. Our goal, from observing limited information about the results of these interactions, is to reconstruct both the preferences of the buyers and the mechanism of the seller. More specifically, we consider an online setting where at each stage, a subset of the buyers arrive and are allocated items, according to some unknown priority that the seller has among the buyers. Our learning algorithm observes only which buyers arrive and the allocation produced (or some function of the allocation, such as just which buyers received positive utility and which did not), and its goal is to predict the outcome for future subsets of buyers. For this task, the learning algorithm needs to reconstruct both the priority among the buyers and the preferences of each buyer. We derive mistake bound algorithms for additive, unit-demand and single minded buyers. We also consider the case where buyers' utilities for a fixed bundle can change between stages due to different (observed) prices. Our algorithms are efficient both in computation time and in the maximum number of mistakes (both polynomial in the number of buyers and items).

Team Performance with Test Scores

Team performance is a ubiquitous area of inquiry in the social sciences, and it motivates the problem of team
selection  choosing the members of a team for maximum performance. Influential work of Hong and Page
has argued that testing individuals in isolation and then assembling the highest-scoring ones into a team is
not an effective method for team selection. For a broad class of performance measures, based on the expected
maximum of random variables representing individual candidates, we show that tests directly measuring
individual performance are indeed ineffective, but that a more subtle family of tests used in isolation can
provide a constant-factor approximation for team performance. These new tests measure the "potential" of
individuals, in a precise sense, rather than performance; to our knowledge they represent the first time
that individual tests have been shown to produce near-optimal teams for a non-trivial team performance
measure. We also show families of subdmodular and supermodular team performance functions for which
no test applied to individuals can produce near-optimal teams, and discuss implications for submodular
maximization via hill-climbing.

Public projects, Boolean functions and the borders of Border's theorem

Border's theorem gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment, and it has several applications in economic and algorithmic mechanism design. All known generalizations of Border's theorem either restrict attention to relatively simple settings, or resort to approximation. This paper identifies a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art. We also identify a surprisingly tight connection between Myerson's optimal auction theory, when applied to public project settings, and some fundamental results in the analysis of Boolean functions.

Revenue Maximization and Ex-Post Budget Constraints



We consider the problem of a revenue-maximizing seller with $m$ items for sale to $n$ additive bidders with hard budget constraints, assuming that the seller has some prior distribution over bidder values and budgets. The prior may be correlated across items and budgets of the same bidder, but is assumed independent across bidders. We target mechanisms that are Bayesian Incentive Compatible, but that are \emph{ex-post} Individually Rational and \emph{ex-post} budget respecting. Virtually no such mechanisms are known that satisfy all these conditions and guarantee any revenue approximation, even with just a single item. We provide a computationally efficient mechanism that is a $3$-approximation with respect to all BIC, ex-post IR, and ex-post budget respecting mechanisms. Note that the problem is NP-hard to approximate better than a factor of $16/15$, even in the case where the prior is a point mass~\cite{ChakrabartyGoel}. We further characterize the optimal mechanism in this setting, showing that it can be interpreted as a \emph{distribution over virtual welfare maximizers.}

We prove our results by making use of a black-box reduction from mechanism to algorithm design developed by~\cite{CaiDW13b}. Our main technical contribution is a computationally efficient $3$-approximation algorithm for the algorithmic problem that results by an application of their framework to this problem. The algorithmic problem has a mixed-sign objective and is NP-hard to optimize exactly, so it is surprising that a computationally efficient approximation is possible at all. In the case of a single item ($m=1$), the algorithmic problem can be solved exactly via exhaustive search, leading to a computationally efficient exact algorithm and a stronger characterization of the optimal mechanism as a distribution over virtual value maximizers.

Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction Markets

We provide the first concrete algorithm for combining market makers and limit orders in a prediction mar- ket with continuous trade. Our mechanism is general enough to handle both bundle orders and arbitrary securities defined over combinatorial outcome spaces. We define the notion of an µ-fair trading path, a path in security space along which no order executes at a price more than µ above its limit, and every order exe- cutes when its market price falls more than µ below its limit. We show that, under a certain supermodularity condition, a fair trading path exists for which the endpoint is efficient, but that under general conditions reaching an efficient endpoint via an µ-fair trading path is not possible. We develop an algorithm for operating a continuous market maker with limit orders that respects the µ-fairness conditions in the general case. We conduct simulations of our algorithm using real combinatorial predictions made during the 2008 U.S. Presidential election and evaluate it against a natural baseline according to trading volume, social welfare, and violations of the two fairness conditions.


All ACM Journals | See Full Journal Index

Search TEAC
enter search term and/or author name