International Conference "Economic Design and Algorithms in St Petersburg", July 8-9, 2019

Photos on Google Drive

On July, 8-9, the International Laboratory of Game Theory and Decision Making held the International Conference Economic Design and Algorithms in St. Petersburg.

OVERVIEW
The conference brought together 20 economists and computer scientists. It focused on design problems where the methodologies of these two communities interact successfully, including but not limited to:
●    Market design
●    Matching and assignment
●    Voting rules
●    Fair division
●    Information design
●    Auctions
●    Networks

ORGANIZING COMMITTEE
Anna Bogomolnaia (HSE, University of Glasgow)
Herve Moulin (HSE, University of Glasgow)
Alexander Nesterov (HSE)
Fedor Sandomirskiy (HSE, Technion)
Constantine Sorokin (HSE, University of Glasgow)

CONFERENCE PROGRAM

Conference Program (PDF, 98 Kb)

Our speakers:
Francis Bloch (Université Paris 1 Panthéon-Sorbonne): Pricing in anonymized networks

Abstract: This paper analyzes monopoly pricing in a network with consumption externalities. The monopolist only receives anonymized information about the network. We characterize network architectures for which first best screening is possible. We show that first best screening is impossible when the network is unbalanced and characterize second best pricing in two classes of unbalanced networks (hierarchy of influencers and intermediated influence).

Philip Grech (ETH Zurich): A posteriori power indices: organizing theory, a new index, and Brexit

Abstract: We propose a simple new a posteriori power index and apply it to the Council of the European Union as a case in point. Our index is developed within a framework that allows for a systematization and generalization of several existing a posteriori voting power indices as well as a transparent and intuitive connection with standard a priori power indices. Crit- ically, our analysis reveals various conceptual difficulties of existing approaches to which our own index can be seen as a minimal remedy. Empirical results are based on data from the Chapel Hill Expert survey and indicate that a posteriori power in the Council is more unequally distributed than a priori power. More precisely, it is almost exclusively held by relatively few rather populous states, predominantly by France, Germany and Poland. The United Kingdom, by contrast, is usually found to be significantly less powerful. As regards Brexit, France appears as the main benefactor in terms of gaining a posteriori power; Poland loses substantive power in several areas but remains one of the most powerful EU member states.

Moshe Babaioff (Microsoft Research): Competitive Equilibrium with Indivisible Goods and Generic Budgets

Abstract: Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods [Foley'67, Varian'74]. Every agent receives an equal budget of artificial currency with which to purchase goods, and prices match demand and supply. However, a CEEI is not guaranteed to exist when the goods are indivisible, even in the simple two-agent, single-item market. Yet, it is easy to see that once the two budgets are slightly perturbed (made generic), a competitive equilibrium does exist. In this paper, we aim to extend this approach beyond the single-item case and study the existence of equilibria in markets with two agents and additive preferences over multiple items. We show that for agents with equal budgets, making the budgets generic -- by adding vanishingly small random perturbations -- ensures the existence of an equilibrium. We further consider agents with arbitrary non-equal budgets, representing non-equal entitlements for goods. We show that competitive equilibrium guarantees a new notion of fairness among non-equal agents and that it exists in cases of interest (like when the agents have identical preferences) if budgets are perturbed. Our results open opportunities for future research on generic equilibrium existence and fair treatment of non-equals. Joint work with Noam Nisan and Inbal Talgam-Cohen. https://arxiv.org/abs/1703.08150

Arunava Sen (Indian Statistical Institute): When is checking a subset of incentive-compatibility constraints sufficient for strategy-proofness? A Characterization and Applications

Abstract: A firm raises capital from multiple investors to fund a project. The project succeeds only if the capital raised exceeds a stochastic threshold, and the firm offers payments contingent on success. We study the firm's optimal unique-implementation scheme, namely the scheme that guarantees the firm the maximum payoff. This scheme pays investors differential net returns (per unit of capital) depending on the size of their investments. We show that if the distribution of the investment threshold is log-concave, larger investors receive higher net returns than smaller investors. Moreover, higher dispersion in investor size increases the firm's payoff. Our analysis highlights strategic risk as an important potential driver of inequality.

