Latest Articles

## Bid-Limited Targeting

This article analyzes a mechanism for selling items in auctions in which the auctioneer specifies a cap on the ratio between the maximum and minimum bids that bidders may use in the auctions. Such a mechanism is widely used in online advertising through the caps that companies impose on the minimum and maximum bid multipliers that advertisers may... (more)

## Fractional Hedonic Games

The work we present in this article initiated the formal study of fractional hedonic games (FHGs), coalition formation games in which the utility of a player is the average value he ascribes to the members of his coalition. Among other settings, this covers situations in which players only distinguish between friends and non-friends and desire to... (more)

## Simple Pricing Schemes for the Cloud

The problem of pricing the cloud has attracted much recent attention due to the widespread use of cloud computing and cloud services. From a theoretical perspective, several mechanisms that provide strong efficiency or fairness guarantees and desirable incentive properties have been designed. However, these mechanisms often rely on a rigid model,... (more)

## Knapsack Voting for Participatory Budgeting

We address the question of aggregating the preferences of voters in the context of participatory budgeting. We scrutinize the voting method currently used in practice, underline its drawbacks, and introduce a novel scheme tailored to this setting, which we call “Knapsack Voting.” We study its strategic properties—we show... (more)

## Sequential Equilibrium in Computational Games

We examine sequential equilibrium in the context of computational games (Halpern and Pass 2015), where agents are charged for computation. In such games, an agent can rationally choose to forget, so issues of imperfect recall arise. In this setting, we consider two notions of sequential equilibrium. One is an ex ante notion, where a player chooses... (more)

## Earning and Utility Limits in Fisher Markets

Earning limits and utility limits are novel aspects in the classic Fisher market model. Sellers with earning limits have bounds on their income and lower the supply they bring to the market if income exceeds the limit. Buyers with utility limits have an upper bound on the amount of utility that they want to derive and lower the budget they bring to... (more)

### New Editors-In-Chief

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

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

#### Introduction to the Special Issue on EC?16

The Stochastic Matching Problem with (Very) Few Queries

Motivated by an application in kidney exchange, we study the following stochastic matching problem: we are given a graph G(V,E) (not necessarily bipartite), where each edge in E is realized with some constant probability p > 0 and the goal is to find a maximum matching in the realized graph. An algorithm in this setting is allowed to make queries to edges in E in order to determine whether or not they are realized.

We design an adaptive algorithm for this problem that, for any graph G, computes a (1-eps)-approximate maximum matching in the realized graph G_p with high probability, while making O(log(1/eps p)/(eps p)) queries per vertex, where the edges to query are chosen adaptively in O(log(1/eps p)/(eps p)) rounds. We further present a non-adaptive algorithm that makes O(log(1/eps p)/(eps p)) queries per vertex and computes a (1/2 - eps)-approximate maximum matching in G_p with high probability.

Both our adaptive and non-adaptive algorithms achieve the same approximation factor as the previous best algorithms of Blum et al. (EC 2015) for this problem, while requiring exponentially smaller number of per-vertex queries (and rounds of adaptive queries for the adaptive algorithm). Our results settle an open problem raised by Blum et al. by achieving only a polynomial dependency on both eps and p. Moreover, the approximation guarantee of our algorithms is instance-wise as opposed to only being competitive in expectation as is the case for Blum et al. This is of particular relevance to the key application of stochastic matching in kidney exchange. We obtain our results via two main techniques, namely matching-covers and vertex sparsification that may be of independent interest.

#### Minimizing Regret with Multiple Reserves

Dynamics of Evolving Social Groups

Exclusive social groups are ones in which the group members decide whether or not to admit a candidate to the group. Examples of exclusive social groups include academic departments and fraternal organizations. In the present paper we introduce an analytic framework for studying the dynamics of exclusive social groups. In our model, every group member is characterized by his opinion, which is represented as a point on the real line. The group evolves in discrete time steps through a voting process carried out by the group's members. Due to homophily, each member votes for the candidate who is more similar to him (i.e., closer to him on the line). An admission rule is then applied to determine which candidate, if any, is admitted. We consider several natural admission rules including majority and consensus.

We ask: how do different admission rules affect the composition of the group in the long run?
We study both growing groups (where new members join old ones) and fixed-size groups (where new members replace those who quit). Our analysis reveals intriguing phenomena and phase transitions, some of which are quite counterintuitive.

The Unreasonable Fairness of Maximum Nash Welfare

The maximum Nash welfare (MNW) solution -- which selects an allocation that maximizes the product of utilities -- is known to provide outstanding fairness guarantees when allocating divisible goods. And while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is unexpectedly, strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy free up to one good -- a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and -- even more so -- in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation, and demonstrate that it scales well on real data. These results lead us to believe that MNW is the ultimate solution for allocating indivisible goods, and underlie its deployment on a popular fair division website.

Dynamic Taxes for Polynomial Congestion Games

We consider the efficiency of taxation in congestion games with polynomial latency functions along the line of research initiated by [Caragiannis et al., {\em ACM Transactions on Algorithms}, 2010] who focused on both pure and mixed Nash equilibria in games with affine latencies only. By exploiting the primal-dual method [Bil\o, {\em Proceedings of the 10th Workshop on Approximation and Online Algorithms}, 2012], we obtain interesting upper bounds with respect to a variety of different solution concepts ranging from approximate pure Nash equilibria up to approximate coarse correlated equilibria, and including also approximate one-round walks starting from the empty state. Our findings show a high beneficial effect of taxation which increases more than linearly with the degree of the latency functions. In some cases, a tight relationship with some well-studied polynomials in Combinatorics and Number Theory, such as the Touchard and the Geometric polynomials, arises. In these cases, we can also show matching lower bounds, albeit under mild assumptions; interestingly, our upper bounds are derived by exploiting the combinatorial definition of these polynomials, while our lower bounds are constructed by relying on their analytical characterization.

The Good, the Bad, and the Unflinchingly Selfish: Prosociality can be well predicted using payoffs and three behavioral types

The human willingness to pay costs to benefit anonymous others is often explained by social preferences: rather than only valuing their own material payoff, people also include the payoffs of others in their utility function. But how successful is this concept of outcome-based social preferences for actually predicting out-of-sample behavior? We investigate this question by having 1067 participants each make 20 cooperation decisions with randomized parameters (eg. outcomes for the self, for the other, benefit/cost ratio of cooperation). We then use machine learning to try to predict cooperative behavior by each participant in each cooperation decision. A representative agent model (a small, shared, set of parameters) predicts better than random but still quite poorly (AUC=.69). Allowing for full heterogeneity across individuals in the mapping from decision-parameters to outcome yields good predictive performance (AUC=0.89). However, this heterogeneous model is complicated and unwieldy, thus we also investigate whether a simpler model can yield similar performance. We find that the vast majority of the predictive power (AUC=0.88) is achieved by a model that allows for three behavioral types. Finally, we show that cannot be well proxied for by other measures in psychology. This final analysis adds further evidence to the literature that human `cooperative phenotypes'' are indeed meaningful, relatively orthogonal person-level traits.

###### All ACM Journals | See Full Journal Index

Search TEAC
enter search term and/or author name