2015

Feasible elimination procedures (Peleg, 1978) play a central role in constructing social choice functions which have the following property: in the associated game form, for any preference profile there exists a strong Nash equilibrium resulting in the sincere outcome. In this paper we provide an axiomatic characterization of the social choice correspondence resulting from applying feasible elimination procedures. The axioms are anonymity, Maskin monotonicity, and independent blocking.

We consider the problem of implementation in models of independent private values in which the valuation an agent attributes to a particular alternative is a function from a multidimensional Euclidean space to the real line. We first consider implementation by standard mechanisms, that include a decision rule and a profile of personal transfers. We present impossibility results on the implementation of decision rules that assign different outcomes to profiles of signals that result in the same profile of valuations. We then consider implementation by extended mechanisms that include, in addition to a decision rule and a profile of personal transfers, a profile of functions that affect the arguments of the valuation functions. We show that decision rules that assign different outcomes to profiles of signals that result in the same profile of valuations can be implemented by such mechanisms.

From drop-down computer menus to department-store aisles, people in everyday life often choose from simultaneous displays of products or options. Studies of position effects in such choices show seemingly inconsistent results. For example, in restaurant choice, items enjoy an advantage when placed at the beginning or end of the menu listings, but in multiple-choice tests, answers are more popular when placed in the middle of the offered list. When reaching for a bottle on a supermarket shelf, bottles in the middle of the display are more popular. But on voting ballots, first is the most advantageous position. Some of the effects are quite sensible, while others are harder to justify and can aptly be regarded as biases. This paper attempts to put position effects into a unified and coherent framework, and to account for them simply, using a small number of familiar psychological principles.

Naor (1969) was the first to observe that in a single-server memoryless queue, customers who inspect the queue length upon arrival and accordingly decide whether to join or not may join even if from the social point of view they are worse of. The question then is how to mechanically design the system such that customers will join only queue lengths that are advised by society, while still minding their own selfish utility. After reviewing some existing mechanisms (some involving money transfers and some not), we suggest novel ones that do not involve money transfers. They possess some advantages over the existing ones, which we itemize.

In this work we present five axioms for a risk-order relation defined over (monetary) gambles. We then characterize an index that satisfies all these axioms "the probability of losing money in a gamble multiplied by the expected value of such an outcome "and prove its uniqueness. We propose to use this function as the risk of a gamble. This index is continuous, homogeneous, monotonic with respect to first- and second-order stochastic dominance, and simple to calculate. We also compare our index with some other risk indices mentioned in the literature.

It is a commonly held intuition that increasing punishment leads to less crime. Let's move our glance from the punishment for the crime itself to the punishment for the attempt to commit a crime, or to the punishment for the threat to carry it out. We'll argue that the greater the punishment for the attempt to rob, i.e. for the threat, "give me your money or else ¦", the greater the number of robberies and attempts there will be. The punishment for the threat makes the withdrawal from it more expensive for the criminal, making the relative cost of committing the crime lower. In other words, the punishment of the attempt turns the attempt into a commitment by the robber, while at the same time turning an incredible threat into a credible one. Therefore, the robber has a strong interest in a legal system that increases the punishment of the attempt.

We attempt to answer why sex is nearly ubiquitous when asexual reproduction is ostensibly more efficient than sexual reproduction. From the perspective of a genetic allele, each individual bearing that allele is akin to a stock share yielding dividends equal to that individual's number of offspring, and the totality of individuals bearing the allele is its portfolio investment. Alleles compete over portfolio growth, and evolutionary reproduction strategies are essentially on-line learning algorithms seeking improved portfolio growth, with sexual reproduction a goal-directed algorithmic exploration of genotype space by sampling in each generation. The model assumes a stochastically changing environment but not weak selection. We show that in finite population models the algorithm of sexual reproduction yields, with high probability, higher expected growth than the algorithm of asexual reproduction does, proposing this as an explanation to why a majority of species reproduce sexually.