Fabrizio Germano (Universitat Pompeu Fabra): The few-get-richer: a surprising consequence of popularity-based rankings

Abstract: Ranking algorithms play a crucial role in online platforms ranging from search engines to recommender systems. In this paper, we identify a surprising consequence of popularity-based rankings: the fewer the items reporting a given signal, the higher the share of the overall traffic they collectively attract. This few-get-richer effect emerges in settings where there are few distinct classes of items (e.g., left-leaning news sources versus right-leaning news sources), and items are ranked based on their popularity. We demonstrate analytically that the few-get-richer effect emerges when people tend to click on top-ranked items and have heterogeneous preferences for the classes of items. Using simulations, we analyze how the strength of the effect changes with assumptions about the setting and human behavior. We also test our predictions experimentally in an online experiment with human participants. Our findings have important implications to understand the spread of misinformation.

Eyal Winter (Hebrew University of Jerusalem): Raising Capital from Heterogeneous Investors

Olga Gorelkina (University of Liverpool Management School): Collusion via Information Sharing and Optimal Auctions

Abstract: This paper studies collusion via information sharing in the context of auctions. The model of collusion via information sharing builds on Aumann’s (1976) description of knowledge. Robustness of auction mechanisms to collusion via information sharing is defined as the impossibility of an agreement to collude. A cartel can agree to collude on a contract if it is common knowledge within that cartel that the contract is incentive compatible and individually rational. Robust mechanisms are characterized in a number of settings where some, all, or no bidders are bound by limited liability. Finally, the characterization is used in a simple IPV setting to design a mechanism that is both optimal and robust to collusion.

Hadi Hosseini (Rochester Institute of Technology): Fair Division through Information Withholding

Abstract: Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In general, each pair of agents might require the (hypothetical) removal of different good, resulting in a weak aggregate guarantee. We study allocations that are nearly envy-free in aggregate and define a novel fairness notion based on information withholding. Under our notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in practice, envy-freeness can be achieved by withholding only a small number of goods overall. We show that finding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. On our way, we show that for binary valuations, finding an envy-free allocation is NP-complete—somewhat surprisingly, this fundamental question was unresolved prior to our work. In contrast to the worst-case results, our experiments on synthetic and real-world preference data show that existing algorithms for finding EF1 allocations withheld a close-to-optimal amount of information.

Jay Sethuraman (Columbia University): Dynamic Matching in School Choice: Efficient Seat Reassignment after Late Cancellations

Abstract: In the school choice market, where scarce public school seats are assigned to students, a key operational issue is how to reassign seats that are vacated after an initial round of centralized assignment. Practical solutions to the reassignment problem must be simple to implement, truthful, efficient and fair while also alleviating costly student movement between schools. In this talk, I shall propose and axiomatically justify a class of reassignment mechanisms, the Permuted Lottery Deferred Acceptance (PLDA) mechanisms. Our mechanisms generalize the commonly used Deferred Acceptance (DA) school choice mechanism to a two-round setting and retain its desirable incentive, fairness and efficiency properties. Empirical investigations based on data from NYC high school admissions support our theoretical findings. (Joint work with Itai Feigenbaum, Yash Kanoria, and Irene Lo)

Wolfgang Leininger (TU Dortmund University): Evolutionary Equilibrium in Contests with Stochastic Participation: Entry, Effort, and Overdissipation

Abstract: This paper examines the evolutionary stability of behaviour in contests where players’ participation can be stochastic. We find, for exogenously given participation probabilities, players exert more effort under the concept of a finite-population evolutionarily stable strategy (FPESS) than under Nash equilibrium (NE). We show that there is ex-ante overdissipation under FPESS for sufficiently large participation probabilities, if, and only if, the impact function is convex. With costly endogenous entry, players enter the contest with a higher probability and exert more effort under FPESS than under NE. Importantly, under the endogenous entry, overdissipation can occur for all (Tullock) contest success functions, in particular, those with concave impact functions.

Umut Dur (North Carolina State University): Family Ties: School Assignment With Siblings

