DATE: November 26(Tue.) -- 28(Thu.), 2013 VENUE: Raiosha Building, Hiyoshi Campus of Keio University INVITED SPEAKERS: Tamas Fleiner (Eotvos Lorand University, HUNGARY) Enrico Gerding (University of Southampton, UK) Mingyu Guo (University of Adelaide, AUSTRALIA) Akifumi Ishihara (Kyoto University, JAPAN) Tomasz Michalak (University of Oxford, UK) Kazuo Murota (University of Tokyo, JAPAN) Takeshi Nagae (Tohoku University, JAPAN) Szilvia Papai (Concordia University, CANADA) Yu Yokoi (University of Tokyo, JAPAN) PROGRAM: Tuesday, Nov. 26 14:00 – 14:30 Opening 14:30 – 15:30 Mingyu Guo: Revenue Maximization via Hiding Item Attributes 15:30 – 16:00 Coffee Break 16:00 – 16:30 Julien Lesca: Coexistence of Pareto Efficiency and False-name-proofness in Social Choice 16:30 – 17:00 Dengji Zhao: Incentives in Ridesharing with Deficit Control 17:00 – 17:30 Taiki Todo: Strategy-proof exchange with multiple private endowments Wednesday, Nov. 27 10:00 – 11:00 Enrico Gerding: Online Mechanism Design with Pre-Commitment 11:00 – 12:00 Takeshi Nagae: Tradable Time-Specific Permits with Multiple Purchase Opportunity under Dynamic Uncertainty 12:00 – 13:30 Lunch Meeting (for Board Members Only) 13:30 – 14:30 Tamas Fleiner: Two-sided problems with choice functions, matroids and lattices 14:30 – 15:00 Kazuo Murota: Brief Introduction to Discrete Convex Analysis 15:00 – 15:30 Yu Yokoi: On the Lattice Structure of Stable Allocations in Two-Sided Discrete-Concave Market 15:30 – 16:00 Coffee Break 16:00 – 17:00 Szilvia Pápai: Matching With Minimal Priority Rights 17:00 – 18:00 Yosuke Yasuda: Matching with Weak Priorities: Application to School Choice 18:00 – 18:30 Discussion 18:30 – 21:00 Reception/Board Meeting Thursday, Nov. 28 10:00 – 11:00 Tomasz Michalak: On the Shapley value, its extensions to games with externalities and the application to the analysis of terrorist networks 11:00 – 12:00 Akifumi Ishihara: A Citizen-Candidate Model with Sequential Entry 12:00 – 13:30 Lunch Meeting (for Board Members Only) 13:30 – 14:00 Yujiro Kawasaki: Matching Search with Noisy Types 14:00 – 14:30 Suguru Ueda: Finding the Core for Coalition Structure Utilizing Dual Solution 14:30 – 15:30 Discussion 15:30 – 16:00 Closing TITLE & ABSTRACT Tamas Fleiner (Eotvos Lorand University, HUNGARY) Title: Two-sided problems with choice functions, matroids and lattices Abstract: We illustrate a nonstandard choice function based graph-theoretic approach to certain two-sided market economies by presenting some extensions of the stable marriage theorem of Gale and Shapley. We point out the close connection between stability related results and the fixed point theorem of Tarski. As an example to our method, we present a generalization of a previous result of Huang on a certain college admission problem where sets of colleges may have lower and upper quotas on the admitted students. This latter result is joint work with Naoyuki Kamiyama. Title: Online Mechanism Design with Pre-Commitment Abstract: Online mechanism design is used in situations where resources and demand for these from self-interested agents become available over time, and scheduling decisions are made online. Agents can misreport their true demand, as well as their arrival and departure from the market, and the goal in to incentivise truthful reporting through the design of appropriate scheduling mechanisms and payments. In this talk, I will focus on the problem of designing mechanisms for continuously-produced resources, such as electricity, and introduce the concept of pre-commitment to achieve truthful reporting. Here, whenever an agent is selected, the mechanism pre-commits to allocate a certain amount of resources by the reported departure time, but maintains flexibility about when the allocation takes place and at what rate (i.e. the amount allocated per time unit). Furthermore, to make effective pre-commitment decisions, I propose a model-based approach that uses probabilistic information about future demand. Specifically, I will discuss a modified version of Consensus, a well-known online optimisation algorithm, and show that it is truthful when combined with pre-commitment. In addition to the theoretical results, I will discuss an important application of the mechanism to the problem of charging electric vehicles at the home, which has been the basis for this work. As more electric vehicles are introduced, these pose a real problem for electricity networks, which have a restricted capacity, limiting the number of vehicles that can be charged simultaneously. Therefore, the charging of vehicles needs to be effectively scheduled in an online fashion. Such a system also needs to be robust and prevent strategic manipulation. We produce simulations of this setting based on real-world data and show that, empirically, using our truthful mechanism, the average utility achieved is 93% or more of the offline optimal. Mingyu Guo (University of Adelaide, AUSTRALIA) Title: Revenue Maximization via Hiding Item Attributes Abstract: We study probabilistic single-item second-price auctions where the item is characterized by a set of attributes. The auctioneer knows the actual instantiation of all the attributes, but he may choose to reveal only a subset of these attributes to the bidders. Our model is an abstraction of the following Ad auction scenario. The website (auctioneer) knows the demographic information of its impressions, and this information is in terms of a list of attributes (e.g., age, gender, country of location). The website may hide certain attributes from its advertisers (bidders) in order to create thicker market, which may lead to higher revenue. We study how to hide attributes in an optimal way. We show that it is NP-hard to compute the optimal attribute hiding scheme. We then derive a polynomial-time solvable upper bound on the optimal revenue. Finally, we propose two heuristic-based attribute hiding schemes. Experiments show that revenue achieved by these schemes is close to the upper bound. Tomasz Michalak (University of Oxford, UK) Title: On the Shapley value, its extensions to games with externalities and the application to the analysis of terrorist networks Abstract: In this talk we discuss our recent work on two topics related to the Shapley value. We start with the issue of extending the Shapley value to games with externalities - one of the long-debated challenges in coalitional game theory. In particular, when externalities occur, a direct translation of Shapley's axioms does not imply a unique value. In our work, we study the marginality approach to this problem, based on the idea of an alpha-parametrized definition of the marginal contribution, where alpha is a vector of weights associated with an agent joining/leaving a coalition. We prove that all values that satisfy the direct translation of Shapley's axioms can be obtained using the marginality approach. Moreover, we show that every such value can be uniquely derived using marginality approach by choosing appropriate weights alpha. Next, we analyze how properties of a value translate to the requirements on the definition of the marginal contribution (i.e. weights alpha). Building upon this analysis, we show that under certain conditions, two other axiomatizations of the Shapley value (i.e., Young's marginality axiomatization and Myerson's axiomatization based on the concept of balanced contributions), translated to games with externalities using the proper definition of the alpha-parametrized marginal contribution, are equivalent to Shapley's axiomatization. In the second part of the talk, we study computational aspects of a recently developed centrality metric to identify key players in terrorist organisations due to Lindelauf et al. [2013]. This metric, which involves computation of the Shapley value for connectivity games on graphs proposed by Amer and Gimenez [2004], has a potential to produce better results than previously used standard centralities. In this paper, we present the first computational analysis of this class of coalitional games, and propose two algorithms for computing Lindelauf et al.’s centrality metric. Our first algorithm is exact, and runs in time linear by number of connected subgraphs in the network. As shown in the numerical simulations, our algorithm identifies key players in the WTC 9/11 terrorist network, constructed of 36 members and more than 60 links, in less than 50 seconds. In contrast, a general-purpose Shapley value algorithm would require weeks to solve this problem. Our second algorithm is approximate and can be used to study much larger networks. Kazuo Murota (University of Tokyo, JAPAN) Title: Brief Introduction to Discrete Convex Analysis Abstract: This talk describes fundamental properties of M-convex and L-convex functions that play the central roles in discrete convex analysis. These concepts were originally introduced in combinatorial optimization, but turned out to be relevant in economics. Emphasis is put on the idea behind the formal definitions. The discrete Fenchel duality and the conjugacy respect to the Legendre-Fenchel transformation are described. Akifumi Ishihara (Kyoto University, JAPAN) Title: A Citizen-Candidate Model with Sequential Entry Abstract: This article studies a citizen-candidate model where the entry decision is sequential rather than simultaneous. We focus on a situation where there exist three potential candidates including a minor citizen who never wins in a vote unless she is the unique candidate. This sequential entry model has several contrasts to the simultaneous entry models: (i) strategic candidacy occurs on a two-candidate equilibrium; and (ii) the minor citizen may be pivotal in that her more preferred competitor becomes the winner. Furthermore, a Condorcet winner is no longer a dominant candidate in that the entrant on a one-candidate equilibrium may not be a Condorcet winner and there may exist no one-candidate equilibrium even if there exists a Condorcet winner among the potential candidates. Title: Tradable Time-Specific Permits with Multiple Purchase Opportunity under Dynamic Uncertainty Abstract: We study a market mechanism for tradable time-specific permits (TTP) under dynamic uncertainty, which is a right that allows its holder to receive certain service at a pre-specified time (which is referred to as the exercise time). One good example of TTP is a flight ticket, which allows its holder to board an airplane that departs at pre-determined time. In our framework, a TTP can be purchased not only in a ``spot market'' opened at the exercise time, but also in ``presale markets'' opened before the exercise time. It is also assumed that each customer's value for the TTP fluctuates with respect to time due to arrivals of information about situations at the exercise time (e.g. weather forecasts, response about business proposals, political climate). We first formulated the TTP allocation/assignment problem as a stochastic control problem, in which a set of TTP is allocated to the spot and the presale markets and assigned to customers to maximize the ``social surplus''. Our analyses reveals that the optimality condition of the TTP assignment problem can be interpreted as a Bayesian-Nash equilibrium, which implies that the social optimal assignment can be achieved as a result of customers' selfish behavior based on local information. We further discuss the possibility of dominant strategy mechanism by showing that, when each customer can accurately estimates their option value (i.e. expected payoff from postponing the purchase), the TTP assignment problem can be decomposed into a time-series of a traditional assignment problem, for which dominant truth-telling mechanisms are known. Some technical topics also would be discussed such that (i) Benders' decomposition approach for finding the optimal TTP allocation (i.e. how many TTPs should be sold in the spot and the presale markets?); (ii) learning dynamics of the option values and its convergence. Title: Matching With Minimal Priority Rights Abstract: I study the two most well-known strategyproof matching rules when strict priorities over objects are given exogenously: the Deferred Acceptance Rule (DA) and the Top Trading Cycle Rule With Inheritance (TTC). It is well known that the DA rule is stable while the TTC rule is efficient, but not vice versa, and that these two properties cannot be reconciled. The primary innovation of the paper is the introduction of a new weaker concept of stability, Individual Trade Stability, which allows for trading the priorities for objects, a property that is satisfied by both the DA and TTC rules, as well as by all the hybrid rules of these two matching rules that I propose, called Deferred Trading Cycle Rules. The main results are a characterization of the class of Deferred Trading Cycle Rules by Individual Trade Stability, Constrained Efficiency, and an invariance property, and a characterization of a subclass of Deferred Trading Cycle Rules which satisfy strategyproofness. Both of the characterized classes of matching rules include the DA and TTC rules as the two extreme rules in the class. Yu Yokoi (University of Tokyo, JAPAN) Title: On the Lattice Structure of Stable Allocations in Two-Sided Discrete-Concave Market Abstract: Stable allocation model is a many-to-many matching model in which each pair's partnership is represented by a nonnegative integer. This talk describes the significance of M-concave functions as value functions in this model. We show that the choice functions induced from M-concave value functions are endowed with consistency, persistence and size-monotonicity. This implies , by the result of Alkan and Gale, that the stable allocations for M-concave value functions form a distributive lattice with several significant properties such as polarity, complementarity, and uni-size property. Furthermore, these results can be extended for quasi M-concave value functions. This is a joint work with Kazuo Murota. |
|
|