We propose to smooth out the calibration score, which measures how good a forecaster is, by combining nearby forecasts. While regular calibration can be guaranteed only by randomized forecasting procedures, we show that smooth calibration can be guaranteed by deterministic procedures. As a consequence, it does not matter if the forecasts are leaked, i.e., made known in advance: smooth calibration can nevertheless be guaranteed (while regular calibration cannot). Moreover, our procedure has finite recall, is stationary, and all forecasts lie on a finite grid. We also consider related problems: online linear regression, weak calibration, and uncoupled Nash dynamics in n-person games.

We consider the class of two-person zero-sum allocation games known as Captain Lotto games (Hart 2014). These are Colonel Blotto type games in which the players have capacity constraints. We show that the players optimal strategies are unique in most cases.

2014

As a selling mechanism, auctions have acquired a central position in the free market econ-omy all over the globe. This development has deepened, broadened, and expanded the theory of auctions in new directions. This chapter is intended as a selective update of some of the developments and applications of auction theory in the two decades since Wilson (1992) wrote the previous Handbook chapter on this topic.

A Lotto game is a two-person zero-sum game where each player chooses a distribution on nonnegative real numbers with given expectation, so as to maximize the probability that his realized choice is higher than his opponent's. These games arise in various competitive allocation setups (e.g., contests, research and development races, political campaigns, Colonel Blotto games). A Captain Lotto game is a Lotto game with caps, which are upper bounds on the numbers that may be chosen. First, we solve the Captain Lotto games. Second, we show how to reduce all-pay auctions to simpler games expenditure games using the solution of the corresponding Lotto games. As a particular application we solve all-pay auctions with unequal caps, which yield a significant increase in the seller's revenue (or, the players' efforts).

Drawing intuition from a (physical) hydraulic system, we present a novel framework, constructively showing the existence of a strong Nash equilibrium in resource selection games with nonatomic players, the coincidence of strong equilibria and Nash equilibria in such games, and the invariance of the cost of each given resource across all Nash equilibria. Our proofs allow for explicit calculation of Nash equilibrium and for explicit and direct calculation of the resulting (invariant) costs of resources, and do not hinge on any fixed-point theorem, on the Minimax theorem or any equivalent result, on the existence of a potential, or on linear programming. A generalization of resource selection games, called resource selection games with I.D.-dependent weighting, is defined, and the results are extended to this family, showing that while resource costs are no longer invariant across Nash equilibria in games of this family, they are nonetheless invariant across all strong Nash equilibria, drawing a novel fundamental connection between group deviation and I.D.-congestion. A natural application of the resulting machinery to a large class of constraint-satisfaction problems is also described.

We show that feasible elimination procedures (Peleg, 1978) can be used to select k from m alternatives. An important advantage of this method is the core property: no coalition can guarantee an outcome that is preferred by all its members. We also provide an axiomatic characterization for the case k = 1, using the conditions of anonymity, Maskin monotonicity, and independent blocking. Finally, we show for any k that outcomes of feasible elimination procedures can be computed in polynomial time, by showing that the problem is computationally equivalent to finding a maximal matching in a bipartite graph.

Biases such as the preference of a particular response for no obvious reason, are an integral part of psychophysics. Such biases have been reported in the common two-alternative forced choice (2AFC) experiments, where participants are instructed to compare two consecutively presented stimuli. However, the principles underlying these biases are largely unknown and previous studies have typically used ad-hoc explanations to account for them. Here we consider human performance in the 2AFC tone frequency discrimination task, utilizing two standard protocols. In both protocols, each trial contains a reference stimulus. In one (Reference-Lower protocol), the frequency of the reference stimulus is always lower than that of the comparison stimulus whereas in the other (Reference protocol), the frequency of the reference stimulus is either lower or higher than that of the comparison stimulus. We find substantial interval biases. Namely, participants perform better when the reference is in a specific interval. Surprisingly, the biases in the two experiments are opposite: performance is better when the reference is in the first interval in the Reference protocol, but is better when the reference is second in the Reference-Lower protocol. This inconsistency refutes previous accounts of the interval bias, and is resolved when experiments statistics is considered. Viewing perception as incorporation of sensory input with prior knowledge accumulated during the experiment accounts for the seemingly contradictory biases both qualitatively and quantitatively. The success of this account implies that even simple discriminations reflect a combination of sensory limitations, memory limitations, and the ability to utilize stimuli statistics.

We consider an infinite two-player stochastic zero-sum game with a Borel winning set, in which the opponent's actions are monitored via stochastic private signals. We introduce two conditions of the signalling structure: Stochastic Eventual Perfect Monitoring (SEPM) and Weak Stochastic Eventual Perfect Monitoring (WSEPM). When signals are deterministic these two conditions coincide and by a recent result due to [Shmaya (2011)] entail determinacy of the game. We generalize [Shmaya (2011)]'s result and show that in the stochastic learning environment SEPM implies determinacy while WSEPM does not.

We performed controlled experiments of human participants in a continuous sequence of ad auctions, similar to those used by Internet companies. The goal of the research was to understand users' strategies in making bids. We studied the behavior under two auction types: (1) the Generalized Second-Price (GSP) auction and (2) the Vickrey–Clarke–Groves (VCG) payment rule, and manipulated also the participants' knowledge conditions: (1) explicitly given valuations and (2) payoff information from which valuations could be deduced. We found several interesting behaviors, among them are: - No convergence to equilibrium was detected; moreover the frequency with which participants modified their bids increased with time. - We can detect explicit "better-response" behavior rather than just mixed bidding. - While bidders in GSP auctions do strategically shade their bids, they tend to bid higher than theoretically predicted by the standard VCG-like equilibrium of GSP. - Bidders who are not explicitly given their valuations but can only deduce them from their gains behave a little less "precisely" than those with such explicit knowledge, but mostly during an initial learning phase. - VCG and GSP yield approximately the same (high) social welfare, but GSP tends to give higher revenue.

{A new Secretary Problem is considered, where for fixed k and m one wins if at some time i = m(j .. 1) + 1 up to jm one selects one of the j best items among the first jm items

When asked to mentally simulate coin tosses, people generate sequences which differ systematically from those generated by fair coins. It has been rarely noted that this divergence is apparent already in the very first mental toss. Analysis of several existing data sets reveals that about 80% of respondents start their sequence with Heads. We attributed this to the linguistic convention describing coin toss outcomes as "Heads or Tails", not vice versa. However, our subsequent experiments found the "first-toss" bias reversible under minor changes in the experimental setup, such as mentioning Tails before Heads in the instructions. We offer a comprehensive account in terms of a novel response bias, which we call reachability. It is more general than the first-toss bias, and reflects the relative ease of reaching one option compared to its alternative in any binary choice context. When faced with a choice between two options (e.g., Heads and Tails, when "tossing" mental coins), whichever of the two is presented first by the choice architecture (hence, is more reachable) will be favored. This bias has far-reaching implications extending well beyond the context of randomness cognition, and in particular to binary surveys (e.g., accept vs. reject) and tests (e.g., True-False). In binary choice, there is an advantage to what presents first. Keywords: acquiescence bias; order effects; randomness cognition; reachability; response bias

Maximizing the revenue from selling two goods (or items) is a notoriously difficult problem, in stark contrast to the single-good case. We show that simple "one-dimensional" mechanisms, such as selling the two goods separately, guarantee at least 73% of the optimal revenue when the valuations of the two goods are independent and identically distributed, and at least 50% when they are independent. However, in the general case where the valuations may be correlated, simple mechanisms cannot guarantee any positive fraction of the optimal revenue. We also introduce a "measure of complexity" for mechanisms–-the menu size–-and show that it is naturally related to the fraction of the optimal revenue that can be guaranteed.

Many competitions require investment of nonrefundable resources, e.g., political campaigns, financial markets, sports or courting rituals. One contestant wins the prize for the invested amount, while all others forfeit their investments without receiving compensation. Frequently, contests are asymmetric, due to differing resources or prize valuations. This could lead weaker contestants to avoid investing, and stronger ones to lower their investment. Two experiments explored the effects of asymmetry between the contestants "arising from their endowments or prizes "on investments. Subjects played both symmetric and asymmetric contests, enabling direct within-subject comparisons. We observed an effect of asymmetry only when it concerned endowments: Subjects invested less when their endowments were asymmetric, whereas (a-)symmetry in the prizes did not influence investments. The changes between consecutive investments can be explained by reactions to the previous outcome (win or loss) in terms of regret over the previous investment being too much or too little.