Abstract: We introduce a new school choice problem motivated by the following observations: students are assigned to grades within schools, many students have siblings who are applying as well, and many school districts require siblings to attend the same school. The latter disqualifies the standard approach of considering grades independently as doing so separates siblings. We argue that the central criterion in school choice elimination of justified envy is now inappropriate as it does not consider siblings. We propose a new solution concept that addresses the issues. Moreover, we introduce a strategy-proof mechanism that satisfies it. Using data from the Wake County magnet school assignment, we demonstrate the impact on families of our proposed mechanism versus the naive assignment where in sibling constraints are not taken into account. Interestingly, the problem can be equivalently modeled within the many-to-many matching with contracts framework, and our results have novel implications in this literature. Despite the fact that neither families' nor schools' choice functions are substitutable (even bilaterally), we show that there always exists a stable assignment.

Rida Laraki (University of Paris Dauphine): Stable Matching with Efforts

Abstract: In this ongoing and preliminary version (to not circulate), we introduce an extension of the classical matching problem of Gale and Shapley by allowing agents to make an effort which can increase their attractiveness on the other side of the market. We extend the stable matching definition to that case and prove the existence of a stable matching in the one-side effort case, by providing an algorithm in the spirit of Gale Shapley, thought the proof is less obvious. The existence in the both-side case and several variations of the model are under study.

Peter Biro (Hungarian Academy of Sciences): Complexity of finding Pareto-efficient allocations of highest welfare

Abstract: We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the object-allocating agency are encoded as edge weights in the acceptability graph. The welfare of an allocation is the sum of its edge weights. We introduce the constrained welfare-maximizing solution, which is the allocation of highest welfare among the Pareto-efficient allocations. We identify conditions under which this solution is easily determined from a computational point of view. For the unrestricted case, we formulate an integer program and find this to be viable in practice as it quickly solves a real-world instance of kindergarten allocation. Incentives to report preferences truthfully are discussed briefly.

Debasis Mishra (Indian Statistical Institute): Stable dissolution of a partnership

Abstract: We consider a model where ex-ante informationally symmetric agents have property rights (partnership) of an object. The agents need to efficiently dissolve this partnership. In a seminal result, Cramton, Gibbons, and Klemperer (CGK) show that the set of partnerships that can be efficiently dissolved (i.e., using an efficient, budget-balanced, Bayesian incentive compatible (BIC), and interim individually rational (IR) mechanism) is a convex symmetric set centered around the equal partnership. They also propose a mechanism (CGK mechanism) which efficiently dissolves every efficiently dissolvable partnership. We consider the notion of ex-ante stability in this model, where agents form blocking coalitions before they realize their types. We investigate two questions: (1) When can a partnership be dissolved using an ex-ante stable mechanism? (2) When can a partnership be dissolved using an ex-ante stable and interim IR mechanism (this implies an interim notion of stability, called coarse stability proposed by Wilson)? We find that every partnership can be dissolved using an ex-ante stable mechanism. On the other hand, the set of partnerships that can be dissolved using an ex-ante stable and interim IR mechanism is a convex symmetric set centered around the equal partnership. This set coincides with the set of efficiently dissolvable partnerships if the number of agents is 2 or 3. For a higher number of agents, these two sets coincide if and only if the CGK mechanism is ex-ante stable for the extreme points of the efficiently dissolvable partnerships. Surprisingly, the CGK mechanism need not be ex-ante stable, even for partnerships that can be dissolved using an ex-ante stable and interim IR mechanism. We describe a canonical mechanism which can dissolve every partnership that can be dissolved using an ex-ante stable and interim IR mechanism.

Haris Aziz (The University of New South Wales): Fair Allocation of Indivisible Goods and Chores

Abstract: We consider the problem of fairly dividing a set of indivisible items. Much of the fair division literature assumes that the items are “goods” i.e., they yield positive utility for the agents. There is also some work where the items are “chores” that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.

Rodrigo Velez (Texas A&M University): Expressive mechanisms for equitable rent division on a budget

Abstract: We design envy-free mechanisms for the allocation of rooms and rent payments among roommates. We achieve four objectives: (1) each agent is allowed to make a report that expresses her preference about violating her budget constraint, a feature not achieved by mechanisms that only elicit quasi-linear reports; (2) these reports are finite dimensional; (3) computation is feasible in polynomial time; and (4) incentive properties of envy-free mechanisms that elicit quasi-linear reports are preserved. https://arxiv.org/abs/1902.02935

Antonio Nicolo (University of Padua): Stable Sharing

Abstract: In this paper, we consider a division problem such that agents have to be matched in pairs and share a unitary task. Agents have single-peaked preferences. An allocation rule specifies an assignment of pairs and a division of the task for each pair. We propose an algorithm that generates stable allocations and we show that in the special case in which agents have Euclidean preferences it also maximizes agents’ welfare.

Nick Gravin (Shanghai University of Finance and Economics): Envy-freeness up to any item with high Nash welfare

Abstract: In this talk, we will discuss the problem of fairly and efficiently allocating indivisible goods to agents with additive valuations for the items. A recently proposed concept of envy-freeness up to any item (EFX) is arguably the closest approximation to the notion of envy-freeness for divisible items. Nash social welfare is a natural measure of efficiency in the fair division context. Unfortunately, EFX allocations are not known to exist except in a few special cases. We show that for every instance with additive valuations, there is an EFX allocation of a subset of items with a Nash welfare that is at least half of the maximum possible Nash welfare for the original set of items. That is, after donating some items to a charity, one can distribute the remaining items in a fair way with high efficiency. This bound is proved to be best possible. Our proof is constructive and highlights the importance of maximum Nash welfare allocation. Starting with such an allocation, our algorithm decides which items to donate and redistributes the initial bundles to the agents, eventually obtaining an allocation with the claimed efficiency guarantee. The application of our algorithm to large markets, where the valuations of an agent for every item is relatively small, yields EFX allocation with almost optimal Nash welfare. Based on joint work with Ioannis Caragiannis and Xin Huang.

Yu Zhou (Waseda University): Competitive Equilibria in Matching Models with Financial Constraints

Abstract: We consider the matching with contracts model in which buyers face financial constraints. In this model, there is a stable outcome, but not necessarily a competitive equilibrium. We propose a new equilibrium notion, quantity-constrained competitive equilibrium (QCCE) that allows buyers to form rational expectations on the lack of supply when their financial constraints are binding. We show the existence of QCCEs and establish the equivalence among QCCE outcomes, stable outcomes, and core outcomes. We also analyze the existence of QCCEs with uniform prices, the lattice property of QCCEs, and the rural hospital theorem of QCCEs.

Katharina Huesmann (University of Cologne): Public Assignment of Scarce Resources under Income Effects

Abstract: Many people are repugnant towards the use of money for the assignment of certain goods like school places or human organs. Yet, proponents of selling the goods emphasize efficiency benefits. If no income effects exist - a standard assumption in the literature - a market-price approach indeed has superior efficiency and welfare properties. However, under income effects, this may no longer hold. I show that characteristics of income effects are crucial for efficiency and welfare properties of classical market-price (like selling the good for a market-clearing price) and no-price approaches (like a fair lottery). For positive income effects, a fair lottery can be ex-post efficient despite heterogeneity in the willingness to pay for the good and it may even Pareto-dominate a market- price approach that redistributes the revenues in a lump-sum fashion. If poor agents benefit more from the goods than rich ones, random assignments can be even optimal though the rich are willing to pay more for the good. These positive welfare properties of random assignments without monetary transfers are particularly strong if benefits from consuming the goods are large. In general, for goods with positive income effects that yield high consumption benefits, repugnance towards classical price mechanisms can be supported by efficiency and welfare arguments.

The conference was preceded by a 2-days Summer School Game Theory: Applications, Networks, Emotions (July 5-6, 2019)
SUMMER SCHOOL WEBPAGE

VENUE
3A Kantemirovskaya st, St Petersburg, Russia

CONFERENCE MANAGER
Xenia Adaeva xeniya.adayeva@gmail.com

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!
To be used only for spelling or punctuation mistakes.